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
0 votes
0 answers
60 views

Determining the first move in go using CGT

I am exploring Combinatorial Game Theory (CGT) and particularly interested in Berlekamp's book "Mathematical Go Endgames". However I am a bit puzzled by the fact that, once he uses the ...
user avatar
2 votes
3 answers
924 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 ---...
user avatar
1 vote
2 answers
86 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 ...
user avatar
2 votes
1 answer
158 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 ...
user avatar
2 votes
1 answer
103 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 ...
user avatar
  • 17.2k
1 vote
0 answers
135 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 ...
user avatar
  • 11
26 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 ...
user avatar
8 votes
1 answer
201 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 ...
user avatar
4 votes
1 answer
810 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. ...
user avatar
1 vote
1 answer
97 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$...
user avatar
13 votes
0 answers
153 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 ...
user avatar
1 vote
1 answer
121 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 ...
user avatar
  • 65
20 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 ...
user avatar
0 votes
1 answer
92 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-...
user avatar
8 votes
0 answers
235 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 ...
user avatar
  • 3,357
18 votes
3 answers
583 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, ...
user avatar
  • 1,179
1 vote
0 answers
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 ...
user avatar
  • 909
3 votes
0 answers
99 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 ...
user avatar
  • 131
1 vote
0 answers
113 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 ...
user avatar
  • 111
3 votes
2 answers
184 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\ $...
user avatar
  • 3,379
9 votes
1 answer
259 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 ...
user avatar
6 votes
0 answers
198 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 ...
user avatar
  • 161
6 votes
1 answer
92 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 {\ \...
user avatar
27 votes
1 answer
933 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 ...
user avatar
  • 531
12 votes
0 answers
264 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 ...
user avatar
  • 4,156
7 votes
0 answers
220 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 ...
user avatar
15 votes
1 answer
781 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 &...
user avatar
52 votes
1 answer
2k 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 ...
user avatar
10 votes
1 answer
455 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 $...
user avatar
  • 32.2k
25 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 ...
user avatar
4 votes
0 answers
76 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 \...
user avatar
  • 2,265
5 votes
0 answers
191 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\}$. ...
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, ...
user avatar
1 vote
0 answers
37 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 ...
user avatar
2 votes
1 answer
214 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: ...
user avatar
  • 2,598
5 votes
0 answers
194 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 ...
user avatar
1 vote
1 answer
107 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 ...
user avatar
  • 1,095
28 votes
2 answers
900 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 ...
user avatar
  • 331
29 votes
0 answers
818 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$), "...
user avatar
4 votes
3 answers
219 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 ...
user avatar
  • 323
1 vote
0 answers
108 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'...
user avatar
1 vote
0 answers
86 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 ...
user avatar
2 votes
0 answers
131 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$. ...
user avatar
  • 343
1 vote
0 answers
27 views

Bound for the additive period length of certain Sprague-Grundy functions

Let $\left( Y_x \right)_{x=0}^\infty $ be a sequence of finite subsets of $\mathbb{Z}$, and let $G : \mathbb{N}_0 \to \mathbb{N}_0$ be a greedy permutation, defined by $$ G(x) = \operatorname{mex} \...
user avatar
2 votes
0 answers
233 views

Combining a Nim-variation and Wyrthoff's game. How to find a winning strategy? [closed]

Wythoff's game is a variation of the classical Nim - There are two heaps and the players take turns either taking any amount from one heap, or the same amount of both heaps. The winner is the one ...
user avatar
3 votes
2 answers
152 views

Satisfier-Falsifier games

In a Maker-Breaker game, there is a finite set of elements $X$, and a family $F$ of subsets of $X$ called the "winning sets". Two players, Maker and Breaker, take turns picking untaken elements from $...
user avatar
2 votes
0 answers
97 views

A combinatorial number game

Alice and Bob play the following (base 10) number game. A target N is fixed, N being a positive integer. Alice then writes the number 1 on the blackboard. Bob responds with the number 2. Thereafter, ...
user avatar
6 votes
1 answer
151 views

What is the minimum worst-case length of an element removal game?

A game is played as follows. There is a set $X = \{1, \ldots, n\}$. Player 1 is trying to find a "locally minimal subset" $M \subseteq X$ - that is, player 2 has said that $M$ is good, and also that ...
user avatar
2 votes
1 answer
270 views

Combinatorial games with infinite paths, and generalized Sprague-Grundy theory

Generalized Sprague-Grundy theory has been used to analyze finite impartial loopy games with normal play. There is a nice short account by Mark S. in this answer. It was introduced by Cedric Smith in ...
user avatar
  • 3,363
1 vote
0 answers
110 views

Is there only one meaningful definition of product of games?

Work in the context of combinatorial games as introduced by Conway. For surreals, the definition of the product is forced by the requirement that surreals should form an ordered field. Say, if $s' <...
user avatar

1
2 3 4 5