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
4answers
73 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
51 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
23 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
361 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
24 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
51 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 ...
9
votes
1answer
418 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
60 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
361 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
511 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
515 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
65 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
83 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
296 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
51 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
236 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
0answers
97 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
32 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
20 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
34 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
53 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
87 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
34 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
31 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
72 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
42 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
20 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
278 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
95 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
125 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
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 ...
1
vote
0answers
26 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
72 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
70 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
92 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
89 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
298 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
67 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
72 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 ...