4.12 Adversarial search: minimax and alpha-beta pruning

Work through these

• Formulate a game: players, moves, terminal states and a utility for each outcome

  The pieces a two-player game needs before any algorithm can run, and the one that matters most is the number attached to each ending. Everything the search does is an attempt to reach a good one of those numbers.

• Run minimax on a small game tree by hand

  Working the values up from the endings, taking the largest at your own turn and the smallest at the opponent's. Doing it by hand once is what makes the alternation stop feeling arbitrary.

• Apply alpha-beta pruning, and show it returns the same answer

  Skipping parts of the tree that cannot change the result, using the best values found so far on each side. The saving is large and the answer is identical, which is the point worth proving to yourself.

• Explain why move ordering decides how much alpha-beta saves

  Looking at strong moves first lets the cutoffs happen early, and a good ordering roughly squares the depth reachable in the same time. A bad ordering leaves you with plain minimax and extra bookkeeping.

• Cut the search off with a depth limit and an evaluation function

  Real games do not end within reach, so the search stops early and scores the position with a hand-built or learned estimate. Every practical player is this compromise, and its quality is the estimate's quality.

• Explain the horizon effect and what is done about it

  A cut-off search can push a bad outcome past the depth it looks at and report a position as safe when it is not. Quiescence search and deeper looks at unstable positions are the standard answers.