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
44 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 ...
7
votes
1answer
265 views
+50

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
57 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 ...
3
votes
0answers
225 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?
4
votes
2answers
501 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
506 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
59 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
78 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
278 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
45 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 ...
15
votes
2answers
233 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 ...
-1
votes
0answers
23 views

Finding matrices values

I was trying to teach myself some things about saddle points. This is a little more advance when it comes to finding the number for each matrices and a value $v$ $($say $v=(1/3), (1/3), (1/3))$ ...
4
votes
0answers
95 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
30 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
17 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
33 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
51 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
25 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
83 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
36 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
20 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
30 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
29 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
65 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
26 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
19 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
214 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
89 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
52 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
120 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
14 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
61 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 ...
1
vote
0answers
24 views

Does any $\omega$-cover in which $X \in L(\mathcal U)$ is also a $\gamma$-cover?

As a continuation to this question: An $\omega$-cover, is an open cover $\mathcal U$ of $X$, such that, $X \notin \mathcal U$, and for every finite set $F \subset X$, there exists an open set $U ...
3
votes
0answers
30 views

The point-open game and $\omega$-covers

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 ...
5
votes
3answers
67 views

Weird Card Game Problem

I feel like I know what game this is mimicking but I cannot put my name on its title: There are two players in the game (one is Even, the other is Odd). Even starts off with 30 blank cards, and Odd ...
1
vote
2answers
65 views

Can we construct from $[0,\omega_1)$ a space which is strictly-Frechet with no winning strategy in $G_{np}(q,E)$?

I have asked in here a question which tured out to make no sense. I think I have found the confusion and would like to try and rephrase my question: Let $E$ be a topological space, $q \in E$. ...
1
vote
1answer
38 views

Coin transport chain game

Suppose we have a line of 2013 banks that ends with a vault. The bank nearest to the vault has 1 sack of money, the bank second nearest has 2 sacks. The bank farthest away has 2013 sacks. Jerry ...
1
vote
0answers
66 views

Proof that 12 in a row tic-tac-toe is a tie game?

How can be it proved that tic-tac-toe on an infinite grid (winning with 12 in a row, a column or a diagonal) can always end in a tie (with optimal strategies of both players)? There is a hint: to use ...
2
votes
2answers
91 views

Pi in combinatorial game theory

Here, on slide 27, it says that $\pi = \{3, 25/8, 201/64, ... | 4, 7/2, 13/4, ... \}$ The largest number on the left will be $3 + 1/8 + 1/64 + \dots$ which I evaluated as \begin{align} 2 + (1 + 1/8 ...
2
votes
0answers
85 views

The name of a game from the 2013 Putnam

Does the following game from the 2013 Putnam have an official name? Based on my searches, it seems to have been created just for the exam. Let $n\geq 1$ be an odd integer. Alice and Bob play the ...
0
votes
1answer
265 views

What is the probability of a $4$ appearing in the game $2048$? [closed]

I'm not sure if this is the appropriate SE, so please suggest a more appropriate website if not. I'm making a facsimile of $2048$, and I've just one question I've been unable to work out: what is the ...
4
votes
1answer
59 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
128 views

Are there non-zero combinatorial games of odd order?

Are there any combinatorial games with odd order (under the usual addition of combinatorial games), apart from $0$? In Are there combinatorial games of finite order different from $1$ or $2$? I asked ...
3
votes
1answer
70 views

For which chess boards do solutions exist for this generalised Knight's Tour problem?

We know from a theorem by Schwenk that for any (m x n) chess board with $m \leq n$ it is always possible to create a knight's tour unless one or more of these three conditions are met: m and n are ...
22
votes
8answers
49k views

Maximum board position in 2048 game

A game called 2048 is making rounds on social media. I am trying to determine the maximum score attainable for this game. Let's assume WLOG that only 2s are returned (if 4s are possible the max score ...
3
votes
2answers
62 views

Are there combinatorial games of finite order different from $1$ or $2$?

Are there any combinatorial games whose order (in the usual addition of combinatorial games) is finite but neither $1$ nor $2$? Finding examples of games of order $2$ is easy (for example any ...
2
votes
2answers
119 views

Winning a restricted game of Nim?

Given the following piles, find the Grundy number of the initial position and make the first move in a winning strategy given that no more than two sticks may be removed from a pile at any time. Pile ...
1
vote
1answer
59 views

Determining Grundy Numbers for an inverted takeaway game

Given the following game, I need to determine a winning strategy and find the set of positions in the kernel. I figure the best way to do so would be with Grundy numbers. Rules: The game consists ...