Topological game

Many frameworks can be defined for infinite positional games of perfect information.

The typical setup is a game between two players, I and II, who alternately pick subsets of a topological space X. In the nth round, player I plays a subset I_n of X, and player II responds with a subset J_n. There is a round for every natural number n, and after all rounds are played, player I wins if the sequence

I₀, J₀, I₁, J₁,...

satisfies some property, and otherwise player II wins.

The game is defined by the target property and the allowed moves at each step. For example, in the Banach–Mazur game BM(X), the allowed moves are nonempty open subsets of the previous move, and player I wins if ${\displaystyle \bigcap _{n}I_{n}\neq \emptyset }$ .

This typical setup can be modified in various ways. For example, instead of being a subset of X, each move might consist of a pair ${\displaystyle (I,p)}$  where ${\displaystyle I\subseteq X}$  and ${\displaystyle p\in x}$ . Alternatively, the sequence of moves might have length some ordinal number other than ω.

• A play of the game is a sequence of legal moves

I₀, J₀, I₁, J₁,...

The result of a play is either a win or a loss for each player.

• A strategy for player P is a function defined over every legal finite sequence of moves of P's opponent. For example, a strategy for player I is a function s from sequences (J₀, J₁, ..., J_n) to subsets of X. A game is said to be played according to strategy s if every player P move is the value of s on the sequence of their opponent's prior moves. So if s is a strategy for player I, the play

${\displaystyle s(\lambda ),J_{0},s(J_{0}),J_{1},s(J_{0},J_{1}),J_{2},s(J_{0},J_{1},J_{2}),\ldots }$ 

is according to strategy s. (Here λ denotes the empty sequence of moves.)

• A strategy for player P is said to be winning if for every play according to strategy s results in a win for player P, for any sequence of legal moves by P's opponent. If player P has a winning strategy for game G, this is denoted ${\displaystyle P\uparrow G}$ . If either player has a winning strategy for G, then G is said to be determined. It follows from the axiom of choice that there are non-determined topological games.
• A strategy for P is stationary if it depends only on the last move by P's opponent; a strategy is Markov if it depends both on the last move of the opponent and on the ordinal number of the move.

The first topological game studied was the Banach–Mazur game, which is a motivating example of the connections between game-theoretic notions and topological properties.

Let Y be a topological space, and let X be a subset of Y, called the winning set. Player I begins the game by picking a nonempty open subset ${\displaystyle I_{0}\subseteq Y}$ , and player II responds with a nonempty open subset ${\displaystyle J_{0}\subseteq I_{0}}$ . Play continues in this fashion, with players alternately picking a nonempty open subset of the previous play. After an infinite sequence of moves, one for each natural number, the game is finished, and I wins if and only if

${\displaystyle X\cap \bigcap _{n\in \omega }I_{n}\neq \emptyset .}$ 

The game-theoretic and topological connections demonstrated by the game include:

• II has a winning strategy in the game if and only if X is of the first category in Y (a set is of the first category or meagre if it is the countable union of nowhere-dense sets).
• If Y is a complete metric space, then I has a winning strategy if and only if X is comeagre in some nonempty open subset of Y.
• If X has the property of Baire in Y, then the game is determined.

Some other notable topological games are:

• the binary game introduced by Ulam — a modification of the Banach–Mazur game;
• the Banach game — played on a subset of the real line;
• the Choquet game — related to siftable spaces;
• the point-open game — in which player I chooses points and player II chooses open neighborhoods of them;
• selection games — each round player I chooses a (topological) collection and II chooses a member or finite subset of that collection. See Selection principle § Topological games.

Many more games have been introduced over the years, to study, among others: the Kuratowski coreduction principle; separation and reduction properties of sets in close projective classes; Luzin sieves; invariant descriptive set theory; Suslin sets; the closed graph theorem; webbed spaces; MP-spaces; the axiom of choice; computable functions. Topological games have also been related to ideas in mathematical logic, model theory, infinitely-long formulas, infinite strings of alternating quantifiers, ultrafilters, partially ordered sets, and the chromatic number of infinite graphs.

For a longer list and a more detailed account see the 1987 survey paper of Telgársky.^[6]

• Topological puzzle