Local search and games
Improving one candidate at a time with hill climbing, restarts and 2-opt, and choosing moves against an opponent with minimax, alpha-beta pruning and expectimax.
About 5 hours of study
Learning objectives
- Use hill climbing and random restarts
- Compute minimax values and best moves
- Prune game trees with alpha-beta and handle chance with expectimax
Lessons
- 1
Local search and optimization Intermediate
When only the final state matters, improve one candidate step by step instead of searching for a path. Use hill climbing, random restarts and simulated annealing on the N-queens and travelling-salesman problems, and understand local optima.
- 2
Game playing with minimax Intermediate
Search when an opponent moves too. Represent a two-player game as a tree of moves, score the end positions, and use minimax to pick the move that is best against the best reply.
- 3
Alpha-beta pruning and chance Advanced
Get the same answer as minimax while searching far fewer positions by pruning branches that cannot change the decision. See how move ordering affects pruning, and extend minimax to games with dice using expectimax.
Module practice
- AI: Count attacking queensEasy
- AI: Hill climbing for N queensMedium
- AI: Shorten a tour with 2-optHard
- AI: Minimax on a game treeEasy
- AI: The best tic-tac-toe moveMedium
- AI: Who wins the take-away game?Hard
- AI: Count the leaves alpha-beta examinesEasy
- AI: Expectimax for games of chanceMedium
- AI: How much does move ordering help?Hard