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

135
votes
0answers
4k 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 ...
32
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 ...
32
votes
9answers
70k 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 ...
31
votes
3answers
780 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 ...
30
votes
1answer
710 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 ...
24
votes
2answers
882 views

The expected outcome of a random game of chess?

Imagine a game of chess where both players generate a list of legal moves and pick one uniformly at random. Q: What is the expected outcome for white? 1 point for black checkmated, 0.5 for a ...
18
votes
2answers
397 views

Game involving points on $[0,1]$

You're given a list of $22$ points in $[0,1]$ (not necessarily distinct), and you're asked to select, at every iteration, $2$ points to be substituted by their midpoint. After $20$ iteration, you ...
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)$ ...
17
votes
2answers
502 views

Is it true that we can get zero for all $(x,y,z)\in\mathbb{N}^3$?

There are three distinct positive integers $x$, $y$, and $z$. We can choose two numbers $a,b\in\{x,y,z\}$, where $b\leq a$, then replace $b$ by $2b$ and replace $a$ by $a-b$. Is it true that there ...
17
votes
2answers
297 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 ...
15
votes
3answers
4k 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: ...
15
votes
3answers
692 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 ...
15
votes
1answer
557 views

How many possible board states in 2048?

I recently found out about the famous 2048 game. For those of you who don't know how it works, it consists on a 4x4 board on where tiles which are powers of 2 are placed. On every turn, you "swipe" ...
14
votes
2answers
248 views

Game to maintain distinct number of balls in glasses

There are $n$ glasses, containing $n+1,n+2,\ldots,2n$ balls, respectively. Two players $A$ and $B$ play a game, alternately taking turns with $A$ going first. In each move, the player must choose some ...
14
votes
4answers
224 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
646 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
475 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 ...
12
votes
2answers
754 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 ...
12
votes
3answers
146 views

Game on simple finite graphs

Consider the following game on graphs (no multiple edges, but graphs can be disconnected). Players A and B alternate picking a vertex. After picking a vertex, a number is assigned to that vertex such ...
12
votes
0answers
411 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 ...
11
votes
0answers
385 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 ...
10
votes
2answers
550 views

Prime Numbers and a Two-Player Game

In this question, $\mathbb{N}_0$ is the set of all nonnegative integers. The notation $\mathbb{N}$ is reserved for the set of all positive integers. Alex and Beth are playing the following game. ...
10
votes
1answer
317 views

Bidding Tic Tac Toe

In regular tic tac toe, both the players get alternate chances. This is a variant of that. Player $A$ has $\$x$ amount and player $B$ has $\$y$ amount as initial balance. Assume that $y>x$. Both ...
10
votes
2answers
591 views

Breaking chocolate bars game

About two weeks ago, a friend of mine taught me the following game without his knowing the answer. It may be famous, but I haven't known it. There are $N\ (\in\mathbb N)$ chocolate bars composed of ...
10
votes
1answer
869 views

Solving Chess - alternatives to brute force

It is well known that solving Chess is practically impossible using brute force methods. I'm interested to know if there have been any serious attempts using alternate methods. What theory and ...
10
votes
1answer
223 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
4answers
533 views

Big List of examples of recreational finite unbounded games

What are some examples of mathematical games that can take an unbounded amount of time (a.k.a. there are starting positions such that for any number $n$, there is a line of play taking $>n$ times) ...
9
votes
1answer
262 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
2answers
359 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
493 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
4answers
431 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. ...
8
votes
2answers
868 views

Converting a Gomoku winning strategy from a small board to a winning strategy on a larger board

Gomoku is the game where Black and White take turns placing stones of their own color, and the winner is the player who first gets five of their own stones in a row. Black moves first. In Gomoku on ...
8
votes
1answer
97 views

Game replacing two numbers by mean

Alicia and Bart plays a game. Alicia first writes $100$ real numbers on the board. After that they move alternately; Bart goes first. In every move, the player chooses two numbers, erases them, and ...
8
votes
1answer
153 views

Wizard against two dwarfs: guess the whole function

An evil wizard plays the following game with two dwarfs $A$ and $B$: he thinks of a function $f:\mathbb{R}\to\mathbb{R}$ (which is not required to have any regularity properties, such as ...
8
votes
0answers
125 views

NIM with multiple winning final positions

I've been looking at a variant of NIM. You can skip this bit where I'll describe NIM as usually described: There's a starting position with some number of piles of counters and two players ...
7
votes
3answers
2k 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 ...
7
votes
3answers
361 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, ...
7
votes
2answers
245 views

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 ...
7
votes
2answers
302 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
165 views

How can a Devil catch a Fool in the Angel and Devils game?

The Angel and Devils game (http://en.wikipedia.org/wiki/Angel_problem) is a two-player game, played on an infinite chessboard (i.e. the integer coordinates of $\mathbb{R}^2$). One player is the angel, ...
7
votes
1answer
537 views

Optimal Tic Tac Toe algorithm without lookahead

Is there any algorithm for tic tac toe that does not rely on a lookahead algorithm that is perfect for any sized boards? Edit: For boards larger than $3 \times 3$, we have to find the best move for ...
7
votes
1answer
138 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
549 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
1k views

John Nash's Hex proof

I am reading a book on Combinatorial Game Theory that describes a proof by John Nash that Hex is a 'first player' win, but I find the proof very confusing. This proof uses a strategy-stealing ...
6
votes
6answers
553 views

Brain teaser Strategic choice… [closed]

$X$ and $Y$ are playing a game. There are $11$ coins on the table and each player must pick up at least $1$ coin, but not more than $5$. The person picking up the last coin loses. $X$ starts. How many ...
6
votes
4answers
356 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
6
votes
1answer
924 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
530 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
217 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 ...
6
votes
1answer
735 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 ...