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

16
votes
0answers
831 views

Are the moves/rules of standard chess delicately balanced?

           (While the world chess championship is in progress in Sochi...) Is there mathematical evidence that standard chess is somehow ...
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 ...
13
votes
0answers
1k views

Characterizing the surcomplex numbers

Conway showed that the Field of surreal numbers ("${\bf No}$") is the maximal totally ordered Field. Later Jacob Lurie showed that the Group of all partizan games ${\bf Pg}$ is the universally ...
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 \...
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 ...
8
votes
0answers
449 views

A Banach-Tarski game

This is partially inspired by the question https://math.stackexchange.com/questions/1383397/cutting-a-banach-tarski-cake, which I find intriguing if unclearly written. A paradoxical family of subsets ...
7
votes
0answers
1k views

Is there a chess position equivalent to the Collatz conjecture?

Suppose we have an infinite board with a finite number of chess pieces. The question is whether white can checkmate black (without the after 50 moves it is a draw rule). Can you give an explicit ...
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 ...
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 ...
6
votes
0answers
473 views

Number of Configurations in the optimal Hanoi tower

There is a unique strategy how to move $n$ disks from the first rod to the second optimally and it takes $2^n-1$ steps, solution is obtained by simple recursion. I am interested into the following ...
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
0answers
187 views

A winning move for the first player in $3 \times 3 \times \omega$ Ordinal Chomp

I have been trying to analyse the game of Ordinal Chomp played on a $3 \times 3 \times \omega$ board. The rules can be found in the Wikipedia article, briefly: This game is played between two players ...
5
votes
0answers
209 views

Topological Subset Take-Away

David Gale's subset take-away game is a game where two players A and B play with a finite set $S$. Players alternately choose proper nonempty subsets of $S$ such that if a subset is chosen, then none ...
5
votes
0answers
198 views

Generalization of Sprague-Grundy Theorem

In my research on Combinatorial Game Theory, I used a certain theorem that is essentially a generalization of the Sprague-Grundy theorem. Because the result hinges too much on the work of others to be ...
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 ...
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}...
4
votes
0answers
287 views

Why is this transfinite game not determined?

This question originates from the paper On the Axiom of Determinateness by Jan Mycielski, section 7. Given a set $X$ and an ordinal $\alpha$, the author defines a transfinite game of length $\alpha$ ...
4
votes
0answers
135 views

Combinatorial fairness property in division of goods

Given $n$ agents, and $m$ items where $v_i(g) \geq 0$ is the value of item $g$ for agent $i$, does there always exist a partition $A_1, ..., A_n$ of the $m$ items into $n$ sets s.t. for all $i, j \in \...
4
votes
0answers
390 views

SWAT vs Rioters (cops vs robbers variant)

I thought of this while at the Combinatorial Potlatch at Seattle University, where Peter Winkler gave an excellent talk on Cops vs Drunken Robbers. I'll just open it up to the floor. The problem ...
3
votes
0answers
160 views

Does a generalized Queen split the upper P-positions of Wythoff Nim into two new beams of P-positions?

Wythoff Nim is an impartial game where 2 players take turns in reducing the heights of two finite heaps of tokens. Two types of moves are allowed (I) Remove any number of tokens from precisely one ...
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, ...
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 ...
2
votes
0answers
92 views

On subset of Deterministic games

Denote strings $u,v$ from $\{0,1\}^n$. Denote concatenated pair $[uv]$. Denote $$[uv]_{1}=\{[uv]\oplus e_i\}_{i=1}^{2n}$$ collection of pairs with Hamming distance $1$ from $[uv]$ string ...
2
votes
0answers
128 views

Open games formed by pasting together infinitely many clopen games

Throughout, I think of games and their underlying trees as the same: so a "clopen game" and a "well-founded tree" mean the same thing. Fix a sequence of clopen games $\lbrace T_i: i\in\omega\rbrace$. ...
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} \...
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 ...
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' <...
1
vote
0answers
57 views

Does handle reduction determine braid equivalence in quotients of braid groups?

Let $B_{n}$ denote the $n$-strand braid group. Let $G$ be a group generated by elements $x_{1},...,x_{n-1}$. Let $N$ be the smallest normal subgroup of $B_{n}$ such that the mapping $x_{1}\mapsto\...
1
vote
0answers
154 views

A universal framework for Game Theory?

Ever since the seminal work of Von Neumann and Morgestern Game Theory has grown into a formidable sector of pure and applied mathematics. There are all sorts of games: perfect information, ...
1
vote
0answers
138 views

What is known about infinite diminished disjunctive compounds of loopfree partizan combinatorial games?

Background Basic theories of loopy (normal-play) games which may go on forever under the usual disjunctive sum (the game ends when there are no moves available for you in any component on your turn) ...
1
vote
0answers
345 views

Has anyone seen this version of ring toss (combinatorial object) before?

In reference to a question on work of Westzynthius and another question relating to Jacobsthal's function, I have formed a game which I immodestly call Paseman's Ring Toss. I hope that it has been ...
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 ...
0
votes
0answers
62 views

Factorization (separation?) of n-player game into p-player game and (n-p)-player game

When is an n-player game factorizable (separable?) into a p-player game and an (n-p)-player game? Apologies if this is known among game theorists already - but it leads to further questions, ...
0
votes
0answers
1k views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
0
votes
0answers
513 views

Proof of Upper bound of price of anarchy in local connection game

I am looking at the work by Fabrikant "On a Network Connection Game" (http://webcourse.cs.technion.ac.il/236620/Spring2005/ho/WCFiles/FLMPS_netDesign.pdf). This work presents a game-theoretic ...
-1
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,...