# Questions tagged [combinatorial-game-theory]

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

233 questions
Filter by
Sorted by
Tagged with
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 ...
• 181
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 ...
• 141
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,496
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$ ...
• 167
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 ...
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 ...
• 19.3k
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 ...
• 1,320
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 (...
• 21
550 views

• 19.3k
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 ...
• 976
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 ...
• 17.5k
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
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'...
• 19.3k
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 ...
• 19.3k
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
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 ...
75 views

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 ...
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 ...
• 19.5k
1 vote
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 ...
• 11
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 ...
• 469
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 ...
• 17.5k
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
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$...
• 17.5k
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 ...
• 17.5k
1 vote
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 ...
• 107
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 ...
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-...
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 ...
• 6,290
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,199
1 vote
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 ...
• 909
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 ...
• 131
1 vote
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 ...
• 111
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\$...
• 4,696
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 ...
• 49.7k
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 ...
• 161
115 views

• 611
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 ...
• 6,437
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 ...
• 415