Section 2 : Adversarial search algorithms: Minimax and alpha-beta pruning

Commentary

Section Goals

• To present the minimax algorithm and alpha-beta pruning for adversarial search.
• To discuss some issues regarding multiplayer games.

Learning Objectives

Learning Objective 1

• Design and implement the minimax algorithm.
• Explain the principle of alpha-beta pruning.
• Describe the features and difficulties of multiplayer games.

Objective Readings

Required Readings

Reading topics:

Optimal Decisions in Games, Alpha-Beta Pruning (see Sections 5.2 - 5.3 of AIMA3ed)

Objective Questions

• How can alpha-beta pruning be used to increase the efficiency of the minimax algorithm?
• What issues arise when dealing with multiplayer games?

Objective Activities

• Explore the following adversarial search programs found on the online course website.
  • Minimax-Decision
  • Alpha-Beta-Search
• Complete Exercise 5.8 of AIMA3ed.