Articles of combinatorial game theory

TicTacToe State Space Choose Calculation

I understand there are numerous questions around the internet about the state space of tic-tac-toe but I have a feeling they’ve usually got it wrong. Alternatively, perhaps it is I who have it wrong. Which is what leads me to my question. Common Over Estimates: Over Estimate One: First some common answers to the number […]

Placing stones on vertices of polygon

We have an $n$-gon with $n\geq 3$. Players $A$ and $B$ place a stone alternately on one of the unused vertices that is not adjacent to a vertex with a stone. The player who cannot move loses. Who has a winning strategy? If $n$ is even, $B$ can win by placing a stone at a […]

Exceptional values in a combinatorial game

Consider the following combinatorial game: We have two heaps of sizes $n_1 \leq n_2$ (with $n_1,n_2 \in \mathbb{N}$). A move leaves the sizes $m_1,m_2$, where $0 \leq m_1 \leq n_1 \leq m_2 \leq n_2$, and $m_i \neq n_i$ for at least one $i$. Equivalently, we move some piece on an infinite checker board above the […]

It seems like a nim variant

Now this is a more of a computer science problem than a math problem but it is concerning game theory and it does seem a lot like nim (it’s from an online judge), so i’m kinda stuck on this one i’d really appreciate any help you could give me. You have $n$ piles of stones, […]

Why can a Nim sum be written as powers of 2?

I have this confusion. Why do we express a nim sum as powers of 2 and why do nim sums cancel in pairs of 2 only? For instance, let’s take the nim game(6,10,15) Now clearly *6 = * $2^2$ + * $2^1$ *10 = * $2^3$ + * $2^1$ *15 = * $2^3$ + * […]

board game: 10 by 10 light bulbs, minimum switches to get all off?

Hy all! My problem is as follows: There’s a board of 10 by 10 light bulbs. (So it’s a square with 10 columns and 10 rows.) Every single bulb has got its own switch. However, something went wrong and when you use a switch not only does it change the state of the proper light […]

How many turns can a chess game take at maximum?

The shortest number of moves that a game of chess can have is 2, as far as I know: White moves pawn from f2 to f3, black moves pawn from e7 to e5 White moves pawn from g2 to g4, black moves queen from d8 to h4. Checkmate. Which results in this situation: There might […]

Winning strategies in multidimensional tic-tac-toe

This question is a result of having too much free time years ago during military service. One of the many pastimes was playing tic-tac-toe in varying grid sizes and dimensions, and it lead me to a conjecture. Now, after several years of mathematical training at a university, I am still unable to settle the conjecture, […]

The application of Nimbers to Nim strategy

I’ve been reading about combinatorial game theory, and some works start with the game of Nim. After that, they introduce Nimbers, which are numbers that represent Nim games. So far so good. I get that, and I understand Nimber addition. But I don’t understand how any of this helps to play Nim. So I’m interested […]

Nimbers for misère games

Let $G$ be an impartial combinatorial game. I claim that there is a game $G’$ such that $G$ (without terminal positions; see below) under the misère play rule is equivalent to $G’$ under the normal play rule. I wonder if this construction is already known and written down somewhere in the literature (so that I […]