Introduction to Game Search and Minimax

Foundations of Multi-Agent Game Environments

• General Definition of a Game:

  • Broadly defined, a game is a multi-agent environment where an agent's success depends on the operations of other agents.

  • While early AI focused on game theory involving two competing agents, modern definitions include more than two agents.

  • Agents in a game can either compete with one another or cooperate to achieve mutual goals.

• Fundamental Assumptions in Game Search:

  • State Space: The environments are often huge but "clean," meaning the environment itself is static and does not influence agent decisions; only agents affect each other.

  • Rules: Rules of movement and interaction are clearly defined.

  • Success Criterion: Well-defined objectives for determining the winner or the utility of an outcome.

• Hyperparameters of a Game:

  • Players: Number of agents involved. In standard introductory models, this is typically assumed to be two agents.

  • Moves: These are usually alternating (turn-based). Agents do not execute actions simultaneously; agent A moves, then agent B moves.

  • Information: Perfect information implies all agents have the same observation of the environment. There is no requirement to reason about hidden or unseen factors.

  • Utility: Frequently defined as zero-sum, where one agent's win is another's loss.

  • Outcomes: Deterministic results are used for simplicity, meaning an action in a specific state always leads to the same resulting state.

Notations and Framework for Game Search

• Borrowed Notations (Reinforcement Learning Context):

  • State ($s$): Represents the current configuration of the environment.

  • Players ($P$): The set of agents currently in the environment.

  • Actions ($a$): The set of possible moves available to each agent.

  • Transition Function ($T(s, a) \rightarrow s'$): Defines how the current state changes after an agent executes an action.

  • Terminal Test: A condition that determines when the game or the search process ends.

  • Utility Function ($U(s, P)$): A function that provides a reward or value based on the state and the specific agent.

• Zero-Sum Game Dynamics:

  • In a zero-sum setting, the total sum of the utilities of all competitors equals zero.

  • If one agent tries to maximize its value, the opponent is effectively trying to minimize that same value.

  • A single number can describe the position for both players. For instance, if Agent A has a reward of $x$, Agent B's reward is $-x$.

Comparison: Classical Search vs. Game Search

• Classical Search (e.g., Eight-Puzzle):

  • Goal: Find a path to the goal state.

  • Interruption: None. The agent executes a planned sequence of steps without interference.

  • Planning: A fixed sequence of moves can be determined in advance.

• Game Search (e.g., Chess):

  • Goal: Determine a policy. A policy is a function that maps the current state and observations to an action.

  • Interruption: Constant. Actions must account for the opponent's movements.

  • Contingency: Because the opponent "has a say" in the state progression, an agent cannot fix a sequence of moves in advance. The next move depends on the opponent's previous response.

The Minimax Algorithm

• Core Logic:

  • Minimax aims to maximize the reward for the "Max" player while assuming the "Min" player (the opponent) will act to minimize that reward.

  • The Minimax value of a state is the best value the Max player can guarantee, given that the Min player always provides the worst possible reply.

• Implementation as a Recursive Search:

  • The function is called from the top (root) to the bottom (leaves) of the search tree.

  • Values are computed and returned from the bottom (terminal states) back to the top.

  • Max Value Function:

    1. Initialize state to $-\infty$.

    2. For each successor, call the Min Value Function.

    3. Update the state to the maximum value returned.

  • Min Value Function:

    1. Initialize state to $+\infty$.

    2. For each successor, call the Max Value Function.

    3. Update the state to the minimum value returned.

• Computational Complexity:

  • Branching Factor ($b$): The number of legal moves at a typical position (e.g., $b \approx 35$ for Chess).

  • Maximum Depth ($m$): The depth of the search tree.

  • Time Complexity: $O(b^m)$.

  • Space Complexity: $O(bm)$ (storing the path in memory).

  • Because both time and space are often unaffordable in deep trees, optimization strategies are required.

Alpha-Beta Pruning

• Definition and Purpose:

  • Alpha-beta pruning is an optimization strategy that speeds up the Minimax algorithm by ignoring branches that cannot possibly affect the final decision.

  • It maintains the optimality of Minimax, meaning it returns the exact same value as a full search.

• Search Parameters:

  • Alpha ($\alpha$): The best value (highest) that the Max node can guarantee so far along the path to the root. It acts as a lower bound.

  • Beta ($\beta$): The best value (lowest) that the Min node can guarantee so far. It acts as an upper bound.

  • Initial Values: $\alpha = -\infty$ and $\beta = +\infty$.

• Pruning Mechanism:

  • Min Node Pruning: If a Min node discovers a child value that is less than or equal to the current $\alpha$, it stops exploring its remaining children. This is because the Max node above it already has a better option ($\alpha$), so it will never choose this Min branch anyway.

  • Max Node Pruning: If a Max node discovers a child value that is greater than or equal to the current $\beta$, it stops exploration because the Min node above it will never allow the game to reach this state.

• The Power of Ordering:

  • The efficiency of pruning is highly dependent on the order in which successors are examined.

  • Worst Case: If the strongest moves are searched last, early pruning is impossible, and complexity remains $O(b^m)$.

  • Perfect Ordering: Can significantly reduce the number of nodes examined, though the specific cost remains high in games with large branching factors.

Practical Scenarios and Specialized Concepts

• Single-Agent Game Transformation:

  • If a game involves only one agent and a static environment, it transforms into a classical search problem.

  • Example: Chopping wood in Minecraft (ignoring combat). The environment is static, and there is no opponent to minimize your progress. This is equivalent to a Hill Climbing algorithm where you move toward the successor with the highest value.

• Cooperation vs. Credit Assignment:

  • In cooperative games (e.g., two robots moving a task), the utility is not zero-sum.

  • The challenge shifts from competing to credit assignment—determining which agent contributed more effort to the shared success.

• Meta-Reasoning:

  • Alpha-beta pruning is an example of meta-reasoning: deciding which computations (searches) are worth performing to save resources.

• Real-World Application (Embodied Agents):

  • In self-driving cars, other cars are not explicitly "competing" in a zero-sum game, but their movements are independent and affect the agent's optimal path. Search and planning must account for these dynamic interruptions in real-time.

Questions & Discussion

• Question: Why do we not need to look at the rest of the branch if a Min node returns a value (e.g., 4) that is already lower than the value Max is holding (e.g., 11)?

• Response: Because the Min node will always choose the minimum value. If it found a 4, the final value it returns will be 4 or even smaller. Since the Max player is already holding an 11, it will never choose a branch that results in a 4 or less. Therefore, looking at the rest of that branch is unnecessary as it cannot change the Max player's decision.