Combinatorial game theory (abbreviated CGT) is the subfield of combinatorics (not traditional game theory) which deals with games of perfect information such as Nim and Go. It includes topics such as the Sprague-Grundy theorem and is tangentially related to the Surreal Numbers.

learn more… | top users | synonyms

7
votes
3answers
396 views

Winning strategies in multidimensional tic-tac-toe

This question is a result of having too much free time years ago during military service. One of the many pastimes was playing tic-tac-toe in varying grid sizes and dimensions, and it lead me to a ...
2
votes
1answer
4k views

Game combinations of tic-tac-toe

How many combinations are possible in the game tic-tac-toe (Noughts and crosses)? So for example a game which looked like: (...
3
votes
1answer
34 views

Proof of XOR properties

I want to prove the following two properties of the Nim-sum/XOR operator $\oplus$ to better understand Nim games. For the position $n = a_1 \oplus a_2 \oplus a_3 \oplus \cdots \oplus a_k = 0$, ...
2
votes
2answers
61 views
1
vote
1answer
32 views

On a possibility/impossibility of a certain twisted situation in a tournament

Recently I encountered the following puzzle: Consider a game for two players which can only result in a win of one of the players (no ties). Now $n$ players decided to play this game each with ...
3
votes
0answers
54 views

Can this game end in a draw?

We have this game: Clarifications: Pawns can move and take across sides. Pawns can't jump over other pieces when moving by two squares. "Forward" means from the middle of your side towards the ...
5
votes
1answer
651 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 ...
2
votes
0answers
18 views

Finitely many steps to $n$-stone pile.

I have a combinatoric problem still unsolved: $2n$ ($n$ is a positive integer) stones are divided into $3$ piles. In each step, we pick half of a pile which has even number of stones and move those ...
0
votes
1answer
128 views

Counting Game Question, 2 players

Players A and B play the following game. Two integers, m and n, are written on the board. On each turn, a player selects one of the numbers on the board, erases it, and writes down a positive divisor ...
2
votes
1answer
71 views

Strategy set in Tic-Tac-Toe [closed]

I read in a book that the cardinality of the strategy set of the first player in a game of Tic-Tac-Toe is approximately equal to $10^{126}$ but I cannot see how to arrive at this result. Disclaimer: ...
1
vote
1answer
52 views

The Thirty-one Game: Winning Strategy for the First Player

I am going through UCLA's Game Theory, Part I. Below is an exercise on page 6: The Thirty-one Game. (Geoffrey Mott-Smith (1954)) From a deck of cards, take the Ace, 2,3,4,5, and 6 of each suit. ...
1
vote
0answers
36 views

Games based on sheaves (or sheaf gluing?)

my question is quite simple (and I hope it is NOT stupid). It is well-known that many successful games have clear mathematical underpinnings (see for example http://web.mit.edu/sp.268/www/rubik.pdf ...
10
votes
4answers
2k views

Adding digits to make a number prime or composite

Players A and B alternate writing one digit to make a six-figure number. That means A writes digit $a$, B writes digit $b$, ... to make a number $\overline{abcdef}$. $a,b,c,d,e,f$ are distinct, $a\...
5
votes
1answer
1k views

How many different chess-board situations can occur?

If you play a standard chess game on a normal $8 \cdot 8$ chess board with the usual rules: How many different "board representations" can exist? Upper bound: Well, you have 16+16 = 32 chess pieces ...
-2
votes
1answer
26 views

Combinatorics in a restaurant

In a restaurant menu there are 6 types of drinks : Coca cola , lemonade , sprite , wine , tea and diet sprite . How many people need to order a drink to ensure that at least one drink would be ...
3
votes
2answers
117 views

Binary encryption puzzle

There are 8 rooms, one containing a pot of gold. You know which room the gold is in, but your partner does not. The task is to inform your partner which room the gold is in under the following ...
1
vote
0answers
20 views

Results about high dimensional Tic-Tac-Toe game strategy

I read the book 'Tic-Tac-Toe Theory (author : Jozsef Beck)', and saw the author's mention like this. "we know only two explicit winning strategies in the whole class of $n^d$ Tic-Tac-Toe games: the $...
1
vote
1answer
34 views

A question about interval operation result in a game

A state is:$A_{q}=(A_{q}^{0},...,A_{q}^{E})$ where $A_{i}^{j}$ is interval, $q$ and $E$ are positive integer The initial state is $A_{m}=((0,1),\emptyset...,\emptyset)$ , $m>E$ Procedure: Every ...
1
vote
0answers
27 views

Proving that problem of finding the winner in symmetrical game is in NP

Recently, I've stuck in quite an interesting problem. Here's its full description: Consider a connected, non-directed, weighted graph G. In some $v \in V(G)$ stays a chip. Two players are playing ...
0
votes
0answers
21 views

Probability of getting a “full house” by rolling dice [duplicate]

In poker, full house means getting three cards with the same rank, and another two cards with the same rank (not the same as other three cards). I can understand how to use combination to solve this ...
1
vote
1answer
802 views

Relationship between regular Nim and Lasker's Nim

So I'm trying to do qn $6$ (on pg I-13) about staircase Nim in Game Theory by Ferguson Game Theory, Ferguson and it's asking to prove that $(x_1, x_2, \ldots, x_k) \in P $ only if $(x_1, x_3, x_5, \...
0
votes
1answer
36 views

Calculating the odds of winning a game

Problem: You, the user have 3 lives. In front of you are 5 cups - in each cup there is a piece of paper with 1 random number between 1 and 5 (inclusive) written on it. You must guess the number in ...
-1
votes
1answer
35 views

Two guys pick from $n$ stones, the numbers of stones they can pick lie in a given set S. When the guy who pick first will win?

Alice and Bob take turns to pick stones from a pile of $n$ stones. Each number of stones they pick must lie in a given finite set $S\subset \mathbb{N}$. Who cannot pick will lose. If Alice picks first,...
0
votes
0answers
533 views

Optimal Solution

Players $1$ and $2$ are playing a game. They have a pile containing $N$ coins. Players take alternate turns, removing some coins from the pile. On each turn, a player can remove either one ...
5
votes
0answers
472 views

Create the most 'stressful' tennis game ever!

Some games, such as tennis, use a complicated points system (point, game, set, match; with deuces and tie-breaks) for what would otherwise be an extremely simple and monotonous game. The main reason, ...
1
vote
0answers
117 views

A variation of Nim game

There are two players X and Y . They write N integers on paper ( A_1 , A_2 , A_3 , .... A_N ). They have also p integers (b_1 , b_2 , b_3 , .... b_p ) . Now , Player X always takes turn first . He ...
3
votes
0answers
104 views

Mathematical game with numbers

We invented a mathematical game, which i am going to explain here. The first player choose a natural number, lets call it $n$ (if you play it for real, you must choose a sufficiently big number so ...
3
votes
2answers
553 views

Game involving tiling a 1 by n board with 1 x 2 tiles?

Consider a $1$ by $n$ tiled rectangle. You want to play a game with one opponent in which you place $1$ by $2$ "dominoes" on this rectangle. The player who places the last domino wins. Which player ...
2
votes
1answer
219 views

Tutorials for Sprague-Grundy Theorem/Nimbers?

Help needed in understanding S-Grundy Number , any good tutorial. I am trying to solve Mathalon Problem 146 S-Grundy Game (dead link).
4
votes
2answers
131 views

Variation of Nim, where one has to divide a pile into any number of piles.

I am learning the basics of combinatorial game theory (impartial games). After learning about decompose a game into the sum of games, I feel comfortable with games that can divided into the sum of 1 ...
3
votes
1answer
68 views

Tic Tac Toe: What is the probability that a random player draws against an infallible player?

I have simulated a tournament between an infallible Tic Tac Toe player and one that chooses its moves randomly. Even after 5 million games, the infallible player wins every single game. I know that ...
1
vote
0answers
119 views

Position games: how to fill a matrix with dominos? [duplicate]

Dominos of size $2 × 1$ can be placed on a $m × n$ board so as to cover two squares exactly. Two players alternate placing dominos. The first one who is unable to place a domino is the loser. I can ...
3
votes
2answers
51 views

When can you win this directed graph game?

I am trying to consider the conditions under which you can win the following directed graph game: Directed graph game: At the start of the game, you are given a directed, acyclic graph $G$ with ...
5
votes
2answers
445 views

Notation for surreal numbers

On the sound of sounding ridiculous, but in the line of "There are no stupid quetsions": Is there a way to express $\omega_1$ (and in general $\omega_k$ with $k >= 1$ as a Conway game (that is $<...
5
votes
3answers
270 views

What is the optimal strategy in a game where players subtract 7 or add or divide by 2?

I made up a nim type game where players start with a relatively high number and then for each turn if the number is odd, the player either subtracts 7 from the number or alternately if the number is ...
0
votes
1answer
21 views

Find the Grundy number of the initial position and make the first move in a winning strategy for the following game

Find the Grundy number of the initial position and make the first move in a winning strategy for the following game: In a pile there are two red balls, four green balls, four blue balls, and six ...
1
vote
0answers
37 views

Check an algorithm to win hex as first player guaranteed

This question has more to do with the validity of the alogirthm than help per se. I'm unsure if this works with all board setups or just this one, or if it's valid at all. I'm going to start with a ...
0
votes
0answers
30 views

Measure of Connectivity on a Chessboard

I'm programming a boardgame...game. The basic idea of it is there are two players (call them $X$ and $Y$) that are trying to trying to build a wall connecting the North and South, and East and West ...
5
votes
1answer
127 views

Solving the Gobblet game

In 1995 the Connect-4 Game was solved with a brute force approach. Using the standard 6 high / 7 wide grid, first player can force a win in 41 moves. Complexity of the Connect-4 game could be ...
0
votes
0answers
12 views

Is there an extension for sign expansion for any games?

A surreal number can be written as a sequence of $+$ and $-$, called the sign expansion. Is there something similar for any combinatorial games, supposedly with $+$, $-$ and some more symbols? If I ...
1
vote
2answers
178 views

Optimal Strategy for Card Split and Discard game

In a game of 2 players, there are 2 piles of cards. In every turn, a player has to discard one pile and divide the other into two equal parts (as close as possible). The game ends when a player is ...
1
vote
1answer
37 views

Define Grundy values

I want to helt to find out the grundy value to define a winning strategy for this game. Player 1 and 2 starts from position A where player 1 is the first one to move. The arrows show possibles ways ...
0
votes
0answers
145 views

A Combinatorial Game: the Snake and the Hunter

The Snake and the Hunter is a game for two players who play in two rounds interchanging the roles of snake and hunter. The game is played in a rectangular grid of points, say $6 \times 6$. In both ...
2
votes
2answers
113 views

Game: Group and Multi-Dimensional Chessboard

Let $G$ be a group and $S\subseteq G$. Consider a $d$-dimensional chessboard of size $n_1\times n_2\times \ldots \times n_d$, where $n_1,n_2,\ldots,n_d\in\mathbb{N}$. Each unit hypercube of the ...
1
vote
0answers
76 views

Finding a Mathematical definition of a Discrete Time Game

Preface: Suppose we have a game world as depicted in the following figure: Where each of the white blocks is passable, And each of the black blocks is a wall and so impassable. Each of the Green ...
188
votes
0answers
7k views

The Ring Game on $K[x,y,z]$

I recently read about the Ring Game on MathOverflow, and have been trying to determine winning strategies for each player on various rings. The game has two players and begins with a commutative ...
3
votes
0answers
56 views

Candy Crush as an integer programming problem

I'm trying to model the basic version of a match-three game, where the player (has a maximum number of swaps) must swap any two adjacent gems (no diagonals) in an 8x8 grid of gems in order to match ...
0
votes
2answers
61 views

Game of nim in which the number of heaps with odd coins is odd

Consider a Nim game in which the number of heaps with an odd number of coins is odd. Which player can guarantee a win and why? My idea is if the number of piles with an odd number of coins is odd ...
5
votes
1answer
127 views

Game: two pots with coins

Rules of the game with two players. First player puts any number of coins in the first pot. Then second player, knowing that number, puts any amount of coins in the second pot. Then they in turns (...
0
votes
1answer
153 views

Misere nim, 2nd player winning strategy proof by induction

I'm having a problem with writing on paper things that I came up with. There's a Misere nim game with n stones, two players, every player can take 1, 2, 3 or 4 stones in one round, the one to remove ...