65
votes
Accepted
A game on integers
I claim that Player A has a winning strategy in your game, and furthermore, it is a winning strategy for her simply to play the smallest available number.
Let me consider the game along with several ...
- 236k
58
votes
Accepted
Does knight behave like a king in his infinite odyssey?
Consider the following open knight's tour on a $5\times 5$ board, starting at position $1$ and then touring the $5\times 5$ board in the indicated move order. The final position is $25$, from which ...
- 236k
38
votes
Accepted
Is there a position in infinite Go for which the life of a particular stone has transfinite game value?
This is a really great question!
Previous attempts to make sense of infinite Go have sometimes had problems because it wasn't clear how to define the winner of a game of Go after transfinite play. ...
- 236k
32
votes
Why is game theory formulated in terms of equilibrium instead of winning strategies?
There's a few issues that need to be distinguished here. First, one can distinguish the question of how you find the winning strategy from the question of how you define what the winning strategy even ...
- 148k
25
votes
Does knight behave like a king in his infinite odyssey?
(Moved from a comment.)
Questions 2, 3, and 4 are answered negatively by [W], which decomposes the plane into concentric annuli of width two.
OP observes that this construction is still spiral (...
- 576
23
votes
Accepted
An infinite game possibly due to Ernst Specker
I don't know about the game attributed to Specker, but here is a
simple game with your desired features.
Let us call it the Chocolatier's game. There are two players,
the Chocolatier and the Glutton. ...
- 236k
21
votes
Checkmate in $\omega$ moves?
Dropping the assumption of finitely many pieces as in this answer, we construct for any countable ordinal $\alpha$ a position having mate in $\beta > \alpha$, so $\gamma = \omega_1$ in the context ...
- 531
20
votes
Why is game theory formulated in terms of equilibrium instead of winning strategies?
Let me address the criticism that the Nash equilibrium is of questionable real-life significance.
I'll begin by openly admitting something that theorists often are reluctant to admit: One big reason ...
- 82.6k
19
votes
Examples of concrete games to apply Borel determinacy to
The game of infinite Hex, proceeding from an arbitrary position, is a good example with all the features you seek. The game was the subject of my Oxford student Davide Leonessi's masters MFoCS ...
- 236k
15
votes
The Chocolatier's game: can the Glutton win with a restricted form of strategy?
Yes. See Theorem 1.2 in K. Ciesielski and R. Laver, A game of D. Gale in which one of the players has limited memory, Period. Math. Hungar. 21 (1990), no. 2, 153–158
- 151
13
votes
Accepted
Choosing subsets of $\mathbb R$ of cardinality $\frak c$, who wins?
In ZFC, the player aiming for the empty set has a winning strategy in the game played on any infinite set, including the reals. Using the axiom of choice, we can well-order the set and thereby pretend ...
- 236k
13
votes
Accepted
The Axiom of Determinacy and the Banach-Mazur game
The claim is false. The Banach-Mazur game, also known as the $**$-game shows (and is equivalent to) that every set of reals has the Baire property. What is true, as you've noted, is that if one has a ...
- 3,804
13
votes
Accepted
The Chocolatier's game: can the Glutton win with a restricted form of strategy?
(Not an answer; promoted from a comment on another answer)
If we modify the game so that the glutton can remember (only) the last chocolate they ate, they have a winning strategy as follows:
Well-...
- 590
12
votes
A game on integers
Joel's answer uses heavy machinery to give a much stronger result. Below is a strong result for $k=1$ using heavy computations (not mine.)
My suspicion is that for the question as asked there might ...
- 30.1k
12
votes
Checkmate in $\omega$ moves?
Introducing a position of game value ω² with finitely many pieces
In the following position with finitely many pieces, White has mate-in-ω² (Black to move): (For convenience, I put the position into a ...
- 271
12
votes
Examples of concrete games to apply Borel determinacy to
Here are four, of various different flavors:
A silly one
I described in a different MO question a game where players work together to turn the harmonic series into an alternating (so conditionally ...
- 21.1k
11
votes
Accepted
Undetermined Banach-Mazur games in ZF?
This is only a partial answer. ZF + DC + 'every Banach-Mazur game is determined' is inconsistent.
Let $X$ be the set of all functions of the form $f: \alpha \rightarrow \{0,1\}$, with $\alpha$ an ...
- 12.4k
11
votes
The Chocolatier's game: can the Glutton win with a restricted form of strategy?
Instead of looking at the unordered set of previously eaten chocolates, let's consider a slight modification, where the Glutton knows the finite sequence of previously eaten chocolates. That is, I ...
- 18.5k
11
votes
Strategic vs. tactical closure
The answer to the topological version of Banach-Mazur games is negative, proved by Gabriel Debs in 1985:
Debs, Gabriel, Stratégies gagnantes dans certains jeux topologiques (Winning strategies in ...
- 236k
11
votes
Let $R, S$ be infinite sets. Alice and Bob will play a game over $R\times S$
The following partial answer (inspired by Pace Nielsen's deleted answer) addresses only the instances where $|R|=\aleph_0$ and $|S|\gt2^{\aleph_0}$. I claim that it's consistent (relative to the ...
- 13.4k
10
votes
The Chocolatier's game: can the Glutton win with a restricted form of strategy?
If the chocolate space is $[0,1]$, then Glutton can't win with a positional measurable strategy, where positional means knowing what was eaten when and what is currently on offer; and moreover we ...
- 4,667
9
votes
Accepted
Existence of a winning strategy in the $\boldsymbol{\Delta}_2^0$ game
Player I has a winning strategy: First play a singleton $A_0=A_1=\ldots=\{z_0\}$, for some real $z_0$, and the $x_n$'s consistent with $z_0$, until player II plays their first 1, if they ever do. ...
- 9,902
9
votes
What is the complexity of the winning condition in infinite Hex? In particular, is infinite Hex a Borel game?
The complexity is arithmetic, and at most $\Sigma^0_7$.
The proof is based on showing that my counterexample to PyRulez's proposed formula is essentially the only one.
Let $G$ be the set of tiles of ...
- 740
8
votes
Choosing subsets of $\mathbb R$ of cardinality $\frak c$, who wins?
This problem (with inconsequential differences in the rules of play) was posed by S. Banach as Problem 67 in The Scottish Book, which is available here. The following text is copied from R. Daniel ...
- 13.4k
8
votes
The Sudoku game: Solver-Spoiler variation
For all $n \geq 2$, here is a simple winning strategy for Spoiler on the $n^2 \times n^2$ board, that requires at most $n^2-1$ moves to win. I assume that Solver plays first, but the strategy can ...
- 32.1k
8
votes
Why is game theory formulated in terms of equilibrium instead of winning strategies?
The problem of finding a winning strategy (if one exists) is purely computational (with rare exceptions), and its solution very much depends on the game. So, this problem cannot be part of a general ...
- 128k
7
votes
Why is game theory formulated in terms of equilibrium instead of winning strategies?
I recommend you read "Harrington on Cash Games, Volume I" by Dan Harrington and Bill Robertie. It is not a formal math book, but rather a book on winning strategies for poker.
What I find ...
- 7,337
7
votes
Strategic vs. tactical closure
For a partial answer, let me prove that every strategically closed partial order admits a nearly tactical winning strategy, one that depends only on the previous two moves, that is, on the previous ...
- 236k
7
votes
Accepted
Embeds in a topological W-group, or a W-space that embeds in a topological group?
No, every Tychonoff space $X$ (so in particular every compact Hausdorff space) embeds (as a closed subspace) in $F(X)$, the free topological group over $X$.
See chapter 7 of Topological groups and ...
- 3,011
7
votes
Embeds in a topological W-group, or a W-space that embeds in a topological group?
Or, you can embed $X$ into a Tychonoff cube $[0,1]^\kappa$, where $\kappa$ is the weight of $X$, say.
The Tychonoff cube embeds in the corresponding power of the unit circle, say by embedding $[0,1]$ ...
- 11.4k
Only top scored, non community-wiki answers of a minimum length are eligible