Stack Exchange Network

Stack Exchange network consists of 174 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

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

Game on undirected graphs

One of my friends suggested the following 2-player game. ...
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 ...