20. Optimal Score Difference in a Token-Picking Game

Problem

DeepMind's game-playing research group sanity-checks new self-play agents against a minimal reference game before scaling up to something the size of Go or an RTS. One such reference game: two players alternate turns picking a token from either end of a row of point-valued tokens (never from the middle), each trying to maximize their own total score, and both play perfectly.

Given the row of token values, return player 1's total score minus player 2's total score under optimal play from both sides. This is the same terminal-value computation a value function gets checked against on a toy game before it's trusted on a harder one.

Source: src/20_token_game_optimal_value.py

def max_score_difference(tokens: list[int]) -> int:
    ...

Examples:
>>> max_score_difference([1, 5, 2])
-2

>>> max_score_difference([1, 5, 233, 7])
222

Step-by-Step Approach

1. Notice that tracking "whose turn is it" explicitly doubles the state space for no benefit — instead define dp[i][j] as the best score difference (current player minus opponent) achievable from the subarray tokens[i..j], regardless of which physical player that is.
2. Base case: a subarray of one token, dp[i][i] = tokens[i] — the current player takes it and there is nothing left for the opponent.
3. Recurrence: the current player either takes tokens[i] (leaving tokens[i+1..j] to the opponent) or takes tokens[j] (leaving tokens[i..j-1]). Whichever token they take, the opponent then plays optimally on the remainder, so subtract the opponent's best achievable diff on that remainder.
4. dp[i][j] = max(tokens[i] - dp[i+1][j], tokens[j] - dp[i][j-1]).
5. Fill the table by increasing subarray length, since dp[i][j] depends on two strictly shorter subarrays.
6. The answer is dp[0][n-1]: a positive value means player 1 wins by that margin, negative means player 2 wins, zero is a tie.
7. Handle the empty-array edge case directly (difference 0, no turns to take).

The key insight is the "relative score" reformulation: by always asking "how much better does the current mover do than whoever moves after them," you avoid tracking two separate running scores and turn parity, and the recurrence becomes symmetric regardless of which player is actually moving.

Reference solution

def max_score_difference(tokens: list[int]) -> int:
    n = len(tokens)
    if n == 0:
        return 0
    # dp[i][j] = best score difference (current player minus opponent) achievable
    # over the remaining subarray tokens[i..j], for whichever player is to move there
    dp = [[0] * n for _ in range(n)]
    for i in range(n):
        dp[i][i] = tokens[i]  # one token left: take it
    for length in range(2, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # take the left token, or the right token; either way the opponent then
            # plays optimally on what's left, so subtract their best achievable diff
            take_left = tokens[i] - dp[i + 1][j]
            take_right = tokens[j] - dp[i][j - 1]
            dp[i][j] = max(take_left, take_right)
    return dp[0][n - 1]

Key Functions & Tricks

• dp[i][j] = max(tokens[i] - dp[i+1][j], tokens[j] - dp[i][j-1]) — relative-score recurrence, avoids tracking turn parity
• Length-increasing fill order — dp[i][j] always depends only on strictly shorter subarrays, so this order guarantees dependencies are ready
• Diagonal base case dp[i][i] = tokens[i] — the one-token subgame has an obvious optimal move
• Sign of the final dp[0][n-1] — directly answers "does the first mover win," not just "by how much"
• O(n²) time / O(n²) space, reducible to O(n) space with a rolling diagonal since each length only reads the previous length's row

How to Recognize This Pattern