Minimax Search ■Minimax values can be found by depth-first game-tree search ■Introduced by Claude Shannon:Programming a Computer for Playing Chess Ran on paper! # 口卡回t·三4色，是分Q0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Minimax Search
Minimax Search Example max -2 2 min 2 4 max 2 111n 4口◆4⊙t1三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Minimax Search Example
Game tree(2-player,deterministic,turns) MAX闲 MIN MAX闭 M时O可 ERMA 口·三4，进分双0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Game tree (2-player, deterministic, turns)
Deterministic Two-Player E.g.tic-tac-toe,chess,checkers Game search A state-space search tree Players alternate Players Each layer,or ply,consists of a round of moves Choose move to position with highest achievable utility Zero-sum games One player maximizes result The other minimizes result max min 4口◆4⊙t1三1=，￥9QC
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Deterministic Two-Player ▶ E.g. tic-tac-toe, chess, checkers ▶ Game search ▶ A state-space search tree ▶ Players alternate ▶ Players Each layer, or ply, consists of a round of moves ▶ Choose move to position with highest achievable utility ▶ Zero-sum games ▶ One player maximizes result ▶ The other minimizes result
Table of Contents Games Perfect play(最优策略) minimax decisions o-8 Pruning Resource limits and approximate evaluation Gam苎of chance(包含几率因素的游戏) Games of imperfect information 口卡回t·三4色，是分Q0
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Table of Contents Games Perfect play（最优策略） minimax decisions α − β Pruning Resource limits and approximate evaluation Games of chance (包含几率因素的游戏) Games of imperfect information