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

47
votes
0answers
1k views

The Ring Game on $K[x,y,z]$

I recently read about the Ring Game on Mathoverflow, and have been trying to determine winning strategies for each player on various rings. The game has two players and begins with a commutative ...
30
votes
1answer
600 views

A 20+ year old combinatorial problem - the cookie game

Learned about this not too long after the time of the original problem publication through a classmate who visited MIT one summer. http://faculty.uml.edu/jpropp/cookie2.pdf The problem goes as ...
26
votes
3answers
584 views

Three against the devil: a combinatorial game

A team of three sinners plays a game against the devil. They confer on strategy beforehand; then they go into three separate rooms, and there is no more communication between them. The play in each ...
23
votes
3answers
1k views

Guaranteed Checkmate with Rooks in High-Dimensional Chess

Given an infinite (in all directions), $n$-dimensional chess board $\mathbb{Z^n}$, and a black king. What is the minimum number of white rooks necessary that can guarantee a checkmate in a finite ...
18
votes
8answers
7k 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 ...
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)$ ...
14
votes
3answers
3k views

Average Scrabble graph structure: diameter?

Tonight a game of Scrabble ended in what I consider a very unusual graph structure, unlike this generic web image, which seems more typical: ...
13
votes
4answers
178 views

perfect play in 1-dimensional Minesweeper

