**3**

votes

**0**answers

129 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 ...

**7**

votes

**1**answer

274 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 ...

**3**

votes

**2**answers

324 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

100 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 ...

**27**

votes

**5**answers

1k 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

102 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 ...

**4**

votes

**0**answers

101 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 ...

**3**

votes

**1**answer

378 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

129 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 ...

**12**

votes

**0**answers

182 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

196 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

275 views

### A Banach-Tarski game

This is partially inspired by the question http://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

190 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 ...

**2**

votes

**0**answers

142 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, ...

**1**

vote

**0**answers

236 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

365 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 ...

**4**

votes

**0**answers

142 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 ...

**11**

votes

**3**answers

753 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

303 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

121 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 ...

**5**

votes

**1**answer

122 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

250 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' ...

**8**

votes

**1**answer

500 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

88 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 ...

**1**

vote

**1**answer

433 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 ...

**15**

votes

**0**answers

584 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
...

**16**

votes

**1**answer

794 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

381 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

850 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

229 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 ...

**7**

votes

**3**answers

507 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 ...

**17**

votes

**2**answers

951 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".
...

**4**

votes

**1**answer

386 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

3k 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

218 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

297 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 ...

**7**

votes

**1**answer

242 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 ...

**17**

votes

**1**answer

667 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

188 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

995 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

261 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 ...

**1**

vote

**1**answer

253 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

**4**answers

4k views

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

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 ...

**9**

votes

**1**answer

481 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 ...

**23**

votes

**2**answers

852 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 ...

**39**

votes

**7**answers

4k views

### Conway's game of life for random initial position

What is the behavior of Conway's game of life when the initial position is random? -- We can ask this question on an infinite grid or on an $n$ by $n$ table (planar or on a torus). Specifically ...

**8**

votes

**3**answers

980 views

### Mathematical model for Hanoi Towers

The strategy for the Hanoi Tower puzzle is quite simple. It is based on parity only. In an $n$-pieces puzzle, $2^n-1$ moves are sufficient to carry the whole pile from one pole to another one. My ...

**5**

votes

**0**answers

393 views

### Number of Configurations in the optimal Hanoi tower

There is a unique strategy how to move $n$ disks from the first rod to the second optimally and it takes $2^n-1$ steps, solution is obtained by simple recursion. I am interested into the following ...

**38**

votes

**4**answers

4k views

### Verifying the correctness of a Sudoku solution

A Sudoku is solved correctly, if all columns, all rows and all 9 subsquares are filled with the numbers 1 to 9 without repetition. Hence, in order to verify if a (correct) solution is correct, one has ...

**3**

votes

**3**answers

981 views

### Motivation and Intuition for Sprague-Grundy Theorem

I have read about Sprague Grundy Theorem and understand the proof of its correctness. However, I am unable to see the motivation behind the definitions. How do Sprague and Grundy know that they should ...