Questions tagged [combinatorial-game-theory]
Two-player turn-based perfect-information games, surreal numbers, impartial games and Sprague-Grundy theory, partizan games
246 questions
3 votes
0 answers
180 views
In a nonempty Baire space, the first player does not have a winning strategy in the Choquet Game
Suppose $X$ is a nonempty topological space. The Choquet Game on $X$ is a two-player infinite game defined as follows. The first player choose a nonempty open subset $U_0\subseteq X$. The second ...
- 1,538
11 votes
1 answer
342 views
Are the "strategy operators" generated from strategy stealing ever useful?
In the strategy-stealing proof that (say) player $1$ has a winning strategy in Chomp, assuming towards contradiction that player $2$ has a winning strategy $\Sigma$ we define a strategy $\Sigma'$ for ...
- 19.5k
4 votes
1 answer
308 views
Birthday of a surreal number
There are two ways that one could reasonably define the birthday of a surreal number $x$: The smallest birthday among all forms $\{L|R\}$ that are equal to $x$. The smallest birthday among all ...
- 507
9 votes
1 answer
364 views
What is the algebra of games with miserification?
The set of finite combinatorial games is the smallest set $\mathscr{G}$ such that $\{\vert\}\in\mathscr{G}$ and, whenever $A,B\subseteq\mathscr{G}$ are finite, we have $\{A\vert B\}\in\mathscr{G}$. ...
- 19.5k
18 votes
1 answer
821 views
How to approximate the max and min of Hydra-Game?
Basic background: A hydra is a finite rooted tree (with the root usually drawn at the bottom). The leaves of the hydra are called heads. Hercules is engaged in a battle with the hydra. At each step of ...
- 71
12 votes
2 answers
534 views
Can every 2-player-coalition avoid losing in 5-player-nim?
I'm interested in $5$-player nim (it will become clear why $5$). Individual players - which I'll identify with the numbers from $1$ to $5$ - make moves as usual, with the move order going $... \...
- 19.5k
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 ...
- 53.2k
8 votes
1 answer
437 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 ...
- 507
1 vote
1 answer
433 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
10 votes
1 answer
707 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 $\...
- 507
14 votes
1 answer
1k 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 ...
- 246k
34 votes
7 answers
4k 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 ...
- 246k
10 votes
0 answers
272 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 ...
- 8,096
8 votes
0 answers
121 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 ...
- 303
12 votes
0 answers
625 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 ...
- 671
4 votes
1 answer
552 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,347
2 votes
0 answers
94 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$ ...
- 187
1 vote
0 answers
217 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 ...
7 votes
0 answers
275 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 ...
- 19.5k
10 votes
0 answers
479 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,558
2 votes
0 answers
241 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
4 votes
2 answers
723 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 ...
- 41
12 votes
1 answer
953 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 $...
- 19.5k
5 votes
1 answer
492 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,703
6 votes
1 answer
238 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 ...
- 18.4k
97 votes
3 answers
7k 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 ...
- 901
1 vote
0 answers
128 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'...
- 19.5k
5 votes
1 answer
331 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 ...
- 19.5k
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, ...
- 246k
1 vote
0 answers
148 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 ...
3 votes
0 answers
122 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 ...
- 5,263
7 votes
1 answer
607 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 ...
- 5,263
1 vote
0 answers
138 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,211
5 votes
1 answer
2k 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,469
12 votes
1 answer
642 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 ...
- 18.4k
4 votes
0 answers
246 views
Two-player item picking game
Two players $A$ and $B$ play this game: There are $n$ items, where the $i$th item is of value $a_i$ to player $A$ and is of value $b_i$ to player $B$. Two players take turns picking items, and each ...
- 41
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 ---...
- 47k
1 vote
2 answers
427 views
Do restricted Nim-like games have winning strategies?
Considering a Nim-like game to be: There are three piles $A,B,C$, and the amount of their elements are $|A|=2, |B|=5, |C|=6$; There are 2 players. Each time a player can either take $x (1\leq x \leq ...
3 votes
1 answer
406 views
What does it mean for the surreal numbers/partizan games to be "universally embedding"?
In "On numbers and games", Conway writes that the surreal Numbers form a universally embedding totally ordered Field. Later Jacob Lurie proved that (the equivalence classes of) the partizan ...
- 83
2 votes
1 answer
151 views
Does Conway’s field of finite nim values have arithmetically tractable isomorphisms?
Conway constructed a field of characteristic 2 whose elements are the finite Nim values, indexed by the natural numbers. What is known about nontrivial automorphisms of this field? Do any of them ...
- 20.1k
1 vote
0 answers
300 views
The maximum number of moves in a game of Nim [closed]
I was assigned a fun, but also quite hard problem for my computer science class - I have to write a java program that computes the maximum number of turns in an optimal game of Nim. In case you are ...
- 11
28 votes
7 answers
7k 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
8 votes
1 answer
281 views
Name of a game : Remove two chips from a vertex or one chip from both ends of an edge
Consider a finite graph $\Gamma$ with a positive number $n_v\geq 0$ of chips stacked at each vertex $v$ of $\Gamma$. Two players play in turn with moves consisting either of removing two chips from a ...
- 18.4k
6 votes
1 answer
2k 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. ...
- 587
1 vote
1 answer
185 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$...
- 18.4k
17 votes
0 answers
381 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 ...
- 18.4k
1 vote
1 answer
197 views
Complexity of games with graph classes
Let $\mathfrak{G}$ be the class of all finite directed and undirected graphs. Let $A,B\subseteq \mathfrak{G} $, $A$ and $B$ are closed under graph isomorphisms, and $A \cap B = \varnothing$. Consider ...
- 107
25 votes
4 answers
3k 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 ...
- 246k
0 votes
1 answer
125 views
Mapping problem reminiscent of Mastermind
Given 2 finite sets $S$ and $M$, with $\operatorname{card}(S) \geq \operatorname{card}(M)$, and an item $z \not\in M$. There is an unknown function $f: S \to M \cup \{z\}$, which is known to be one-to-...
8 votes
0 answers
621 views
Winning moves in Hex
The game "Hex" is a simple game which apparently has been invented at least twice (Piet Hein and John Nash). The game consists of an n by n grid of hexagons, with two opposite sides marked ...
- 8,395