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

learn more… | top users | synonyms

27
votes
5answers
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
2answers
98 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
0answers
95 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
1answer
373 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
1answer
106 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
0answers
154 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
1answer
191 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
0answers
267 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
0answers
185 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
0answers
135 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
0answers
213 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
1answer
334 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
0answers
133 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
3answers
723 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
2answers
285 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 ...
4
votes
0answers
110 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
1answer
116 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
1answer
245 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
1answer
493 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
0answers
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
1answer
425 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
0answers
572 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
1answer
788 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
2answers
367 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
1answer
798 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
1answer
223 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
3answers
493 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 ...
16
votes
1answer
858 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
1answer
360 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
0answers
2k 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
1answer
198 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
1answer
288 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
1answer
241 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
1answer
655 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
1answer
186 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
1answer
890 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
3answers
249 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
1answer
249 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
4answers
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
1answer
464 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
2answers
822 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
7answers
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
3answers
933 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
0answers
379 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 ...
31
votes
4answers
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
3answers
868 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 ...
0
votes
2answers
539 views

Generalized Sprague-Grundy Theorem

Hey, I know what is Sprague-Grundy theorem, but I want to know about generalized Sprague-Grundy (GSG) theorem ( which is used for games with cycles ). Apparently there seems to be very less ...
14
votes
1answer
826 views

Principal maximal ideals in Z[x]/(F)

Is there some irreducible $F \in \mathbb{Z}[x]$ such that $\mathbb{Z}[x]/(F)$ has no principal maximal ideal? Equivalently, is it possible that the $1$-dimensional integral domain $\mathbb{Z}[x]/(F)$ ...
2
votes
0answers
115 views

Open games formed by pasting together infinitely many clopen games

Throughout, I think of games and their underlying trees as the same: so a "clopen game" and a "well-founded tree" mean the same thing. Fix a sequence of clopen games $\lbrace T_i: i\in\omega\rbrace$. ...
0
votes
1answer
244 views

Equilibrium of random zero-sum game,

Hi, How to find, or at least express, the equilibrium of a zero-sum game with an $n*n$ payoff matrix (each player has $n$ strategies) and the payoff of the entry $(i,j)$ is $u(i,j)$. $u$ a random ...