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

0
votes
1answer
16 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 ...
1
vote
0answers
21 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
27 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 ...
4
votes
1answer
110 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 ...
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 ...
0
votes
0answers
11 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
51 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
30 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 ...
2
votes
1answer
208 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).
0
votes
0answers
127 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
110 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 ...
179
votes
0answers
6k 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 ...
2
votes
0answers
46 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 ...
1
vote
1answer
607 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, ...
4
votes
1answer
638 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 ...
0
votes
2answers
48 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
101 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
32 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 ...
2
votes
1answer
46 views

Alice and bob xor nim game

Alice and Bob are playing a game. The rules of this game are as follows: Initially, there are $N$ piles of stones, numbered $1$ through $N$. The i-th pile contains $A[i]$ stones. The players take ...
2
votes
1answer
207 views

More than Nim (combinatorics problem)

A two-player game is played with two piles of stones, with sizes m,n. On a player's turn, that player can remove any positive number of stones from one pile, or the same positive number of stones from ...
6
votes
1answer
231 views

A game problem- double or increment by 1

Its a two player game. Initially $P=1$, and there is some fixed integer $Q>1$. A valid move consists of either increasing $P$ by $1$ or doubling it iff on doing so $P$ does NOT exceed $Q$.The ...
2
votes
1answer
212 views

Winning strategy of a game

The following is a game on monomials. Let $M(X,Y)$ denote the set of all monomials in $X$ and $Y$, i.e., $$ M(X,Y)=\{X^aY^b\mid(a,b)\in\mathbb{N}^2\}, $$ where $\mathbb{N}=\{0,1,\dots\}$. ...
9
votes
2answers
206 views

Factorization game, can we find winning strategy?

I'm thinking about a game theory problem related to factorization. Here it is, Q: two players A and B are playing this factorization game. At very first, we have a natural number $270000=2^4\times ...
1
vote
1answer
131 views

Determine optimal strategy in board game

We have a $25 \times 25$ board and two players. The fields of the board are numbered like this: From $0$ to $24$ from west to the east, and from $24$ to $0$ from north to the south. The first ...
2
votes
2answers
144 views

Reverse Hex board game winning strategy

I just wanted to know the winning strategy to this question: In a reverse Hex board game I know it means where the player who first forms a path between his/her edges loses. Find a winning ...
4
votes
1answer
156 views

Who has a winning strategy in “knight” and why?

Perhaps, this game is already known, but I did not find anything about it, I call it "knight". The rules : Player 1 chooses the starting square of a knight on a normal 8x8 - chessboard. The ...
6
votes
0answers
63 views

Game, stealing edges in a graph.

I was inventing a problem for a math contest, I was really pleased with it, but then I found a mistake in my solution and have not been able to solve it. It is as follows: Alice and Bob play a game. ...
-1
votes
2answers
120 views

Finding p positions with 2 subtraction sets in the take-away game [closed]

Find the set of P-positions for the takeaway game with the subtraction sets: $S = {1,3,5,7}$ $S = {1,2,4,8,16,32}$ Who wins each game when there are 100 tokens on the table to start, the first or the ...
0
votes
2answers
24 views

What does “1/2 positive advantage” mean in Hackenbush?

I'm currently reading "Winning Ways for Your Mathematical Plays" at http://annarchive.com/files/Winning%20Ways%20for%20Your%20Mathematical%20Plays%20V1.pdf. I'm on page 5, and I don't really ...
1
vote
1answer
82 views

How to find periodicity of a nim sequence?

I am trying to solve a problem which is a simple algorithmic game. Link to the problem - https://community.topcoder.com/stat?c=problem_statement&pm=6856 I have basically figured out that for ...
6
votes
1answer
58 views

Are all nimbers included in the surreals?

