Adversarial Search

• Minimax simply builds the state tree, and assigns a value to each.
• For adversarial games the values are inverted for each player. (2 player, alternating moves)
• Player A chooses the maximum value, and player B chooses the minimum.
• From a leaf, you calculate the value.
• The values propogate up following the minimax rule (A maximizes, B Minimizez).
• Of course the tree may be huge.
• Iterative Deepining: start at a relatively shallow level, and continue down as time allows.
• Alpha Beta Pruning: if you've got a move with a value X (and you're maximizing), and as you explore another move,
• a minimize passes up something less than X, then stop exploring this branch.
• Do the opposite for a minimize level.
• This reduces search levels.