Combinatorial game theory (abbreviated CGT) is the subfield of combinatorics (not traditional game theory) which deals with games of perfect information such as Nim and Go. It includes topics such as the Sprague-Grundy theorem and is tangentially related to the Surreal Numbers.

learn more… | top users | synonyms

28
votes
9answers
57k views

Maximum board position in 2048 game

A game called 2048 is making rounds on social media. I am trying to determine the maximum score attainable for this game. Let's assume WLOG that only 2s are returned (if 4s are possible the max score ...
0
votes
1answer
156 views

Combination problem

There are N advertisement boards of which M consecutive boards should have at least K advertisements. How to find number of ways in which this is possible keeping cost minimum. Eg: N=6,M=3,K=2 which ...
11
votes
3answers
450 views

Reference for combinatorial game theory.

What is a good reference material for elementary combinatorial game theory? By combinatorial game theory I mean chiefly the study of zero-sum, deterministic two-player games (perhaps even more ...
4
votes
2answers
223 views

Does a finite game that cannot be drawn imply a winning strategy exists?

The author of this page, about a simple game (Chomp) http://plus.maths.org/content/mathematical-mysteries-chomp makes the following statement: "One of the players is sure to have a winning strategy. ...
3
votes
1answer
97 views

Name for a certain “product game”

Let $G,H$ be two (combinatorial impartial) games. Consider the following new game $P$: The positions are the pairs of positions of $G$ and $H$. A move in $P$ is a move in $G$, or a move in $H$, or a ...
2
votes
2answers
2k views

Winning strategy for a matchstick game

There are $N$ matchsticks at the table. Two players play the game. Rules: (i) A player in his or her turn can pick $a$ or $b$ match sticks. (ii) The player who picks the last matchstick loses the ...
1
vote
2answers
65 views

Can we construct from $[0,\omega_1)$ a space which is strictly-Frechet with no winning strategy in $G_{np}(q,E)$?

I have asked in here a question which tured out to make no sense. I think I have found the confusion and would like to try and rephrase my question: Let $E$ be a topological space, $q \in E$. ...
18
votes
1answer
1k views

Number of moves to solve a flood-it/sock-dye game

[ Question based on the sock dye game ] [ Update: It appears that this game is better known as "Flood it" and is NP-hard. Also, "the number of moves required to flood the whole board is $\Omega(n)$ ...
16
votes
2answers
245 views

A game on a graph

Alice and Bob play a game on a complete graph ${G}$ with $2014$ vertices. They take moves in turn with Alice beginning. At each move Alice directs one undirected edge of $G$. At each move Bob chooses ...
4
votes
1answer
34 views

Optimal strategy for this Nim generalisation?

Consider the following game: There are a number of piles of stones. On each turn a player can remove as many stones he likes (at least 1) from up to $N$ piles (at least 1). It is allowed to remove a ...
7
votes
1answer
497 views

Traversing the infinite square grid

Suppose we start at $(0.5,0.5)$ in an infinite unit square grid, and our goal is to traverse every square on the board. At move $n$ one must take $a_n$ steps in one of the directions, north,south, ...
3
votes
1answer
195 views

A question about something in Conway's “On Numbers and Games”

In the book mentioned in the title, which deals with (among other things), Conway's "surreal numbers", there is a small section (pp. 37-38) where the "gaps" in the surreal number line are discussed. ...
12
votes
2answers
469 views

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 ...
3
votes
2answers
113 views

probable squares in a square cake

There is a probability density function defined on the square [0,1]x[0,1]. The pdf is finite, i.e., the cumulative density is positive only for pieces with positive area. Now Alice and Bob play a ...
2
votes
2answers
440 views

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. ...
2
votes
1answer
144 views

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 ...
1
vote
4answers
425 views

two elementary games in number theory

I solved these two problems from a programming challenge website: numgame and numgame2. These two problems are very similar. In the first one, the position is a number $n$ and each player can ...
5
votes
2answers
346 views

Why does the strategy-stealing argument for tic-tac-toe work?

On the Wikipedia page for strategy-stealing arguments, there is an example of such an argument applied to tic-tac-toe: A strategy-stealing argument for tic-tac-toe goes like this: suppose that the ...
3
votes
2answers
62 views

Are there combinatorial games of finite order different from $1$ or $2$?

Are there any combinatorial games whose order (in the usual addition of combinatorial games) is finite but neither $1$ nor $2$? Finding examples of games of order $2$ is easy (for example any ...
3
votes
1answer
64 views

Ring structure on subsets of the natural numbers

Let $$\mathcal{N}=\{\{k_1,\ldots,k_s\}:\ s>0,\ \mbox{and the}\ k_i\ \mbox{are non-negative and pairwise different integers}\}\cup\{\emptyset\}.$$ Note that there is a bijection with the naturals, ...
2
votes
1answer
129 views

Are there non-zero combinatorial games of odd order?

Are there any combinatorial games with odd order (under the usual addition of combinatorial games), apart from $0$? In Are there combinatorial games of finite order different from $1$ or $2$? I asked ...
2
votes
1answer
71 views

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$, ...
2
votes
1answer
334 views

Nim Variant (reducing by divisors)

Alice and Bob play the following game. They choose a number $N$ to play with. The rules are as follows: Alice plays first, and the two players alternate. In his/her turn, a player can subtract from ...
1
vote
1answer
29 views

Algorithm to multiply nimbers

Let $a,b$ be nimbers. Is there an efficient algorithm to calculate $a*b$, the nim-product of $a$ and $b$? The following rule seems like it could be helpful: $$ 2^{2^m} * 2^{2^n} = \begin{cases} ...
0
votes
1answer
356 views

Nim Variant (Restricted removal)

Alice and Bob play the following game : There are $N$ piles of stones with $S_i$ stones in the $i$th pile. Piles are numbered from 1 to $N$. Alice and Bob play alternately, with Alice starting. In a ...