Questions tagged [combinatorial-game-theory]
Two-player turn-based perfect-information games, surreal numbers, impartial games and Sprague-Grundy theory, partizan games
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 ...
25
votes
2answers
1k views
Is there any superstable configuration in the game of life?
This question spins off of Gil Kalai's recent question on Conway's game of life for a random initial configuration.
There are numerous configurations in the game of life that are known to be stable-...
43
votes
7answers
6k views
Conway's game of life for random initial position
What is the behavior of Conway's game of life when the initial position is random? -- We can ask this question on an infinite grid or on an $n$ by $n$ table (planar or on a torus). Specifically ...
8
votes
3answers
1k views
Mathematical model for Hanoi Towers
The strategy for the Hanoi Tower puzzle is quite simple. It is based on parity only. In an $n$-pieces puzzle, $2^n-1$ moves are sufficient to carry the whole pile from one pole to another one. My ...
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 ...
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
3answers
2k views
Motivation and Intuition for Sprague-Grundy Theorem
I have read about Sprague Grundy Theorem and understand the proof of its correctness. However, I am unable to see the motivation behind the definitions. How do Sprague and Grundy know that they should ...
1
vote
2answers
861 views
Generalized Sprague-Grundy Theorem
Hey,
I know what is Sprague-Grundy theorem, but I want to know about generalized Sprague-Grundy (GSG) theorem ( which is used for games with cycles ). Apparently there seems to be very less ...
15
votes
1answer
1k views
Principal maximal ideals in Z[x]/(F)
Is there some irreducible $F \in \mathbb{Z}[x]$ such that $\mathbb{Z}[x]/(F)$ has no principal maximal ideal? Equivalently, is it possible that the $1$-dimensional integral domain $\mathbb{Z}[x]/(F)$ ...
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$. ...
0
votes
1answer
270 views
Equilibrium of random zero-sum game,
Hi,
How to find, or at least express, the equilibrium of a zero-sum game with an $n*n$ payoff matrix (each player has $n$ strategies) and the payoff of the entry $(i,j)$ is $u(i,j)$. $u$ a random ...
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) ...
22
votes
1answer
973 views
Sane bound on number of moves for Maker-Breaker game on $\mathbb R^2$ for $\{0,1,2,3,4\}$
The description below comes from
József Beck. Combinatorial games. Tic-tac-toe theory, Encyclopedia of Mathematics and its Applications, 114. Cambridge University Press, Cambridge, 2008, MR2402857 (...
0
votes
1answer
314 views
a question on game of chess [closed]
In the game of chess,it is a proven fact that either of the three conditions hold:
1)white has a winning strategy
2) black has a winning strategy or
3)either of them can at least force a draw.
It is ...
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 ...
4
votes
3answers
880 views
Generalized tic-tac-toe
We begin with $2n+1$ cards, each with a distinct number from $-n$ to $+n$ on it, face up in between the two players of the game. The players take turns selecting a card and keeping it. The first ...
5
votes
1answer
424 views
Resources-Aware Combinatorial Game Theory
First of all, I preemptively apologize if my question happens to be naive, I am no expert of CGT (or general game theory, for that matter).
Now the question:
**is there such a thing as the study of ...
3
votes
2answers
837 views
The game of removing two vertices in a graph
Consider the following impartial combinatorial game played with finite graphs: A move removes two adjacent vertices; and of course all edges connected with them. The game then continues with the new ...
12
votes
1answer
712 views
Sliding blocks puzzle
Consider a 'game' played on a subset $S$ of an $n^2$ square grid as follows. There are 3 types of pieces, each occupying a square of $S$, 1 green, some red and the rest are blue, a move consists of ...
2
votes
2answers
920 views
2
votes
3answers
1k views
Motivation for the Sprague-Grundy theorem
The Sprague-Grundy theorem states that every impartial combinatorial game under the normal play convention is equivalent to a (unique) nimber.
What does the equivalence relation thus defined tell us ...
3
votes
3answers
633 views
Chomp! without the law of the excluded middle
Consider the following impartial combinatorial game, a generalization of Chomp! as mentioned in the paper by David Gale: At each step, we have a finite partially ordered set $S$. Player I or II ...
1
vote
1answer
701 views
A modified divisor game
Consider a two player game. There are N balls marked 1 to N. A move consists of removing a ball n and all other balls which are divisors of n (including 1). The players alternate the moves. The one ...
191
votes
3answers
11k views
A Game on Noetherian Rings
A friend suggested the following combinatorial game. At any time, the state of the game is a (commutative) Noetherian ring $\neq 0$. On a player's turn, that player chooses a nonzero non-unit element ...
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 ...
17
votes
3answers
1k views
Traversing the infinite square grid
Starting somewhere on an infinite square grid, is it possible to visit every square exactly once, if at move $n$, one must jump $a_n$ steps in one of the directions north,south,east or west, and mark ...
11
votes
2answers
1k views
Can anyone analyze this misere game?
Problem
Let $* = \{0\}$ be the one matchstick nim game, let $*2 = \{0,*\}$ be the two matchstick nim game, let $*3 = \{0,*,*2\} = *2+*$ be the three matchstick nim game, let $g = \{0, *2+*3, *2+*2+*2\...
6
votes
3answers
905 views
Has Sid Sackson's “Hold That Line” been analyzed?
In Sid Sackson's classic book A Gamut of Games, he introduces a game that he calls "Hold That Line." Briefly, it is an impartial pencil-and-paper game played on a finite grid of dots. The first ...
4
votes
1answer
462 views
Graph connectivity related game
I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of ...
-2
votes
4answers
1k views
Breaking down an impartial game into Nim equivalent [closed]
This is the game:
The playing field consists of permutation of numbers. The players take turns playing the game. Each player removes single number from the sequence. The game is finished when the ...
5
votes
1answer
690 views
Algorithmic war
No, not the war on drugs, but the game of War considered in
Does War have infinite expected length?
As noted in that discussion, the game of war can go on forever, but my question is: can it be ...
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 ...
2
votes
7answers
2k views
Nim-like(?) game winning strategy?
I have the following Nim-like game (at least, it seems Nim-like to me).
There are $2k$ tokens in a row, $k \in \mathbb{N}$.
Each token $a_i$ has a value $ v_i \in \mathbb{N}$
All this information ...
8
votes
4answers
1k views
A “rewiring process” on graphs
I am interested in a discrete process defined as follows. We start with a given graph. At each time step we delete an edge $(i,j)$ and add two edges $e$ and $f$; the edge $e$ is incident with $i$ and ...
6
votes
1answer
2k views
Are there any interesting connections between game theory and engineering?
I am doing a senior project and it must be based off game theory, but I am having trouble finding any connections to engineering, possibly structural, or architectural, maybe even civil or mechanical. ...
16
votes
5answers
3k views
Irreversible chess
Suppose we play a chess-variant, where any finite number of pieces are allowed, and the board is as large as we wish, but only two kings in total. And there is no 50 move-rule, no castling and no ...
8
votes
1answer
10k views
Analysis of Misere Nim?
My friend likes to impress people by playing 3-5-7 which has three piles of counters of sizes 3, 5 and 7. You can remove any number of coins from a single pile, the last player to move loses.
ooo
...
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: $...
7
votes
2answers
621 views
Sets as Combinatorial Games
Just a few days ago my seemingly eternal and recurrent fascination for Conway's combinatorial game theory (CGT) & surreal numbers had a recrudescence, so I grabbed this excellent survey, and began ...
0
votes
0answers
511 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 ...
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 ...
23
votes
3answers
2k views
Rolling-ball game
The analyses
in two recent MO questions
("recent" with respect to the original posting in 2011),
"Rolling a random walk on a sphere"
and
"Maneuvering with limited moves on $S^2$,"
suggest a Rolling-...
6
votes
1answer
636 views
Bridge game with only one suit: strategy
This game looks like bridge, but 1- there are only two players Alice and Bob, 2- there is only one suit, whose cards are numbered $1, 2,\ldots,2n$. One deals each player $n$ cards. Therefore Alice ...
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 ...
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
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 ...
4
votes
2answers
407 views
Approximate search space on a 5x5x5 cube with 3 different possible classes?
Hey all,
I read the meta, and I realize this question might be pretty elementary for this site, but I'm having trouble computing this, and I know it won't take too much insight for someone to give me ...
14
votes
2answers
13k views
Winning strategy at chomp (a chocolate bar game)?
The game of chomp is an example of a game with very simple rules, but no known winning strategy in general.
I copy the rules from Ivars Peterson's page:
Chomp starts with a rectangular array of ...
3
votes
3answers
638 views
Probability theory and measuring the true strength of chessplayers
If you wanted to measure the strength of, say, a chess player, the best way would involve knowing the true value of each position: then you could compute the frequency $W$ with which the player finds ...
8
votes
1answer
1k views
A Game of Knights and Queens
Let $m,n,u,v \in \mathbb{N}$ be parameters with $m,n \geq 3$. Suppose two players play a game on a $m \times n$ chess board and we denote the squares of the board by the set of points $ (i,j) $ such ...
