Transcript MS PowerPoint format - Kansas State University

Lecture 9 of 14
Game Tree Search: Minimax and Alpha-Beta
Friday, 10 September 2004
William H. Hsu
Department of Computing and Information Sciences, KSU
http://www.kddresearch.org
http://www.cis.ksu.edu/~bhsu
Reading:
Chapter 6, Russell and Norvig 2e
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Lecture Outline
•
Today’s Reading
– Sections 6.1-6.4, Russell and Norvig 2e
– Recommended references: Rich and Knight, Winston
•
Reading for Next Class: Sections 6.5-6.8, Russell and Norvig
•
Games as Search Problems
– Frameworks: two-player, multi-player; zero-sum; perfect information
– Minimax algorithm
• Perfect decisions
• Imperfect decisions (based upon static evaluation function)
– Issues
• Quiescence
• Horizon effect
– Need for pruning
•
Next Lecture: Alpha-Beta Pruning, Expectiminimax, Current “Hot” Problems
•
Next Week: Knowledge Representation – Logics and Production Systems
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Overview
•
Perfect Play
– General framework(s)
– What could agent do with perfect info?
•
Resource Limits
– Search ply
– Static evaluation: from heuristic search to heuristic game tree search
– Examples
• Tic-tac-toe, connect four, checkers, connect-five / Go-Moku / wu3 zi3 qi2
• Chess, go
•
Games with Uncertainty
– Explicit: games of chance (e.g., backgammon, Monopoly)
– Implicit: see project suggestions!
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Games versus Search Problems
•
Unpredictable Opponent
– Solution is contingency plan
– Time limits
• Unlikely to find goal
• Must approximate
•
Plan of Attack
– Algorithm for perfect play (J. von Neumann, 1944)
– Finite horizon, approximate evaluation (C. Zuse, 1945; C. Shannon, 1950, A.
Samuel, 1952-1957)
– Pruning to reduce costs (J. McCarthy, 1956)
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Types of Games
•
Information: Can Know (Observe)
– … outcomes of actions / moves?
– … moves committed by opponent?
•
Uncertainty
– Deterministic vs. nondeterministic outcomes
– Thought exercise: sources of nondeterminism?
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Minimax
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Figure 5.2 p. 125 R&N
Kansas State University
Department of Computing and Information Sciences
Minimax Algorithm:
Decision and Evaluation
 what’s this?
 what’s this?
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Figure 5.3 p. 126 R&N
Kansas State University
Department of Computing and Information Sciences
Properties of Minimax
•
Complete?
– … yes, provided following are finite:
• Number of possible legal moves (generative breadth of tree)
• “Length of game” (depth of tree) – more specifically?
– Perfect vs. imperfect information?
• Q: What search is perfect minimax analogous to?
• A: Bottom-up breadth-first
•
Optimal?
– … yes, provided perfect info (evaluation function) and opponent is optimal!
– … otherwise, guaranteed if evaluation function is correct
•
Time Complexity?
– Depth of tree: m
– Legal moves at each point: b
– O(bm) – NB, m  100, b  35 for chess!
•
Space Complexity? O(bm) – why?
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Resource Limits
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Static Evaluation Function Example:
Chess
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Figure 5.4(c), (d) p. 128 R&N
Kansas State University
Department of Computing and Information Sciences
Do Exact Values Matter?
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Cutting Off Search [1]
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Cutting Off Search [2]
•
Issues
– Quiescence
• Play has “settled down”
• Evaluation function unlikely to exhibit wild swings in value in near future
– Horizon effect
• “Stalling for time”
• Postpones inevitable win or damaging move by opponent
• See: Figure 5.5 R&N
•
Solutions?
– Quiescence search: expand non-quiescent positions further
– “No general solution to horizon problem at present
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Why Prune?
Adapted from slides by S. Russell, UC Berkeley
CIS 730: Introduction to Artificial Intelligence
Figure 5.6 p. 131 R&N
Kansas State University
Department of Computing and Information Sciences
Summary Points
•
Introduction to Games as Search Problems
– Frameworks
• Two-player versus multi-player
• Zero-sum versus cooperative
• Perfect information versus partially-observable (hidden state)
– Concepts
• Utility and representations (e.g., static evaluation function)
• Reinforcements: possible role for machine learning
• Game tree
•
Family of Algorithms for Game Trees: Minimax
– Propagation of credit
– Imperfect decisions
– Issues
• Quiescence
• Horizon effect
– Need for pruning
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences
Terminology
•
Game Graph Search
– Frameworks
• Two-player versus multi-player
• Zero-sum versus cooperative
• Perfect information versus partially-observable (hidden state)
– Concepts
• Utility and representations (e.g., static evaluation function)
• Reinforcements: possible role for machine learning
• Game tree: node/move correspondence, search ply
•
Family of Algorithms for Game Trees: Minimax
– Propagation of credit
– Imperfect decisions
– Issues
• Quiescence
• Horizon effect
– Need for (alpha-beta) pruning
CIS 730: Introduction to Artificial Intelligence
Kansas State University
Department of Computing and Information Sciences