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
0answers
34 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
28 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 ...
38
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
44 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
62 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
21 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
48 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
37 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 ...
3
votes
1answer
75 views

Tetris-esque strategy problem

My friend, while we played tetris, offered me this problem: Suppose we are playing Netris, an edited versiom of tetris. The field is 7 units long and infinitely tall, with a bottom. The only piece is ...
3
votes
1answer
81 views

How many pawns, bishops, rooks or kings can be put on a $n \times n$ chessboard such that they don't threaten each other?

A friend of mine asked me this question and I know this is not easy to solve. I found some informations similar to this question here: https://en.wikipedia.org/wiki/Eight_queens_puzzle; First of all, ...
1
vote
1answer
69 views

Finding the optimal moves for a puzzle.

Let $G = \mathbb{Z}/n\mathbb{Z}$ be the cyclic group of order $n$. Suppose we are given a vector $g = (g_1, \ldots, g_m) \in G^m$ as input along with the sets $S_1, \ldots, S_k \subseteq [m]$. Define ...
0
votes
0answers
157 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: ...
2
votes
1answer
39 views

Conway's Soldiers

I've been working on a modification to the standard Conway's soldiers game. In Conway's soldiers, we have an endless number of soldiers in a grid of squares at and below point 0 North, and I can ...
0
votes
0answers
38 views

Validating a connect 4 board state

All connect 4 states aren't possible. For instance, the number of token of each color should be equal or at most only one should be missing for either color. Discussing with a colleague, he told me ...
4
votes
0answers
92 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 ...
1
vote
1answer
25 views

Game Dealing with Multiplication and Winning Strategy

Two players play the following game. Initially X=1. The players take turns multiplying X by any whole number from 2 to 9 (inclusive). The player who first names a number greater than 1000 wins. Which, ...
1
vote
2answers
180 views

Determine if a 4-tuple exists

Starting with 2,0,0,3, we construct the sequence 2,0,0,3,5,8,6,..., where each new digit is the mod10 sum of the preceding four terms. Will the 4-tuple 0,4,0,7 ever occur? Any help is greatly ...
1
vote
1answer
34 views

Working Backwards to Determine Winning Strategy

There are two piles of candy. One pile contains 20 pieces, and the other 21. Two players take turns eating all the candy in one pile and separating the remaining candy into two (not necessarily equal) ...
0
votes
0answers
32 views

Combinatorial Allocation Problem

The problem I am trying to solve is that there are $m$ distinct items to sell through a combinatorial auction and bids have been received. But for any pairs of bids $b_i(X)$ and $b_i(Y)$, the subsets ...
3
votes
2answers
48 views

Some very particular strictly ordered sequence of numbers

You can construct a sequence of 5 numbers $(a,b,c,d,e)$ with the following rule: $a\in\{1\}$ $b\in\{2,3\}$ $c\in\{3,4,5\}$ $d\in\{4,5,6,7\}$ $e\in\{5,6,7,8,9\}$ How many sequence are strictly ...
0
votes
0answers
42 views

Is there a field size such that it makes perpetual “candy crush”

a.k.a Infinite Candy Crush Background: "Candy Crush Saga" is called a match3, but it has some "special" events that will eliminate all rows, eliminate all "candies" of a particular shape, or even ...
1
vote
1answer
39 views

Nash equilibrium indifference principle

In the Hebrew wiki page on Nash equilibrium there is a reference to an indifference principle which means that once we know the other player uses the equilibrium strategy then the first player can use ...
1
vote
0answers
48 views

Applications of Combinatorial Game Theory

Last semester I took a course on Game Theory over at KTH (Stockholm, Sweden), and within that course we went through both classical and combinatorial game theory. While it was very fun to study ...
2
votes
0answers
44 views

Queen moves — The Squared Chain Puzzle

Karl Scherer made the interesting Squared Chain Puzzle. Start with a $7\times7$ board, with a queen somewhere. Make a legal move with the queen, placing coins over all squares visited. For subsequent ...
3
votes
1answer
49 views

Game theory: power and mod

Given two non negative integers $a, b$. Two players alternate turns. If at any state of the game the two integers are $a\le b$ then the player with the turn can either replace $b$ with $b\bmod a$ or ...
3
votes
2answers
53 views

Is there a last winning position in “Prime Nim”?

Consider a single-pile NIM variant, played under standard (not misere) objective, with the rule that you may remove any prime number from the pile. The winning positions of this game are all numbers ...
2
votes
1answer
40 views

Winning strategy - nim variation

i was reading about different variations of nim game and i'm trying to find winning strategy to one of them: There are n empty places on the circle. Two players are placing their "coins: on empty ...
1
vote
0answers
37 views

Can anyone explain this more clearly?

I'm new to CGT so i might need help but could anyone simplify this and explain it to me please- "set f ⊕ f = 0 for any f. (A nice correspondence can be made if we think back to the original game of ...
4
votes
0answers
51 views

1000 marbles in a line winning strategy [closed]

There is an infinite grid. Two players play a game. Player A places two black marbles in consecutive blocks in his turn, and player B places one white marble in any of the squares. Player A wins, if ...
1
vote
1answer
42 views

The application of Nimbers to Nim strategy

