Questions tagged [combinatorial-game-theory]
Two-player turn-based perfect-information games, surreal numbers, impartial games and Sprague-Grundy theory, partizan games
1
vote
0answers
18 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} \...
2
votes
0answers
40 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 ...
1
vote
0answers
128 views
How often do random games of go end in illegal moves?
Suppose that moves are generated from two players in accordance with three rules: each move is chosen uniformly at random among places on the board ($19 \times 19$, $9 \times 9$, or $k \times k$ with ...
3
votes
2answers
124 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 $...
2
votes
0answers
86 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, ...
5
votes
1answer
107 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
vote
1answer
178 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 ...
1
vote
0answers
90 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' <...
5
votes
1answer
176 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 ...
6
votes
0answers
82 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 ...
0
votes
0answers
84 views
Decidability of mate-in-n for infinite chess with huygens piece
Consider a game like chess on an infinite board, where we have the usual chess piece types and an additional piece which moves a prime number of square horizontally or vertically.
If we assume a ...
1
vote
0answers
240 views
surreal form star is a xor cipher [closed]
i have been doing a lot of surreal analysis lately & it dawn'd on me that star in the surreal numbers has the same properties of a simple xor cipher.
star operations are given as:
...
6
votes
1answer
265 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 ...
1
vote
2answers
211 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 \...
30
votes
1answer
2k 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 ...
1
vote
1answer
65 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.
27
votes
4answers
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 ...
18
votes
1answer
441 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). ...
9
votes
3answers
704 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 ...
33
votes
2answers
2k 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 ...
19
votes
3answers
512 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 ...
37
votes
3answers
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$ ...
43
votes
2answers
4k 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 ...
5
votes
0answers
128 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
votes
1answer
2k 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 ...
10
votes
2answers
217 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 ...
21
votes
4answers
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, \...
28
votes
1answer
777 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$.
...
17
votes
5answers
870 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 ...
9
votes
1answer
225 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 ...
4
votes
1answer
246 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), ...
8
votes
0answers
156 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 \...
3
votes
2answers
198 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 ...
4
votes
0answers
202 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 ...
4
votes
0answers
119 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 ...
10
votes
2answers
455 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 ...
2
votes
1answer
329 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, ...
5
votes
1answer
381 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 ...
8
votes
0answers
146 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 ...
9
votes
1answer
414 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 ...
8
votes
1answer
290 views
A game of singletons
Alice and Bob play the following zero-sum game, parametrized by two integers $m$ and $k$:
Alice picks $m$ sets, each of which has $k$ items.
Bob colors some items in green.
Bob's score is the number ...
3
votes
3answers
381 views
A faster way to spoil an injection?
Ultimately this is about how primes jump. I will abstract the situation somewhat as there may be related applications which do not spring to my mind.
I want to find small spoilers to Hall's Marriage ...
2
votes
0answers
82 views
Difficulty of 3-color forest Hackenbush
"Forest Hackenbush" (for lack of a better name) is the particular case of the game of Hackenbush where the initial position (and therefore all subsequent positions) is a (finite) forest (:= disjoint ...
6
votes
1answer
177 views
Maximum $2$-D bootstrap percolation time for $n$ points on an $n\times n$ grid
I hesitate to ask this question here, but since it remained unanswered after a bounty on MSE, I ask it here with some reservation.
Is the maximum bootstrap percolation time for $n$ points on an $n\...
4
votes
0answers
247 views
A game played on binary matrices ($2$-dimension coin-turning game)
Let $r\geq 1$ be a natural number. I am interested in the following (two-player, impartial, perfect-information) game:
The state of the game is an $n\times n$ matrix with coefficients in $\mathbb{F}...
9
votes
1answer
314 views
A Combinatorial Game with Integer Sequences
Two players, Alice and Bob, take turns constructing a sequence $a_1,a_2,a_3,\dots$, of distinct positive integers, none greater than a given parameter $K$. Alice plays first and makes $a_1=1$. ...
11
votes
1answer
178 views
A game: building a bounded degree graph
Given positive integers $n$ and $d\leqslant n-1$. Two players build a graph, starting with $n$ vertices and no edges. On each turn, a player joins two yet not joined vertices by an edge. It is ...
9
votes
2answers
537 views
Choosing subsets of $\mathbb R$ of cardinality $\frak c$, who wins?
Consider the following infinite game: two players, I and II, are alternating and choosing a descending sequence of subsets of $\mathbb R$ of cardinality $\frak c$, so I chooses a set $A_1\subseteq\...
6
votes
0answers
129 views
Combinatorial game similar to Sprouts
Is there a name for the following combinatorial game? Is there a solution which player has a winning strategy?
Basically this game is "Sprouts without midpoints". One starts with $n$ points in the ...
0
votes
0answers
136 views
Local Connection Game
A local connection game is given by a set of vertices and graph G where connection is built by adding edges.
If the cost to user a(user at node a) is given by $$C(u)=\alpha n_u + \beta \sum_v(dist(u,...
