# Questions tagged [combinatorial-game-theory]

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

172 questions
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, ...
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 ...
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: ...
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 ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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\...
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, ...
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 ...
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 ...
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 ...
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?
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).