As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [combinatorial-game-theory]

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

222 questions
Filter by
Sorted by
Tagged with
150 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 ...
5k 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
80 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'...
200 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 ...
553 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
107 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 ...
61 views

239 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 ...
120 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
177 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 ...
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 ...
215 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 ...
864 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
110 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$...
166 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
139 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 ...
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 ...
96 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-...
294 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 ...
625 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
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 ...
140 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
129 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 ...
189 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\$...
275 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 ...
233 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 ...
102 views

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 ...
109 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 \...
250 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\}$. ...
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
39 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 ...
225 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: ...
198 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
141 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 ...
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$), "...