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

89
votes
0answers
3k 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 ...
12
votes
0answers
371 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 ...
10
votes
0answers
325 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 ...
5
votes
0answers
178 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
62 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 ...
4
votes
0answers
40 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
61 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
82 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
167 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
109 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
32 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 ...
3
votes
0answers
54 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
53 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
65 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 ...
3
votes
0answers
695 views

How many different chess-board situations can occur?

If you play a standard chess game on a normal $8 \cdot 8$ chess board with the usual rules: How many different "board representations" can exist? Upper bound: Well, you have 16+16 = 32 chess pieces ...
2
votes
0answers
74 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
38 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
381 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 ...
2
votes
0answers
133 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
102 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
147 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
197 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
116 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
25 views

Coloring the balls

Bob and Alice are playing a game. Initially they have balls of black and white color arranged together in a line. Rules of the game are as follows: 1.They start the game by going from right to left ...
1
vote
0answers
44 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
66 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
69 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
40 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
39 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
30 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
119 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 use ...
1
vote
0answers
58 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
40 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$ ...
1
vote
0answers
110 views

More than Nim (combinatorics problem)

A two-player game is played with two piles of stones, with sizes m,n. On a player's turn, that player can remove any positive number of stones from one pile, or the same positive number of stones from ...
1
vote
0answers
192 views

S-Grundy Number

Help needed in understanding S-Grundy Number , any good tutorial. I am trying to solve Mathalon Problem 146 S-Grundy Game
0
votes
0answers
33 views

explaining the pattern

I have been given the following math puzzle: you are given a matrix that is filled by the following rule: every cell i,j is evaluated by taking the lowest non-negative number that is not present in ...
0
votes
0answers
39 views

Combinatorial approach to calculate determinant

Suppose you have set of $n*n$ matrices with entries from the set $\{1,-1\}$. Then what can be the maximum determinant which you can obtain from such type of matrices.
0
votes
0answers
11 views

Linearization bounds on 0-1 quadratic problems

What are the best linearization methods for approximating the following constrained 0-1 Quadratic problem, where $Q \in \mathbb{R}^{n\times n}$ and $k$ is an integer $1\leq k \leq n$ $$ \max ...
0
votes
0answers
7 views

Combinatorics- related to poker

In how many ways can a straight flush be dealt ,if two of the cards originally dealt must be discarded and replaced but not if all the 5 cards are clubs ?
0
votes
0answers
28 views

Game placing numbers in increasing order

Let $k\leq m\leq 100$ be positive integers. Aaron and Britney play a game on a $1\times m$ board, using $100$ paper pieces numbered from $1$ to $100$. The game has $k$ turns. In each turn, Aaron ...
0
votes
0answers
28 views

Number of ways to shuffle a cardset with fixed top 4 while ignoring the suit

I am interested in the number of possible orders in a standard 52 card deck. There are $52!$ possible orders, if I care for suit and type. If I don't care for the suit / color of the card there are ...
0
votes
0answers
42 views

countable subset of surreal games

Surreal numbers are the largest possible structure to have a complete order. Games are an extension of the Surreals which only admits a partial order. Along with being larger, smaller or equal to each ...
0
votes
0answers
35 views

Mex and Grundy Numbers explanation

I've been reading this small tutorial on Nimbers and game theory. Could someone explain why the mex rule governs the nimber of a game position? See: http://en.wikipedia.org/wiki/Mex_(mathematics) ...
0
votes
0answers
51 views

Matrix Saddle Points and Dominance

I was teaching myself about dominance relations and saddle points after a friend of mine started discussing it with me and how it can be used in games. I wanted to know how to prove a problem like ...
0
votes
0answers
92 views

Proof of Conway's “Simplicity Rule” for Surreal Numbers

A "number" in the sense of Combinatorial Game Theory is a game $G = \{ a,b,c,\dots | \; d,e,f,\dots \}$ such that $a,b,c < d,e,f$. Then our game is between the left and right options: $$ a,b,c ...
0
votes
0answers
26 views

de Bono's L-game modification

I am trying to find out if a simple modification od de Bono's L-game is still infinite if two players are perfect. Modified rule is that there no neutral pieces but, there is one piece for each player ...
0
votes
0answers
33 views

Interesting Probability Game With Uneven Return Scenarions

Let say we play a game. The game which spans the course of 5 trials. The game is as follows. You either receive 100 points or 40 points as a final payout. The only time a payout of a 100 points occurs ...
0
votes
0answers
49 views

Recursive core of coalition game

Can someone please explain the recursive core concept possibly with an example? http://arno.unimaas.nl/show.cgi?fid=5152 I don't understand how the recursion works. Thank you
0
votes
0answers
30 views

What algorithms do you know for beltway reconstruction?

I've faced the beltway reconstruction problem and I've developed a simple backtrack algorithm, what algorithms do you know for this problem? Beltway Reconstruction Problem: Assume there is a set of ...
0
votes
0answers
119 views

Mathematical reason for 2-player turn-based games

I've been reading Games, Puzzles, and Computation which analyzes games through game theory and complexity theory. The authors introduce something called "Constraint Logic" as a way of modeling games ...