Stochastic Games and Depth-Limited Search Vocabulary

Vocabulary flashcards based on the lecture covering search algorithms, evaluation functions, horizon effects, and stochastic game trees.

Minimax Algorithm

A search algorithm used in zero-sum game settings where the maximizing player aims to maximize their score assuming the opponent always plays optimally to minimize it.

Alpha-Beta Pruning

A search technique that reduces the search space of a minimax tree—potentially halving the search depth exponent—without affecting the final optimal decision.

Cutoff Test

A test that replaces the standard terminal test in depth-limited search, stopping the search recursion once a specified depth limit $d$ is reached.

Evaluation Function

A function used in depth-limited search to estimate the utility or expected return score of a state when leaf nodes cannot be reached.

Horizon Effect

A phenomenon in depth-limited search where an unavoidable loss or negative outcome is hidden just below the cutoff depth limit, leading to suboptimal search decisions.

Chance Node

A node in a game tree that calculates an expected value by taking the weighted average of its children's values according to their probability of occurrence.

Expectimax Algorithm

A search algorithm that evaluates game trees containing chance nodes by computing average expected values rather than strictly assuming adversarial min decisions.

KL Divergence

A measure of statistical similarity between two vectors, used to minimize output differences between neural networks in techniques such as knowledge distillation.