# Questions tagged [combinatorial-game-theory]

Two-player turn-based perfect-information games, surreal numbers, impartial games and Sprague-Grundy theory, partizan games

**1**

vote

**0**answers

154 views

### A universal framework for Game Theory?

Ever since the seminal work of Von Neumann and Morgestern Game Theory has grown into a formidable sector of pure and applied mathematics.
There are all sorts of games: perfect information, ...

**14**

votes

**0**answers

709 views

### A Combinatorial Game: the Snake and the Hunter

The Snake and the Hunter is a game for two players who play in two rounds interchanging the roles of snake and hunter. The game is played in a rectangular grid of points, say $6 \times 6$. In both ...

**4**

votes

**0**answers

135 views

### Combinatorial fairness property in division of goods

Given $n$ agents, and $m$ items where $v_i(g) \geq 0$ is the value of item $g$ for agent $i$, does there always exist a partition $A_1, ..., A_n$ of the $m$ items into $n$ sets s.t. for all $i, j \in \...

**1**

vote

**0**answers

50 views

### Characteristics for impartial games with the same nimber? [closed]

I am working on a specific impartial game on graphs. It turns out that graphs that are not isomorphic may have the same nimber. My goal is to characterize graphs with the same nimber. I simply wonder ...

**-1**

votes

**0**answers

62 views

### Factorization (separation?) of n-player game into p-player game and (n-p)-player game

When is an n-player game factorizable (separable?) into a p-player game and
an (n-p)-player game?
Apologies if this is known among game theorists already - but it leads to further questions, ...

**6**

votes

**1**answer

463 views

### A different equivalence relation on partizan combinatorial games

