Questions tagged [combinatorial-game-theory]
Two-player turn-based perfect-information games, surreal numbers, impartial games and Sprague-Grundy theory, partizan games
56 questions with no upvoted or accepted answers
31
votes
0
answers
919
views
Is this representation of Go (game) irreducible?
This post is freely inspired by the basic rules of Go (game), usually played on a $19 \times 19$ grid graph.
Consider the $\mathbb{Z}^2$ grid. We can assign to each vertex a state "black" ($b$), "...
18
votes
0
answers
987
views
Are the moves/rules of standard chess delicately balanced?
(While the world chess championship is in progress in Sochi...)
Is there mathematical evidence that standard chess is somehow
...
- 151k
16
votes
0
answers
988
views
A Combinatorial Game: the Snake and the Hunter
The Snake and the Hunter is a game for two players who play in two rounds interchanging the roles of snake and hunter. The game is played in a rectangular grid of points, say $6 \times 6$. In both ...
- 3,717
16
votes
0
answers
2k
views
Characterizing the surcomplex numbers
Conway showed that the Field of surreal numbers ("${\bf No}$")
is the maximal totally ordered Field.
Later Jacob Lurie showed that the Group of all partizan games ${\bf Pg}$ is
the universally ...
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 ...
- 6,652
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
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
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
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
9
votes
0
answers
177
views
Is there a better way to understand this particle?
I've been reading through Winning Ways and was working through some examples of my own related to cooling and particles, and I managed to stump myself. If we let ...
- 99
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
8
votes
0
answers
531
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 ...
- 6,969
8
votes
0
answers
327
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 ...
- 455
8
votes
0
answers
544
views
A Banach-Tarski game
This is partially inspired by the question https://math.stackexchange.com/questions/1383397/cutting-a-banach-tarski-cake, which I find intriguing if unclearly written.
A paradoxical family of subsets ...
- 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
7
votes
0
answers
285
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 ...
- 171
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 ...
- 2,811
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 ...
- 19.1k
6
votes
0
answers
186
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,482
6
votes
0
answers
669
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 ...
- 399
5
votes
0
answers
259
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,590
5
votes
0
answers
220
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,393
5
votes
0
answers
184
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,590
5
votes
0
answers
396
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$ ...
- 907
5
votes
0
answers
219
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
306
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
4
votes
0
answers
180
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
165
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,811
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,590
4
votes
0
answers
309
views
A game played on binary matrices ($2$-dimension coin-turning game)
Let $r\geq 1$ be a natural number. I am interested in the following (two-player, impartial, perfect-information) game:
The state of the game is an $n\times n$ matrix with coefficients in $\mathbb{F}...
- 32.5k
4
votes
0
answers
149
views
Combinatorial fairness property in division of goods
Given $n$ agents, and $m$ items where $v_i(g) \geq 0$ is the value of item $g$ for agent $i$, does there always exist a partition $A_1, ..., A_n$ of the $m$ items into $n$ sets s.t. for all $i, j \in \...
- 388
4
votes
0
answers
408
views
SWAT vs Rioters (cops vs robbers variant)
I thought of this while at the Combinatorial Potlatch at Seattle University, where Peter Winkler gave an excellent talk on Cops vs Drunken Robbers. I'll just open it up to the floor. The problem ...
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
3
votes
0
answers
180
views
What values are representable by Hackenbush stalks?
It is known that every number can be represented by some red-blue Hackenbush stalk (see here, for instance). What values can be represented by red-blue-green Hackenbush stalks? In addition, what games ...
- 131
3
votes
0
answers
175
views
Does a generalized Queen split the upper P-positions of Wythoff Nim into two new beams of P-positions?
Wythoff Nim is an impartial game where 2 players take turns in reducing the heights of two finite heaps of tokens. Two types of moves are allowed
(I) Remove any number of tokens from precisely one ...
- 71
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
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
2
votes
0
answers
103
views
A combinatorial number game
Alice and Bob play the following (base 10) number game. A target N is fixed, N being a positive integer. Alice then writes the number 1 on the blackboard. Bob responds with the number 2. Thereafter, ...
- 3,717
2
votes
0
answers
96
views
On subset of Deterministic games
Denote strings $u,v$ from $\{0,1\}^n$.
Denote concatenated pair $[uv]$.
Denote
$$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$
collection of pairs with Hamming distance $1$ from $[uv]$ string ...
- 13.9k
2
votes
0
answers
146
views
Open games formed by pasting together infinitely many clopen games
Throughout, I think of games and their underlying trees as the same: so a "clopen game" and a "well-founded tree" mean the same thing.
Fix a sequence of clopen games $\lbrace T_i: i\in\omega\rbrace$. ...
- 20.7k
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 ...
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
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 ...
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
1
vote
0
answers
85
views
Winning criterion for a combinatorial game
Given $n$,
let $\mathcal{R}$ be a set of pairs $(\rho,A)$
where $A\subseteq n, \rho\in 2^A$.
Consider the following game between A and B.
At each round $t$, A enumerates an $m\in n$ (that has not been ...
- 909
1
vote
0
answers
136
views
Nim variant with minimum number of objects?
I'm wondering where I can find in the literature (if it exists) a discussion of a Nim variant where we impose the additional condition on Nim that we can remove only up to $c$ objects before the game ...
- 111
1
vote
0
answers
40
views
Suggestions for two-choice game played in ladder graph
I was just working on counting all the possible Nash Equilibrium solutions for a two-choice game played on a ladder graph (I got my results and all that for a generic number of players).
And I was ...
- 11
1
vote
0
answers
143
views
Strategy of Responder in Rényi Ulam Liar Games
I tried posting this in Math Stack Exchange but got no responses, so I figured I could try my luck here. My main concern is that I can't figure out how to get started on my "research" (bear with me, I'...
- 11
1
vote
0
answers
96
views
Is there a well-posed definition of game on a graph? Or a well defined category of games on graphs?
All I ever found about this were natural language rules à la Asimov's three laws of robotics. The questions are straightforward questions:
1) Is there a well-posed mathematical definition of game on ...
- 11
1
vote
0
answers
32
views
Bound for the additive period length of certain Sprague-Grundy functions
Let $\left( Y_x \right)_{x=0}^\infty $ be a sequence of finite subsets of $\mathbb{Z}$, and let $G : \mathbb{N}_0 \to \mathbb{N}_0$ be a greedy permutation, defined by
$$ G(x) = \operatorname{mex} \...
- 111