In 1-dimensional Minesweeper with a known number of mines (that are distributed uniformly), is there a known somewhat-simple strategy for perfect play? When there are n cells and [0 or n-1 ...
12
votes
2answers
423 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 ...
12
votes
2answers
292 views

Prime one heap Nim

I have been working on an interesting problem my lecturer mentioned recently. Prime Nim is a variant of the Nim game where you have a single pile with an arbitrary number $n\in \Bbb N+\{0\}$ of ...
11
votes
1answer
222 views

Determining the number of valid TicTacToe board states in terms of board dimension

I am attempting to find a closed form equation in terms of $n$, for the number of valid Tic-Tac-Toe board states (ignoring symmetry), where the board has dimension $n \times n ,\; 0 \lt n,\;n \in \Bbb ...
10
votes
3answers
344 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 ...
10
votes
0answers
282 views

Analyzing a class of vertex-deletion games

As part of the discussion on this question (Permutation Game Redux), a simple vertex-deletion game was proposed. The game is very simple. Disconnect. Players alternately remove vertices from a ...
9
votes
1answer
224 views

Strategy-stealing argument in generalization of positional game?

Suppose we have a set $\mathcal{F}$ and a family, $\mathcal{W}$, of non-empty subsets of $\mathcal{F}$. Alice and Bob are going to play a game using this data. Play proceeds with Alice and Bob ...
9
votes
1answer
200 views

permutation search game

Arrange the natural numbers $1$ through $n$ in a random order (the order is unknown and has a uniform distribution). Now make a sequence of guesses as to which number is in which slot, one number and ...
9
votes
2answers
309 views

Number of cycles in a grid such that each cycle traverse all the lines

Definition: An edge-component is a sequence of some consecutive collinear-segments. Consider an $n \times n$ grid-like arrangement of $2n$ lines. Is there any idea about the number of simple cycles ...
8
votes
4answers
210 views

Modify the rules of Gomoku (Five-in-a-row) or Connect Four type games to enforce the fairness among players

One colleague and me were discussing this problem during lunch today, and I did a little bit digging for several hours after returning to my office. Fact: For an $(m,n,k)$-game, there does not exist ...
8
votes
0answers
369 views

Irreversible chess [closed]

Suppose we play a chess-variant, where any finite number of pieces are allowed, and the board is as large as we wish, but only two kings in total. And there is no 50 move-rule, no castling and no ...
7
votes
2answers
217 views

A Nim-like game with conditions and strategies

The game: Given $S = \{ a_1,..., a_n \}$ of positive integers ($n \ge 2$). The game is played by two people. At each of their turns, the player chooses two different non-zero numbers and subtracts ...
7
votes
1answer
100 views

In what way is combinatorial game theory connected to the rest of mathematics?

Since my University library lists Conway's "Winning ways for your mathematical plays in the section "recreational mathematics" alongside books on origami and puzzles, I wondered to what extent game ...
7
votes
1answer
464 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, ...
6
votes
2answers
819 views

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 ...
6
votes
1answer
548 views

Stone picking puzzle

Two players are playing a stone picking game. The players pick a stone from two pile of stone in turn. One can choose to pick any number of stones from either pile, or pick the same number of stone ...
6
votes
3answers
266 views

Splitting Stacks Nim

A game is played with two players and an initial stack of $n$ pennies ($n\geq 3$). The players take turns choosing one of the stacks of pennies on the table and splitting it into two stacks. When a ...
6
votes
1answer
642 views

Math and Logic of Infinite Chess

Hello could you help me in this... Two players (White and Black) are playing on an infinite chess board (extending infinitely in all directions). First, White places a certain number of queens (and ...
5
votes
3answers
223 views

Integral of a function defined in the set of Surreal Numbers

Given ${\{C}\}\ $ the set of all the $Surreal\ numbers$, is it possible to define the integral: $$\int_a^b{dxf(x)}$$where $$a\in{\{C}\},b\in{\{C}\},x\in{\{C}\}$$ Thanks
5
votes
2answers
116 views

clearing coins from a grid

There is two-dimensional grid with integer coordinates. We can do some moves by coins. If the coin is in point $(x,y)$ and point $(x+1,y)$ and $(x,y+1)$ are free from coins, we can remove coin from ...
5
votes
2answers
342 views

Notation for surreal numbers

On the sound of sounding ridiculous, but in the line of "There are no stupid quetsions": Is there a way to express $\omega_1$ (and in general $\omega_k$ with $k >= 1$ as a Conway game (that is ...
5
votes
3answers
212 views

Why are the surreals considered “recreational” mathematics?

One of my college math professors once remarked to me that it was interesting that John Conway's two "biggest" contributions to math were both recreational: the Game of Life and the Surreals. No one, ...
5
votes
2answers
210 views

Nim addition- binary addition without carrying

A nim addition table is essentially created by putting, in any cell, the smallest number not to the left of the cell and not above that cell in its column. However, I know for a fact that nim addition ...
5
votes
1answer
82 views

Which of the players will first draw a triangle?

6 vertices are given. No edges are given at first. Two players play the following game: the first player draws one black edge. Then the second player draws one green edge. Then the first player draws ...
5
votes
2answers
177 views

A puzzle on game theory

Bob and Alice are playing a game. They will start with an integer $n$. Alice goes first, in each turn, a player can choose an integer between 1 and 13 and that number is to be subtracted from $n$. ...
5
votes
1answer
167 views

Stone games again

Two players are playing a stone-picking game. There are some piles of stones. The number of stones in each pile is given. Every player takes action in turns as following rules: The one in his turn ...
5
votes
1answer
183 views

Motivation for the Sprague-Grundy theorem

The Sprague-Grundy theorem states that every impartial combinatorial game under the normal play convention is equivalent to a (unique) nimber. What does the equivalence relation thus defined tells us ...
4
votes
3answers
138 views

Consider a card game-parity

Consider a card game where the deck consists of 63 distinct cards. The deck is created in the following manner: each card consists of some number of symbols, where no two symbols are the same. There ...
4
votes
2answers
252 views

pseudo numbers and surreal numbers

A surreal number $\{x_L\|x_R\} \in No$ is a number when for all $\xi\in x_L$ and all $\eta \in x_R$ we have $\eta > \xi$. All the things $\{x_L\|x_R\}$ which are not of that form are called ...
4
votes
4answers
118 views

Infinite Chomp is a finite game?

Regard the $(\omega \times \omega)$ version of Chomp. It is stated here that the version of chomp on an infinite chocolate bar is in fact a finite game. I am confused by this statement. Isn't it ...
4
votes
2answers
279 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 ...
4
votes
2answers
147 views

Counting board states in a game?

I'd like to count the number of board states possible in the game Pentago. It's similar to tic-tac-toe, only the object is it get 5 in a row on a 6x6 board. I've created a strong AI for the game, ...
4
votes
1answer
90 views

A game of Chess - Ideal Solution

I am a student of physics. I have learnt some basic group theory, and I am wondering if there is any ideal solution for a given Chess game (like solving Rubik's cube). I know the no. of permutations ...
4
votes
1answer
77 views

Analysis of “Dungeon Raid”

The computer game Dungeon Raid is quite complicated, but for our purposes we can consider the following simplified version. The player has a current health $\def\hcur{h}\hcur$ and a maximum health ...
4
votes
1answer
33 views

A game problem- double or increment by 1

Its a two player game. Initially $P=1$, and there is some fixed integer $Q>1$. A valid move consists of either increasing $P$ by $1$ or doubling it iff on doing so $P$ does NOT exceed $Q$.The ...
4
votes
0answers
111 views

Chat Noir solvable?

There is a relatively simple flash game that I enjoy playing -- http://www.gamedesign.jp/flash/chatnoir/chatnoir.html is one version of it, though I've found many -- and it centers around trying to ...
4
votes
0answers
73 views

Linear Independence Game

Suppose you have a set $X$ of vectors in $\mathbb{F}_2^n$, with $|X| \ge n+1$, and consider the following game. On their turn, each player (2 player game) chooses from $X$ one vector and sets it aside ...
4
votes
0answers
203 views

“Infinito”, a combinatorial game with infinite width game-tree

I recently designed a combinatorial game (sequential game of perfect information) with an infinite branching factor, that is it has a game-tree of infinite width. I'm wondering how is it possible to ...
4
votes
0answers
144 views

Efficiently count possible nim-like moves

Consider $n$ piles of coins, with pile $i$ having $a_i$ coins. A valid move is to remove zero or more coins from each of the piles, with the constraint that atleast one pile should remain unchanged, ...
3
votes
5answers
221 views

Don't be Greedier

Consider the following two-player game, Don't be Greedier, that involves players taking alternate turns removing pebbles from one pile of pebbles, subject to the following rules: (1) The player to ...
3
votes
2answers
346 views

Chess Board and Knights

I can't solve this question. anyone knows how I must solve? You have a 6x3 chess board. How many forms exist to put a Knight in a square and with valid moviments pass in all squares but only one time ...
3
votes
2answers
111 views

Game involving tiling a 1 by n board with 1 x 2 tiles?

Consider a $1$ by $n$ tiled rectangle. You want to play a game with one opponent in which you place $1$ by $2$ "dominoes" on this rectangle. The player who places the last domino wins. Which player ...
3
votes
2answers
3k views

average number of moves needed to complete a game of FreeCell

Sometimes finishing a game of FreeCell takes me 10 minutes, other times just one minute. I know that all but one of the FreeCell deals in windows can be won, but I'm not sure if they are random or ...