# Questions tagged [combinatorial-game-theory]

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.

967 questions
Filter by
Sorted by
Tagged with
1 vote
30 views

### (Combinatorial) Game Theory: Determinacy and Determinism

I am struggling with the concepts of Determinacy and Determinism. Are the following statements correct(for 2-player, zero-sum games)? Or am I getting something mixed up in my head? A game has the ...
• 13
132 views

### Is there a winning strategy in the card removal game?

A and B play a game with blue, red, and green cards. They start with an even number of $n$ blue cards ("stacks"). Player A starts, and the players take turns. Only two moves can be made: (i) ...
• 53
1 vote
51 views

### Game theory question on a 2 player game

Paul and Luke are playing a game with stacks of black, red and green tiles. At the start of the game, there are n stacks of one black tile on the board, where n is any positive integer. Paul begins. ...
1 vote
84 views

### Nim variant with two piles where in each turn the sum of their sizes gets reduced by three

So in this game we have two piles of size n and m respectively. Two players take turns, in each turn the player chooses one pile to reduce its size by 2 and the other gets reduced by 1. For example ...
144 views

### What is the chance of one player winning a chess tournament?

Person A plays a chess tournament against persons B and C. Person B is a professional, while person C is an amateur. Person A wins the tournament if they achieve at least $k$, $k<n$ consecutive ...
1 vote
57 views

### Solving a Certain Combinatorial Game

I've been trying to come up with a combinatorial game even simpler than Hex with non-trivial gameplay and been failing dismally. Currently, my idea is that players sequentially lay pieces on a ...
• 2,246
1 vote
86 views

### What Hackenbush game represents oof? [closed]

I have been reading about Hackenbush recently and have learned that the surreal numbers can be represented using RGB Hackenbush. I am having a hard time understanding On, Off, and Oof. What Hackenbush ...
194 views

### When is "do-almost-nothing" a good idea in CHOMP?

Now asked at MO: The proof by strategy-stealing that CHOMP on a rectangular board is a first-player win involves player 1 taking the top-right square on their first move. Of course given the proof-by-...
• 237k
24 views

### Maximizing Neighboring Count in a Sequential Grid Placement: A Combinatorial Optimization Problem [closed]

Given a 20x20 grid and an initial value of N = 0, we follow a certain strategy to place a piece into each cell of the grid sequentially. Upon each placement of a piece, we calculate the number of ...
37 views

### A graph coloring game of merging subgraphs

A graph coloring game This is a 2-player game played by players $A$ and $B$. A random non-trivial planar connected graph $G(V,E)$ is chosen. Player $A$ sets up the game as follows: Player $A$ ...
• 3,133
43 views

### Jeson Mor chess variant - graph problem equivalent

It is rather a kind of general question, any hints are very pleasant to see :) There is a chess variant called Jeson Mor: https://en.wikipedia.org/wiki/Jeson_Mor. Briefly speaking, the goal of this ...
• 31
205 views

### 4-color coloring game.

Similar to this question. 5-color coloring game. Let there be two players, $𝐴$ and $𝐵$, and a map. They now play a game such that: Player $𝐴$ picks a region and player $𝐵$ colors it such that the ...
• 796
40 views

### Minesweeper sparsity and information processing

I've noticed while playing Minesweeper that when I have too few bombs, I get very easy to play games. In other words, I get games that can be solved with very simple algorithms. When I play games with ...
154 views

### How come $\omega^3=2$ for infinite nimber $\omega$?

The Details: I don't know much about nimbers. It is my understanding that their multiplication is different than ordinary numbers. I'm not sure how to multiply infinite nimbers together; it's given ...
• 43k
61 views

### Translate an extensive form game into normal form game

I have the following problem. It is about how to analyze the coin game and finally find its Nash equilibrium. The coin game: 2 players each get $n$ coins and will play $k$ rounds. Each round each of ...
• 21
1 vote
128 views

### What are some applications of Surreal Numbers outside of Go endgames?

