AI Game Trees, Minimax, Alpha-Beta Pruning, Negamax, and Expectiminimax

Comprehensive vocabulary flashcards covering AI Game Trees, Minimax, Alpha-Beta Pruning, Negamax, and Expectiminimax based on the lecture notes.

Game Tree

A graphical representation of all possible moves in a game, starting from the initial position and extending to all possible future positions.

Nodes (in a Game Tree)

The structural elements in a game tree that represent the specific states of the game.

Edges (in a Game Tree)

The links in a game tree that represent the moves or actions taken by players to transition from one game state to another.

Root Node

The node representing the starting point or initial state of the game in a game tree.

Leaf Nodes

Nodes in a game tree that represent terminal positions or end states of the game, such as a win, lose, or draw.

Single-Player Game Trees

Game trees utilized for single-agent decision-making, such as in puzzles like Sudoku or the 8-puzzle.

Two-Player Game Trees

Game trees used in competitive turn-based games such as chess, checkers, or tic-tac-toe, where two adversaries alternate moves.

Tic-Tac-Toe Game Tree Diagram

A game tree structure showing the initial state at the root node, branching into intermediate game states, and ending at terminal leaf nodes (goal states).

Minimax Algorithm

A decision rule and specialized search algorithm used in two-player zero-sum games to determine the optimal move by minimizing the possible loss for a worst-case scenario.

Maximizing Player

The player in a game tree search whose objective is to select moves that maximize their own score or utility.

Minimizing Player

The opposing player in a game tree search whose objective is to minimize the maximizing player's score.

Alpha-Beta Pruning

An optimization technique for the minimax algorithm that reduces the number of nodes evaluated by eliminating branches that cannot influence the final decision.

Deep Blue

A historic chess engine referenced as a prime example of an AI using game tree search to evaluate moves and select optimal actions.

Stockfish and AlphaZero

Modern chess engines cited as implementations of game tree evaluation techniques to determine the best moves.

AlphaGo

A Go AI system that combines traditional game tree search methods with Monte Carlo Tree Search (MCTS) and neural networks to handle enormous game state spaces.

Exponential Growth (Game Tree Challenge)

The issue where the total number of game tree nodes expands exponentially with depth and move count, making exhaustive exploration computationally infeasible.

Heuristic Evaluation

A function applied to evaluate the desirability of non-terminal game states in large trees to effectively limit the required depth of search.

Zero-Sum Game

A game scenario where one player's gain exactly equals the opponent's loss, providing the theoretical basis for minimax decision-making.

Depth-First Search (in Minimax)

The systematic traversal algorithm used by minimax to fully explore game tree branches, initialized with $\text{Max} = -\infty$ and $\text{Min} = \infty$.

Completeness of Minimax

The property guaranteeing that the minimax algorithm will definitely find a complete solution if one exists within the game tree.

Optimality of Minimax

The property ensuring that minimax selects the best possible moves, assuming the opponent is also playing optimally.

Time Complexity of Minimax

The computational runtime of the minimax algorithm, expressed as $O(b^m)$, where $b$ is the branching factor and $m$ is the maximum depth.

Space Complexity of Minimax

The memory requirement of the minimax algorithm during its recursive depth-first exploration, specified as $O(b^m)$.

Branching Factor ($b$)

The average or fixed number of legal moves (child nodes) available from any given game state node in a game tree.

Maximum Depth ($m$)

The maximum number of levels or plies extending from the root node to the deepest leaf node in a game tree.

Initial Value of Max

Negative infinity ($-\infty$), used as the baseline comparison score for a maximizing node before evaluating child moves.

Initial Value of Min

Positive infinity ($\infty$), used as the baseline comparison score for a minimizing node before evaluating child moves.

Terminal State Evaluation

The step in minimax where a heuristic evaluation function is applied to leaf nodes at maximum depth or game-ending positions.

Minimax Worked Tree Evaluation

A standard minimax tree where bottom-up propagation selects the maximum score at yellow and blue nodes and the minimum score at green nodes, yielding a root score of $2$.

Propagate Scores Up the Tree (Minimax)

The recursive process of passing scores upward: selecting the child move with the highest score if the node is a maximizer, or the lowest score if it is a minimizer.

Select Optimal Move (Minimax)

The final execution step where the value established at the root node after backpropagation indicates the best action for the maximizing player.

Alpha ($\alpha$)

The best value (highest score) that the maximizing player is guaranteed to achieve at the current level or above in alpha-beta pruning.

Beta ($\beta$)

The best value (lowest score) that the minimizing player is guaranteed to achieve at the current level or above in alpha-beta pruning.

Alpha-Beta Initialization

The starting parameter assignment where alpha is set to negative infinity ($\alpha = -\infty$) and beta is set to positive infinity ($\beta = \infty$).

Pruning Condition (Alpha-Beta)

The mathematical cutoff criteria where search along a node is terminated whenever $\alpha \ge \beta$ (or $\beta \le \alpha$).

Efficiency Benefit (Alpha-Beta Pruning)

The enhancement that reduces the total number of evaluated game tree nodes, resulting in a faster search without altering the final decision.

Deeper Searches Benefit

An advantage of alpha-beta pruning that allows an AI engine to explore more moves ahead within fixed time constraints, improving move quality.

Alpha-Beta Pruned Game Tree

A completed game tree visualization highlighting pruned branches in solid red where $\beta \le \alpha$, resulting in a final evaluated root value of $3$.

Negamax Algorithm

A streamlined variant of the minimax algorithm for two-player zero-sum games that evaluates every position strictly from the perspective of the player currently taking their turn.

Single Evaluation Function (Negamax)

A unified evaluation design in Negamax that eliminates the need for separate heuristic routines for the maximizing and minimizing players.

Negamax Formula

The core recursive relationship expressed as $\text{score} = -\text{Negamax}(\text{depth} - 1, -\text{player})$, which negates the value returned from the opponent's view.

Negamax Multiplier Step Diagram

An illustration showing how Negamax multiplies child values by $-1$ at each ply to invert player scores, such as converting a child max of $8$ into $-8$.

Negamax Base Case

The condition where recursive exploration terminates either upon reaching a predefined search depth or encountering an end state (win, lose, or draw).

Games of Chance

Games like card or dice games that include nondeterministic or stochastic elements affecting move outcomes.

Expectiminimax Algorithm

An extension of the minimax algorithm designed for games of chance that incorporates chance nodes along with standard max and min nodes.

Max Nodes (Expectiminimax)

Tree nodes representing the AI player's turn where the choice maximizing the expected utility is selected.

Min Nodes (Expectiminimax)

Tree nodes representing the opponent's turn where the choice minimizing the AI player's expected utility is selected.

Chance Nodes

Nodes in an expectiminimax tree representing stochastic events where the expected value is calculated based on probability distributions.

Die Roll Branching in Pile Stone Game

A chance node structure showing an initial state of 3 stones branching into Die Roll 1, Die Roll 2, and Die Roll 3, which leave 2 stones, 1 stone, and 0 stones left respectively.

Expected Value Calculation (Pile Stone Game)

The expectiminimax probability calculation yielding an overall expected utility of $0.25$ via $\left(\frac{1}{6}\right)(-1 + -1 + 1) + \left(\frac{1}{2}\right)(1 + 1 + 1)$.