Questions tagged [combinatorial-game-theory]
Two-player turn-based perfect-information games, surreal numbers, impartial games and Sprague-Grundy theory, partizan games
211
questions
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 ...
- 5,065
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 ---...
- 37.4k
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 ...
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 ...
- 73
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 ...
- 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 ...
- 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 ...
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 ...
- 13.6k
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. ...
- 445
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$...
- 13.6k
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 ...
- 13.6k
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 ...
- 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 ...
- 194k
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-...
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 ...
- 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, ...
- 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 ...
- 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 ...
- 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 ...
- 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\ $...
- 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 ...
- 43.7k
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 ...
- 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 {\ \...
- 155
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 ...
- 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 ...
- 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 ...
- 395
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 &...
- 151
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 ...
- 194k
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 $...
- 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 ...
- 3,819
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 \...
- 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\}$. ...
- 5,121
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, ...
- 194k
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 ...
- 11
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: ...
- 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 ...
- 3,053
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 ...
- 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 ...
- 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$), "...
- 22.9k
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 ...
- 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'...
- 11
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 ...
- 11
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$. ...
- 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} \...
- 11
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 ...
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 $...
- 3,501
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, ...
- 3,229
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 ...
- 1,311
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 ...
- 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' <...
- 183