DSA Notes

Math

Game Theory

Label every position as winning or losing for the player to move.

The idea

In a two-player game with perfect play and no chance, each position is either winning or losing for whoever moves next.

A position is winning if some move leads to a losing position for the opponent, and losing if every move leads to a winning one. Positions with no move are losing. Fill the table from the smallest positions up.

When players collect points, store the best score difference the mover can force: f[i][j] = max(a[i] − f[i+1][j], a[j] − f[i][j−1]) for taking from either end of a row.

Sample problem

1025. Divisor Game ↗ Easy

A number n is on the board. Alice and Bob take turns, Alice first. A move picks a divisor x of the current number with 0 < x < n and replaces the number by n − x. The player who cannot move loses. Does Alice win with perfect play?

n = 8
output = true

Why the solution works

Who wins depends only on the number on the board and whose turn it is, so label every number as winning or losing for the player about to move.

A number is winning if at least one move leaves the opponent a losing number. It is losing if every move leaves a winning number, or if there is no move at all.

Fill the table from 1 upward, since every move goes to a smaller number. (The table reveals that exactly the even numbers win, which gives a one-line solution; the table is the method that works for any such game.)

Complexity: O(n²) time for the table, O(n) memory.

Watch out

  • The state must say everything that matters, including whose turn it is when the players have different moves.
  • “Optimal play” applies to both players: never assume the opponent blunders.
  • Get the terminal positions right; everything else follows from them.
Watch it run

Try your own input

Practise on LeetCode