Game Theory DP Patterns: Complete Reference¶

def can_win(state):
    """Track score difference from current player's perspective."""
    if base_case:
        return 0

    # Current player tries all moves, picks best
    best = -infinity
    for action in available_actions(state):
        # Score gained minus what opponent will achieve
        value = gain(action) - can_win(next_state(state, action))
        best = max(best, value)

    return best

# Winner check: can_win(initial_state) >= 0 for current player

def current_player_wins(state, memo):
    """Return True if current player can force a win."""
    if state in memo:
        return memo[state]

    if base_case:
        return base_result

    # Current player wins if ANY move leads to opponent losing
    for action in available_actions(state):
        opponent_wins = current_player_wins(next_state, memo)
        if not opponent_wins:
            memo[state] = True
            return True

    memo[state] = False
    return False

def interval_game(piles, i, j, memo):
    """Game where players take from either end."""
    if i > j:
        return 0
    if (i, j) in memo:
        return memo[(i, j)]

    # Take left or right, opponent gets best of remaining
    take_left = piles[i] - interval_game(piles, i+1, j, memo)
    take_right = piles[j] - interval_game(piles, i, j-1, memo)

    memo[(i, j)] = max(take_left, take_right)
    return memo[(i, j)]

from functools import lru_cache

def score_difference_game(piles: list[int]) -> int:
    """
    Return score difference if both players play optimally.
    Positive = first player wins, Negative = second player wins.
    """
    @lru_cache(maxsize=None)
    def dp(left: int, right: int) -> int:
        if left > right:
            return 0

        # Try taking from left or right
        take_left = piles[left] - dp(left + 1, right)
        take_right = piles[right] - dp(left, right - 1)

        return max(take_left, take_right)

    return dp(0, len(piles) - 1)

from functools import lru_cache

def bitmask_game(max_choice: int, target: int) -> bool:
    """
    Can current player force a win given choices 1 to max_choice?
    """
    @lru_cache(maxsize=None)
    def can_win(mask: int, remaining: int) -> bool:
        for choice in range(1, max_choice + 1):
            if mask & (1 << choice):
                continue  # Already used

            if choice >= remaining:
                return True  # Win immediately

            new_mask = mask | (1 << choice)
            if not can_win(new_mask, remaining - choice):
                return True  # Opponent loses after this move

        return False  # No winning move

    return can_win(0, target)

from functools import lru_cache

def multi_choice_game(piles: list[int]) -> str:
    """
    Each turn: take 1, 2, or 3 from the front.
    Return winner: "Alice" or "Bob" or "Tie".
    """
    n = len(piles)

    # Compute suffix sums
    suffix_sum = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix_sum[i] = suffix_sum[i + 1] + piles[i]

    @lru_cache(maxsize=None)
    def dp(start: int) -> int:
        """Return score difference from current player's view."""
        if start >= n:
            return 0

        best = float('-inf')
        current_sum = 0
        for take in range(1, 4):
            if start + take - 1 >= n:
                break
            current_sum += piles[start + take - 1]
            # Score gained minus opponent's best outcome
            value = current_sum - dp(start + take)
            best = max(best, value)

        return best

    diff = dp(0)
    if diff > 0:
        return "Alice"
    elif diff < 0:
        return "Bob"
    else:
        return "Tie"

class SolutionMath:
    def stoneGame(self, piles: list[int]) -> bool:
        """Alice always wins with even number of piles."""
        return True

class SolutionDP:
    def stoneGame(self, piles: list[int]) -> bool:
        """
        Track score difference from current player's perspective.

        dp(i, j) = max score difference current player can achieve
                   when piles[i..j] remain.

        At each state:
        - Take left: gain piles[i], opponent gets dp(i+1, j)
        - Take right: gain piles[j], opponent gets dp(i, j-1)

        Since opponent's gain is our loss:
        - take_left = piles[i] - dp(i+1, j)
        - take_right = piles[j] - dp(i, j-1)
        """
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(left: int, right: int) -> int:
            if left > right:
                return 0

            take_left = piles[left] - dp(left + 1, right)
            take_right = piles[right] - dp(left, right - 1)

            return max(take_left, take_right)

        # Alice wins if her score difference >= 0
        return dp(0, len(piles) - 1) > 0

class Solution:
    def predictTheWinner(self, nums: list[int]) -> bool:
        """
        Return True if Player 1 can win or tie.

        dp(i, j) = max score difference current player can achieve
                   from nums[i..j].

        Player 1 wins if dp(0, n-1) >= 0.
        """
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(left: int, right: int) -> int:
            if left > right:
                return 0

            take_left = nums[left] - dp(left + 1, right)
            take_right = nums[right] - dp(left, right - 1)

            return max(take_left, take_right)

        return dp(0, len(nums) - 1) >= 0

