Questions tagged [combinatorial-game-theory]
Two-player turn-based perfect-information games, surreal numbers, impartial games and Sprague-Grundy theory, partizan games
230
questions
7
votes
1
answer
205
views
Maximum $2$-D bootstrap percolation time for $n$ points on an $n\times n$ grid
I hesitate to ask this question here, but since it remained unanswered after a bounty on MSE, I ask it here with some reservation.
Is the maximum bootstrap percolation time for $n$ points on an $n\...
- 1,893
7
votes
3
answers
816
views
Decidability of the winning-position problem in an infinity chess with a finite number of short-range pieces only
Definitions
Long-range pieces: queens, rooks, bishops.
Short-range pieces: pawns, knights, kings.
We can extend the definition of short-range pieces to include also fairy pieces like: Berolina ...
- 1,107
7
votes
1
answer
348
views
A Bitwise Xor Problem
Consider a sequence $a_i$ defined by
$$
\begin{align*}
a_1&=p,\\
a_2&=q,\\
a_i&=a_{i-1} \oplus a_{i-2}+1,
\end{align*}$$
where $\oplus$ is the bitwise xor operation. How can we give an ...
- 601
7
votes
2
answers
634
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) ...
- 30.2k
7
votes
1
answer
292
views
Games in non-standard models
Has anyone studied Combinatorial game theory in non-standard models?
In particular, we can work in either non-standard models of set theory, or we can work in non-standard models of arithmetic, where ...
- 5,831
7
votes
0
answers
225
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.3k
7
votes
0
answers
291
views
How does Conway's proposed compromise for constructing the real numbers in ONAG actually work?
I have also asked this question on Math Stack Exchange (link).
In On Numbers and Games, after discussing the inclusion of the real numbers in the surreal numbers, No, Conway discusses the merits of ...
- 415
7
votes
0
answers
440
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 ...
- 2,691
7
votes
0
answers
2k
views
Is there a chess position equivalent to the Collatz conjecture?
Suppose we have an infinite board with a finite number of chess pieces. The question is whether white can checkmate black (without the after 50 moves it is a draw rule). Can you give an explicit ...
- 18.4k
6
votes
1
answer
718
views
Bridge game with only one suit: strategy
This game looks like bridge, but 1- there are only two players Alice and Bob, 2- there is only one suit, whose cards are numbered $1, 2,\ldots,2n$. One deals each player $n$ cards. Therefore Alice ...
- 51.6k
6
votes
2
answers
456
views
A (possibly boring) Voronoi Game
The board for this game is a compact convex region $\cal C$ of $\mathbb{R}^2$.
Below I illustrate with $\cal C$ an equilateral triangle.
Two players, $A$ and $B$, alternate turns.
At each turn they ...
- 149k
6
votes
1
answer
113
views
pursuit-evasion based on Schroeder's upper bound for graphs of genus $g$
I am following Schroeder's work on pursuit-evasion games on graphs (often called "cops and robbers"). In his 2001 publication ("The copnumber of a graph is bounded by $\lfloor 3/2 {\ \...
- 155
6
votes
1
answer
182
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.5k
6
votes
1
answer
169
views
What is the minimum worst-case length of an element removal game?
A game is played as follows. There is a set $X = \{1, \ldots, n\}$. Player 1 is trying to find a "locally minimal subset" $M \subseteq X$ - that is, player 2 has said that $M$ is good, and also that ...
- 1,331
6
votes
1
answer
314
views
Anything known about the Grundy Ordinal of Sylver's Coinage
Sylver's coinage is an example of an unbounded finite (if slightly modified) combinatorial impartial game. Quoth wikipedia:
The two players take turns naming positive integers that are not the
sum of ...
- 5,831
6
votes
1
answer
632
views
A different equivalence relation on partizan combinatorial games
The following definitions are fairly standard, but reworded in a way that will be more appropriate for my question (so what follows is fairly long, but should be easy to read for the experts and might ...
- 30.2k
6
votes
0
answers
257
views
Quantum surreal numbers
Toward Quantum Combinatorial Games presents the definition of a "quantum game", allowing a superposition of moves rather than a single classical move. This leaves me wondering: Since surreal ...
- 161
6
votes
0
answers
179
views
Combinatorial game similar to Sprouts
Is there a name for the following combinatorial game? Is there a solution which player has a winning strategy?
Basically this game is "Sprouts without midpoints". One starts with $n$ points in the ...
- 5,402
6
votes
0
answers
662
views
Number of Configurations in the optimal Hanoi tower
There is a unique strategy how to move $n$ disks from the first rod to the second optimally and it takes $2^n-1$ steps, solution is obtained by simple recursion. I am interested into the following ...
- 389
5
votes
1
answer
6k
views
How many Tic Tac Toe games are possible? [closed]
Consider the average game of Tic Tac Toe or Noughts and Crosses. The game is played on a 3 by 3 two dimentional board. The game is played by two people and each person is allowed to only add one type ...
- 482
5
votes
1
answer
453
views
Can a game be an option of itself?
My question is, can a game contain itself as an option? and can it be a surreal number? For example $A=\{A|\}$ or $B=\{C|B\}$ where $C$ is a surreal number.
from the point of view of games, it is ...
- 51
5
votes
1
answer
411
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 ...
- 976
5
votes
1
answer
471
views
What ordinal corresponds to the T(3)?
Let's play a game. You start with the ordinal $\alpha$ and I start with the empty sequence. Each turn, you decrease your ordinal, and I add a tree (where each node can have one of three labels), ...
- 5,831
5
votes
1
answer
2k
views
Is it possible to evaluate Connect 4 positions with Combinatorial Game Theory?
The surreal numbers in Combinatorial Game Theory only work for certain classes of games (e.g. they must satisfy normal play convention). This rules out even reasonable games with fairly well-...
- 22.6k
5
votes
2
answers
593
views
Approximate search space on a 5x5x5 cube with 3 different possible classes?
Hey all,
I read the meta, and I realize this question might be pretty elementary for this site, but I'm having trouble computing this, and I know it won't take too much insight for someone to give me ...
- 153
5
votes
1
answer
969
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 ...
- 4,958
5
votes
1
answer
203
views
A set-family game
Two players, Green and Red, play a zero-sum game. It is parametrized by two integers $n\geq 0, k\geq 0$, and a finite family $F$ of sets of size $n$ (each set may appear multiple times in $F$).
Each ...
- 3,585
5
votes
1
answer
276
views
Duration and critical groups order in sandpile models and chip firing games
The famous chip firing game (which is closely related to sandpile models) goes like this:
Place chips at the vertices of a graph. REPEATEDLY: If a vertex $v$ of
degree $d_{v}$ has at least $d_{v}...
- 6,882
5
votes
1
answer
764
views
Algorithmic war
No, not the war on drugs, but the game of War considered in
Does War have infinite expected length?
As noted in that discussion, the game of war can go on forever, but my question is: can it be ...
- 95.6k
5
votes
1
answer
238
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.3k
5
votes
1
answer
461
views
Resources-Aware Combinatorial Game Theory
First of all, I preemptively apologize if my question happens to be naive, I am no expert of CGT (or general game theory, for that matter).
Now the question:
**is there such a thing as the study of ...
- 7,613
5
votes
0
answers
257
views
Nimber $2^{2^k} - 1$ is a multiplicative generator of $[2^{2^k}]$?
Let $t = 2^{2^k}$, and consider the field $[t]$ of nimbers below $t$. For $k \leq 6$ one can check that $t - 1$ (in the usual arithmetic sense) is a multiplicative generator of $[t] \backslash \{0\}$. ...
- 5,380
5
votes
0
answers
214
views
Is Domineering on any finite approximation of the Sierpinski Carpet always a second-player win?
The game of Domineering can be played on any board consisting of some subset of $\mathbb{Z} \times \mathbb{Z}$.
In particular, consider the boards $K_n$ generated by iterating the following inductive ...
- 3,353
5
votes
0
answers
389
views
Why is this transfinite game not determined?
This question originates from the paper On the Axiom of Determinateness by Jan Mycielski, section 7. Given a set $X$ and an ordinal $\alpha$, the author defines a transfinite game of length $\alpha$ ...
- 897
5
votes
0
answers
217
views
Topological Subset Take-Away
David Gale's subset take-away game is a game where two players A and B play with a finite set $S$. Players alternately choose proper nonempty subsets of $S$ such that if a subset is chosen, then none ...
user62675
5
votes
0
answers
287
views
Generalization of Sprague-Grundy Theorem
In my research on Combinatorial Game Theory, I used a certain theorem that is essentially a generalization of the Sprague-Grundy theorem. Because the result hinges too much on the work of others to be ...
- 1,129
5
votes
0
answers
210
views
Analysis of Nim-Like Game? [closed]
There are a finite number of heaps, each with a finite number of counters. Two players take turns; on each move, they may remove exactly one counter from any heap, and also, if the heap is of size $n$,...
- 151
4
votes
3
answers
1k
views
Generalized tic-tac-toe
We begin with $2n+1$ cards, each with a distinct number from $-n$ to $+n$ on it, face up in between the two players of the game. The players take turns selecting a card and keeping it. The first ...
- 78.7k
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 ...
- 17.5k
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. ...
- 537
4
votes
3
answers
235
views
Best strategy for a combinatorial game
Consider the following scenario. We have 20 balls and 100 boxes. We put all 20 balls into the boxes, and each box can contain at most one ball.
Now suppose we are given 5 chances to pick 20 out of ...
- 281
4
votes
3
answers
2k
views
Motivation and Intuition for Sprague-Grundy Theorem
I have read about Sprague Grundy Theorem and understand the proof of its correctness. However, I am unable to see the motivation behind the definitions. How do Sprague and Grundy know that they should ...
- 41
4
votes
2
answers
376
views
Study of Hex on the Torus
Hex is usually played on a parallelogram shaped board. What if you play it on a Torus?
One thing I notice is that the idea of connecting opposite sides doesn't make much sense anymore, since a torus ...
- 5,831
4
votes
1
answer
771
views
Nash Equilibrium in general graphical game
Any one has any ideas about how to compute the Nash Equilibrium in general graphical game? Especially, when the graph structure is not a tree.
user39815
4
votes
1
answer
402
views
Lights Out game over GF(p)
On Jaap's Puzzle Page
http:// www.jaapsch.net/puzzles/lomath.htm#domtilings
Theorem 7 says:
If standard Lights Out is played on a m x n grid-like board, ...
- 329
4
votes
1
answer
538
views
Graph connectivity related game
I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of ...
- 172
4
votes
0
answers
151
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
4
votes
0
answers
148
views
Infinite positions in 3D chomp
I've recently come back to investigating ordinal chomp. See A winning move for the first player in $3 \times 3 \times \omega$ Ordinal Chomp for a definition. I made a new discovery, that the position \...
- 2,691
4
votes
0
answers
241
views
Mistake in ONAG?
In the second edition of the book "On Numbers and Games" by Conway there is a theorem 88 (p. 194) on comparison of sums of ${\uparrow} x$ games. It contains a weird statement:
... (If $X$ is a sum ...
- 5,380
4
votes
0
answers
173
views
Modern advances in combinatorial game theory
I'm going to take part in teaching a course in combinatorial game theory in the best of ONAG's spirit. I was wondering if there are interesting post-ONAG results that are worth mentioning in (a later ...
- 5,380