# Questions tagged [combinatorial-game-theory]

Two-player turn-based perfect-information games, surreal numbers, impartial games and Sprague-Grundy theory, partizan games

186
questions

**6**

votes

**0**answers

99 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**

votes

**0**answers

104 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 ...

**15**

votes

**1**answer

401 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 &...

**49**

votes

**1**answer

2k 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 ...

**8**

votes

**1**answer

201 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 $...

**23**

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**

votes

**0**answers

39 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 \...

**4**

votes

**0**answers

150 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\}$. ...

**20**

votes

**2**answers

2k 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, ...

**1**

vote

**0**answers

30 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 ...

**3**

votes

**1**answer

204 views

### Is following function a metric on the set of isomorphism classes of graphs with countably many vertices?

Suppose $\Gamma_1(V_1, E_1)$ and $\Gamma_2(V_2, E_2)$ are simple graphs with countably many vertices. And suppose $A_1$ and $A_2$ are initially empty sets. Suppose two players play the following game: ...

**6**

votes

**0**answers

169 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 ...

**1**

vote

**1**answer

47 views

### Perturbation of the value of a general-sum game at a equilibirium

Consider a general-sum game with $N$ players. Let $u_i(a_1, \ldots, a_N)\colon \prod_{i=1}^N A_i \rightarrow \mathbb{R} $ be the payoff of the player $i\in \{ 1, \ldots, N \}$ when each player takes ...

**28**

votes

**2**answers

864 views

### Solution to simple mathematical game

Consider the following game (that I made up). Two players each attempt to name a target number. The first player begins by naming 1. On each subsequent turn, a player can name any larger number that ...

**28**

votes

**0**answers

718 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$), "...

**4**

votes

**3**answers

203 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 ...

**1**

vote

**0**answers

67 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'...

**1**

vote

**0**answers

77 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 ...

**2**

votes

**0**answers

97 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$. ...

**1**

vote

**0**answers

24 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} \...

**2**

votes

**0**answers

153 views

### Combining a Nim-variation and Wyrthoff's game. How to find a winning strategy? [closed]

Wythoff's game is a variation of the classical Nim - There are two heaps and the players take turns either taking any amount from one heap, or the same amount of both heaps. The winner is the one ...

**3**

votes

**2**answers

136 views

### Satisfier-Falsifier games

In a Maker-Breaker game, there is a finite set of elements $X$, and a family $F$ of subsets of $X$ called the "winning sets". Two players, Maker and Breaker, take turns picking untaken elements from $...

**2**

votes

**0**answers

94 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, ...

**6**

votes

**1**answer

134 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 ...

**2**

votes

**1**answer

215 views

### Combinatorial games with infinite paths, and generalized Sprague-Grundy theory

Generalized Sprague-Grundy theory has been used to analyze finite impartial loopy games with normal play. There is a nice short account by Mark S. in this answer. It was introduced by Cedric Smith in ...

**1**

vote

**0**answers

100 views

### Is there only one meaningful definition of product of games?

Work in the context of combinatorial games as introduced by Conway.
For surreals, the definition of the product is forced by the requirement that surreals should form an ordered field.
Say, if $s' <...

**5**

votes

**1**answer

185 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 ...

**6**

votes

**0**answers

92 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 ...

**7**

votes

**1**answer

293 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 ...

**1**

vote

**2**answers

233 views

### How to describe the common boundaries between regions in a infinite Sudoku?

This relates to the answer to a question "Who wins two player sudoku?" and this awesome blog.
A Sudoku can be $N \times N$ where $\sqrt{N}$ is a natural number because $N \times N / \sqrt{N} \times \...

**31**

votes

**1**answer

2k views

### Is there a position in infinite Go for which the life of a particular stone has transfinite game value?

As follow up to Checkmate in $\omega$ moves?, we can ask the same question about go. Is there a position on a $\mathbb Z \times \mathbb Z$ goban such that either black can kill a white group, but ...

**1**

vote

**1**answer

70 views

### Effective way to find Nash equilibrium

Is there any good algorithm for finding Nash equilibrium point, for one and repeated game theory? Thansk a lot for giving me some guidance.

**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 ...

**19**

votes

**1**answer

624 views

### Who wins the Rubik's cube game?

This game has two players, Spoiler and Solver. We start with a solved 3x3x3 rubik's cube (to make the problem easier).
Solver and Spoiler take turns making 90 degree twists (starting with Solver). ...

**10**

votes

**3**answers

855 views

### The Sudoku game: Solver-Spoiler variation

Consider the Sudoku Solver-Spoiler game, a natural variation of the Sudoku game recently appearing in the question Who wins two-player Sudoku? posted by user PyRulez. In that game, the players attempt ...

**34**

votes

**2**answers

3k views

### Who wins two player sudoku?

Let's say players take turns placing numbers 1-9 on a sudoku board. They must not create an invalid position (meaning that you can not have the same number in within a row, column, or box region). The ...

**19**

votes

**3**answers

739 views

### The arithmetic progression game and its variations: can you find optimal play?

Consider the arithmetic progression game, a two-player game of
perfect information, in which the players take turns playing
natural numbers, or finite sets of natural numbers, all distinct,
and the ...

**37**

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$ ...

**46**

votes

**3**answers

4k 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

233 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**

votes

**1**answer

3k 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 ...

**10**

votes

**2**answers

228 views

### For which number of pairs is it an advantage to start in memory

Players A and B play memory starting with $n$ pairs of cards. We assume that they can remember all cards which have been turned. At his turn a player will first recall if two cards already turned ...

**21**

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, \...

**28**

votes

**1**answer

875 views

### Vanishing line on Conway's game of life

If the initial state of Conway's game of life is a line of $n \in [0,100]$ alive cells, then it vanishes completely after some steps iff $n \in \{0,1,2,6,14,15,18,19,23,24 \}$. See below for $n=24$.
...

**17**

votes

**5**answers

979 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 ...

**59**

votes

**4**answers

14k 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 open for more ...

**9**

votes

**1**answer

242 views

### Ordered Nim game

Consider the following variant of Nim:
There are two players and $n$ piles of stones, with sizes $a_1,\dots,a_n$, such that $a_i\leq a_j$ for any $i<j$.
A move consists of removing a positive ...

**5**

votes

**1**answer

290 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), ...

**9**

votes

**0**answers

196 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 \...

**3**

votes

**2**answers

242 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 ...