Questions tagged [infinite-games]
Infinite games. Combinatorial game theory for infinite two-player games of perfect information. Open games, clopen games. Determinacy. Transfinite game values. Topological games.
5
votes
0answers
55 views
Is each Choquet topological group strong Choquet?
A topological space $X$ is called (strong) Choquet if the player II has a winning strategy in the (strong) Choquet game.
It is known that a metrizable space $X$ is
$\bullet$ Choquet if and only if ...
3
votes
0answers
124 views
final coalgebra of the 𝓟${_{<κ}}$(A×X) endo-functor in $Set^*$?
In the paper Coalgebraic Games and Strategies F. Honsell, M. Lenisa, and R. Redamalla use the functor $F_A$(X) = ${\mathscr{P}_{<κ}}$(A×X) to define games coalgebraically. This is a functor from ...
2
votes
0answers
74 views
A community effort: equilibrium in quitting games [closed]
This thread is in the spirit of the polymath project:
a combined effort of the community to solve a difficult open problem.
It is an activity of the European Network for Game Theory
whose goal is to ...
1
vote
0answers
49 views
Continuous limits of Hex on larger and larger boards
Consider the game of Hex on a variable sized $n \times n$ board. Remap each board to be a discrete subset of the unit square $[0,1]^2$. Optimal games are now finite sequences on the unit square. We ...
1
vote
2answers
209 views
How to describe the common boundaries between regions in a infinite Sudoku?
This relates to the answer to a question "Who wins two player sudoku?" and this awesome blog.
A Sudoku can be $N \times N$ where $\sqrt{N}$ is a natural number because $N \times N / \sqrt{N} \times \...
30
votes
1answer
2k views
Is there a position in infinite Go for which the life of a particular stone has transfinite game value?
As follow up to Checkmate in $\omega$ moves?, we can ask the same question about go. Is there a position on a $\mathbb Z \times \mathbb Z$ goban such that either black can kill a white group, but ...
9
votes
3answers
697 views
The Sudoku game: Solver-Spoiler variation
Consider the Sudoku Solver-Spoiler game, a natural variation of the Sudoku game recently appearing in the question Who wins two-player Sudoku? posted by user PyRulez. In that game, the players attempt ...
19
votes
3answers
503 views
The arithmetic progression game and its variations: can you find optimal play?
Consider the arithmetic progression game, a two-player game of
perfect information, in which the players take turns playing
natural numbers, or finite sets of natural numbers, all distinct,
and the ...
37
votes
3answers
4k views
A game on integers
$A$ and $B$ take turns to pick integers: $A$ picks one integer and then $B$ picks $k > 1$ integers ($k$ being fixed). A player cannot pick a number that his opponent has picked. If $A$ has $5$ ...
9
votes
1answer
358 views
The Axiom of Determinacy and the Banach-Mazur game
The Wikipedia article on the Axiom of Determinacy (AD) claims:
Equivalent to the axiom of determinacy is the statement that for every subspace X of the real numbers, the Banach–Mazur game BM(X) is ...
43
votes
2answers
4k views
Does knight behave like a king in his infinite odyssey?
The Knight's Tour is a well-known mathematical chess problem. There is an extensive amount of research concerning this question in two/higher dimensional finite boards. Here, I would like to tackle ...
5
votes
1answer
206 views
On the topological complexity of the set of winning strategies for Gale-Stewart Games
Given a set $A \subseteq \omega^\omega$, let $G_A$ denote the Gale-Stewart game with payoff set $A$ (so player $I$ wants the real built over the course of play to be in $A$ and player $II$ wants it ...
3
votes
1answer
348 views
If non-empty player has a winning strategy in Banach-Mazur game BM(X), then it also has in BM(Y)?
Let $f:X\rightarrow Y$ be a continuous, open, surjection function and second player (non-empty) has a winning strategy (not important which one, say for simplicity stationery st.) in $BM(X)$. Then can ...
6
votes
1answer
235 views
Products and Gale-Stewart games
For the purpose of this post, I will say that the Gale-Stewart game is the infinite two-player game of perfect information where players I and II alternate playing natural numbers, with I going first. ...
9
votes
2answers
534 views
Choosing subsets of $\mathbb R$ of cardinality $\frak c$, who wins?
Consider the following infinite game: two players, I and II, are alternating and choosing a descending sequence of subsets of $\mathbb R$ of cardinality $\frak c$, so I chooses a set $A_1\subseteq\...
6
votes
2answers
459 views
Determinacy of (infinite, possibly loopy) combinatorial games
I am looking for references and hopefully enlightening proofs of the following statement(s) concerning the determinacy of not-necessarily-well-founded (i.e., possibly infinite, possibly loopy) ...
1
vote
0answers
477 views
On the Theory of Infinite Step Processes of Sequential Decision Making
On the border of Set Theory and Game Theory there is a broad class of Infinite Step Processes of Sequential Decision Making that can be characterized by the main following property: a Future ...
9
votes
1answer
317 views
Infinite-dimensional hex
Suppose $n$ players take turns selecting vertices of the grid $[k]^n = \left\{0, 1, 2, \ldots, k-1\right\}^n$. Each player is assigned a pair of opposite faces of the grid, and wins the game if they ...
17
votes
1answer
873 views
A game on sets of reals
A 2 player game on $\mathcal{P}(\mathbb{R})$: Players take turns playing uncountable sets of reals. Each play must be a subset of the previously played set. Player 1 wins if the intersection of all ...
0
votes
1answer
355 views
Infinite board games: sentences about
As a unified approach if we have an ( read any) infinite board game described as $\mathcal{G}$ using a particular axiom set A..
can a sentence be devised in A which automatically answers the basic ...
11
votes
1answer
834 views
The infinite X in Conway's game of life
In Conway's game of life, take the initial position to be two infinite diagonal lines of live cells, with a single cell in common. Does this thing converge to a stable configuration? I.e., is the ...
91
votes
11answers
12k views
Checkmate in $\omega$ moves?
Is there a chess position with a finite number of pieces on the infinite chess board $\mathbb{Z}^2$ such that White to move has a forced win, but Black can stave off mate for at least $n$ moves for ...
9
votes
4answers
1k views
Infinite games: are they well defined?
It is just my curiosity about this question where we have an infinite game and (according to the answers) winning strategies for both players. I am familiar with terminating games only, and I am ...
54
votes
5answers
7k views
Decidability of chess on an infinite board
The recent question Do there exist chess positions that require exponentially many moves to reach? of Tim Chow reminds me of a problem I have been interested in. Is chess with finitely many men on an ...
6
votes
2answers
807 views
Is perfect play possible in continuous rock-paper-scissors? game “step size” vs. “acceleration”
The first part of my question is simple: Is every game continuous in time and strategy-space also a game of perfect information with a good equilibrium? For example, consider rock-paper-scissors. The ...
