The combinatorial-game-theory tag has no wiki summary.

**7**

votes

**3**answers

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

**15**

votes

**1**answer

549 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

**1**answer

123 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

258 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

123 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

223 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

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

**16**

votes

**1**answer

456 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

155 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

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

**1**

vote

**3**answers

181 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

187 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

**4**answers

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

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

**24**

votes

**2**answers

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

**37**

votes

**7**answers

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

**3**answers

578 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

324 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

**4**answers

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

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

**-1**

votes

**2**answers

257 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

**1**answer

700 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

**0**answers

104 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

**1**answer

186 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

**0**answers

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

**20**

votes

**1**answer

632 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

**1**answer

248 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

**0**answers

394 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

**3**answers

653 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

**1**answer

347 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

**2**answers

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

**10**

votes

**1**answer

617 views

### Sliding blocks puzzle

Consider a 'game' played on a subset $S$ of an $n^2$ square grid as follows. There are 3 types of pieces, each occupying a square of $S$, 1 green, some red and the rest are blue, a move consists of ...

**2**

votes

**2**answers

378 views

**2**

votes

**3**answers

837 views

### Motivation for the Sprague-Grundy theorem

The Sprague-Grundy theorem states that every impartial combinatorial game under the normal play convention is equivalent to a (unique) nimber.
What does the equivalence relation thus defined tell us ...

**3**

votes

**3**answers

520 views

### Chomp! without the law of the excluded middle

Consider the following impartial combinatorial game, a generalization of Chomp! as mentioned in the paper by David Gale: At each step, we have a finite partially ordered set $S$. Player I or II ...

**1**

vote

**1**answer

292 views

### A modified divisor game

Consider a two player game. There are N balls marked 1 to N. A move consists of removing a ball n and all other balls which are divisors of n (including 1). The players alternate the moves. The one ...

**111**

votes

**3**answers

5k views

### A Game on Noetherian Rings

A friend suggested the following combinatorial game. At any time, the state of the game is a (commutative) Noetherian ring $\neq 0$. On a player's turn, that player chooses a nonzero non-unit element ...

**2**

votes

**0**answers

136 views

### Does a generalized Queen split the upper P-positions of Wythoff Nim into two new beams of P-positions?

Wythoff Nim is an impartial game where 2 players take turns in reducing the heights of two finite heaps of tokens. Two types of moves are allowed
(I) Remove any number of tokens from precisely one ...

**17**

votes

**3**answers

1k views

### Traversing the infinite square grid

Starting somewhere on an infinite square grid, is it possible to visit every square exactly once, if at move $n$, one must jump $a_n$ steps in one of the directions north,south,east or west, and mark ...

**11**

votes

**2**answers

953 views

### Can anyone analyze this misere game?

Problem
Let $* = \{0\}$ be the one matchstick nim game, let $*2 = \{0,*\}$ be the two matchstick nim game, let $*3 = \{0,*,*2\} = *2+*$ be the three matchstick nim game, let $g = \{0, *2+*3, ...

**5**

votes

**3**answers

813 views

### Has Sid Sackson's “Hold That Line” been analyzed?

In Sid Sackson's classic book A Gamut of Games, he introduces a game that he calls "Hold That Line." Briefly, it is an impartial pencil-and-paper game played on a finite grid of dots. The first ...

**4**

votes

**1**answer

328 views

### Graph connectivity related game

I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of ...

**0**

votes

**4**answers

552 views

### Breaking down an impartial game into Nim equivalent

This is the game:
The playing field consists of permutation of numbers. The players take turns playing the game. Each player removes single number from the sequence. The game is finished when the ...

**4**

votes

**1**answer

624 views

### Algorithmic war

No, not the war on drugs, but the game of War considered in
Does War have infinite expected length?
As noted in that discussion, the game of war can go on forever, but my question is: can it be ...

**5**

votes

**0**answers

352 views

### SWAT vs Rioters (cops vs robbers variant)

I thought of this while at the Combinatorial Potlatch at Seattle University, where Peter Winkler gave an excellent talk on Cops vs Drunken Robbers. I'll just open it up to the floor. The problem ...

**2**

votes

**7**answers

925 views

### Nim-like(?) game winning strategy?

I have the following Nim-like game (at least, it seems Nim-like to me).
There are $2k$ tokens in a row, $k \in \mathbb{N}$.
Each token $a_i$ has a value $ v_i \in \mathbb{N}$
All this information ...

**8**

votes

**4**answers

1k views

### A “rewiring process” on graphs

I am interested in a discrete process defined as follows. We start with a given graph. At each time step we delete an edge $(i,j)$ and add two edges $e$ and $f$; the edge $e$ is incident with $i$ and ...

**4**

votes

**1**answer

561 views

### Are there any interesting connections between game theory and engineering?

I am doing a senior project and it must be based off game theory, but I am having trouble finding any connections to engineering, possibly structural, or architectural, maybe even civil or mechanical. ...

**14**

votes

**5**answers

2k views

### Irreversible chess

Suppose we play a chess-variant, where any finite number of pieces are allowed, and the board is as large as we wish, but only two kings in total. And there is no 50 move-rule, no castling and no ...

**6**

votes

**1**answer

2k views

### Analysis of Misere Nim?

My friend likes to impress people by playing 3-5-7 which has three piles of counters of sizes 3, 5 and 7. You can remove any number of coins from a single pile, the last player to move loses.
ooo
...