I've read through Don Knuth's book, a fair amount of "Winning Ways for your Mathematical Plays" and watched a handful of videos, and almost all the material seems to talk about definitions, ...
94 views

### Why restricted removal Nim games with 1 pile has pattern (cycle in states)?

I working on solution of NIM-like game, where players take from one piece from 1 to k and players can't repeat previous turn (only the opponent's previous move). Total n stones in beginning. Winner is ...
• 21
1 vote
59 views

### Questions on Sprague-Grundy Theorem

In my current understanding, the idea of Sprague-Grundy is basically: There is Nim space $N$, and regular game space $G$ (which is a DAG where vertices are states and edges are possible actions) By ...
• 21
26 views

### Preperiod and Period of the nim-sequence of Octal Games .17 and .117

This refers to a type of impartial game defined as octal games by Berlekamp, Guy and Conway in the first edition of the Winning Ways books. I noticed that the nim-sequences of $.17$ and $.117$ (first ...
• 1
1 vote
85 views

108 views

### Calculating Prize Line Expectation Part 2

Thanks in advance for any help. Yesterday a very helpful member called @joriki answered my original question on this and that conversation came to a conclusion as a result. I have a second part that ...
163 views

### Colour $2$ or $3$ numbers that total $15$

So my friend comes up and confidently says that he can defeat me in this game: The integers $1$ to $14$ are written down on a blackboard (paper in our case). Players take turns colouring (striking ...
• 2,429
87 views

### Maximize the score of a card game

About the game This game consist on a deck of 24 cards. Each has a color (there are only 3 colors) and a number (from 1 to 8), and each card is unique. Every turn you are given cards (randomly) from ...
197 views

### Combinatorial game greater than its left options and smaller than its right options.

A number in combinatorial game theory is a game $x=\{x^L\mid x^R\}$ such that all its options are numbers and there are no $x^L,x^R$ such that $x^L\geq x^R$. It turns out, after some work, that if $x$ ...
• 1,385
110 views

### Show that player I can always win a Nim game in which the number of heaps with an odd number of coins is odd

Show that player 1 can always win a Nim game in which the number of heaps with an odd number of coins is odd. This question is provided in Richard A. Brauldi's book on Introductory Combinatorics. I ...
• 1,377
63 views

### Reference Request for Combinatorial Game Theory

Some time ago I found a paper, written I believe by Conway, in which the author describes different operations we may perform on combinatorial partizan games and how these operations can be used in ...
• 1,385
1 vote
75 views

### TicTacToe on an NxN Board

I am attempting to find a strategy for the second player that leads to a forced draw in the case of a general NxN TicTacToe game where N fields in a row/column or diagonal are required to win the game....
• 73
100 views

### Does "adding rainbows" eventually stabilize in $\ge 4$-color Hackenbush?

EDIT: now generalized and asked at MO. This is an outgrowth of an earlier MSE question, which itself was motivated by an MO question. An answer to this question is claimed there as well, but the ...
• 237k
111 views

### Tricolor columns-only Hackenbush boards: must adding the "rainbow" board eventually stabilize?

This is a question about "columns-only three-color Hackenbush." Formally, a board is a finite formal sum (or multiset if one prefers) of finite strings from $\{1,2,3\}$. For $i\in\{1,2,3\}$ ...
• 237k
1 vote
28 views

### Find an optimal strategy to win with highest probability in a hat game [duplicate]

The magician gives each of $2^n - 1$ prisoners a hat, which is colored black or white. Each prisoner's hat color is likely to be white as much as it is likely to be black (each prisoner's hat color is ...
• 2,408
150 views

### Hat guessing game optimality of best strategy

Given the following variant of the hat guessing game: There are n players and two colors, everybody has to guess his hat color. The aim is to find a strategy guaranteeing as many correct guesses as ...
• 623
Here is a rephrased version of problem $4$ in BMO $2016$ round $2$. I rephrased to make it clearer and shorter. Given is a triple of digits $(a,b,c)$, where $a$, $b$, $c\in\{0,1,\dots,9\}$. Each turn ...