top of page
Chapter 05: adversarial search
ARTIFICIAL INTELLIGENCE MODERN APPROACH
Visual Summaries
Table Summary
.png)
Core Terminology
Master key academic terminology through active recall and spaced repetition concepts.
Game tree
A theoretical construct representing all possible states and moves, where nodes are states and edges are moves.
ply
A single move by one player, or one 'half-move' in a two-player game.
O(bm)
What is the space complexity of minimax if it generates all actions at once?
alpha-beta pruning
A search technique that eliminates branches in a minimax tree that cannot influence the final decision.
killer move heuristic
A move-ordering scheme that tries moves first that were found to be best at the same depth in other parts of the tree.
quiescent position
A position that is unlikely to exhibit wild swings in value in the near future (e.g., no pending captures).
Chapter Quiz
In the context of game theory in AI, what specifically defines a 'zero-sum' game?
In the alpha-beta pruning algorithm, what does the parameter α represent?
Which phenomenon occurs when a search algorithm chooses a move to delay an unavoidable loss, simply because the loss occurs beyond the search depth?
In partially observable games like Kriegspiel, what is a 'belief state'?
In game-playing programs, what is the purpose of a 'transposition table'?
Answers:Â C, A, A, D, B
bottom of page