Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [combinatorial-game-theory]

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

91
votes
11answers
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
5answers
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
4answers
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
2answers
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
3answers
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
4answers
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
3answers
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
2answers
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
3answers
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
5answers
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
2answers
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
1answer
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
1answer
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
1answer
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
4answers
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
5answers
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
3answers
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
3answers
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
0answers
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
1answer
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
2answers
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
2answers
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
0answers
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
3answers
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
0answers
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 ...