Week 5: Adverserial Search Flashcards
(26 cards)
What is adversarial search in AI?
Search in environments where agents compete, such as games, requiring strategies that account for an opponent’s actions.
What are zero-sum games?
Games where one player’s gain is exactly the other’s loss, e.g., chess or tic-tac-toe.
What is the role of MAX and MIN in game trees?
MAX tries to maximize utility, MIN tries to minimize it; they alternate turns in the game tree.
Define a game tree.
A tree representing all possible moves in a game, including branches for each player’s decisions.
What is a terminal state in a game tree?
A game state where the game ends and a utility value is assigned.
What is the minimax algorithm used for?
To find the optimal move in two-player games by assuming both players play optimally.
What is the time complexity of minimax?
O(b^m), where b is branching factor and m is maximum depth.
What is alpha-beta pruning?
A method to eliminate branches in the game tree that do not affect the final decision, improving efficiency.
Does alpha-beta pruning affect the final result?
No, it finds the same move as minimax but more efficiently.
What is the best-case time complexity for alpha-beta pruning?
O(b^(m/2)) with perfect move ordering.
What are alpha and beta in pruning?
Alpha: best already explored option for MAX; Beta: best already explored option for MIN.
What is move ordering and why is it important in alpha-beta pruning?
It determines which nodes are evaluated first and can greatly improve pruning effectiveness.
What is a cutoff test?
A condition to stop search early and apply an evaluation function instead of searching to terminal states.
What is a heuristic evaluation function in games?
A function that estimates the utility of a non-terminal state.
What is a quiescent state?
A game state unlikely to change drastically in the near future—important for evaluation.
What is a quiescence search?
A limited additional search beyond cutoff depth to avoid evaluating volatile (non-quiescent) states.
What is the horizon effect?
A limitation where the AI fails to see a major event just beyond the search depth.
What is a transposition table?
A cache that stores evaluations of previously seen game states to avoid redundant calculations.
What are killer moves?
Moves found to be strong in previous searches and tried early to improve alpha-beta pruning.
What is forward pruning?
Deliberately skipping some moves at a node to reduce search space—risky but efficient.
What is beam search?
A forward pruning technique where only the top n moves (by evaluation) are considered at each level.
What is the PROBCUT algorithm?
A probabilistic version of pruning that uses shallow search statistics to cut branches likely to be irrelevant.
How does the minimax strategy change in multiplayer games?
Each node stores a vector of utility values, and players choose based on their own utility.
What is a utility function in games?
A function assigning a numeric value to terminal states representing outcomes (win, loss, draw, etc.).
