Basics of Game States - Resources

Home Courses Resources Problems National Olympiad Contests Leaderboard

Home/Resources/Game Theory/Basics of Game States

Basics of Game States

Game States

Consider a game with a pile of $N$ sticks. Alice and Bob take turns, with Alice moving first. On each turn, a player must remove $1$ , $2$ , or $3$ sticks from the pile. The player who removes the last stick wins.

We represent the state of the game as $(n)$ , where $n$ is the number of sticks remaining.

According to the problem statement:

0 \leq n \leq N

External Problems

Solve these external problems (e.g., from Codeforces) to reinforce the lesson material:

ATCODERA. Very Very Primitive Game

ATCODERA. Zero Sum Game

ATCODERB. Card Game for Two

ATCODERD. An Ordinary Game

ATCODERD. Harlequin

ATCODERD. Prime Sum Game

ATCODERD. The Simple Game

ATCODERF. Dividing Game

CODEFORCESMahmoud and Ehab and the even-odd game

Rating: 800

CODEFORCESEven-Odd Game

Rating: 1200

CODEFORCESSalyg1n and the MEX Game

Rating: 1300

CODEFORCESGame on Permutation

Rating: 1400

CODEFORCESEven Number Addicts

Rating: 1500

CODEFORCESGame On Leaves

Rating: 1600

CODEFORCESPermutation Game

Rating: 1600

CODEFORCES3-Coloring

Rating: 1700

CODEFORCESEat the Chip

Rating: 1600

CODEFORCESDeleting Divisors

Rating: 1700

CODEFORCESStoned Game

Rating: 1800

0 \leq n \leq N

Example

Winning and Losing States

A winning state is a state from which the current player can force a win if both players play optimally.

A losing state is a state from which the current player will lose if the opponent also plays optimally.

So every state of the game can be classified as either winning or losing.

Let us look at the game above:

State $0$ is losing, because no move is possible.
States $1$ , $2$ , and $3$ are winning, because the player can remove all remaining sticks and win immediately.
State $4$ is losing, because every possible move leads to a winning state for the opponent.

This gives the main rule:

if there is at least one move from the current state to a losing state, then the current state is winning;
otherwise, the current state is losing.

Using this idea, we can classify all states one by one, starting from the states where no moves are possible.

For the game above, the states from $0$ to $12$ are classified as follows:

States	0	1	2	3	4	5	6	7	8	9	10	11	12
Result	L	W	W	W	L	W	W	W	L	W	W	W	L

Here, W means a winning state and L means a losing state.

State Graph

Now consider another game with sticks.

At a state $n$ , a player may remove any number $x$ of sticks such that:

$x < n$
$x$ divides $n$

For example:

from a pile of $8$ sticks, we may remove $1$ , $2$ , or $4$ sticks;
from a pile of $11$ sticks, we may remove only $1$ stick.

We can represent the game as a graph:

each state is a vertex;
each valid move is a directed edge from one state to another.

In this game, the process always ends at state $1$ , because no move is possible there. So state $1$ is a losing state.

After classifying all states, we get the following picture, where losing states are marked in red and winning states in green:

N = 7  -> Initial state (n = 7)
Alice removes 3 sticks -> New state (n = 4)
Bob removes 2 sticks   -> New state (n = 2)
Alice removes 2 sticks -> New state (n = 0)