Game theory & Grundy

The idea

In combinatorial games (like Nim or Tic-Tac-Toe), two players take turns with perfect information and no chance. A game state is a Losing state if every valid move leads to a Winning state for the opponent. A state is a Winning state if there is at least one move that forces the opponent into a Losing state.

By mapping out the state space as a Directed Acyclic Graph (DAG) and working backward from terminal states (where no moves can be made, which are usually Losing states), we can determine perfectly who will win from any starting position.

How it works (Minimax DP)

def canWin(state, memo):
    if state in memo:
        return memo[state]
        
    # If there are no valid moves, we lose.
    valid_moves = get_moves(state)
    if not valid_moves:
        return False
        
    # If there is ANY move that leaves the opponent 
    # in a losing state, we can force a win!
    for move in valid_moves:
        if not canWin(move, memo):
            memo[state] = True
            return True
            
    # All moves lead to opponent winning. We lose.
    memo[state] = False
    return False