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
17 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, ...
1
vote
1answer
19 views

CGT: value of sum game is sum of values of games

I am involved in a little study about combinatorial game theory. The study makes heavy use of the fact that, at least in a simple combinatorial game called domineering, the value of the sum game is ...
1
vote
2answers
52 views

Probability that 20 sided die beats 12 sided die with reroll

Alice rolls a 12 sided die (the faces labeled 1 through 12) and Bob rolls a 20 sided die (the faces labeled 1 through 20). After seeing their roll (but not the other person's roll), each person can ...
0
votes
0answers
9 views

countable subset of surreal games

Surreal numbers are the largest possible structure to have a complete order. Games are an extension of the Surreals which only admits a partial order. Along with being larger, smaller or equal to each ...
14
votes
1answer
450 views

How many possible board states in 2048?

I recently found out about the famous 2048 game. For those of you who don't know how it works, it consists on a 4x4 board on where tiles which are powers of 2 are placed. On every turn, you "swipe" ...
1
vote
0answers
52 views

Distribute the gold, silver and bronze

A pirate ship has 2015 treasure chests (all chests are closed). Each chest contains some amount of gold, some amount of silver and some amount of bronze. To distribute the gold, silver and bronze the ...
0
votes
0answers
11 views

Mex and Grundy Numbers explanation

I've been reading this small tutorial on Nimbers and game theory. Could someone explain why the mex rule governs the nimber of a game position? See: http://en.wikipedia.org/wiki/Mex_(mathematics) ...
4
votes
1answer
34 views

Optimal strategy for this Nim generalisation?

Consider the following game: There are a number of piles of stones. On each turn a player can remove as many stones he likes (at least 1) from up to $N$ piles (at least 1). It is allowed to remove a ...
18
votes
2answers
332 views

Game involving points on $[0,1]$

You're given a list of $22$ points in $[0,1]$ (not necessarily distinct), and you're asked to select, at every iteration, $2$ points to be substituted by their midpoint. After $20$ iteration, you ...
5
votes
2answers
72 views

Winning strategies in multidimensional tic-tac-toe

This question is a result of having too much free time years ago during military service. One of the many pastimes was playing tic-tac-toe in varying grid sizes and dimensions, and it lead me to a ...
1
vote
1answer
29 views

Algorithm to multiply nimbers

Let $a,b$ be nimbers. Is there an efficient algorithm to calculate $a*b$, the nim-product of $a$ and $b$? The following rule seems like it could be helpful: $$ 2^{2^m} * 2^{2^n} = \begin{cases} ...
1
vote
1answer
57 views

Iterations of Pascal's Identity

Pascal's Identity states that $n \choose k$ = $n-1 \choose k-1$ + $n-1 \choose k$ since if one element is separated from the rest we can claim that either it is chosen (resulting in $k-1$ elements ...
1
vote
4answers
82 views

Probability of drawing at least 1 red, 1 blue, 1 green, 1 white, 1 black, and 1 grey when drawing 8 balls from a pool of 30?

Given a pool of 30 balls (5 of each color). When drawing 8 balls without replacement, what is the probability of getting at least one of each color? Related: Probability of drawing at least one red ...
1
vote
1answer
61 views

Subtraction Game

I recently read about the Nim Subtraction Game. I have a variant, Suppose you have N stones and two players Alice and Bob, who can choose to pick either 1 stones or K stones. If Alice plays first when ...
0
votes
1answer
24 views

Bernouilli trial with variable number of experiments

I'm kinda stuck on a probability problem I encountered in designing a game. Here is its description : I'm calculating the number of turns (Tf) before a integer variable (A) reaches 0. Each turn, A ...
6
votes
6answers
371 views

Brain teaser Strategic choice… [closed]

$X$ and $Y$ are playing a game. There are $11$ coins on the table and each player must pick up at least $1$ coin, but not more than $5$. The person picking up the last coin loses. $X$ starts. How many ...
2
votes
1answer
32 views

2 player game subtracting perfect squares from a given number

this is my first question on these forums. I apologize in advance if I've overlooked a rule or done something wrong. Unfortunately, I can't remember where I came across this problem, but it's been ...
1
vote
1answer
58 views

Proving something about the Game Nim

I was reading Elementary Number Theory and Its Applications by Rosen wherein I came across the problem (located on Page 31 summarized below) Consider the Game Nim. In this game there exist a finite ...
8
votes
1answer
431 views

Breaking chocolate bars game

About two weeks ago, a friend of mine taught me the following game without his knowing the answer. It may be famous, but I haven't known it. There are $N\ (\in\mathbb N)$ chocolate bars composed of ...
1
vote
0answers
63 views

Number of ways to make first move

Alice and Bob are playing a game. They have N containers each having one or more chocolates. Containers are numbered from 1 to N, where ith container has A[i] number of chocolates. The game goes like ...
6
votes
1answer
395 views

Optimal Tic Tac Toe algorithm without lookahead

Is there any algorithm for tic tac toe that does not rely on a lookahead algorithm that is perfect for any sized boards? Edit: For boards larger than $3 \times 3$, we have to find the best move for ...
4
votes
2answers
538 views

John Nash's Hex proof

I am reading a book on Combinatorial Game Theory that describes a proof by John Nash that Hex is a 'first player' win, but I find the proof very confusing. This proof uses a strategy-stealing ...
10
votes
1answer
535 views

Solving Chess - alternatives to brute force

It is well known that solving Chess is practically impossible using brute force methods. I'm interested to know if there have been any serious attempts using alternate methods. What theory and ...
5
votes
1answer
71 views

How can a Devil catch a Fool in the Angel and Devils game?

The Angel and Devils game (http://en.wikipedia.org/wiki/Angel_problem) is a two-player game, played on an infinite chessboard (i.e. the integer coordinates of $\mathbb{R}^2$). One player is the angel, ...
4
votes
1answer
89 views

A game with stones and finding the winning set

For a positive integer $n$, two players $A$ and $B$ play the following game : Given a pile of $s$ stones, the players take turn alternatively with $A$ going first. On each turn the player is allowed ...
16
votes
2answers
324 views

The expected outcome of a random game of chess?

Imagine a game of chess where both players generate a list of legal moves and pick one uniformly at random. Q: What is the expected outcome for white? 1 point for black checkmated, 0.5 for a ...
1
vote
2answers
59 views

Complete vs Perfect infomation in Combinatorial game theory

In their book "Winning Ways for Your Mathematical Plays", Berlekamp, Conway, and Guy used as the 7th condition for a combinatorial game "Both players know what is going on; There is complete ...
16
votes
2answers
245 views

A game on a graph

Alice and Bob play a game on a complete graph ${G}$ with $2014$ vertices. They take moves in turn with Alice beginning. At each move Alice directs one undirected edge of $G$. At each move Bob chooses ...
4
votes
1answer
103 views

Saddle Points on Matrices

Let $n$, $m$ be positive integers. Suppose that $A$ is a $2$ x $n$ or an $m$ x $2$ matrix and that it has a saddle point. Show that among the saddle points of $A$ there exists at least one which ...
0
votes
0answers
30 views

Matrix Saddle Points and Dominance

I was teaching myself about dominance relations and saddle points after a friend of mine started discussing it with me and how it can be used in games. I wanted to know how to prove a problem like ...
0
votes
1answer
39 views

A nim-game variant

Suppose a bucket contains n balls. In each turn one removes some balls k from the basket. If first player removes even-number balls then second player must removes odd-number of balls and vice-versa. ...
0
votes
1answer
22 views

Upper bound on number of starting positions of a grid coloring game

Let's play a game! The game has the following rules: Let $G$ be a $N\times N$ grid. To each grid square $(x,y)\in G$, assign either $true$ or $false$; call this mapping $C$ (that is, if $(x,y)$ is ...
1
vote
1answer
35 views

Probabilistic game

Suppose a rich person offers you $\$1000$ and says that you can participate in $1000$ rounds of this game: In each round a coin is flipped and you get a $50$% return on the portion of your money that ...
2
votes
1answer
59 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 ...
1
vote
1answer
26 views

Card probabilities with conditional probability

What is the probability that two hands of 13 cards dealt from a normal shuffled pack of 52 cards contain exactly two kings and one ace? What is the probability that both contain exactly one ace given ...
1
vote
2answers
90 views

Hex game winning strategy

I was teaching myself how to play a hex board game by reading some books a couple days ago. I learned how to do $2$ x $2$ and $3$ x $3$ hex games by starting at the principal diagonal. I wanted to ...
1
vote
0answers
37 views

What is the optimal strategy?

There are $m+n+1$ cards numbered $1,2,\ldots m+n+1$. Participants A and B respectively get $m$ and $n$ cards. Meanwhile, they only know what they get. The remaining card is face down on the desk. ...
2
votes
1answer
21 views

How to represent a job-sequencing?, with binary code

Suposse a job sequence of 6 jobs, as 3-5-4-2-6-1, that point the job 3 is attended in 1st place, and then the job 5,.... How could I represent this sequencies with binary code to use in metaheuristic ...
1
vote
0answers
35 views

How many lines needed to not lose in tetris game?

Suppose we play a tetris game with tetris be given randomly. Is there exists a number of lines that we can play infinitely, i.e. do not lose the game?
2
votes
0answers
32 views

Computation of a 3-dimensional game matrix

For natural numbers $n_1 \leq n_2 \leq n_3$ we define $\beta(n_1,n_2,n_3)$ recursively to be the smallest natural number which is not among the numbers $\beta(m_1,m_2,m_3)$, where $m_1 \leq n_1 \leq ...
4
votes
1answer
80 views

How many possible game boards(game states) of tic tac toe n x n is possible?

If I have board of size n x n in tic tac toe and I have used one field to put cross there like below ...
0
votes
0answers
55 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 ...
0
votes
0answers
22 views

de Bono's L-game modification

I am trying to find out if a simple modification od de Bono's L-game is still infinite if two players are perfect. Modified rule is that there no neutral pieces but, there is one piece for each player ...
2
votes
0answers
326 views

What is the highest possible score in 2048 hard?

There is a variant of the popular game 2048, called 2048 hard or 2048 impossible, which automatically places each new tile in the hardest possible location. Is this variation possible to solve, and if ...
0
votes
0answers
26 views

Interesting Probability Game With Uneven Return Scenarions

Let say we play a game. The game which spans the course of 5 trials. The game is as follows. You either receive 100 points or 40 points as a final payout. The only time a payout of a 100 points occurs ...
1
vote
1answer
109 views

If a game ends after finite number of moves, does it mean that at least one of the players has winning strategy?

Let us consider a game played by two players and if the game reaches some of the ending positions, one of the players is declared a winner. Let us assume that the game has to end after finitely many ...
2
votes
1answer
53 views

Forming a combination that is mathematically possible?

I have to implement an algorithm for a game. I will briefly explain the requirement for the team forming for the game. The game consist of two teams selected randomly from a pool of players. There ...
2
votes
0answers
130 views

What is the optimal strategy for this 2 player game?

Let some finite array of integers is given initially. There is a number k which is initially '0'. In a move, a player will select a number from the array arr[i] and change k to gcd(k,arr[i]). Also, ...
1
vote
1answer
15 views

Pairwise sums in an ordered list

The scenario: In a game with n players, each player has a in individual score and players are ranked accordingly (P1 is the player/score in 1st place, and Pn is last place). Ties are allowed. Next, ...
3
votes
1answer
63 views

The proof of ONE$\uparrow G_{po}^s(X) \Rightarrow$ ONE$\uparrow G_{po}(X) $.

Let $X$ be a topological space. The point-open game $G_{po}(X)$ is defined as folows. It is played by two players ONE and TWO. In the n'th step $(n \in \omega)$, ONE choose a finite subset $F$ of ...