# Questions tagged [combinatorial-game-theory]

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

211
questions

0
votes

0
answers

60
views

### Determining the first move in go using CGT

I am exploring Combinatorial Game Theory (CGT) and particularly interested in Berlekamp's book "Mathematical Go Endgames". However I am a bit puzzled by the fact that, once he uses the ...

2
votes

3
answers

924
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

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

2
votes

1
answer

158
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

103
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

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

26
votes

7
answers

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

201
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

810
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

97
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

153
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

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

20
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

92
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

235
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

583
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

82
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

99
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

113
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

184
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\ $...

9
votes

1
answer

259
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

198
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

92
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

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

12
votes

0
answers

264
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

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

15
votes

1
answer

781
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 &...

52
votes

1
answer

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

10
votes

1
answer

455
views

### Free category with product and coproduct

Is there a known description of the free category with both product and coproduct?
That is, given a small category $C$, I want to consider a category $U C$ which has product and coproduct, a functor $...

25
votes

1
answer

2k
views

### Are Conway's combinatorial games the "monster model" of any familiar theory?

This is related to this question about a "mother of all" groups, and so seemed like it'd fit in better at MO than MSE.
If I understand the answer to that question correctly, the surreal numbers have ...

4
votes

0
answers

76
views

### Infinite positions in 3D chomp

I've recently come back to investigating ordinal chomp. See A winning move for the first player in $3 \times 3 \times \omega$ Ordinal Chomp for a definition. I made a new discovery, that the position \...

5
votes

0
answers

191
views

### Nimber $2^{2^k} - 1$ is a multiplicative generator of $[2^{2^k}]$?

Let $t = 2^{2^k}$, and consider the field $[t]$ of nimbers below $t$. For $k \leq 6$ one can check that $t - 1$ (in the usual arithmetic sense) is a multiplicative generator of $[t] \backslash \{0\}$. ...

19
votes

2
answers

3k
views

### What is the winning strategy in this pebble game?

Consider the following two-player pebble game. We have finitely
many stones on a finite linear track of squares. We take turns, and
the allowed moves are:
move any one stone one square to the left, ...

1
vote

0
answers

37
views

### Suggestions for two-choice game played in ladder graph

I was just working on counting all the possible Nash Equilibrium solutions for a two-choice game played on a ladder graph (I got my results and all that for a generic number of players).
And I was ...

2
votes

1
answer

214
views

### Is following function a metric on the set of isomorphism classes of graphs with countably many vertices?

Suppose $\Gamma_1(V_1, E_1)$ and $\Gamma_2(V_2, E_2)$ are simple graphs with countably many vertices. And suppose $A_1$ and $A_2$ are initially empty sets. Suppose two players play the following game: ...

5
votes

0
answers

194
views

### Is Domineering on any finite approximation of the Sierpinski Carpet always a second-player win?

The game of Domineering can be played on any board consisting of some subset of $\mathbb{Z} \times \mathbb{Z}$.
In particular, consider the boards $K_n$ generated by iterating the following inductive ...

1
vote

1
answer

107
views

### Perturbation of the value of a general-sum game at a equilibirium

Consider a general-sum game with $N$ players. Let $u_i(a_1, \ldots, a_N)\colon \prod_{i=1}^N A_i \rightarrow \mathbb{R} $ be the payoff of the player $i\in \{ 1, \ldots, N \}$ when each player takes ...

28
votes

2
answers

900
views

### Solution to simple mathematical game

Consider the following game (that I made up). Two players each attempt to name a target number. The first player begins by naming 1. On each subsequent turn, a player can name any larger number that ...

29
votes

0
answers

818
views

### Is this representation of Go (game) irreducible?

This post is freely inspired by the basic rules of Go (game), usually played on a $19 \times 19$ grid graph.
Consider the $\mathbb{Z}^2$ grid. We can assign to each vertex a state "black" ($b$), "...

4
votes

3
answers

219
views

### Best strategy for a combinatorial game

Consider the following scenario. We have 20 balls and 100 boxes. We put all 20 balls into the boxes, and each box can contain at most one ball.
Now suppose we are given 5 chances to pick 20 out of ...

1
vote

0
answers

108
views

### Strategy of Responder in Rényi Ulam Liar Games

I tried posting this in Math Stack Exchange but got no responses, so I figured I could try my luck here. My main concern is that I can't figure out how to get started on my "research" (bear with me, I'...

1
vote

0
answers

86
views

### Is there a well-posed definition of game on a graph? Or a well defined category of games on graphs?

All I ever found about this were natural language rules à la Asimov's three laws of robotics. The questions are straightforward questions:
1) Is there a well-posed mathematical definition of game on ...

2
votes

0
answers

131
views

### Game on groups (generalization of spinning switches puzzle)

Alice and Bob are playing a game as follows:
Initially
There're two subgroups $A,B$ of Sym(n) known to both Alice and Bob
There're $n$ slots $S_1, \cdots, S_n$ and $n$ boxes $B_1, \cdots, B_n$. ...

1
vote

0
answers

27
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} \...

2
votes

0
answers

233
views

### Combining a Nim-variation and Wyrthoff's game. How to find a winning strategy? [closed]

Wythoff's game is a variation of the classical Nim - There are two heaps and the players take turns either taking any amount from one heap, or the same amount of both heaps. The winner is the one ...

3
votes

2
answers

152
views

### Satisfier-Falsifier games

In a Maker-Breaker game, there is a finite set of elements $X$, and a family $F$ of subsets of $X$ called the "winning sets". Two players, Maker and Breaker, take turns picking untaken elements from $...

2
votes

0
answers

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

6
votes

1
answer

151
views

### What is the minimum worst-case length of an element removal game?

A game is played as follows. There is a set $X = \{1, \ldots, n\}$. Player 1 is trying to find a "locally minimal subset" $M \subseteq X$ - that is, player 2 has said that $M$ is good, and also that ...

2
votes

1
answer

270
views

### Combinatorial games with infinite paths, and generalized Sprague-Grundy theory

Generalized Sprague-Grundy theory has been used to analyze finite impartial loopy games with normal play. There is a nice short account by Mark S. in this answer. It was introduced by Cedric Smith in ...

1
vote

0
answers

110
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' <...