# 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

120 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

123 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

85 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

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

**1**

vote

**1**answer

175 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

89 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

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

**6**

votes

**0**answers

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

**0**

votes

**0**answers

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

**1**

vote

**0**answers

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

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

**1**

vote

**2**answers

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

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

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

**18**

votes

**1**answer

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

**9**

votes

**3**answers

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

**32**

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

**19**

votes

**3**answers

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

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

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

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

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

**28**

votes

**1**answer

768 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

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

**9**

votes

**1**answer

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

**4**

votes

**1**answer

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

**8**

votes

**0**answers

151 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

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

**4**

votes

**0**answers

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

**4**

votes

**0**answers

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

**10**

votes

**2**answers

446 views

### What surreal numbers are representable by Red-Blue Hackenbush games?

Every game of Red-Blue Hackenbush represents a surreal number. Is the converse true? Assuming that it is false, what can be said about the class of surreal numbers that are representable by such ...

**2**

votes

**1**answer

325 views

### Are Surreal Numbers the same as Trans-series?

I recently found the paper of Berarducci + Mantova [1, 2] saying that surreal numbers are equivalent to trans-series. These are very different objects:
trans-series are used in physics to correct, ...

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

**8**

votes

**0**answers

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

**9**

votes

**1**answer

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

**8**

votes

**1**answer

288 views

### A game of singletons

Alice and Bob play the following zero-sum game, parametrized by two integers $m$ and $k$:
Alice picks $m$ sets, each of which has $k$ items.
Bob colors some items in green.
Bob's score is the number ...

**3**

votes

**3**answers

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

**2**

votes

**0**answers

81 views

### Difficulty of 3-color forest Hackenbush

"Forest Hackenbush" (for lack of a better name) is the particular case of the game of Hackenbush where the initial position (and therefore all subsequent positions) is a (finite) forest (:= disjoint ...

**6**

votes

**1**answer

177 views

### Maximum $2$-D bootstrap percolation time for $n$ points on an $n\times n$ grid

I hesitate to ask this question here, but since it remained unanswered after a bounty on MSE, I ask it here with some reservation.
Is the maximum bootstrap percolation time for $n$ points on an $n\...

**4**

votes

**0**answers

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

**9**

votes

**1**answer

312 views

### A Combinatorial Game with Integer Sequences

Two players, Alice and Bob, take turns constructing a sequence $a_1,a_2,a_3,\dots$, of distinct positive integers, none greater than a given parameter $K$. Alice plays first and makes $a_1=1$. ...

**11**

votes

**1**answer

178 views

### A game: building a bounded degree graph

Given positive integers $n$ and $d\leqslant n-1$. Two players build a graph, starting with $n$ vertices and no edges. On each turn, a player joins two yet not joined vertices by an edge. It is ...

**9**

votes

**2**answers

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

**6**

votes

**0**answers

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

**0**

votes

**0**answers

121 views

### Local Connection Game

A local connection game is given by a set of vertices and graph G where connection is built by adding edges.
If the cost to user a(user at node a) is given by $$C(u)=\alpha n_u + \beta \sum_v(dist(u,...

**1**

vote

**0**answers

57 views

### Does handle reduction determine braid equivalence in quotients of braid groups?

Let $B_{n}$ denote the $n$-strand braid group. Let $G$ be a group generated by elements $x_{1},...,x_{n-1}$. Let $N$ be the smallest normal subgroup of $B_{n}$ such that the mapping $x_{1}\mapsto\...

**4**

votes

**0**answers

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