# Questions tagged [combinatorial-game-theory]

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

**91**

votes

**11**answers

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

**54**

votes

**5**answers

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

**43**

votes

**4**answers

6k views

### Verifying the correctness of a Sudoku solution

A Sudoku is solved correctly, if all columns, all rows and all 9 subsquares are filled with the numbers 1 to 9 without repetition. Hence, in order to verify if a (correct) solution is correct, one has ...

**33**

votes

**2**answers

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

**191**

votes

**3**answers

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

**47**

votes

**4**answers

8k views

### Do there exist chess positions that require exponentially many moves to reach?

By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an $n\...

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

**25**

votes

**2**answers

1k views

### Is there any superstable configuration in the game of life?

This question spins off of Gil Kalai's recent question on Conway's game of life for a random initial configuration.
There are numerous configurations in the game of life that are known to be stable-...

**19**

votes

**3**answers

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

**17**

votes

**5**answers

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

**18**

votes

**2**answers

1k views

### Determine or estimate the number of maximal triangle-free graphs on $n$ vertices

Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
http://www.math.ucsd.edu/~erdosproblems/erdos/...

**28**

votes

**1**answer

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

**20**

votes

**1**answer

1k views

### A Ramsey avoidance game

Consider the following game: Given $K_n$ the complete graph on $n$ vertices, two players take turns coloring its edges. Initially no edges are colored. At his turn a player can color a prevoiusly not ...

**6**

votes

**1**answer

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

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

**16**

votes

**5**answers

3k views

### Irreversible chess

Suppose we play a chess-variant, where any finite number of pieces are allowed, and the board is as large as we wish, but only two kings in total. And there is no 50 move-rule, no castling and no ...

**9**

votes

**3**answers

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

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

**3**

votes

**0**answers

404 views

### Nimbers and Surreal Numbers [closed]

I have been researching Combinatorial Game Theory. One common theme is the assignment of values to games in order to classify the game as a win for a specific player. One such way is class of surreal ...

**10**

votes

**1**answer

761 views

### What does “game theory” cover and how should it be called?

There seems to be a huge discrepancy in what people refer to when they speak of "game theory". I tend to think of it as including, among other things:
Combinatorial game theory dealing with certain ...

**1**

vote

**2**answers

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

**1**

vote

**2**answers

861 views

### Generalized Sprague-Grundy Theorem

Hey,
I know what is Sprague-Grundy theorem, but I want to know about generalized Sprague-Grundy (GSG) theorem ( which is used for games with cycles ). Apparently there seems to be very less ...

**5**

votes

**0**answers

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

**3**

votes

**3**answers

381 views

### A faster way to spoil an injection?

Ultimately this is about how primes jump. I will abstract the situation somewhat as there may be related applications which do not spring to my mind.
I want to find small spoilers to Hall's Marriage ...

**1**

vote

**0**answers

345 views

### Has anyone seen this version of ring toss (combinatorial object) before?

In reference to a
question on work of Westzynthius and another
question relating to Jacobsthal's function, I have formed a game which I immodestly call Paseman's Ring Toss. I hope that it has been ...