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

181
votes
0answers
6k 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 ...
14
votes
0answers
454 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 ...
14
votes
0answers
433 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
0answers
180 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
0answers
89 views

Has this subset-sum game been studied?

Consider the following game: two players, Yolanda (who always goes first) and Zachary, take turns selecting (not yet chosen) numbers between $1$ and $9$. The first player who can make three of their ...
6
votes
0answers
67 views

Game, stealing edges in a graph.

I was inventing a problem for a math contest, I was really pleased with it, but then I found a mistake in my solution and have not been able to solve it. It is as follows: Alice and Bob play a game. ...
6
votes
0answers
530 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 ...
5
votes
0answers
73 views

Conway's Game OF Life maximum periods on a set x by x game board.

I have taken interest in Conway's Game of Life and want to know if you guys can help me with a mathematical problem :) That is what this website is for right? You need to be familiar with the rules ...
5
votes
0answers
56 views

Prime number building game

Players $A$ and $B$ choose digits $(0, \dots , 9)$ turn by turn and build number by concatenating the digit they chose to the end of the number. Player $A$ starts by picking the first (one-digit) ...
4
votes
0answers
564 views

What is the highest possible score in 2048 hard?

There is a variant of the popular game 2048, called 2048 hard or 2048 impossible, which automatically places each new tile in the hardest possible location. Is this variation possible to solve, and if ...
4
votes
0answers
44 views

The point-open game and $\omega$-covers

Let $X$ be a topological space. The point-open game $G_{po}(X)$ is defined as folows. It is played by two players ONE and TWO. In the n'th step $(n \in \omega)$, ONE choose a finite subset $F$ of ...
4
votes
0answers
71 views

Nimber of selective compound games

Background/Definitions. Let $\alpha,\beta$ ordinal numbers. The Hessenberg sum $\alpha \# \beta$ is defined recursively as the smallest ordinal which is $>\alpha' \# \beta$ and $> \alpha \# ...
4
votes
0answers
96 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

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, ...
4
votes
0answers
134 views

Number Theoretic Game

2 players A and B play a game. At the start of the game, $n$ positive integers (not necessarily distinct) are written on a notebook. First, player A chooses a number from the notebook and declares it ...
3
votes
0answers
89 views

News on SG values of Grundy's Game?

Is there any recent research into the Sprague-Grundy values of Grundy's game? It was calculated to $2^{35}$ integers but with no sight of recurrence. Has anyone come up with anything new to compute ...
3
votes
0answers
87 views

How many different Forsyth-Edwards Notation ranks are possible?

(This is a combinatorics question, and therefore more appropriate here than at the Chess Stack Exchange.) Background: in chess, board positions are recorded using a system called Forsyth-Edwards ...
3
votes
0answers
67 views

Terminology questions about a game where one may “save his progress” at the cost of a turn.

The game is for $p$ players who each start at square $1$. Each turn, a player can either roll an $m$-sided dice or place a marker on his current square. If he rolls $x\in\{2,\ldots, m\}$, he ...
2
votes
0answers
47 views

Candy Crush as an integer programming problem

I'm trying to model the basic version of a match-three game, where the player (has a maximum number of swaps) must swap any two adjacent gems (no diagonals) in an 8x8 grid of gems in order to match ...
2
votes
0answers
42 views

The hardest game of mahjongg

I was playing Mahjongg solitaire the other day. It got me thinking... The board has $2n$ pieces at the beginning and assuming that the game is winnable. The game would be trivial if there would be ...
2
votes
0answers
49 views

Queen moves — The Squared Chain Puzzle

Karl Scherer made the interesting Squared Chain Puzzle. Start with a $7\times7$ board, with a queen somewhere. Make a legal move with the queen, placing coins over all squares visited. For subsequent ...
2
votes
0answers
31 views

Number of connected sets intersecting a given set in $\mathbb{Z}^d$

Let $A \subset \mathbb{Z}^d$ and let $|A|$ be its cardinality. Let $F_n(A)$ be the number of connected sets of $\mathbb{Z}^d$ having cardinality $n$ and intersecting $A$ in at least one site. Assume ...
2
votes
0answers
282 views

stable marriage algorithm problem

Better of the two Suppose that in the stable marriage problem with $n$ men and $n$ women, we have found two (possibly different) stable matchings $S$ and $T$. We will show how to combine $S$ and $T$ ...
2
votes
0answers
109 views

What is the largest value one can get in game 2048 without new tiles appear

This is a simplified version of the famous game 2048. Given a 4x4 grids with some values chosen from {0, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048}. A value of 0 indicates that the position in ...
2
votes
0answers
73 views

Computation of a 3-dimensional game matrix

For natural numbers $n_1 \leq n_2 \leq n_3$ we define $\beta(n_1,n_2,n_3)$ recursively to be the smallest natural number which is not among the numbers $\beta(m_1,m_2,m_3)$, where $m_1 \leq n_1 \leq ...
2
votes
0answers
217 views

What is the optimal strategy for this 2 player game?

Let some finite array of integers is given initially. There is a number k which is initially '0'. In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]). Also, ...
2
votes
0answers
124 views

The name of a game from the 2013 Putnam

Does the following game from the 2013 Putnam have an official name? Based on my searches, it seems to have been created just for the exam. Let $n\geq 1$ be an odd integer. Alice and Bob play the ...
2
votes
0answers
240 views

Stable Marriage Problem

I would just like clarification for the following problem: Suppose $M_1$ and $M_2$ are two stable matchings between n men and n women, and we allow each woman to choose between the man she is paired ...
2
votes
0answers
284 views