class SolutionBottomUp:
    def predictTheWinner(self, nums: list[int]) -> bool:
        """
        Bottom-up DP with O(n) space optimization.

        dp[j] represents score difference for interval ending at j.
        """
        n = len(nums)
        dp = nums[:]  # Base case: single element intervals

        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                # dp[j] currently holds dp[i+1][j] from previous iteration
                take_left = nums[i] - dp[j]
                # After this update, dp[j-1] holds dp[i][j-1]
                take_right = nums[j] - dp[j - 1]
                dp[j] = max(take_left, take_right)

        return dp[n - 1] >= 0

class Solution:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        """
        Return True if first player can force a win.

        State: (bitmask of used numbers, remaining to reach)
        """
        # Edge case: if sum of all choices can't reach target, no one wins
        total_sum = maxChoosableInteger * (maxChoosableInteger + 1) // 2
        if total_sum < desiredTotal:
            return False

        # Edge case: if target is 0 or less, first player wins immediately
        if desiredTotal <= 0:
            return True

        from functools import lru_cache

        @lru_cache(maxsize=None)
        def can_win(mask: int, remaining: int) -> bool:
            """Return True if current player can force a win."""
            for choice in range(1, maxChoosableInteger + 1):
                bit = 1 << choice

                if mask & bit:
                    continue  # Already used

                # Win immediately if choice >= remaining
                if choice >= remaining:
                    return True

                # Win if this choice makes opponent lose
                new_mask = mask | bit
                if not can_win(new_mask, remaining - choice):
                    return True

            # No winning move found
            return False

        return can_win(0, desiredTotal)

class SolutionOptimized:
    def canIWin(self, maxChoosableInteger: int, desiredTotal: int) -> bool:
        total_sum = maxChoosableInteger * (maxChoosableInteger + 1) // 2
        if total_sum < desiredTotal:
            return False
        if desiredTotal <= 0:
            return True

        from functools import lru_cache

        @lru_cache(maxsize=None)
        def can_win(mask: int) -> bool:
            # Calculate remaining from mask
            used_sum = sum(i for i in range(1, maxChoosableInteger + 1)
                          if mask & (1 << i))
            remaining = desiredTotal - used_sum

            for choice in range(1, maxChoosableInteger + 1):
                if mask & (1 << choice):
                    continue

                if choice >= remaining:
                    return True

                if not can_win(mask | (1 << choice)):
                    return True

            return False

        return can_win(0)

class Solution:
    def stoneGameII(self, piles: list[int]) -> int:
        """
        Return maximum stones Alice can get.

        dp(start, M) = max stones current player can get from piles[start:]
                       with current M value.

        Use suffix sums: current_player_gets = suffix_sum[start] - opponent_gets
        """
        n = len(piles)

        # Compute suffix sums
        suffix_sum = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffix_sum[i] = suffix_sum[i + 1] + piles[i]

        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(start: int, M: int) -> int:
            if start >= n:
                return 0

            # If we can take all remaining, do it
            if start + 2 * M >= n:
                return suffix_sum[start]

            max_stones = 0
            for take in range(1, 2 * M + 1):
                if start + take > n:
                    break

                # Stones we get = total remaining - opponent's best
                opponent_best = dp(start + take, max(M, take))
                stones = suffix_sum[start] - opponent_best
                max_stones = max(max_stones, stones)

            return max_stones

        return dp(0, 1)

class SolutionDirect:
    def stoneGameII(self, piles: list[int]) -> int:
        """Direct tracking of stones taken."""
        n = len(piles)
        suffix_sum = [0] * (n + 1)
        for i in range(n - 1, -1, -1):
            suffix_sum[i] = suffix_sum[i + 1] + piles[i]

        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(start: int, M: int) -> int:
            """Return max stones current player gets."""
            if start >= n:
                return 0

            if start + 2 * M >= n:
                return suffix_sum[start]

            best = 0
            stones_taken = 0
            for take in range(1, 2 * M + 1):
                if start + take > n:
                    break
                stones_taken += piles[start + take - 1]

                # I get stones_taken now
                # Plus whatever remains after opponent takes their best
                remaining_after_me = suffix_sum[start + take]
                opponent_gets = dp(start + take, max(M, take))
                my_total = stones_taken + (remaining_after_me - opponent_gets)
                best = max(best, my_total)

            return best

        return dp(0, 1)

