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.

888 questions
Filter by
Sorted by
Tagged with
37 views

Game of two players on table $20 \times 20$

Game of two players on table 20X20: Player one is starting the game. Each turn he can put red stone on any point $(i,j)$ such that there isn't another stone on $(i,j)$ and there isn't another red ...
19 views

To find the subgame equilibrium

So I am trying to solve the following question: X and Y are dividing a pie according to the following procedure. First, X proposes a division. If Y agrees then the division is implemented. Otherwise, ...
70 views

How to find winning Strategy for 4 celled animals of Harary's generalized tic tac toe

A polyomino is a structure made of unit squares joined along their sides. A single square is called a monomino. Two make a domino. Three join in two different ways to make two trominoes. Let's call ...
262 views

Optimal strategy for river crossing game

Background: the bridge-and-torch game In this bridge-and-torch game, $n$ people are trying to cross a river on a boat that carries at most two people. Each person takes a different amount of time to ...
126 views

Amidakuji Puzzle and math behind it

Ghost Leg (Chinese: 畫鬼腳), known in Japan as Amidakuji (阿弥陀籤, "Amida lottery", so named because the paper was folded into a fan shape resembling Amida's halo1) or in Korea as Sadaritagi (...
68 views

Standard Tic Tac Toe is -- Impartial or Partisan?

I am currently studying basic game theory (combinatorial) and was introduced to impartial games. The "definition" of impartial games I saw was: "An impartial game is a two-player game ...
32 views

Misere Nim rigurous proof

I know that this is the optimal strategy for misere nim game: When played as a misère game, Nim strategy is different only when the normal play move would leave only heaps of size one. In that case, ...
39 views

Generate all stars and bars Combinations with different capacities per bar

I have m "slots" with indivual capacity c_m. Now I want to distribute a certain amount of integer k to those m slots without exceeding their capacity c_m. Such that every slot has a certain &...
15 views

Handling of infinite utility children when backward inducting into a Nature node of a Expectiminimax game tree

Background I am coding a game playing engine for a (3+, but for now assume) 2 player card game, which has a shuffled (AKA random) & face down (AKA hidden) deck. This game has perfect* and complete ...
90 views

32 views

Weighted Nim with Stacks and each player picks from opposite sides

There n stacks of coins. Each stack contains $k_i$ coins and the coins in a particular stack have distinct values. In each turn, you get to pick one coin from the top of any stack, and your opponent ...
48 views

Number of ways Nim-sum is X

Find the number of ways, four distinct piles of stones can be made with each pile containing at least 1 and not more than 9 stones, such that the nim-sum of the four piles is zero. I could only think ...
53 views

This is kind of a crazy question. I was looking up the expected value of a binomial distribution here the other day. I was looking at it in relation to basketball where it is clear if you took $n$ ...
29 views

Find dominating strategies in a game

Problem Colonel Blotto can send each of his five companies to one of ten locations whose importance is valued at $1, 2, 3, . . . , 10$, respectively. No more than one company can be sent to any one ...
44 views

Intuition to move-optimality in Sokoban

The puzzle game of Sokoban has been fascinating to me since I was a child. It is played on a rectangular grid. Each square may be empty ( ) or contain a wall (...
156 views

Is this conjecture about a stick game correct?

My math teacher described the following game and for a few days I have been thinking about it. Let $A$ and $B$ be two perfect players. Let $n$ be a positive integer and let's consider a stick of ...
38 views

Optimal play in Strings & Coins

Consider the following Position of Strings & Coins: (taken from Albert, Michael H., Richard J. Nowakowski, and David Wolfe. Lessons in play: an introduction to combinatorial game theory. CRC ...
43 views

Why aren't all games impartial games?

We can take any partisan game, like Chess, and make it into an impartial game like so: Take the game tree of moves for both players and make each game state a spot on the board. Now we start the game ...
159 views

Does an unsolvable game exist? (And can you formulate an example?)

Let me first of all be more clear by explaining what a unsolvable game is. An unsolvable game is a game which can never be solved, not even hypothetically, because no strategy can force a win if the ...
67 views

Why do we say Treblecross' octal game notation is .007?

I've recently been reading a lot about game theory and octal games, and in the few sources on it I can find, people seem to agree that Treblecross' value is .007. For reference, the game of ...
36 views

Precise statement of Number Avoidance Theorem in game theory

Background: In the book Winning Ways for Your Mathematical Plays on combinatorial game theory, the Number Avoidance Theorem is stated: DON'T MOVE IN A NUMBER UNLESS THERE'S NOTHING ELSE TO DO! (sic.)...
115 views

Proof that there is a winning strategy for player 1 in Chomp.

This question is regarding the game "Chomp" which can be found here: https://en.wikipedia.org/wiki/Chomp My quesiton is regarding the proof that there is a winning strategy, the proof can be ...
135 views