I guess the question says it all. The **nimber* (https://en.wikipedia.org/wiki/Nimber) concept, sometimes called "Sprague-Grundy numbers" embodies the "values" of positions in impartial games which ...
2
votes
2answers
75 views

Placing circles inside of a regular polygon.

Alice and Bob play the following game: on a table there is a regular $n$-gon. On each person's turn, they are required to place a circle of radius $r$ fully in the interior of the $n$-gon such that it ...
3
votes
2answers
97 views

Game-winning strategy

Player A and Player B are playing a turn-based game. At the beginning of the game there are $N(N \ge 3)$ points in a plane. In each turn one of the players chooses exactly $3$ different points and he ...
7
votes
1answer
81 views

Polynomial game problem: do we have winning strategy for this game?

I'm thinking about some game theory problem. Here it is, Problem: Consider the polynomial equation $x^3+Ax^2+Bx+C=0$. A priori, $A$,$B$ and $C$ are "undecided", yet and two players "Boy" and ...
1
vote
1answer
42 views

Nimber multiplication

In the question on nimbers, the original poster asks for the meaning of Nimber multiplication in the context of impartial games. Edit: As noted by Mark Fischler in the comments below, the following ...
3
votes
1answer
2k views

Counting to 21 game - strategy?

In a game players take it in turns to say up to 3 numbers (starting at 1 and working their way up) and who every say's 21 is eliminated. So we may have a situation like the following for 3 players: ...
4
votes
1answer
95 views

Winning Strategy with Addition to X=0

Problem: Two players play the following game. Initially, X=0. The players take turns adding any number between 1 and 10 (inclusive) to X. The game ends when X reaches 100. The player who reaches 100 ...
7
votes
1answer
75 views

What is the winning strategy for this Game on the Power Set

Given a finite set, players alternately choose proper subsets. Once a subset has been chosen, none of its subsets may be chosen later. The last player to move wins. I figured out that, with optimal ...
7
votes
1answer
155 views

Proving that one has solved chess by exhibiting the zeroes of polynomials over finite fields?

My question is based on one of Scott Aaronson blog post which states that a God-like being could convinced the villagers, to any degree of confidence, that she has solved chess by answering a few ...
7
votes
2answers
109 views

Characteristic 3 analogue of nimbers?

Finite nimbers are a way of turning the natural numbers (finite ordinals) into a characteristic 2 field. Addition in this field is found by writing the numbers in binary and adding without carry, ...
1
vote
1answer
177 views

References on a game with white and black stones

I'm looking for references on this game (name, strategies analysis, ...) : It's a two player game with two players (Black and White) A position of the game is a single line (sequence) of black and ...
0
votes
1answer
53 views

Will cows win always if both play optimally?

There is a green rectangular grid of size $n \times m$ with $k$ cows in it. The objective of the cow is to escape the field. If any one of the cows escape, all cows are set free. There is a farmer ...
2
votes
1answer
31 views

Switching balls among 3 piles

There are 3 piles of balls. Each hour, I take a ball from one pile and move it to another. The amount of points I earn from this move is the amount of balls in the pile I took the ball from minus the ...
42
votes
4answers
5k views

Sharing a pepperoni pizza with your worst enemy

You are about to eat a pepperoni pizza, which is sliced into eight pieces. Each pepperoni will unambiguously belong to some slice (no pepperoni is "between" slices). The caveat is that you have to ...
1
vote
1answer
65 views

Placing stones on vertices of polygon

We have an $n$-gon with $n\geq 3$. Players $A$ and $B$ place a stone alternately on one of the unused vertices that is not adjacent to a vertex with a stone. The player who cannot move loses. Who has ...
3
votes
2answers
70 views

Game with coloring squares in rectangular board

Bob and Susan play a game on an $a\times b$ board by alternating turns. In each turn, the player chooses a square comprising only uncolored cells, and color all of the cells. The first player who is ...
1
vote
1answer
25 views

Clarification in Siegel, combinatorial game theory

On page $65$ of Combinatorial Game Theory by Siegel, under the section of Dominated and Reversible Options, there is this part which I do not understand: Consider $G^{L_1R_1L}-G$. By assumption ...
4
votes
1answer
56 views

Game of Polite Chocolate

I'm starting to play around with some properties of combinatorial games, and I am having problems formalizing an argument based around the game of polite chocolate. There is an $n \times m$ grid of ...
2
votes
0answers
42 views

The hardest game of mahjongg

I was playing Mahjongg solitaire the other day. It got me thinking... The board has $2n$ pieces at the beginning and assuming that the game is winnable. The game would be trivial if there would be ...