Questions tagged [combinatorial-game-theory]
Two-player turn-based perfect-information games, surreal numbers, impartial games and Sprague-Grundy theory, partizan games
240 questions
19
votes
4
answers
1k
views
Generalization of a mind-boggling box-opening puzzle
Motivation. Suppose we are given $6$ boxes, arranged in the following manner:
$$\left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \end{array}\right]$$
Two of these boxes contain a ...
- 48.9k
34
votes
7
answers
3k
views
A hat puzzle question—how to prove the standard solution is optimal?
I am currently writing an essay on hat puzzles, and for the warm-up section I introduce some of the standard finite hat puzzles. One of these proceeds as follows:
You and two friends are each given a ...
- 237k
14
votes
1
answer
607
views
Is there an elementary proof of a better result for the finite guessing-box puzzle?
The infinitary guessing-box puzzle is amazing — see here. In the basic form, the Guessing-box Hall has infinitely many wooden boxes, each containing a real number, and there are 100 mathematicians ...
- 237k
8
votes
1
answer
580
views
Birthday of combinatorial game product
Recall that the birthday $B(G)$ of a combinatorial game $G$ is recursively defined as the least ordinal $\alpha$ such that $G = \{L | R\}$ for some sets of games $L$, $R$ with birthdays less than $\...
- 447
8
votes
1
answer
354
views
Clarification on proof of the algebraic completeness of nimbers
I am currently working on a computer formalization of the algebraic completeness of Conway's nimbers. However, I've found Conway's exposition to be a bit convoluted, and I'm having trouble filling in ...
- 447
93
votes
3
answers
6k
views
A little number theoretic game
I came up with this little two player game:
The players take turns naming a positive integer. When one player says the number $n$, the other player can only reply in two different ways: They can ...
- 861
1
vote
1
answer
141
views
Is there a solution to this subtraction game with extra rules. (combinatorial game theory, CGT, nim like)
All of the rules are as follows:
There is only 1 pile with $n$ objects.
The players can at max pick $m$ objects.
The players cant take the same amount as what the opposite player taken last turn and ...
- 13
9
votes
0
answers
205
views
Placing triangles around a central triangle: Optimal Strategy?
This question has gone for a while without an answer on MSE (despite a bounty that came and went) so I am now cross-posting it here, on MO, in the hope that someone may have an idea about how to ...
- 7,831
12
votes
0
answers
495
views
Connection properties of a single stone on an infinite Hex board
This includes a series of questions.
One of the most typical examples is shown as the picture below.
An half-infinite Hex board with an one row of black stones. Black stones are separated by one ...
- 661
4
votes
1
answer
432
views
"Infinity": A card game based on prime factorization and a question
I have been developing a card game called "Infinity", which involves a unique play mechanic based on card interactions. In this game, each card displays a set of symbols, and players match ...
- 3,144
69
votes
7
answers
17k
views
What is a chess piece mathematically?
Historically, the current "standard" set of chess pieces wasn't the only existing alternative or even the standard one. For instance, the famous Al-Suli's Diamond Problem (which remained ...
128
votes
13
answers
24k
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 ...
- 5,492
8
votes
0
answers
82
views
$2$-for-$2$ asymmetric Hex
This is a crosspost from Math stackexchange as I left the question open a while and bountied it but received no answers.
If the game of Hex is played on an asymmetric board (where the hexes are ...
- 181
1
vote
0
answers
132
views
Are gaps and loopy games interchangeable in the Surreal Numbers?
The class of surreal numbers (commonly called $No$) is not complete: it contains gaps. Some people have studied the "Dedekind completion" of the surreal numbers in order to do limits and ...
28
votes
7
answers
6k
views
Why is game theory formulated in terms of equilibrium instead of winning strategies?
Game theory, on the outset, seems to invite the questions,
"what can I do to win" or "how do I beat my opponent?"
So many people who are not familiar with game theory look to game ...
- 479
3
votes
2
answers
617
views
Negative of combinatorial game
I am having problem understanding what negative of a combinatorial game $G$ exactly means in combinatorial game theory. Does it mean that if I have normal game, if I create inverse, i.e., $-G = \{-G^R ...
- 31
2
votes
0
answers
67
views
How many ways to win a game between two teams with arbitrary player skills
Suppose we have $n\geq 4$ players $p_1,\cdots,p_n$ of a game between two teams: team $A$ and team $B$ (disjoint sets, each with two or more players, so that $|A|+|B|=n$). Assume that each player $p_i$ ...
- 167
24
votes
2
answers
1k
views
What is the complexity of the winning condition in infinite Hex? In particular, is infinite Hex a Borel game?
Consider the game of infinite Hex, where two players Red and Blue alternately place their stones on the infinite hex grid, each aiming to create a winning configuration.
Red wins after infinite play, ...
- 237k
5
votes
1
answer
436
views
Uniform strategy on Kastanas' game
I think my question applies to most games, but for the sake of concreteness, I shall consider one specific game in this question. We consider the game posed by Ilias Kastanas in his paper On the ...
- 1,442
8
votes
1
answer
433
views
Is "do-almost-nothing" ever winning on large CHOMP boards?
This is a special case of a question asked but unanswered at MSE:
Consider the combinatorial game CHOMP (presented as in the linked notes so that the "poison" square is bottom-left). In any $...
- 20.7k
7
votes
0
answers
239
views
Chip firing on hypergraphs
A (finite) hypergraph is a pair $(V, \mathcal{E})$ where $V$ is a finite set of vertices and $\mathcal{E}\subseteq\mathcal{P}(V)$ with each $E\in\mathcal{E}$ having at least two elements; a ...
- 20.7k
10
votes
0
answers
386
views
For which set $A$, Alice has a winning strategy?
Cross-posted from MSE: https://math.stackexchange.com/questions/4775193/for-which-set-a-alice-has-a-winning-strategy
Alice and Bob are playing a game. They take an integer $n>1$, and partition the ...
- 1,462
226
votes
4
answers
17k
views
A game on Noetherian rings
A friend suggested the following combinatorial game. At any time, the state of the game is a (commutative) Noetherian ring $\neq 0$. On a player's turn, that player chooses a nonzero non-unit element ...
- 149k
25
votes
4
answers
2k
views
The Chocolatier's game: can the Glutton win with a restricted form of strategy?
I have a question about the Chocolatier's game, which I had
introduced in my recent answer to a question of Richard
Stanley.
To recap the game quickly, the Chocolatier offers up at each stage
a finite ...
- 237k
2
votes
0
answers
208
views
Are infinite loops possible in the game Prodway?
I'd like to know if infinitely repeating sequences of moves (i.e. cycles) are possible in the following game:
Prodway is a game for two players (Black and White) that is
played on the intersections (...
- 21
12
votes
1
answer
392
views
Euclid's algorithm as a combinatorial game
Consider the following two player game based on the Euclidean algorithm: Positions are given by $(a,b)$ in $\mathbb N^2\setminus\{(0,0)\}$ (where $\mathbb N=\{0,1,2,\ldots\}$) defining a greatest ...
- 17.9k
41
votes
3
answers
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$ ...
- 909
40
votes
6
answers
5k
views
Can one make high-level proofs about chess positions?
I realize this question is risky (as the title and the tags indicate), but hopefully I can make it acceptable. If not, and the question cannot be salvaged, I'm sorry and ready to delete it or accept ...
- 1,445
6
votes
1
answer
196
views
A combinatorial game with seemingly curious arithmetic properties
We consider the following combinatorial game (with two players
alternatively playing optimally). Posititions are given by heaps containing $b\geq 0$ black and $w\geq 0$ white stones and are
encoded by ...
- 17.9k
47
votes
3
answers
5k
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 ...
7
votes
1
answer
572
views
JUSTICE & INJUSTICE — two 2-player finite games
There is a non-empty finite set $\ K,\ $ say, of plates. Initially, there are $\ p_0(k)\ $ stones on the $k$-th plate, where
$\ p_0(k)\in\mathbb Z_{_{\ge0}}\ $ for each $\ k\in K.$
So far, it is like ...
- 4,786
16
votes
1
answer
2k
views
In theory, how would Oneiric numbers be defined?
Background I am not a professional mathematician. I am researching Surreal numbers & games for fun (I think they are truly beautiful). If this question is not appropriate here, I beg forgiveness &...
- 169
5
votes
1
answer
252
views
Monoid associated to $>2$-player Hackenbush
There is some literature on multiplayer combinatorial game theory, but as far as I can tell none of it follows the line of attack below. I'd love a pointer to a similar approach taken in the ...
- 20.7k
2
votes
3
answers
1k
views
Strategy-stealing in chess
Is it proved that white can guarantee at least draw in chess?
A while ago I was told that it was proved using strategy-stealing, but I cannot find a reference.
Postscript. Please accept my apology ---...
- 45k
1
vote
1
answer
147
views
Name for an easy combinatorial game
What is the name of the following combinatorial game:
Two players, moving in turn.
Positions: $0,1,2,\ldots$.
Moves: $n\longmapsto n-1$ or $n\longmapsto \lfloor n/2\rfloor$
if $n>0$.
No move for $0$...
- 17.9k
67
votes
5
answers
10k
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 ...
- 50.8k
5
votes
1
answer
1k
views
Set theory / Formal logic of Baba is You
''Baba is You'' is a recent puzzle game in which the player builds a set of rules by pushing squares with words written on them. If we leave aside the combinatorial difficulty of how to move the ...
- 5,146
13
votes
0
answers
221
views
A game based on the Euclidean algorithm
The following game is based on a somewhat "stupid" version of the Euclidean algorithm (where we allow only subtractions).
Positions are given by finite non-empty multisets (repeated elements ...
- 17.9k
18
votes
3
answers
666
views
Tic-tac-toe with one mark type
Parameters $a,b,c$ are given such that $c\leq\max(a,b)$. In an $a\times b$ board, two players take turns putting a mark on an empty square. Whoever gets $c$ consecutive marks horizontally, vertically, ...
- 1,209
19
votes
5
answers
1k
views
When is a game tree the game tree of a board game?
This question arises from what I find interesting in the recently
asked question What is a chess piece
mathematically?
My answer to that question was that mathematically, game pieces are
in general ...
- 237k
19
votes
2
answers
3k
views
What is the winning strategy in this pebble game?
Consider the following two-player pebble game. We have finitely
many stones on a finite linear track of squares. We take turns, and
the allowed moves are:
move any one stone one square to the left, ...
- 237k
4
votes
1
answer
1k
views
Who wins this two player game of making squares?
Two players take turns coloring edges on an $n$-by-$n$ grid. Both players use the same color. Every time a player surrounds a square of the grid, they mark that square with their name and go again. ...
- 547
54
votes
1
answer
3k
views
In the two-person Killing the Hydra game, what is the winning strategy?
My question is which player has a winning strategy in the
two-player version of the Killing the Hydra game?
In their amazing paper,
Kirby, Laurie; Paris, Jeff, Accessible independence results for ...
- 237k
27
votes
1
answer
2k
views
Are Conway's combinatorial games the "monster model" of any familiar theory?
This is related to this question about a "mother of all" groups, and so seemed like it'd fit in better at MO than MSE.
If I understand the answer to that question correctly, the surreal numbers have ...
- 4,907
1
vote
0
answers
95
views
Eventual stabilization for repeatedly adding multiplayer games
This question is an outgrowth of a couple previous questions of mine. In order: 1,2,3. This should be fully self-contained, but those questions may help motivate this one.
To keep things readable, I'...
- 20.7k
22
votes
4
answers
2k
views
The 1-step vanishing polyplets on Conway's game of life
A $n$-polyplet is a collection of $n$ cells on a grid which are orthogonally or diagonally connected.
The number of $n$-polyplets is given by the OEIS sequence A030222: $1, 2, 5, 22, 94, 524, 3031, \...
11
votes
1
answer
723
views
Free category with product and coproduct
Is there a known description of the free category with both product and coproduct?
That is, given a small category $C$, I want to consider a category $U C$ which has product and coproduct, a functor $...
- 42.4k
46
votes
7
answers
10k
views
Conway's game of life for random initial position
What is the behavior of Conway's game of life when the initial position is random? -- We can ask this question on an infinite grid or on an $n$ by $n$ table (planar or on a torus). Specifically ...
- 24.7k
27
votes
4
answers
3k
views
Alice and Bob playing on a circle
I want to solve this problem:
Let there be $n \ge 2$ points around a circle. Alice and Bob play a game on the circle. They take moves in turn with Alice beginning. At each move:
Alice takes one ...
- 379
11
votes
2
answers
402
views
Length of optimal play in Hex as a function of size
Consider Hex on an $n \times n$ board without a swap rule, so that the first player wins. Assume the first player tries to minimize the length of the game, and the second player tries to maximize the ...
- 1,808