Questions tagged [combinatorial-game-theory]
Two-player turn-based perfect-information games, surreal numbers, impartial games and Sprague-Grundy theory, partizan games
230
questions
5
votes
0
answers
257
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,380
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, ...
- 225k
1
vote
0
answers
40
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
3
votes
1
answer
230
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,618
5
votes
0
answers
214
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,353
1
vote
1
answer
158
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,127
28
votes
2
answers
1k
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
31
votes
0
answers
894
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$), "...
4
votes
3
answers
235
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 ...
- 281
1
vote
0
answers
136
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
93
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
1
answer
210
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$. ...
- 353
1
vote
0
answers
32
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} \...
- 111
2
votes
0
answers
271
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
178
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,585
2
votes
0
answers
103
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,677
6
votes
1
answer
169
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,331
2
votes
1
answer
343
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,787
1
vote
0
answers
120
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
5
votes
1
answer
203
views
A set-family game
Two players, Green and Red, play a zero-sum game. It is parametrized by two integers $n\geq 0, k\geq 0$, and a finite family $F$ of sets of size $n$ (each set may appear multiple times in $F$).
Each ...
- 3,585
8
votes
1
answer
204
views
Length of optimal play in Hex as a function of size
Consider Hex on an $n \times n$ board without a swap rule, so that the first player wins. Assume the first player tries to minimize the length of the game, and the second player tries to maximize the ...
- 1,758
7
votes
1
answer
348
views
A Bitwise Xor Problem
Consider a sequence $a_i$ defined by
$$
\begin{align*}
a_1&=p,\\
a_2&=q,\\
a_i&=a_{i-1} \oplus a_{i-2}+1,
\end{align*}$$
where $\oplus$ is the bitwise xor operation. How can we give an ...
- 601
1
vote
2
answers
295
views
How to describe the common boundaries between regions in a infinite Sudoku?
This relates to the answer to a question "Who wins two player sudoku?" and this awesome blog.
A Sudoku can be $N \times N$ where $\sqrt{N}$ is a natural number because $N \times N / \sqrt{N} \times \...
- 119
33
votes
1
answer
3k
views
Is there a position in infinite Go for which the life of a particular stone has transfinite game value?
As follow up to Checkmate in $\omega$ moves?, we can ask the same question about go. Is there a position on a $\mathbb Z \times \mathbb Z$ goban such that either black can kill a white group, but ...
- 5,821
1
vote
1
answer
92
views
Effective way to find Nash equilibrium
Is there any good algorithm for finding Nash equilibrium point, for one and repeated game theory? Thansk a lot for giving me some guidance.
- 771
27
votes
4
answers
3k
views
Alice and Bob playing on a circle
I want to solve this problem:
Let there be $n \ge 2$ points around a circle. Alice and Bob play a game on the circle. They take moves in turn with Alice beginning. At each move:
Alice takes one ...
- 379
21
votes
1
answer
804
views
Who wins the Rubik's cube game?
This game has two players, Spoiler and Solver. We start with a solved 3x3x3 rubik's cube (to make the problem easier).
Solver and Spoiler take turns making 90 degree twists (starting with Solver). ...
- 5,821
9
votes
3
answers
1k
views
The Sudoku game: Solver-Spoiler variation
Consider the Sudoku Solver-Spoiler game, a natural variation of the Sudoku game recently appearing in the question Who wins two-player Sudoku? posted by user PyRulez. In that game, the players attempt ...
- 225k
34
votes
2
answers
4k
views
Who wins two player sudoku?
Let's say players take turns placing numbers 1-9 on a sudoku board. They must not create an invalid position (meaning that you can not have the same number in within a row, column, or box region). The ...
- 5,821
19
votes
3
answers
1k
views
The arithmetic progression game and its variations: can you find optimal play?
Consider the arithmetic progression game, a two-player game of
perfect information, in which the players take turns playing
natural numbers, or finite sets of natural numbers, all distinct,
and the ...
- 225k
41
votes
3
answers
4k
views
A game on integers
$A$ and $B$ take turns to pick integers: $A$ picks one integer and then $B$ picks $k > 1$ integers ($k$ being fixed). A player cannot pick a number that his opponent has picked. If $A$ has $5$ ...
- 909
46
votes
3
answers
5k
views
Does knight behave like a king in his infinite odyssey?
The Knight's Tour is a well-known mathematical chess problem. There is an extensive amount of research concerning this question in two/higher dimensional finite boards. Here, I would like to tackle ...
7
votes
1
answer
291
views
Games in non-standard models
Has anyone studied Combinatorial game theory in non-standard models?
In particular, we can work in either non-standard models of set theory, or we can work in non-standard models of arithmetic, where ...
- 5,821
5
votes
1
answer
6k
views
How many Tic Tac Toe games are possible? [closed]
Consider the average game of Tic Tac Toe or Noughts and Crosses. The game is played on a 3 by 3 two dimentional board. The game is played by two people and each person is allowed to only add one type ...
- 482
10
votes
2
answers
316
views
For which number of pairs is it an advantage to start in memory
Players A and B play memory starting with $n$ pairs of cards. We assume that they can remember all cards which have been turned. At his turn a player will first recall if two cards already turned ...
- 883
22
votes
4
answers
2k
views
The 1-step vanishing polyplets on Conway's game of life
A $n$-polyplet is a collection of $n$ cells on a grid which are orthogonally or diagonally connected.
The number of $n$-polyplets is given by the OEIS sequence A030222: $1, 2, 5, 22, 94, 524, 3031, \...
31
votes
1
answer
1k
views
Vanishing line on Conway's game of life
If the initial state of Conway's game of life is a line of $n \in [0,100]$ alive cells, then it vanishes completely after some steps iff $n \in \{0,1,2,6,14,15,18,19,23,24 \}$. See below for $n=24$.
...
19
votes
5
answers
1k
views
When is a game tree the game tree of a board game?
This question arises from what I find interesting in the recently
asked question What is a chess piece
mathematically?
My answer to that question was that mathematically, game pieces are
in general ...
- 225k
67
votes
6
answers
17k
views
What is a chess piece mathematically?
Historically, the current "standard" set of chess pieces wasn't the only existing alternative or even the standard one. For instance, the famous Al-Suli's Diamond Problem (which remained ...
9
votes
1
answer
367
views
Ordered Nim game
Consider the following variant of Nim:
There are two players and $n$ piles of stones, with sizes $a_1,\dots,a_n$, such that $a_i\leq a_j$ for any $i<j$.
A move consists of removing a positive ...
- 91
5
votes
1
answer
471
views
What ordinal corresponds to the T(3)?
Let's play a game. You start with the ordinal $\alpha$ and I start with the empty sequence. Each turn, you decrease your ordinal, and I add a tree (where each node can have one of three labels), ...
- 5,821
13
votes
1
answer
375
views
Two-player independent set game
Let $G = (V, E)$ be a finite graph, and $S \subseteq V$ initially be an empty set. Alice and Bob play a game, making moves in turns starting with Alice. A move consists of choosing a vertex $v \in V \...
- 5,380
4
votes
2
answers
376
views
Study of Hex on the Torus
Hex is usually played on a parallelogram shaped board. What if you play it on a Torus?
One thing I notice is that the idea of connecting opposite sides doesn't make much sense anymore, since a torus ...
- 5,821
4
votes
0
answers
241
views
Mistake in ONAG?
In the second edition of the book "On Numbers and Games" by Conway there is a theorem 88 (p. 194) on comparison of sums of ${\uparrow} x$ games. It contains a weird statement:
... (If $X$ is a sum ...
- 5,380
4
votes
0
answers
173
views
Modern advances in combinatorial game theory
I'm going to take part in teaching a course in combinatorial game theory in the best of ONAG's spirit. I was wondering if there are interesting post-ONAG results that are worth mentioning in (a later ...
- 5,380
10
votes
2
answers
1k
views
What surreal numbers are representable by Red-Blue Hackenbush games?
Every game of Red-Blue Hackenbush represents a surreal number. Is the converse true? Assuming that it is false, what can be said about the class of surreal numbers that are representable by such ...
- 203
2
votes
1
answer
447
views
Are Surreal Numbers the same as Trans-series?
I recently found the paper of Berarducci + Mantova [1, 2] saying that surreal numbers are equivalent to trans-series. These are very different objects:
trans-series are used in physics to correct, ...
- 22.6k
5
votes
1
answer
452
views
Can a game be an option of itself?
My question is, can a game contain itself as an option? and can it be a surreal number? For example $A=\{A|\}$ or $B=\{C|B\}$ where $C$ is a surreal number.
from the point of view of games, it is ...
- 51
9
votes
0
answers
176
views
Is there a better way to understand this particle?
I've been reading through Winning Ways and was working through some examples of my own related to cooling and particles, and I managed to stump myself. If we let ...
- 99
9
votes
1
answer
565
views
Is every ordinal the nimber of a ring?
This question is about the game of Noetherian rings, see MO/93276.
Here I will include the zero ring in order to get better formulas.
The nimber of a Noetherian ring is an ordinal number. It is ...
- 61.5k