Skip to main content

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
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 ...
volcanrb's user avatar
  • 181
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 ...
hzy's user avatar
  • 141
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 ...
mathoverflowUser's user avatar
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$ ...
bernardorim's user avatar
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 ...
Farran Khawaja's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Veronica Phan's user avatar
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 (...
Luis's user avatar
  • 21
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 ...
Nick's user avatar
  • 31
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 $...
Noah Schweber's user avatar
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 ...
Clement Yung's user avatar
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 ...
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
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 ...
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
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 ...
Wlod AA's user avatar
  • 4,696
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 ...
Wlod AA's user avatar
  • 4,696
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 ...
Oleksandr  Kulkov's user avatar
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 ...
Hollis Williams's user avatar
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 ...
Roland Bacher's user avatar
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 ...
wcysai's user avatar
  • 41
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
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 ...
Stacker Dragon's user avatar
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 ...
FreakyByte's user avatar
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 ...
James Propp's user avatar
  • 19.5k
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 ...
neobax's user avatar
  • 11
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 ...
Sin Nombre's user avatar
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 ...
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
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 ...
Roland Bacher's user avatar
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 ...
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
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 ...
JoshuaZ's user avatar
  • 6,290
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, ...
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
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 ...
flame's user avatar
  • 131
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 ...
CSSTUDENT's user avatar
  • 111
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\ $...
Wlod AA's user avatar
  • 4,696
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 ...
Richard Stanley's user avatar
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 ...
IS4's user avatar
  • 161
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 {\ \...
soerenssen's user avatar
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 ...
Vepir's user avatar
  • 611
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 ...
Ville Salo's user avatar
  • 6,437
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 ...
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

1
2 3 4 5