class Solution:
    def stoneGameIII(self, stoneValue: list[int]) -> str:
        """
        Return winner: "Alice", "Bob", or "Tie".

        dp(start) = max score difference current player can achieve
                    starting from index start.
        """
        n = len(stoneValue)

        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(start: int) -> int:
            if start >= n:
                return 0

            best = float('-inf')
            stones_taken = 0

            for take in range(1, 4):
                if start + take > n:
                    break

                stones_taken += stoneValue[start + take - 1]

                # Score gained minus opponent's best outcome
                value = stones_taken - dp(start + take)
                best = max(best, value)

            return best

        diff = dp(0)

        if diff > 0:
            return "Alice"
        elif diff < 0:
            return "Bob"
        else:
            return "Tie"

class SolutionBottomUp:
    def stoneGameIII(self, stoneValue: list[int]) -> str:
        """
        Bottom-up DP with O(1) space using rolling array.

        Only need dp[i+1], dp[i+2], dp[i+3] to compute dp[i].
        """
        n = len(stoneValue)

        # dp[i] = best score difference from position i
        # Only need last 3 values
        dp = [0] * 4  # dp[i % 4]

        for i in range(n - 1, -1, -1):
            best = float('-inf')
            stones = 0

            for take in range(1, 4):
                if i + take > n:
                    break
                stones += stoneValue[i + take - 1]
                value = stones - dp[(i + take) % 4]
                best = max(best, value)

            dp[i % 4] = best

        diff = dp[0]

        if diff > 0:
            return "Alice"
        elif diff < 0:
            return "Bob"
        else:
            return "Tie"

from functools import lru_cache

def interval_game(values: list[int]) -> int:
    """
    Two players take turns taking from either end.
    Return score difference (positive = first player wins).
    """
    @lru_cache(maxsize=None)
    def dp(left: int, right: int) -> int:
        if left > right:
            return 0

        take_left = values[left] - dp(left + 1, right)
        take_right = values[right] - dp(left, right - 1)

        return max(take_left, take_right)

    return dp(0, len(values) - 1)

# Usage:
# first_player_wins = interval_game(values) > 0  # Stone Game
# first_player_wins_or_ties = interval_game(values) >= 0  # Predict Winner

from functools import lru_cache

def linear_game(values: list[int], max_take: int = 3) -> int:
    """
    Take 1 to max_take elements from front each turn.
    Return score difference (positive = first player wins).
    """
    n = len(values)

    @lru_cache(maxsize=None)
    def dp(start: int) -> int:
        if start >= n:
            return 0

        best = float('-inf')
        total = 0

        for take in range(1, max_take + 1):
            if start + take > n:
                break
            total += values[start + take - 1]
            value = total - dp(start + take)
            best = max(best, value)

        return best

    return dp(0)

# Usage (Stone Game III):
# diff = linear_game(stones, 3)
# winner = "Alice" if diff > 0 else "Bob" if diff < 0 else "Tie"

from functools import lru_cache

def bitmask_game(max_choice: int, target: int) -> bool:
    """
    Choose integers 1 to max_choice, each used once.
    First to reach target wins.
    Return True if first player can force a win.
    """
    total_sum = max_choice * (max_choice + 1) // 2
    if total_sum < target:
        return False
    if target <= 0:
        return True

    @lru_cache(maxsize=None)
    def can_win(mask: int, remaining: int) -> bool:
        for choice in range(1, max_choice + 1):
            if mask & (1 << choice):
                continue

            if choice >= remaining:
                return True

            if not can_win(mask | (1 << choice), remaining - choice):
                return True

        return False

    return can_win(0, target)

from functools import lru_cache

def variable_take_game(piles: list[int]) -> int:
    """
    Take 1 to 2*M piles each turn, M updates to max(M, taken).
    Return max stones first player can get.
    """
    n = len(piles)

    # Precompute suffix sums
    suffix_sum = [0] * (n + 1)
    for i in range(n - 1, -1, -1):
        suffix_sum[i] = suffix_sum[i + 1] + piles[i]

    @lru_cache(maxsize=None)
    def dp(start: int, M: int) -> int:
        if start >= n:
            return 0

        if start + 2 * M >= n:
            return suffix_sum[start]

        max_stones = 0
        for take in range(1, 2 * M + 1):
            if start + take > n:
                break
            opponent_best = dp(start + take, max(M, take))
            stones = suffix_sum[start] - opponent_best
            max_stones = max(max_stones, stones)

        return max_stones

    return dp(0, 1)

def linear_game_optimized(values: list[int], max_take: int = 3) -> int:
    """
    Same as linear_game but O(max_take) space.
    """
    n = len(values)
    dp = [0] * (max_take + 1)  # Rolling array

    for i in range(n - 1, -1, -1):
        best = float('-inf')
        total = 0

        for take in range(1, max_take + 1):
            if i + take > n:
                break
            total += values[i + take - 1]
            value = total - dp[(i + take) % (max_take + 1)]
            best = max(best, value)

        dp[i % (max_take + 1)] = best

    return dp[0]