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
0answers
16 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
32 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 ...
1
vote
1answer
768 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, \...
5
votes
1answer
648 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
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
32 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 ...
6
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 ...
5
votes
0answers
470 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
116 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 ...
3
votes
2answers
546 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
218 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
122 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
94 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
49 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
438 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
243 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
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 ...
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
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 ...
1
vote
2answers
153 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
36 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
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 ...
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 ...
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 ...
189
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 ...
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
118 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
140 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
64 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
309 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
326 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
313 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
307 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^...
1
vote
1answer
226 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
154 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
170 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
74 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
217 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
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 ...
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 ...
6
votes
1answer
63 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 ...