The following definitions are fairly standard, but reworded in a way that will be more appropriate for my question (so what follows is fairly long, but should be easy to read for the experts and might ...

**10**

votes

**1**answer

763 views

### What does “game theory” cover and how should it be called?

There seems to be a huge discrepancy in what people refer to when they speak of "game theory". I tend to think of it as including, among other things:
Combinatorial game theory dealing with certain ...

**6**

votes

**2**answers

460 views

### Determinacy of (infinite, possibly loopy) combinatorial games

I am looking for references and hopefully enlightening proofs of the following statement(s) concerning the determinacy of not-necessarily-well-founded (i.e., possibly infinite, possibly loopy) ...

**0**

votes

**1**answer

138 views

### Is the linear production game a convex game?

In cooperative game theory, the linear production game (LPG) is defined by letting the characteristic function have the form of a linear programming problem.
Does anyone know if the LPG is a convex ...

**30**

votes

**5**answers

2k views

### Can one make high-level proofs about chess positions?

I realize this question is risky (as the title and the tags indicate), but hopefully I can make it acceptable. If not, and the question cannot be salvaged, I'm sorry and ready to delete it or accept ...

**3**

votes

**2**answers

220 views

### “L-Shaped Positions” in Chomp

In my earlier question I asked about the winning move in Ordinal Chomp played on a $3 \times 3 \times \omega$ board. So far the problem has seemed intractable. Therefore, I now consider Ordinal chomp ...

**5**

votes

**0**answers

188 views

### A winning move for the first player in $3 \times 3 \times \omega$ Ordinal Chomp

I have been trying to analyse the game of Ordinal Chomp played on a $3 \times 3 \times \omega$ board. The rules can be found in the Wikipedia article, briefly:
This game is played between two players ...

**3**

votes

**1**answer

425 views

### Game on a string

I am interested if one can design an efficient (polynomial) algorithm telling whether the first player has a winning strategy for a game described below.
The board is a string consisting of only ...

**3**

votes

**1**answer

340 views

### Misere nim variant

Is there a name (and strategy) for this nim variant?
There are $n$ lists of objects, say $L_1,\ldots,L_n$ where $L_i = \{a_{i,1},a_{i,2},\ldots,a_{i,n_i}\}$. Players take turns choosing a list and ...

**15**

votes

**1**answer

442 views

### Is the game Hanabi NEXPTIME-complete?

The game Hanabi is a cooperative, hidden-information game. You can read the rules elsewhere, but broadly speaking the players are attempting to cooperatively build a fireworks display by playing cards ...

**3**

votes

**1**answer

216 views

### Minimal Birthdays

In combinatorial game theory: The birthday of a game is defined recursively as 1 plus the maximal birthday of its options, with the zero game having birthday 0.
Suppose we define the quasi-birthday ...

**8**

votes

**0**answers

449 views

### A Banach-Tarski game

This is partially inspired by the question https://math.stackexchange.com/questions/1383397/cutting-a-banach-tarski-cake, which I find intriguing if unclearly written.
A paradoxical family of subsets ...

**5**

votes

**0**answers

209 views

### Topological Subset Take-Away

David Gale's subset take-away game is a game where two players A and B play with a finite set $S$. Players alternately choose proper nonempty subsets of $S$ such that if a subset is chosen, then none ...

**4**

votes

**1**answer

265 views

### Lights Out game over GF(p)

On Jaap's Puzzle Page
http:// www.jaapsch.net/puzzles/lomath.htm#domtilings
Theorem 7 says:
If standard Lights Out is played on a m x n grid-like board, ...

**3**

votes

**0**answers

405 views

### Nimbers and Surreal Numbers [closed]

I have been researching Combinatorial Game Theory. One common theme is the assignment of values to games in order to classify the game as a win for a specific player. One such way is class of surreal ...

**5**

votes

**1**answer

808 views

### Is it possible to evaluate Connect 4 positions with Combinatorial Game Theory?

The surreal numbers in Combinatorial Game Theory only work for certain classes of games (e.g. they must satisfy normal play convention). This rules out even reasonable games with fairly well-...

**5**

votes

**0**answers

198 views

### Generalization of Sprague-Grundy Theorem

In my research on Combinatorial Game Theory, I used a certain theorem that is essentially a generalization of the Sprague-Grundy theorem. Because the result hinges too much on the work of others to be ...

**16**

votes

**3**answers

1k views

### Why does the bitxor function appear in Nim?

I am conducting research in Combinatorial Game Theory (CGT). Although I have done a considerable amount of reading, I do not completely understand why the bit-xor function also known as the nim-sum ...

**6**

votes

**2**answers

384 views

### A (possibly boring) Voronoi Game

The board for this game is a compact convex region $\cal C$ of $\mathbb{R}^2$.
Below I illustrate with $\cal C$ an equilateral triangle.
Two players, $A$ and $B$, alternate turns.
At each turn they ...

**5**

votes

**0**answers

174 views

### Analysis of Nim-Like Game? [closed]

There are a finite number of heaps, each with a finite number of counters. Two players take turns; on each move, they may remove exactly one counter from any heap, and also, if the heap is of size $n$,...

**6**

votes

**1**answer

212 views

### Anything known about the Grundy Ordinal of Sylver's Coinage

Sylver's coinage is an example of an unbounded finite (if slightly modified) combinatorial impartial game. Quoth wikipedia:
The two players take turns naming positive integers that are not the
...

**8**

votes

**1**answer

346 views

### Yet another Erdős–Szekeres game

Given $n$. Two players in turn write different real numbers $x_1,x_2,x_3,\dots$
The player after whose turn there is a monotone subsequence of length $n$ loses.
I guess that the question 'who wins' ...

**9**

votes

**1**answer

570 views

### Erdős-Szekeres game

Given $n$. Two players in turn mark points on the plane. No three may be collinear, no $n$ may form a convex $n$-gon. The player who does not have legal move loses. Who has a winning strategy?

**2**

votes

**0**answers

92 views

### On subset of Deterministic games

Denote strings $u,v$ from $\{0,1\}^n$.
Denote concatenated pair $[uv]$.
Denote
$$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$
collection of pairs with Hamming distance $1$ from $[uv]$ string ...

**0**

votes

**1**answer

477 views

### Is it possible to create an infinite sequence in which no subsequence is repeated 3 times in a row?

In Chess, there is the Threefold Repetition rule where if a sequence of moves is repeated 3 times in a row, either player can claim a draw.
Say two players wanted to play a legal, infinite game of ...

**16**

votes

**0**answers

831 views

### Are the moves/rules of standard chess delicately balanced?

(While the world chess championship is in progress in Sochi...)
Is there mathematical evidence that standard chess is somehow
...

**18**

votes

**1**answer

949 views

### Removing pawns - the game

Here is a simple game I've invented (if the idea is not fresh, then please let me know):
The game is played on a board.
The board has some (finite) number of lines drawn on it.
A pawn is placed on ...

**10**

votes

**2**answers

483 views

### Nim and the Sierpinski Gasket

(I discovered this in high school, sent it off to a journal, never heard back, and forgot about it. I've never found anyone else who appeared to know about it; the combinatorial game theorists I've ...

**0**

votes

**1**answer

1k views

### Maximal score for the 2048 game [duplicate]

t's been weeks (months?) since the 2048 game--by Gabriele Cirulli--took Internet by storm. I have an explicit integer $X$ which is greater or equal than any score of this game. Possibly my $X$ is the ...

**5**

votes

**1**answer

246 views

### Duration and critical groups order in sandpile models and chip firing games

The famous chip firing game (which is closely related to sandpile models) goes like this:
Place chips at the vertices of a graph. REPEATEDLY: If a vertex $v$ of
degree $d_{v}$ has at least $d_{v}...

**7**

votes

**3**answers

622 views

### Decidability of the winning-position problem in an infinity chess with a finite number of short-range pieces only

Definitions
Long-range pieces: queens, rooks, bishops.
Short-range pieces: pawns, knights, kings.
We can extend the definition of short-range pieces to include also fairy pieces like: Berolina ...

**18**

votes

**2**answers

1k views

### Determine or estimate the number of maximal triangle-free graphs on $n$ vertices

Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
http://www.math.ucsd.edu/~erdosproblems/erdos/...

**4**

votes

**1**answer

683 views

### Nash Equilibrium in general graphical game

Any one has any ideas about how to compute the Nash Equilibrium in general graphical game? Especially, when the graph structure is not a tree.

**3**

votes

**0**answers

4k views

### How many combinations does Android pattern have? [closed]

Rules-
1) At-least 4 and at-max 9 dots must be connected.
2) There can be no jumps
3) Once a dot is crossed, you can jump over it.

