# Questions tagged [combinatorial-game-theory]

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

**1**

vote

**0**answers

18 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

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

**1**

vote

**0**answers

128 views

### How often do random games of go end in illegal moves?

Suppose that moves are generated from two players in accordance with three rules: each move is chosen uniformly at random among places on the board ($19 \times 19$, $9 \times 9$, or $k \times k$ with ...

**3**

votes

**2**answers

124 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

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

**5**

votes

**1**answer

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

**6**

votes

**1**answer

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

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

**1**

vote

**0**answers

240 views

### surreal form star is a xor cipher [closed]

i have been doing a lot of surreal analysis lately & it dawn'd on me that star in the surreal numbers has the same properties of a simple xor cipher.
star operations are given as:
...

**1**

vote

**1**answer

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

**5**

votes

**1**answer

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

**1**

vote

**0**answers

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

**18**

votes

**1**answer

442 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). ...

**6**

votes

**0**answers

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

**5**

votes

**1**answer

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

**9**

votes

**1**answer

319 views

### Infinite-dimensional hex

Suppose $n$ players take turns selecting vertices of the grid $[k]^n = \left\{0, 1, 2, \ldots, k-1\right\}^n$. Each player is assigned a pair of opposite faces of the grid, and wins the game if they ...

**0**

votes

**0**answers

84 views

### Decidability of mate-in-n for infinite chess with huygens piece

Consider a game like chess on an infinite board, where we have the usual chess piece types and an additional piece which moves a prime number of square horizontally or vertically.
If we assume a ...

**6**

votes

**2**answers

460 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) ...

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

**0**

votes

**1**answer

355 views

### Infinite board games: sentences about

As a unified approach if we have an ( read any) infinite board game described as $\mathcal{G}$ using a particular axiom set A..
can a sentence be devised in A which automatically answers the basic ...

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

**11**

votes

**1**answer

841 views

### The infinite X in Conway's game of life

In Conway's game of life, take the initial position to be two infinite diagonal lines of live cells, with a single cell in common. Does this thing converge to a stable configuration? I.e., is the ...

**30**

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

**43**

votes

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

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

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

**9**

votes

**2**answers

537 views

### Choosing subsets of $\mathbb R$ of cardinality $\frak c$, who wins?

Consider the following infinite game: two players, I and II, are alternating and choosing a descending sequence of subsets of $\mathbb R$ of cardinality $\frak c$, so I chooses a set $A_1\subseteq\...

**19**

votes

**3**answers

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

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

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

**1**

vote

**1**answer

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

**16**

votes

**1**answer

1k views

### Playing an (invertible) matrix game with two players

Players $A$ and $B$ take an empty $n \times n$ matrix and place, one by one, an element (say, a rational number) in an unoccupied place of this matrix. Player $A$ starts. The game ends if there is no ...

**5**

votes

**0**answers

128 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

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

**14**

votes

**0**answers

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

**4**

votes

**1**answer

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

**10**

votes

**2**answers

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

**7**

votes

**2**answers

775 views

### Square Achievement Game on a Grid

Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an n x n grid.
The first player to occupy the vertices of a square with horizontal and vertical ...

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

**4**answers

4k views

### David Gale's subset take-away game

I learned of this problem through Su Gao, who heard of it years ago while a post-doc at Caltech. David Gale introduced this game in the 70s, I believe. I am only aware of two references in print:
...

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

**9**

votes

**1**answer

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

**11**

votes

**4**answers

912 views

### a game on numbers

Hello, here is a little two-players game.
Players A and B choose three numbers : a, b and c for A, a', b' and c' for B. The values are numbers between 0 and 1, their sum is 1, and they are ordered: $...

**17**

votes

**4**answers

2k views

### Variation on a matrix game

The original problem appeared on last year's Putnam exam:
"Alan and Barbara play a game in which they take turns filling entries of an initially empty 2008×2008 array. Alan plays ﬁrst. At each turn, ...

**12**

votes

**12**answers

7k views

### Are there any interesting connections between Game Theory and Algebraic Topology?

I've been learning game theory on my own and was just curious how it connected with previous things I've learned. So are there any interesting connections between Game Theory and Algebraic Topology? ...

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

**4**

votes

**1**answer

246 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

**1**answer

414 views

### Is every ordinal the nimber of a ring?

This question is about the game of Noetherian rings, see MO/93276.
Here I will include the zero ring in order to get better formulas.
The nimber of a Noetherian ring is an ordinal number. It is ...