I've been reading about combinatorial game theory, and some works start with the game of Nim. After that, they introduce Nimbers, which are numbers that represent Nim games. So far so good. I get ...
10
votes
2answers
152 views

Game for mathematicians about differentiation of polynomials and subtractions in their coefficients.

I'm in a french puzzle forum and one of us asked this puzzle Game of polynoms. We are having some difficulties solving it for the first case. And we have not begun to think about the generalisation, ...
25
votes
1answer
900 views

What is the optimal strategy in the “Factor Game”?

Edit (Nov 1, 2015): Bounty awarded, but the full question (i.e., what is the optimal strategy) remains open at the time of this update. Consider the Factor Game played as follows: Given a list of ...
1
vote
1answer
44 views

Numbers written on a board

The numbers $1,2,...,n$ are written on a board ($n\in\mathbb N$). In each step we take any two numbers $a,b$, remove them, and write either $a-b$ or $a+b$ on the board. After $n-1$ steps there will be ...
2
votes
0answers
30 views

Number of connected sets intersecting a given set in $\mathbb{Z}^d$

Let $A \subset \mathbb{Z}^d$ and let $|A|$ be its cardinality. Let $F_n(A)$ be the number of connected sets of $\mathbb{Z}^d$ having cardinality $n$ and intersecting $A$ in at least one site. Assume ...
0
votes
2answers
41 views

stacks with odd number of cards

Given $n$ stacks of cards, stack $i$ contains $a_i$ cards ($1\le i\le n$) such that each $a_i$ is odd. Two players $A$ and $B$ play a game. Players alternate turns. In a move, a player takes an ...
1
vote
1answer
29 views

Perfect information game with heap of objects

I have to find the winning strategy for the following game. There is a heap with $N$ objects. Two players take objects in turn, but there is a limitation: if there were taken $K$ objects on previous ...
0
votes
0answers
27 views

Complete derivation for perfect play for Nim?

Does anybody have a proper derivation for Nim? I don't want to see just Nim sums,binary conversions but also why we use those Nim sums and binary conversions,etc. Basically, teach it to me like i'm ...
6
votes
3answers
119 views

Board game on a $m\times n$ board - winning strategy

Two friends, $A$ and $B$, play a game with one single game piece on a rectangular board with $m$ rows and $n$ columns. $A$ begins the game by moving the game piece from its starting point $(1, 1)$ to ...
1
vote
1answer
34 views

Moves to P-positions in Nim

Let $A$ be an N-position in Nim such that all moves to P-positions reqire exactly $k$ tokens to be removed. What can we say about $A$?
0
votes
0answers
48 views

Probabilistic Game Theory

I would appreciate help on the following problem: Problem. You just bought a new a card printer which continuously prints cards in red or blue, chosen independently and uniformly at random. You play ...
1
vote
0answers
20 views

Game Theory Rulerette, Sprague-Grundy Theorem

Here is the question: Rulerette. Suppose in the game Ruler, we are not allowed to turn over just one coin. The rules are: Turn over any consecutive set of coins with at least two coins being ...
-1
votes
1answer
53 views

Probability's Game

The game goes this way: There are 6 players, numered 1 to 6 (Player 1, Player 2,...,Player 6). Player 1 starts the game, he rolls a dice with six faces. If the result (x) of rolling the dice is 1 ...
0
votes
0answers
64 views

Figuring optimal reset/prestige time for idle/incremental game.

Looking a general answer but to explain exactly lets take a practical example the game will be realm grinder. Every reset you restart with extra gem each gem giving % production bonus of gold, the ...
1
vote
1answer
78 views

Arranging objects in special way

Imagine there is a cinema hall and there are $n$ seats and we want to arrange $n$ people with some special conditions on our seats. Each people have number from $1$ to $n$ and clearly our seats is ...
0
votes
1answer
86 views

A nice form of a given function

First let, $\oplus(a_1,a_2,\ldots,a_n)$ denote the bitwise xor of $a_1,a_2,\ldots,a_n$. Define the function $\Delta(a_1,a_2,\ldots,a_n)$ to be the maximum value of $a_i - ...
1
vote
1answer
45 views

Board game - winning strategy

Consider two friends, Alice and Bob, playing a game on a $1000 \times 1000$ board. Alice's game piece consists of a $2 \times 2$ square while Bob has to content himself with $3$ squares put together ...
3
votes
1answer
66 views

What is the optimal losing move?

I had a hard time trying to find the best-suited stackexchange site to ask this question. I'm still not sure whether this is the right place, so please guide me to the right one if you think this is ...
0
votes
0answers
15 views

Upper bound for the number of possible chess positions [duplicate]

I know that the Shannon number is considered to be the lower bound on the number of possible legal positions in chess. Does anyone know if an upper-bound has also been calculated, and what that might ...
0
votes
2answers
154 views

Is there any winning strategy? 2015 and Game with marbles!!!

Two players, Alex and Brad, take turns removing marbles from a jar which initially contains 2015 marbles. Assume that on each turn the number of marbles withdrawn is a power of two. If Alex has the ...
1
vote
1answer
33 views

Can someone please help me understand what a “player set” is in extensive form game

my text defines player set as: In N-player game $g$, each non-terminating node is partitioned into $N+1$ sets $g^0, ... g^N$. These are player sets. However it makes no attempt to identify ...