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

22
votes
8answers
48k 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
151 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
409 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
206 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
94 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)$ ...
15
votes
2answers
232 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 ...
7
votes
1answer
483 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
174 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
447 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 ...
2
votes
2answers
415 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
133 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 ...
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
59 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
128 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
69 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
316 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 ...
0
votes
1answer
347 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 ...