# Questions tagged [combinatorial-game-theory]

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

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

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

**13**

votes

**0**answers

1k views

### Characterizing the surcomplex numbers

Conway showed that the Field of surreal numbers ("${\bf No}$")
is the maximal totally ordered Field.
Later Jacob Lurie showed that the Group of all partizan games ${\bf Pg}$ is
the universally ...

**8**

votes

**0**answers

156 views

### Two-player independent set game

Let $G = (V, E)$ be a finite graph, and $S \subseteq V$ initially be an empty set. Alice and Bob play a game, making moves in turns starting with Alice. A move consists of choosing a vertex $v \in V \...

**8**

votes

**0**answers

146 views

### Is there a better way to understand this particle?

I've been reading through Winning Ways and was working through some examples of my own related to cooling and particles, and I managed to stump myself. If we let ...

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

**7**

votes

**0**answers

1k views

### Is there a chess position equivalent to the Collatz conjecture?

Suppose we have an infinite board with a finite number of chess pieces. The question is whether white can checkmate black (without the after 50 moves it is a draw rule). Can you give an explicit ...

**6**

votes

**0**answers

82 views

### Length of optimal play in Hex as a function of size

Consider Hex on an $n \times n$ board without a swap rule, so that the first player wins. Assume the first player tries to minimize the length of the game, and the second player tries to maximize the ...

**6**

votes

**0**answers

129 views

### Combinatorial game similar to Sprouts

Is there a name for the following combinatorial game? Is there a solution which player has a winning strategy?
Basically this game is "Sprouts without midpoints". One starts with $n$ points in the ...

**6**

votes

**0**answers

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

**5**

votes

**0**answers

128 views

### Games in non-standard models

Has anyone studied Combinatorial game theory in non-standard models?
In particular, we can work in either non-standard models of set theory, or we can work in non-standard models of arithmetic, where ...

**5**

votes

**0**answers

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

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

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

**4**

votes

**0**answers

202 views

### Mistake in ONAG?

In the second edition of the book "On Numbers and Games" by Conway there is a theorem 88 (p. 194) on comparison of sums of ${\uparrow} x$ games. It contains a weird statement:
... (If $X$ is a sum ...

**4**

votes

**0**answers

119 views

### Modern advances in combinatorial game theory

I'm going to take part in teaching a course in combinatorial game theory in the best of ONAG's spirit. I was wondering if there are interesting post-ONAG results that are worth mentioning in (a later ...

**4**

votes

**0**answers

247 views

### A game played on binary matrices ($2$-dimension coin-turning game)

Let $r\geq 1$ be a natural number. I am interested in the following (two-player, impartial, perfect-information) game:
The state of the game is an $n\times n$ matrix with coefficients in $\mathbb{F}...

**4**

votes

**0**answers

287 views

### Why is this transfinite game not determined?

This question originates from the paper On the Axiom of Determinateness by Jan Mycielski, section 7. Given a set $X$ and an ordinal $\alpha$, the author defines a transfinite game of length $\alpha$ ...

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

**4**

votes

**0**answers

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

**3**

votes

**0**answers

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

**2**

votes

**0**answers

86 views

### A combinatorial number game

Alice and Bob play the following (base 10) number game. A target N is fixed, N being a positive integer. Alice then writes the number 1 on the blackboard. Bob responds with the number 2. Thereafter, ...

**2**

votes

**0**answers

82 views

### Difficulty of 3-color forest Hackenbush

"Forest Hackenbush" (for lack of a better name) is the particular case of the game of Hackenbush where the initial position (and therefore all subsequent positions) is a (finite) forest (:= disjoint ...

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

**2**

votes

**0**answers

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

**1**

vote

**0**answers

18 views

### Bound for the additive period length of certain Sprague-Grundy functions

Let $\left( Y_x \right)_{x=0}^\infty $ be a sequence of finite subsets of $\mathbb{Z}$, and let $G : \mathbb{N}_0 \to \mathbb{N}_0$ be a greedy permutation, defined by
$$ G(x) = \operatorname{mex} \...

**1**

vote

**0**answers

128 views

### How often do random games of go end in illegal moves?

Suppose that moves are generated from two players in accordance with three rules: each move is chosen uniformly at random among places on the board ($19 \times 19$, $9 \times 9$, or $k \times k$ with ...

**1**

vote

**0**answers

90 views

### Is there only one meaningful definition of product of games?

Work in the context of combinatorial games as introduced by Conway.
For surreals, the definition of the product is forced by the requirement that surreals should form an ordered field.
Say, if $s' <...

**1**

vote

**0**answers

57 views

### Does handle reduction determine braid equivalence in quotients of braid groups?

Let $B_{n}$ denote the $n$-strand braid group. Let $G$ be a group generated by elements $x_{1},...,x_{n-1}$. Let $N$ be the smallest normal subgroup of $B_{n}$ such that the mapping $x_{1}\mapsto\...

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

**1**

vote

**0**answers

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

**1**

vote

**0**answers

345 views

### Has anyone seen this version of ring toss (combinatorial object) before?

In reference to a
question on work of Westzynthius and another
question relating to Jacobsthal's function, I have formed a game which I immodestly call Paseman's Ring Toss. I hope that it has been ...

**0**

votes

**0**answers

84 views

### Decidability of mate-in-n for infinite chess with huygens piece

Consider a game like chess on an infinite board, where we have the usual chess piece types and an additional piece which moves a prime number of square horizontally or vertically.
If we assume a ...

**0**

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

**0**

votes

**0**answers

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

**0**

votes

**0**answers

513 views

### Proof of Upper bound of price of anarchy in local connection game

I am looking at the work by Fabrikant "On a Network Connection Game" (http://webcourse.cs.technion.ac.il/236620/Spring2005/ho/WCFiles/FLMPS_netDesign.pdf). This work presents a game-theoretic ...

**-1**

votes

**0**answers

136 views

### Local Connection Game

A local connection game is given by a set of vertices and graph G where connection is built by adding edges.
If the cost to user a(user at node a) is given by $$C(u)=\alpha n_u + \beta \sum_v(dist(u,...