Bài giảng Trí tuệ nhân tạo - Chapter 8: Game playing
Game Playing
Chapter 8
Outline
• Overview
• Minimax search
• Adding alpha-beta cutoffs
• Additional refinements
• Iterative deepening
2
Overview
Old beliefs
Games provided a structured task in which it was very easy to
measure success or failure.
Games did not obviously require large amounts of knowledge,
thought to be solvable by straightforward search.
3
Overview
Chess
The average branching factor is around 35.
In an average game, each player might make 50 moves.
One would have to examine 35100 positions.
4
Overview
• Improve the generate procedure so that only good
moves are generated.
5
Overview
• Improve the generate procedure so that only good
moves are generated.
plausible-moves vs. legal-moves
6
Overview
• Improve the test procedure so that the best moves
will be recognized and explored first.
7
Overview
• Improve the test procedure so that the best moves
will be recognized and explored first.
less moves to be evaluated
8
Overview
• It is not usually possible to search until a goal state is
found.
• It has to evaluate individual board positions by
estimating how likely they are to lead to a win.
Static evaluation function
• Credit assignment problem (Minsky, 1963).
9
Overview
• Good plausible-move generator.
• Good static evaluation function.
10
Minimax Search
• Depth-first and depth-limited search.
• At the player choice, maximize the static evaluation
of the next position.
• At the opponent choice, minimize the static
evaluation of the next position.
11
Minimax Search
-2
-2
A
C
Maximizing ply
Player
-6
-4
D
B
Minimizing ply
Opponent
E F G
9 -6 0
H I
0 -2
J K
-4 -3
Two-ply search
12
Minimax Search
Player(Position, Depth):
for each S SUCCESSORS(Position) do
∈
RESULT = Opponent(S, Depth + 1)
NEW-VALUE = PLAYER-VALUE(RESULT)
if NEW-VALUE > MAX-SCORE, then
MAX-SCORE = NEW-VALUE
BEST-PATH = PATH(RESULT) + S
return
VALUE = MAX-SCORE
PATH = BEST-PATH
13
Minimax Search
Opponent(Position, Depth):
for each S SUCCESSORS(Position) do
∈
RESULT = Player(S, Depth + 1)
NEW-VALUE = PLAYER-VALUE(RESULT)
if NEW-VALUE < MIN-SCORE, then
MIN-SCORE = NEW-VALUE
BEST-PATH = PATH(RESULT) + S
return
VALUE = MIN-SCORE
PATH = BEST-PATH
14
Minimax Search
Any-Player(Position, Depth):
for each S SUCCESSORS(Position) do
∈
RESULT = Any-Player(S, Depth + 1)
NEW-VALUE = − VALUE(RESULT)
if NEW-VALUE > BEST-SCORE, then
BEST-SCORE = NEW-VALUE
BEST-PATH = PATH(RESULT) + S
return
VALUE = BEST-SCORE
PATH = BEST-PATH
15
Minimax Search
MINIMAX(Position, Depth, Player):
• MOVE-GEN(Position, Player).
• STATIC(Position, Player).
• DEEP-ENOUGH(Position, Depth)
16
Minimax Search
1. if DEEP-ENOUGH(Position, Depth), then return:
VALUE = STATIC(Position, Player)
PATH = nil
2. SUCCESSORS = MOVE-GEN(Position, Player)
3. if SUCCESSORS is empty, then do as in Step 1
17
Minimax Search
4. if SUCCESSORS is not empty:
RESULT-SUCC = MINIMAX(SUCC, Depth+1, Opp(Player))
NEW-VALUE = - VALUE(RESULT-SUCC)
if NEW-VALUE > BEST-SCORE, then:
BEST-SCORE = NEW-VALUE
BEST-PATH = PATH(RESULT-SUCC) + SUCC
5. Return:
VALUE = BEST-SCORE
PATH = BEST-PATH
18
Adding Alpha-Beta Cutoffs
• At the player choice, maximize the static evaluation of
the next position.
> α threshold
• At the opponent choice, minimize the static evaluation
of the next position.
< β threshold
19
Adding Alpha-Beta Cutoffs
A
Maximizing ply
Player
3
> 3?
C
B
E
Minimizing ply
Opponent
< 4?
J
D
4
F
3
G H
2
Maximizing ply
Player
I
α cutoff
5
Minimizing ply
Opponent
β cutoff
20
Tải về để xem bản đầy đủ
28 trang
20400
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Trí tuệ nhân tạo - Chapter 8: Game playing", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_tri_tue_nhan_tao_chapter_8_game_playing.pdf
