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

1
vote
1answer
27 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
22 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 ...
0
votes
1answer
35 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
31 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
524 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 ...
1
vote
0answers
114 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
103 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 ...
4
votes
2answers
121 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
65 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
90 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
48 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
3answers
238 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 ...
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 ...
1
vote
0answers
32 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 ...
5
votes
1answer
123 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 ...
0
votes
0answers
135 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 ...
1
vote
2answers
149 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
35 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 ...
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 ...
2
votes
2answers
112 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 ...
3
votes
0answers
54 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
55 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
116 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 (...
2
votes
1answer
61 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 ...
0
votes
1answer
137 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
309 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\}$. ...
1
vote
1answer
222 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 ...
-1
votes
2answers
212 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 ...
6
votes
0answers
73 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. ...
0
votes
2answers
28 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 ...
6
votes
1answer
62 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
77 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 ...
1
vote
1answer
89 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 ...
3
votes
2answers
113 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 ...
9
votes
2answers
303 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 3^...
7
votes
1answer
84 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 "Girl"...
1
vote
1answer
44 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 ...
7
votes
1answer
78 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 ...
8
votes
1answer
161 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 ...
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 ...
1
vote
1answer
263 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 ...
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
6k 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
68 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
72 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 $G^{...
4
votes
1answer
68 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 ...