Questions tagged [combinatorial-game-theory]

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

Filter by
Sorted by
Tagged with
7 votes
0 answers
223 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 ...
Noah Schweber's user avatar
9 votes
0 answers
355 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 ...
Veronica Phan's user avatar
2 votes
0 answers
197 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 (...
Luis's user avatar
  • 21
3 votes
2 answers
531 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 ...
Nick's user avatar
  • 31
8 votes
1 answer
384 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 $...
Noah Schweber's user avatar
5 votes
1 answer
406 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 ...
Clement Yung's user avatar
6 votes
1 answer
182 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 ...
Roland Bacher's user avatar
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 ...
Leif Sabellek's user avatar
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'...
Noah Schweber's user avatar
5 votes
1 answer
238 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 ...
Noah Schweber's user avatar
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, ...
Joel David Hamkins's user avatar
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 ...
Wouter Zandsteeg's user avatar
3 votes
0 answers
72 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 ...
Wlod AA's user avatar
  • 4,686
7 votes
1 answer
564 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 ...
Wlod AA's user avatar
  • 4,686
1 vote
0 answers
91 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 ...
Oleksandr  Kulkov's user avatar
5 votes
1 answer
949 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 ...
Hollis Williams's user avatar
12 votes
1 answer
366 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 ...
Roland Bacher's user avatar
3 votes
0 answers
148 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 ...
wcysai's user avatar
  • 31
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 ---...
Anton Petrunin's user avatar
1 vote
2 answers
249 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 ...
Stacker Dragon's user avatar
3 votes
1 answer
286 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 ...
FreakyByte's user avatar
2 votes
1 answer
128 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 ...
James Propp's user avatar
  • 19.4k
1 vote
0 answers
232 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 ...
neobax's user avatar
  • 11
27 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 ...
Sin Nombre's user avatar
8 votes
1 answer
222 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 ...
Roland Bacher's user avatar
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. ...
Matt Hastings's user avatar
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$...
Roland Bacher's user avatar
13 votes
0 answers
212 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 ...
Roland Bacher's user avatar
1 vote
1 answer
146 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 ...
Ben Tom's user avatar
  • 107
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 ...
Joel David Hamkins's user avatar
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-...
sakuragaoka2001's user avatar
8 votes
0 answers
452 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 ...
JoshuaZ's user avatar
  • 6,090
18 votes
3 answers
646 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, ...
pi66's user avatar
  • 1,199
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 ...
Jiayi Liu's user avatar
  • 909
3 votes
0 answers
164 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 ...
flame's user avatar
  • 131
1 vote
0 answers
133 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 ...
CSSTUDENT's user avatar
  • 111
3 votes
2 answers
200 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\ $...
Wlod AA's user avatar
  • 4,686
12 votes
1 answer
356 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 ...
Richard Stanley's user avatar
6 votes
0 answers
254 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 ...
IS4's user avatar
  • 161
6 votes
1 answer
113 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 {\ \...
soerenssen's user avatar
27 votes
1 answer
998 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 ...
Vepir's user avatar
  • 591
15 votes
0 answers
462 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 ...
Ville Salo's user avatar
  • 6,337
7 votes
0 answers
287 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 ...
Mike Earnest's user avatar
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 &...
user784623's user avatar
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 ...
Joel David Hamkins's user avatar
11 votes
1 answer
680 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 $...
Simon Henry's user avatar
  • 39.9k
27 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 ...
Mike Battaglia's user avatar
4 votes
0 answers
144 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 \...
Thomas's user avatar
  • 2,691
5 votes
0 answers
256 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\}$. ...
Mikhail Tikhomirov's user avatar
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, ...
Joel David Hamkins's user avatar

1
2 3 4 5