Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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 ...
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 ...
6
votes
1answer
463 views

A different equivalence relation on partizan combinatorial games

The following definitions are fairly standard, but reworded in a way that will be more appropriate for my question (so what follows is fairly long, but should be easy to read for the experts and might ...
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: ...
1
vote
1answer
179 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 ...
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 ...
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' <...
18
votes
1answer
442 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). ...
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 ...
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 ...
9
votes
1answer
319 views

Infinite-dimensional hex

Suppose $n$ players take turns selecting vertices of the grid $[k]^n = \left\{0, 1, 2, \ldots, k-1\right\}^n$. Each player is assigned a pair of opposite faces of the grid, and wins the game if they ...
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 ...
6
votes
2answers
460 views

Determinacy of (infinite, possibly loopy) combinatorial games

I am looking for references and hopefully enlightening proofs of the following statement(s) concerning the determinacy of not-necessarily-well-founded (i.e., possibly infinite, possibly loopy) ...
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 ...
0
votes
1answer
355 views

Infinite board games: sentences about

As a unified approach if we have an ( read any) infinite board game described as $\mathcal{G}$ using a particular axiom set A.. can a sentence be devised in A which automatically answers the basic ...
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 \...
11
votes
1answer
841 views

The infinite X in Conway's game of life

In Conway's game of life, take the initial position to be two infinite diagonal lines of live cells, with a single cell in common. Does this thing converge to a stable configuration? I.e., is the ...
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 ...
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 ...
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 ...
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$ ...
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\...
19
votes
3answers
513 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 ...
54
votes
5answers
7k views

Decidability of chess on an infinite board

The recent question Do there exist chess positions that require exponentially many moves to reach? of Tim Chow reminds me of a problem I have been interested in. Is chess with finitely many men on an ...
91
votes
11answers
12k views

Checkmate in $\omega$ moves?

Is there a chess position with a finite number of pieces on the infinite chess board $\mathbb{Z}^2$ such that White to move has a forced win, but Black can stave off mate for at least $n$ moves for ...
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 ...
16
votes
1answer
1k views

Playing an (invertible) matrix game with two players

Players $A$ and $B$ take an empty $n \times n$ matrix and place, one by one, an element (say, a rational number) in an unoccupied place of this matrix. Player $A$ starts. The game ends if there is no ...
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 ...
14
votes
0answers
709 views

A Combinatorial Game: the Snake and the Hunter

The Snake and the Hunter is a game for two players who play in two rounds interchanging the roles of snake and hunter. The game is played in a rectangular grid of points, say $6 \times 6$. In both ...
4
votes
1answer
265 views

Lights Out game over GF(p)

On Jaap's Puzzle Page http:// www.jaapsch.net/puzzles/lomath.htm#domtilings Theorem 7 says: If standard Lights Out is played on a m x n grid-like board, ...
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, \...
7
votes
2answers
775 views

Square Achievement Game on a Grid

Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an n x n grid. The first player to occupy the vertices of a square with horizontal and vertical ...
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 ...
18
votes
4answers
4k views

David Gale's subset take-away game

I learned of this problem through Su Gao, who heard of it years ago while a post-doc at Caltech. David Gale introduced this game in the 70s, I believe. I am only aware of two references in print: ...
28
votes
1answer
778 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$. ...
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 ...
11
votes
4answers
912 views

a game on numbers

Hello, here is a little two-players game. Players A and B choose three numbers : a, b and c for A, a', b' and c' for B. The values are numbers between 0 and 1, their sum is 1, and they are ordered: $...
17
votes
4answers
2k views

Variation on a matrix game

The original problem appeared on last year's Putnam exam: "Alan and Barbara play a game in which they take turns filling entries of an initially empty 2008×2008 array. Alan plays first. At each turn, ...
12
votes
12answers
7k views

Are there any interesting connections between Game Theory and Algebraic Topology?

I've been learning game theory on my own and was just curious how it connected with previous things I've learned. So are there any interesting connections between Game Theory and Algebraic Topology? ...
43
votes
4answers
6k views

Verifying the correctness of a Sudoku solution

A Sudoku is solved correctly, if all columns, all rows and all 9 subsquares are filled with the numbers 1 to 9 without repetition. Hence, in order to verify if a (correct) solution is correct, one has ...
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), ...
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 ...