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

6
votes
2answers
100 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, ...
2
votes
0answers
58 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 ...
1
vote
1answer
55 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
45 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 ...
4
votes
1answer
618 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
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 ...
40
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
45 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 ...
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 ...
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
49 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 ...
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 ...
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
84 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, ...
6
votes
2answers
289 views

Proof of Conway's “Simplicity Rule” for Surreal Numbers

A "number" in the sense of Combinatorial Game Theory is a game $G = \{ a,b,c,\dots | \; d,e,f,\dots \}$ such that $a,b,c < d,e,f$. Then our game is between the left and right options: $$ a,b,c ...
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
300 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, ...
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
187 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: ...
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
181 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) ...
4
votes
1answer
46 views

on a game playable with tokens

Here is a two-player game playable with tokens. At the beginning, all tokens form a single heap. Players must choose among all heaps one of them and cut it in two parts, so that all heaps have ...
1
vote
1answer
53 views

Solving a Recurrence for a Mathematical Game

The problem is: Two players take turns removing coins from a pile. There are initially $n$ coins, and on each turn, a player can remove $a_1, a_2, \dotsc, a_k$ coins. The player who cannot remove ...
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 ...
0
votes
0answers
33 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 ...
0
votes
0answers
43 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 ...
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 ...
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
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 ...
1
vote
1answer
42 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
52 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 ...
1
vote
3answers
1k views

Chance of Winning In Tic Tac Toe

I'm sure everyone knows how to play the game of tic-tac-toe. I have just been wondering what's the probability of winning if one player started his or her move by putting his mark in the middle?
25
votes
1answer
901 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 ...
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
38 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 ...
8
votes
3answers
357 views

A Nim-like game with conditions and strategies

The game: Given $S = \{ a_1,..., a_n \}$ of positive integers ($n \ge 2$). The game is played by two people. At each of their turns, the player chooses two different non-zero numbers and subtracts ...
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, ...
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 ...
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 ...
6
votes
3answers
121 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 ...
0
votes
0answers
28 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 ...