Dynamic Programming • Game Theory

Game Theory DP

Analyze combinatorial games (like Nim or Stone Game) using DP by evaluating winning and losing states under optimal play.

Overview

In turn-based, perfect-information games, a state is Winning if there is AT LEAST ONE move that forces the opponent into a Losing state.

The core logic: you want to maximize your score, while assuming your opponent will minimize your score on their turn. Both play optimally.

Identify the terminal states. For example, if 0 stones remain and it's your turn, you have no valid moves, making it a Losing state.

Many game theory problems just return True/False. `dp[i]` = True means the player whose turn it is WILL win if `i` items remain.

N=0?

N=1?

N=2?

N=3?

N=4?

N=5?

(A state is WIN if it can reach at least one LOSE state)

Code Tracker

:::

1let dp = Array(n + 1).fill(false);

2dp[0] = false;

3for (let i = 1; i <= n; i++) {

4 for (let move of [1, 2, 3]) {

5 if (i - move >= 0 && !dp[i - move]) {

6 dp[i] = true;

7 break;

8 }

9 }

10}