# Questions tagged [combinatorial-game-theory]

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

198 questions
Filter by
Sorted by
Tagged with
58 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 ...
509 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, ...
75 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 ...
66 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 ...
90 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 ...
38 views

Recently, I've asked about the linear Markov game: A "Markov game". It was solved by @JosephGordon (and I followed with a simplification). This time I'll ask about the quadratic Markov game. ...
167 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\$...
241 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 ...
165 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 ...
79 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 ...
59 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 \...
159 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, ...
31 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 ...
210 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: ...
181 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 ...
69 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 ...
881 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 ...
775 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$), "...
212 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 ...
76 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'...
82 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 ...
110 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$. ...
24 views