# Questions tagged [combinatorial-game-theory]

Two-player turn-based perfect-information games, surreal numbers, impartial games and Sprague-Grundy theory, partizan games

**1**

vote

**2**answers

5k views

### How many winning configurations can you have in a nxn Tic-Tac-Toe game where players win if a they get n/2 in either a row or column, consecutively.

Just today I had a bet with my friend over the following problem:
How many winning configurations can you have in a nxn Tic-Tac-Toe game where players win if a they get n/2 in either a row or column, ...

**16**

votes

**1**answer

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 ...

**18**

votes

**4**answers

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:
...

**9**

votes

**2**answers

904 views

### 1..n game, how to analyze?

I came up with a simple game.
A permutation of 1..n is available for purchase in that order. 2 players each have m in money each to bid for one number at a time in the permutation in order and will ...

**3**

votes

**1**answer

938 views

### Sprague-Grundy sequence for the ruler game

Consider the game "Ruler", which is defined as follows. We start with finitely many coins in a line. A move in this game consists of turning over any number of coins, but they must be consecutive, ...

**2**

votes

**1**answer

3k views

### The game of “nimble” with no stacking

The game of Nimble is played as follows. You have a game board consisting of a line of squares labelled by the nonnegative integers. A finite number of coins are placed on the squares, with possibly ...

**8**

votes

**3**answers

674 views

### Choosing lines and points in D^2

I recently heard of a game between two players "Line" and "Point" and wanted to look for more information on it. However, without knowing the name of it (if it has one) finding more information is ...

**7**

votes

**1**answer

984 views

### Game: Avoid the Gaussian primes

Here is a 2-player game played on a region of the
Gaussian integers, $\mathbb{Z}[i]$.
Initially four points are colored, opposite
corners of an $X$ by $Y$ rectangle:
$0 + 0i$ and $X + Yi$ are colored ...

**25**

votes

**1**answer

2k views

### Who wins this two-player game based on the sandpile model?

Given a connected graph $G$, two players, Blue and Green, play the following game: initially, all vertices are unclaimed. Players alternate turns. On her turn, Blue adds a token to either an ...

**7**

votes

**2**answers

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 ...

**7**

votes

**5**answers

878 views

### A Transversal 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 (if any) to occupy some transversal (i.e., a set of n cells having ...

**7**

votes

**1**answer

594 views

### A Game on a Finite Projective Plane

Two players Oh and Ex alternately choose points of a finite projective plane.
The first player (if any) to make a line in his/her chosen points is the winner.
Using the Erdos-Selfridge theorem, we can ...

**54**

votes

**5**answers

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 ...

**47**

votes

**4**answers

8k views

### Do there exist chess positions that require exponentially many moves to reach?

By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an $n\...

**22**

votes

**6**answers

3k views

### Neutral tic tac toe

I heard this puzzle from Bob Koca. Suppose we play misere tic-tac-toe (a.k.a. noughts and crosses) where both players are X. Who wins?
That particular puzzle is easy to solve, but more generally, ...

**13**

votes

**1**answer

625 views

### Bipartite Nim-Geography

Two players are playing a game on a bipartite graph where all of the edges are nim-heaps of various sizes. A token starts on one of the vertices, and on your turn you must move the token over an edge ...

**14**

votes

**1**answer

1k views

### Mathematical solution for a two-player single-suit trick taking game?

The question on games and mathematics that appeared recently on mathoverflow
(Which popular games are the most mathematical?)
reminded me of a problem I encountered some time ago : starting with the ...

**3**

votes

**4**answers

491 views

### proving two partizan games are equivalent

Is there any equivalent version of the Sprague-Grundy theorem (that states that every impartial game under the normal play convention is equivalent to nim) for partizan games?
More specifically, are ...

**7**

votes

**5**answers

2k views

### Just starting with [combinatorial] game theory

I have recently become interested in game theory by way of John Conway's on Numbers and Games. Having virtually no prior knowledge of game theory, what is the best place to start?

**15**

votes

**5**answers

2k views

### Nimber multiplication

Is there a game-theoretic interpretation of nimber multiplication? There is such for addition (a single move in a+b is either a move in a or a move in b).

**12**

votes

**12**answers

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? ...

**17**

votes

**4**answers

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 ﬁrst. At each turn, ...