Game / Minimax DP · bigonotes

In a two-player game where both players "play optimally", grabbing the biggest pile each turn can lose, because your move changes what your opponent can do next. Minimax DP asks, from any position, "what is the best score difference the player to move can force?" One function then covers both players.

The idea#

Let diff(state) be (current player's total) minus (opponent's total) from this state on, with both playing optimally. Suppose the current player takes gain and moves the game to next. The opponent is now the current player there, and gets diff(next) in their favor. So:

diff(state) = max(gain - diff(next) for each move).

This works because the game is zero-sum. Whatever is good for the opponent is bad for you by the same amount. You don't need separate "Alice" and "Bob" functions or a turn flag, because the subtraction flips the point of view at every level.

The sign of diff at the start position decides the result: positive means the first player wins, negative means they lose, zero is a tie.

How to spot it#

Look for these signals in the question.

"Alice and Bob take turns", "both play optimally", "return true if Alice wins".
Moves remove items from the ends or the front of a row (piles, stones).
The question is win/lose/tie or a final score, and the input is small enough to memoize positions.

Template#

The state is whatever decides the remaining game: often a start index, sometimes a range or an extra rule value.

diff(state):                     # best (mover - opponent) from here
    if no moves are left:
        return 0
    best = -infinity             # every move might lose points
    for each legal move from state:
        gain = points the mover takes with this move
        best = max(best, gain - diff(state after move))
    return best
memoize diff on its arguments
answer: compare diff(start) with 0

Thanks to the memo, each state is solved once, so the cost is (number of states) times (moves per state).

Pitfalls#

These mistakes cause the most wrong answers.

Writing a turn flag and two separate recurrences. The difference formulation is shorter and harder to get wrong.
Leaving a rule that changes during the game out of the state. The cache then mixes up positions with different options.
Starting best at 0. Every move might lose points (negative values), so start at -inf.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Stone Game

Players take from either end, so the state is the range [i, j] still on the table. This makes it interval DP too. Try piles[i] - diff(i+1, j) and piles[j] - diff(i, j-1), and keep the larger. The first player wins when diff(0, n-1) > 0.

Hint: Stone Game II

The player may take the first X piles for any 1 ≤ X ≤ 2M, then M = max(M, X). Because M changes what is allowed, the state is (i, M). Here it is easier to return the stones the current player collects. With suffix[i] as the total of piles[i:], the mover gets suffix[i] - best(i + X, max(M, X)), maximized over X.

Hint: Stone Game III

Players take 1, 2 or 3 stones from the front, so the state is the start index i of the remaining row: a suffix DP. Grow gain as you try 1, 2, then 3 stones, and stop at the end of the row. Check: [1, 2, 3, 7] gives -1 (Bob), [1, 2, 3, -9] gives 15 (Alice), and [1, 2, 3, 6] gives 0 (Tie).

Hint: Nim Game

Mark small piles as winning or losing for the player to move: a pile is winning if some move leaves the opponent a losing pile. The pattern that appears gives a one-line answer.

Key takeaways#

Return the score difference for the player to move.
diff = max(gain - diff(next)) flips perspective automatically.
Anything that changes the allowed moves (like M) is part of the state.
The sign of diff at the start decides win, lose or tie.

Core idea#

In a two-player game with optimal play, return the best score difference the player to move can force: diff(state) = max(gain - diff(next)). One function covers both players.

Key points#

Greedy fails, because your move changes what the opponent can do next.
The game is zero-sum, so the subtraction flips the point of view at every level.
No turn flag and no separate "Alice" and "Bob" functions are needed.
The sign of diff at the start decides win, lose or tie.
Anything that changes the allowed moves belongs in the state.
Spot it: "take turns", "both play optimally", "return true if Alice wins".

Variations#

Problem	State	Recurrence
Stone Game III (take 1 to 3 from front)	`i`	`max(gain - diff(i + k + 1))`
Stone Game (take either end)	`(i, j)`	`max(piles[i] - diff(i+1, j), piles[j] - diff(i, j-1))`
Stone Game II (take up to `2M`)	`(i, M)`	`suffix[i] - best(i + X, max(M, X))`

Stone Game II returns the stones the current player collects, not a difference.

Template#

diff(state):                     # best (mover - opponent) from here
    if no moves are left: return 0
    best = -infinity
    for each legal move from state:
        gain = points the mover takes
        best = max(best, gain - diff(state after move))
    return best
memoize diff; compare diff(start) with 0

Pitfalls#

Writing a turn flag and two recurrences. The difference form is shorter and safer.
Leaving a changing rule (like M) out of the state. The cache mixes positions with different options.
Starting best at 0. Every move might lose points, so start at -inf.

Say it in an interview#

"diff is the mover's score minus the opponent's. Subtract the next diff from the gain."
"Anything that changes the allowed moves goes into the state."