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

1
vote
2answers
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
1answer
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
4answers
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
2answers
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
1answer
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
1answer
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
3answers
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
1answer
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
1answer
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
2answers
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
5answers
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
1answer
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
5answers
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
4answers
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
6answers
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
1answer
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
1answer
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
4answers
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
5answers
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
5answers
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
12answers
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
4answers
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 first. At each turn, ...