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

learn more… | top users | synonyms

6
votes
0answers
210 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
127 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
102 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
162 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
249 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
103 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 ...
8
votes
3answers
668 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
242 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
95 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
103 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
236 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
485 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
85 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
399 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 ...
14
votes
0answers
492 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
760 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
341 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
731 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
213 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
450 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
752 views

Paul Erdős: 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
288 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
174 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
274 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
236 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
628 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
173 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
746 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
224 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
217 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 ...
1
vote
4answers
3k 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
445 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
766 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 ...
38
votes
7answers
3k 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
826 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
365 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 ...
30
votes
4answers
3k 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
703 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
447 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
802 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
112 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
238 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 ...
1
vote
0answers
120 views

What is known about infinite diminished disjunctive compounds of loopfree partizan combinatorial games?

Background Basic theories of loopy (normal-play) games which may go on forever under the usual disjunctive sum (the game ends when there are no moves available for you in any component on your turn) ...
21
votes
1answer
737 views

Sane bound on number of moves for Maker-Breaker game on $\mathbb R^2$ for $\{0,1,2,3,4\}$

The description below comes from József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 ...
0
votes
1answer
278 views

a question on game of chess [closed]

In the game of chess,it is a proven fact that either of the three conditions hold: 1)white has a winning strategy 2) black has a winning strategy or 3)either of them can at least force a draw. It is ...
0
votes
0answers
601 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
3
votes
3answers
720 views

Generalized tic-tac-toe

We begin with $2n+1$ cards, each with a distinct number from $-n$ to $+n$ on it, face up in between the two players of the game. The players take turns selecting a card and keeping it. The first ...
5
votes
1answer
382 views

Resources-Aware Combinatorial Game Theory

First of all, I preemptively apologize if my question happens to be naive, I am no expert of CGT (or general game theory, for that matter). Now the question: **is there such a thing as the study of ...
3
votes
2answers
628 views

The game of removing two vertices in a graph

Consider the following impartial combinatorial game played with finite graphs: A move removes two adjacent vertices; and of course all edges connected with them. The game then continues with the new ...