Questions tagged [combinatorial-game-theory]
Two-player turn-based perfect-information games, surreal numbers, impartial games and Sprague-Grundy theory, partizan games
240 questions
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 ...
- 4,536
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 ...
- 1,299
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 ...
- 161
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 ...
- 661
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 ...
- 32.5k
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 ...
- 800
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 $\...
- 6,453
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 ...
- 1,451
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 ...
- 6,377
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
11
votes
5
answers
2k
views
Just starting with [combinatorial] game theory
I have recently become interested in game theory by way of John Conway's on Numbers and Games. Having virtually no prior knowledge of game theory, what is the best place to start?
CommunityBot
- 1
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
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 ...
- 1,887
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 ...
- 20.2k
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
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 ...
- 39.9k
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$...
- 5,429
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 ...
- 105k
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 ...
- 105k
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 ...
- 237k
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
4
votes
3
answers
1k
views
Probability theory and measuring the true strength of chessplayers
If you wanted to measure the strength of, say, a chess player, the best way would involve knowing the true value of each position: then you could compute the frequency $W$ with which the player finds ...
- 540
13
votes
1
answer
399
views
Two-player independent set game
Let $G = (V, E)$ be a finite graph, and $S \subseteq V$ initially be an empty set. Alice and Bob play a game, making moves in turns starting with Alice. A move consists of choosing a vertex $v \in V \...
- 181
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
15
votes
0
answers
488
views
Does the Angel have to be really smart?
My question is about the computational complexity of the Angel's strategy in the Angels and Devils game, tl;dr does the Angel have a polynomial time strategy.
I'm a big Conway fan, so as you can ...
- 540
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 ...
- 1
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 &...
- 101
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 ...
- 4,786
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
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 ...
- 32.5k
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 $...
- 349
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 ...
- 237k
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, ...
- 740
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 ...
- 4,713
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 ...
- 7,226
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
5
votes
1
answer
251
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
9
votes
1
answer
2k
views
Are there any interesting connections between game theory and engineering?
I am doing a senior project and it must be based off game theory, but I am having trouble finding any connections to engineering, possibly structural, or architectural, maybe even civil or mechanical. ...
- 2,821
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$ ...
- 237k
1
vote
0
answers
129
views
A question about a theorem in ONAG by Conway
Does anyone here know about Conway's On numbers and games? Because I can't figure out what he does here on p18. It feels a bit like he's using the statement we want to prove
I will type the proof ...
- 12.9k
16
votes
2
answers
21k
views
Winning strategy at chomp (a chocolate bar game)?
The game of chomp is an example of a game with very simple rules, but no known winning strategy in general.
I copy the rules from Ivars Peterson's page:
Chomp starts with a rectangular array of ...
- 2,821
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 ...
- 2,912
3
votes
0
answers
89
views
Projective plane finite game
This is a 2-person game.
Let $\ P\ $ be any arbitrary projective space (of any dimension $\ \ge2$ and any cardinality, etc., but typically, let it be a finite plane over a field). Let $\ S_0\subseteq ...
- 4,786
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 ...
- 237k
2
votes
1
answer
222
views
Game on groups (generalization of spinning switches puzzle)
Alice and Bob are playing a game as follows:
Initially
There're two subgroups $A,B$ of Sym(n) known to both Alice and Bob
There're $n$ slots $S_1, \cdots, S_n$ and $n$ boxes $B_1, \cdots, B_n$. ...
CommunityBot
- 1
7
votes
0
answers
479
views
A winning move for the first player in $3 \times 3 \times \omega$ Ordinal Chomp
I have been trying to analyse the game of Ordinal Chomp played on a $3 \times 3 \times \omega$ board. The rules can be found in the Wikipedia article, briefly:
This game is played between two players ...
- 101
1
vote
0
answers
102
views
Fast algorithm to compute nimber product
It is known that nimbers (Grundy numbers) below $2^{2^n}$ form a field with the nim addition $\oplus$ and the nim product $\cdot$.
Generally, one can develop an algorithm to compute the product of two ...
- 1,171
13
votes
4
answers
3k
views
Mathematical model for Hanoi Towers
The strategy for the Hanoi Tower puzzle is quite simple. It is based on parity only. In an $n$-pieces puzzle, $2^n-1$ moves are sufficient to carry the whole pile from one pole to another one. My ...
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 $...
- 10.7k