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

Lessons

  1. 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. 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. 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

Module quiz

1. What is a local optimum?
2. At a MIN node, which child value does minimax take?
3. How does simulated annealing escape local optima?
4. Does alpha-beta pruning change the minimax value?
5. When are a node's remaining children pruned?
6. What is the value of a chance node with equally likely children 1, 3 and 8?

‹ Agents and searchConstraints and logic ›