# Questions tagged [combinatorial-game-theory]

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

233
questions

8
votes

0
answers

55
views

### $2$-for-$2$ asymmetric Hex

This is a crosspost from Math stackexchange as I left the question open a while and bountied it but received no answers.
If the game of Hex is played on an asymmetric board (where the hexes are ...

10
votes

0
answers

304
views

### Connection properties of a single stone on an infinite Hex board

This includes a series of questions.
One of the most typical examples is shown as the picture below.
An half-infinite Hex board with an one row of black stones. Black stones are separated by one ...

4
votes

1
answer

376
views

### "Infinity": A card game based on prime factorization and a question

I have been developing a card game called "Infinity", which involves a unique play mechanic based on card interactions. In this game, each card displays a set of symbols, and players match ...

2
votes

0
answers

58
views

### How many ways to win a game between two teams with arbitrary player skills

Suppose we have $n\geq 4$ players $p_1,\cdots,p_n$ of a game between two teams: team $A$ and team $B$ (disjoint sets, each with two or more players, so that $|A|+|B|=n$). Assume that each player $p_i$ ...

0
votes

0
answers

85
views

### Are gaps and loopy games interchangeable in the Surreal Numbers?

The class of surreal numbers (commonly called $No$) is not complete: it contains gaps. Some people have studied the "Dedekind completion" of the surreal numbers in order to do limits and ...

7
votes

0
answers

228
views

### Chip firing on hypergraphs

A (finite) hypergraph is a pair $(V, \mathcal{E})$ where $V$ is a finite set of vertices and $\mathcal{E}\subseteq\mathcal{P}(V)$ with each $E\in\mathcal{E}$ having at least two elements; a ...

9
votes

0
answers

361
views

### For which set $A$, Alice has a winning strategy?

Cross-posted from MSE: https://math.stackexchange.com/questions/4775193/for-which-set-a-alice-has-a-winning-strategy
Alice and Bob are playing a game. They take an integer $n>1$, and partition the ...

2
votes

0
answers

201
views

### Are infinite loops possible in the game Prodway?

I'd like to know if infinitely repeating sequences of moves (i.e. cycles) are possible in the following game:
Prodway is a game for two players (Black and White) that is
played on the intersections (...

3
votes

2
answers

550
views

### Negative of combinatorial game

I am having problem understanding what negative of a combinatorial game $G$ exactly means in combinatorial game theory. Does it mean that if I have normal game, if I create inverse, i.e., $-G = \{-G^R ...

8
votes

1
answer

404
views

### Is "do-almost-nothing" ever winning on large CHOMP boards?

This is a special case of a question asked but unanswered at MSE:
Consider the combinatorial game CHOMP (presented as in the linked notes so that the "poison" square is bottom-left). In any $...

5
votes

1
answer

416
views

### Uniform strategy on Kastanas' game

I think my question applies to most games, but for the sake of concreteness, I shall consider one specific game in this question. We consider the game posed by Ilias Kastanas in his paper On the ...

6
votes

1
answer

183
views

### A combinatorial game with seemingly curious arithmetic properties

We consider the following combinatorial game (with two players
alternatively playing optimally). Posititions are given by heaps containing $b\geq 0$ black and $w\geq 0$ white stones and are
encoded by ...

84
votes

2
answers

6k
views

### A little number theoretic game

I came up with this little two player game:
The players take turns naming a positive integer. When one player says the number n, the other player can only reply in two different ways: They can either ...

1
vote

0
answers

92
views

### Eventual stabilization for repeatedly adding multiplayer games

This question is an outgrowth of a couple previous questions of mine. In order: 1,2,3. This should be fully self-contained, but those questions may help motivate this one.
To keep things readable, I'...

5
votes

1
answer

242
views

### Monoid associated to $>2$-player Hackenbush

There is some literature on multiplayer combinatorial game theory, but as far as I can tell none of it follows the line of attack below. I'd love a pointer to a similar approach taken in the ...

24
votes

2
answers

1k
views

### What is the complexity of the winning condition in infinite Hex? In particular, is infinite Hex a Borel game?

Consider the game of infinite Hex, where two players Red and Blue alternately place their stones on the infinite hex grid, each aiming to create a winning configuration.
Red wins after infinite play, ...

1
vote

0
answers

124
views

### A question about a theorem in ONAG by Conway

Does anyone here know about Conway's On numbers and games? Because I can't figure out what he does here on p18. It feels a bit like he's using the statement we want to prove
I will type the proof ...

3
votes

0
answers

75
views

### Projective plane finite game

This is a 2-person game.
Let $\ P\ $ be any arbitrary projective space (of any dimension $\ \ge2$ and any cardinality, etc., but typically, let it be a finite plane over a field). Let $\ S_0\subseteq ...

7
votes

1
answer

567
views

### JUSTICE & INJUSTICE — two 2-player finite games

There is a non-empty finite set $\ K,\ $ say, of plates. Initially, there are $\ p_0(k)\ $ stones on the $k$-th plate, where
$\ p_0(k)\in\mathbb Z_{_{\ge0}}\ $ for each $\ k\in K.$
So far, it is like ...

1
vote

0
answers

92
views

### Fast algorithm to compute nimber product

It is known that nimbers (Grundy numbers) below $2^{2^n}$ form a field with the nim addition $\oplus$ and the nim product $\cdot$.
Generally, one can develop an algorithm to compute the product of two ...

5
votes

1
answer

1k
views

### Set theory / Formal logic of Baba is You

''Baba is You'' is a recent puzzle game in which the player builds a set of rules by pushing squares with words written on them. If we leave aside the combinatorial difficulty of how to move the ...

12
votes

1
answer

369
views

### Euclid's algorithm as a combinatorial game

Consider the following two player game based on the Euclidean algorithm: Positions are given by $(a,b)$ in $\mathbb N^2\setminus\{(0,0)\}$ (where $\mathbb N=\{0,1,2,\ldots\}$) defining a greatest ...

4
votes

0
answers

156
views

### Two-player item picking game

Two players $A$ and $B$ play this game: There are $n$ items, where the $i$th item is of value $a_i$ to player $A$ and is of value $b_i$ to player $B$. Two players take turns picking items, and each ...

2
votes

3
answers

1k
views

### Strategy-stealing in chess

Is it proved that white can guarantee at least draw in chess?
A while ago I was told that it was proved using strategy-stealing, but I cannot find a reference.
Postscript. Please accept my apology ---...

1
vote

2
answers

260
views

### Do restricted Nim-like games have winning strategies?

Considering a Nim-like game to be:
There are three piles $A,B,C$, and the amount of their elements are $|A|=2, |B|=5, |C|=6$;
There are 2 players. Each time a player can either take $x (1\leq x \leq ...

3
votes

1
answer

295
views

### What does it mean for the surreal numbers/partizan games to be "universally embedding"?

In "On numbers and games", Conway writes that the surreal Numbers form a universally embedding totally ordered Field. Later Jacob Lurie proved that (the equivalence classes of) the partizan ...

2
votes

1
answer

129
views

### Does Conway’s field of finite nim values have arithmetically tractable isomorphisms?

Conway constructed a field of characteristic 2 whose elements are the finite Nim values, indexed by the natural numbers. What is known about nontrivial automorphisms of this field? Do any of them ...

1
vote

0
answers

241
views

### The maximum number of moves in a game of Nim [closed]

I was assigned a fun, but also quite hard problem for my computer science class - I have to write a java program that computes the maximum number of turns in an optimal game of Nim.
In case you are ...

27
votes

7
answers

6k
views

### Why is game theory formulated in terms of equilibrium instead of winning strategies?

Game theory, on the outset, seems to invite the questions,
"what can I do to win" or "how do I beat my opponent?"
So many people who are not familiar with game theory look to game ...

8
votes

1
answer

223
views

### Name of a game : Remove two chips from a vertex or one chip from both ends of an edge

Consider a finite graph $\Gamma$ with a positive number $n_v\geq 0$ of chips stacked at each vertex $v$ of $\Gamma$. Two players play in turn with moves consisting either of removing two chips from a ...

4
votes

1
answer

1k
views

### Who wins this two player game of making squares?

Two players take turns coloring edges on an $n$-by-$n$ grid. Both players use the same color. Every time a player surrounds a square of the grid, they mark that square with their name and go again. ...

1
vote

1
answer

142
views

### Name for an easy combinatorial game

What is the name of the following combinatorial game:
Two players, moving in turn.
Positions: $0,1,2,\ldots$.
Moves: $n\longmapsto n-1$ or $n\longmapsto \lfloor n/2\rfloor$
if $n>0$.
No move for $0$...

13
votes

0
answers

215
views

### A game based on the Euclidean algorithm

The following game is based on a somewhat "stupid" version of the Euclidean algorithm (where we allow only subtractions).
Positions are given by finite non-empty multisets (repeated elements ...

1
vote

1
answer

147
views

### Complexity of games with graph classes

Let $\mathfrak{G}$ be the class of all finite directed and undirected graphs. Let $A,B\subseteq \mathfrak{G} $, $A$ and $B$ are closed under graph isomorphisms, and $A \cap B = \varnothing$. Consider ...

25
votes

4
answers

2k
views

### The Chocolatier's game: can the Glutton win with a restricted form of strategy?

I have a question about the Chocolatier's game, which I had
introduced in my recent answer to a question of Richard
Stanley.
To recap the game quickly, the Chocolatier offers up at each stage
a finite ...

0
votes

1
answer

102
views

### Mapping problem reminiscent of Mastermind

Given 2 finite sets $S$ and $M$, with $\operatorname{card}(S) \geq \operatorname{card}(M)$, and an item $z \not\in M$. There is an unknown function $f: S \to M \cup \{z\}$, which is known to be one-to-...

8
votes

0
answers

475
views

### Winning moves in Hex

The game "Hex" is a simple game which apparently has been invented at least twice (Piet Hein and John Nash). The game consists of an n by n grid of hexagons, with two opposite sides marked ...

18
votes

3
answers

652
views

### Tic-tac-toe with one mark type

Parameters $a,b,c$ are given such that $c\leq\max(a,b)$. In an $a\times b$ board, two players take turns putting a mark on an empty square. Whoever gets $c$ consecutive marks horizontally, vertically, ...

1
vote

0
answers

84
views

### Winning criterion for a combinatorial game

Given $n$,
let $\mathcal{R}$ be a set of pairs $(\rho,A)$
where $A\subseteq n, \rho\in 2^A$.
Consider the following game between A and B.
At each round $t$, A enumerates an $m\in n$ (that has not been ...

3
votes

0
answers

165
views

### What values are representable by Hackenbush stalks?

It is known that every number can be represented by some red-blue Hackenbush stalk (see here, for instance). What values can be represented by red-blue-green Hackenbush stalks? In addition, what games ...

1
vote

0
answers

134
views

### Nim variant with minimum number of objects?

I'm wondering where I can find in the literature (if it exists) a discussion of a Nim variant where we impose the additional condition on Nim that we can remove only up to $c$ objects before the game ...

3
votes

2
answers

201
views

### A "Markov game"

I call games similar to the one I describe below to be Markov games. I am selecting just that one or rather a 1-parameter series of games. The open challenge is to find out which of the players $\ 0\ $...

12
votes

1
answer

357
views

### An averaging game on finite multisets of integers

The following procedure is a variant of one suggested by
Patrek Ragnarsson (age 10). Let $M$ be a finite multiset of
integers. A move consists of choosing two elements
$a\neq b$ of $M$ of the same ...

6
votes

0
answers

262
views

### Quantum surreal numbers

Toward Quantum Combinatorial Games presents the definition of a "quantum game", allowing a superposition of moves rather than a single classical move. This leaves me wondering: Since surreal ...

6
votes

1
answer

115
views

### pursuit-evasion based on Schroeder's upper bound for graphs of genus $g$

I am following Schroeder's work on pursuit-evasion games on graphs (often called "cops and robbers"). In his 2001 publication ("The copnumber of a graph is bounded by $\lfloor 3/2 {\ \...

27
votes

1
answer

1k
views

### Players alternate moving a $\{\swarrow,\uparrow,\rightarrow\}$ piece on a chessboard

Edit $4.$ $-$ Proposing to reopen the question (the related competition should be over by now).
Edit $3.$ $-$ I have just found out that the linked competition (see the "Edit $1$.") is still ...

15
votes

0
answers

471
views

### Does the Angel have to be really smart?

My question is about the computational complexity of the Angel's strategy in the Angels and Devils game, tl;dr does the Angel have a polynomial time strategy.
I'm a big Conway fan, so as you can ...

7
votes

0
answers

295
views

### How does Conway's proposed compromise for constructing the real numbers in ONAG actually work?

I have also asked this question on Math Stack Exchange (link).
In On Numbers and Games, after discussing the inclusion of the real numbers in the surreal numbers, No, Conway discusses the merits of ...

16
votes

1
answer

1k
views

### In theory, how would Oneiric numbers be defined?

Background I am not a professional mathematician. I am researching Surreal numbers & games for fun (I think they are truly beautiful). If this question is not appropriate here, I beg forgiveness &...

54
votes

1
answer

3k
views

### In the two-person Killing the Hydra game, what is the winning strategy?

My question is which player has a winning strategy in the
two-player version of the Killing the Hydra game?
In their amazing paper,
Kirby, Laurie; Paris, Jeff, Accessible independence results for ...