Section 3 : Heuristics and imperfect information in adversarial search

Commentary

Section Goals

• To discuss the use of heuristic evaluation functions to turn nonterminal nodes into terminal leaves, and thus support cutting off search earlier.
• To discuss games with imperfect information and chance nodes, in addition to MAX and MIN nodes.

Learning Objectives

Learning Objective 1

• Explain the following concepts or terms:
  • Evaluation function
  • Expected value and material value
  • Cutting off search
  • Quiescence search
  • Forward pruning
  • Expectiminimax value
• Describe how evaluation functions are used to estimate the expected utility of a game from a given position.
• Explain the idea behind cutting off search and quiescence search.
• Explain how chance nodes are treated in expectiminimax function.
• Exemplify card games and their connection to belief states.

Objective Readings

Required readings:

Reading topics:

Imperfect and Real-Time Decisions, Games with Chance Nodes (see Sections 5.4 - 5.6 of AIMA3ed).

Objective Questions

• How can you modify the alpha-beta search to include cutting off search?
• What are the main solutions leading to real-time decisions?

Objective Activities

• Analyse how heuristic evaluation function, cutting off search, and imperfect information are considered in the recent game programs introduced in the special edition of -- (2002). Artificial Intelligence, 134(1-2), 1-318 (see the next section for more details).
• Complete Exercise 5.6 of AIMA3ed.