What are the chances of shooting the moon in Hearts?

I'm posting this again here from boardgames.SE because it was suggested there that this is the more appropriate question to ask it. So, that said, here's my question: given a fair shuffle, that all ...
2
votes
0answers
120 views

Unavoidable structure of this kind of function:$Z\rightarrow N$.

Suppose that $f$:$Z\rightarrow N$ is a surjection and $|f^{-1}(n)|=2$ for every $n\in N$. I found that there is $n\in Z$ such that $f(n)$, $f(n+1)$, $f(n+4)$, and $f(n+5)$ differ from each other. ...
1
vote
0answers
36 views

Position games: how to fill a matrix with dominos?

Dominos of size $2 × 1$ can be placed on a $m × n$ board so as to cover two squares exactly. Two players alternate placing dominos. The first one who is unable to place a domino is the loser. I can ...
1
vote
0answers
28 views

Check an algorithm to win hex as first player guaranteed

This question has more to do with the validity of the alogirthm than help per se. I'm unsure if this works with all board setups or just this one, or if it's valid at all. I'm going to start with a ...
1
vote
0answers
76 views

Finding a Mathematical definition of a Discrete Time Game

Preface: Suppose we have a game world as depicted in the following figure: Where each of the white blocks is passable, And each of the black blocks is a wall and so impassable. Each of the Green ...
1
vote
0answers
92 views

Applications of Combinatorial Game Theory

Last semester I took a course on Game Theory over at KTH (Stockholm, Sweden), and within that course we went through both classical and combinatorial game theory. While it was very fun to study ...
1
vote
0answers
45 views

Can anyone explain this more clearly?

I'm new to CGT so i might need help but could anyone simplify this and explain it to me please- "set f ⊕ f = 0 for any f. (A nice correspondence can be made if we think back to the original game of ...
1
vote
0answers
64 views

Probabilistic Game Theory

I would appreciate help on the following problem: Problem. You just bought a new a card printer which continuously prints cards in red or blue, chosen independently and uniformly at random. You play ...
1
vote
0answers
26 views

Game Theory Rulerette, Sprague-Grundy Theorem

Here is the question: Rulerette. Suppose in the game Ruler, we are not allowed to turn over just one coin. The rules are: Turn over any consecutive set of coins with at least two coins being ...
1
vote
0answers
29 views

Multi-dimensional naughts and crosses: victory for first player?

In a $2$-dimensional checkerboard which is $2\times2$, the player going first necessarily achieves $2$ in a row. In a $3$-dimensional board which is $3\times3\times3$, a player going first using a ...
1
vote
0answers
39 views

How is Wythoff's Theorem proved?

Specifically, how does one prove the following? Suppose $(a,b)$ is not of the form $(A_n,B_n)$, where $A_n=\lfloor n \phi \rfloor$ and $B_n= \lfloor n \phi^2 \rfloor$. Then there is a move in ...
1
vote
0answers
112 views

Counting all possible legal board states in Quoridor

Ignoring pawns there are 1,375,968,129,062,134,174,771 possible ways to place 0 to 20 walls on the Quoridor board, as answered here. Ignoring walls there are 81 * 81 = 6410 ways to place the two ...
1
vote
0answers
95 views

Distribute the gold, silver and bronze

A pirate ship has 2015 treasure chests (all chests are closed). Each chest contains some amount of gold, some amount of silver and some amount of bronze. To distribute the gold, silver and bronze the ...
1
vote
0answers
94 views

Number of ways to make first move

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
1
vote
0answers
48 views

What is the optimal strategy?

There are $m+n+1$ cards numbered $1,2,\ldots m+n+1$. Participants A and B respectively get $m$ and $n$ cards. Meanwhile, they only know what they get. The remaining card is face down on the desk. ...
1
vote
0answers
61 views

How many lines needed to not lose in tetris game?

Suppose we play a tetris game with tetris be given randomly. Is there exists a number of lines that we can play infinitely, i.e. do not lose the game?
1
vote
0answers
39 views

Does any $\omega$-cover in which $X \in L(\mathcal U)$ is also a $\gamma$-cover?

As a continuation to this question: An $\omega$-cover, is an open cover $\mathcal U$ of $X$, such that, $X \notin \mathcal U$, and for every finite set $F \subset X$, there exists an open set $U ...
1
vote
0answers
316 views

Proof that $12$ in a row tic-tac-toe is a tie game?

How can be it proved that tic-tac-toe on an infinite grid (winning with $12$ in a row, a column or a diagonal) can always end in a tie (with optimal strategies of both players)? There is a hint: to ...
1
vote
0answers
67 views

Any known strategies for toads and frogs?

Are there any heuristic strategic for playing Toads and Frogs known? I reckon the optimal playthrough may be hard to achieve due to the game being NP-hard but at least something that regularly ...
1
vote
0answers
46 views

What are the available libraries or programs for finding extremes of a function with no symbolic definition?

In my current mathematical inquiry, I would like to gain insight on behaviour of a $d$-dimensional continuous function by locating its maximum over the hyperplane $\sum_{i=1}^d x_i = 1$ for $x_i$ ...
0
votes
0answers
29 views

Measure of Connectivity on a Chessboard

I'm programming a boardgame...game. The basic idea of it is there are two players (call them $X$ and $Y$) that are trying to trying to build a wall connecting the North and South, and East and West ...
0
votes
0answers
11 views

Is there an extension for sign expansion for any games?

A surreal number can be written as a sequence of $+$ and $-$, called the sign expansion. Is there something similar for any combinatorial games, supposedly with $+$, $-$ and some more symbols? If I ...