**1**

vote

**1**answer

411 views

### The original proof of Wythoff's game

I am looking for the original proof of Wythoff's game. Wythoff provided the first full analysis of this game in "A modication of the game of nim, Nieuw Archief door Wiskunde, 199{202, 1907". However, ...

**2**

votes

**1**answer

340 views

### efficient arithmetic with (short) Conway games?

We consider "games" in the sense of ONAG. Conway's definition of a game $G$ as a pair $G = \{L \mid R \}$ of sets of games, together with the definitions of inequality and the arithmetic operations (...

**9**

votes

**1**answer

319 views

### Infinite-dimensional hex

Suppose $n$ players take turns selecting vertices of the grid $[k]^n = \left\{0, 1, 2, \ldots, k-1\right\}^n$. Each player is assigned a pair of opposite faces of the grid, and wins the game if they ...

**20**

votes

**1**answer

1k views

### A Ramsey avoidance game

Consider the following game: Given $K_n$ the complete graph on $n$ vertices, two players take turns coloring its edges. Initially no edges are colored. At his turn a player can color a prevoiusly not ...

**0**

votes

**1**answer

214 views

### What is a description of winning strategies in this tile game?

I'm hoping someone can help me figure out how to describe all winning strategies for "Player 1" in the following game:
Consider a board with $n$ tiles arranged in a row. Player 1 and Player 2 each ...

**0**

votes

**1**answer

2k views

### Calculate the probability of winning for a selected tic-tac-toe player

I am not a mathematician, I am a programmer. Sorry, if formulation of the problem is inexact.
I want to calculate the probability of winning for a selected tic-tac-toe player.
I have a directed graph ...

**2**

votes

**3**answers

477 views

### Simulating Mixed Nash Equilibria

I have a $N$ person game where each person has a set of $M$ discrete strategies. I know from the theory that at least one mixed strategy Nash Equilibrium exists.
Can someone please tell me how do I ...

**0**

votes

**1**answer

355 views

### Infinite board games: sentences about

As a unified approach if we have an ( read any) infinite board game described as $\mathcal{G}$ using a particular axiom set A..
can a sentence be devised in A which automatically answers the basic ...

**4**

votes

**5**answers

5k views

### How many possible ways are there to win in Quoridor? [closed]

Quoridor is a board game in which the objective is to move a piece across to the other side. A player can put up fences to block other players from advancing forward. How many possible ways are there ...

**11**

votes

**1**answer

841 views

### The infinite X in Conway's game of life

In Conway's game of life, take the initial position to be two infinite diagonal lines of live cells, with a single cell in common. Does this thing converge to a stable configuration? I.e., is the ...

**25**

votes

**2**answers

1k views

### Is there any superstable configuration in the game of life?

This question spins off of Gil Kalai's recent question on Conway's game of life for a random initial configuration.
There are numerous configurations in the game of life that are known to be stable-...