LIST OF ALGORITHMS NegaMax

Size: px

Start display at page:

Download "LIST OF ALGORITHMS 1..................................... 3 2......................................... 4 3 NegaMax............................... 6 4 "

妹裴充
7 years ago
Views:

1 Alpha-Beta Alpha-Beta λ

2.1........................................ 13 3.2.2...................................... 13 3.2.3 λ-....................................... 14 3.3....................................... 15 3.

2 LIST OF ALGORITHMS NegaMax Alpha-Beta List of Algorithms 1 MinMax Max Min NegaMax AlphaBeta AlphaBeta( with history) Dynamic Programming Monte Carlo λ Temporal Difference AlphaBeta( with hash, history) Reversi Learning ChooseAction D Reversi Othello C/S Server Client Client Agent Monitor Agent 2

............................................... 5 3 Min................................................ 6 4 NegaMax............................................. 7 5 AlphaBeta.

3 2. LIST OF ALGORITHMS (a) (b) 1: Monitor V (S) S S A(S) = arg max V (S ), S S a (1) a agent [1, pages 119] MinMax Search 3

4 2. LIST OF ALGORITHMS 2.1 mobility S V (S) = 8 8 ω[i, j] s[i, j] + Mobility( my color) (2) i = 1 j = 1 s[i, j] = 1 color[i, j] = my color 1 color[i, j] = opp color 0 otherwise (3) color[i, j] i j (i, j) my color opp color ω[i, j] (i, j) Mobility(my color) 2.2 Black W hite Black Black Max Max Black W hite W hite Min Min Max Min Black Black S i V (S i) V (S) a i Black S i V (S i ) V (S j ) S j S j a j a j V (S j ) V (S) 2 [2] 2: [3] 4

color 1 color[i, j] = opp color 0 otherwise (3) color[i, j] i j (i, j) my color opp color ω[i, j] (i, j)

5 2. LIST OF ALGORITHMS 1. Max Min 2. (a) Max (b) Min 3. Max Min Input: board board and max search depth depth Output: best move best move 1 best val ; 2 foreach move do 3 MakeMove(board, move, my color); 4 val Min(board, depth 1); 5 UnMakeMove(board, move, my color); 6 if val > best val then 7 best val val; 8 best move move; 9 return best move; 1 MinMax Input: board board and remain depth depth Output: maximum of its children notes 1 max ; 2 if depth 0 then 3 return Evaluate(board); 4 if! CanMove(board, my color) then 5 if! CanMove(board, opp color) then 6 Game Over 7 return Evaluate(board); 8 I stop for one time, opponent will take it 9 return Min(board, depth); 10 foreach move do 11 MakeMove(board, move, my color); 12 val Min(board, depth 1); 13 UnMakeMove(board, move, my color); 14 max = max(val, max); 15 return max; 2 Max 5

UnMakeMove(board, move, my color); 6 if val > best val then 7 best val val; 8 best move move; 9 return best move; 1 MinMax Input: board board and remain depth depth Output: maximum of its children

2. LIST OF ALGORITHMS Input: board board and remain depth depth Output: minimum of its children notes 1 min ; 2 if depth 0 then 3 return Evaluate(board); 4 if! CanMove(board, opp color) then 5 if!

6 2. LIST OF ALGORITHMS Input: board board and remain depth depth Output: minimum of its children notes 1 min ; 2 if depth 0 then 3 return Evaluate(board); 4 if! CanMove(board, opp color) then 5 if! CanMove(board, my color) then 6 return Evaluate(board); 7 return Max(board, depth); 8 foreach move do 9 MakeMove(board, move, opp color); 10 val Max(board, depth 1); 11 UnMakeMove(board, move, opp color); 12 min = min(val, min); 13 return min; 3 Min Evaluate V (S) Min Max NegaMax NegaMax [2] 3: NegaMax Alpha- Beta 2.3 Alpha-Beta 4 NegaMax [2] A Max B 6

CanMove(board, my color) then 6 return Evaluate(board); 7 return Max(board, depth); 8 foreach move do 9 MakeMove(board, move, opp color);

7 2. LIST OF ALGORITHMS Input: board board, side to move color and remain depth depth Output: maximum of its children notes 1 max ; 2 sign[my color] = 1; 3 sign[opp color] = 1; 4 if depth 0 then 5 return sign[color] Evaluate(board); 6 if! CanMove(board, color) then 7 if! CanMove(board, my color + opp color color) then 8 return sign[color] Evaluate(board); 9 return -NegaMax(board, my color + opp color color, depth); 10 foreach move do 11 MakeMove(board, move, color); 12 val -NegaMax(board, my color + opp color color, depth 1); 13 UnMakeMove(board, move, color); 14 max = max(val, max); 15 return max; 4 NegaMax 4: Alpha-Beta C D A B B B 6 B Min C E E 4-2 E Max E 4 C Min C 4 C A A Max B 4 F G α β α-β β α 1 α = β = α β B A B A Max A α α = 6 E C C Min C β 4 C α 6 A C β α α β Max 7

CanMove(board, my color + opp color color) then 8 return sign[color] Evaluate(board); 9 return -NegaMax(board, my color + opp color color, depth); 10 foreach move do 11 MakeMove(board, move,

8 2. LIST OF ALGORITHMS α α Min β Max α Min β β α Max β Min α α β Max S Max S 1. V (S ) α S 2. V (S ) β β 3. α < V (S ) < β Alpha-Beta 5 Input: board board, alpha α, beta β, side to move color and remain depth depth Output: useful maximum of its children notes 1 max ; 2 sign[my color] = 1; 3 sign[opp color] = 1; 4 if depth 0 then 5 return sign[color] Evaluate(board); 6 if! CanMove(board, color) then 7 if! CanMove(board, my color + opp color color) then 8 return sign[color] Evaluate(board); 9 return -AlphaBeta(board, β, α, my color + opp color color, depth); 10 foreach move do 11 MakeMove(board, move, color); 12 val -AlphaBeta(board, β, α, my color + opp color color, depth 1); 13 UnMakeMove(board, move, color); 14 if val > α then 15 if val β then 16 return val; 17 α = max(val, α); 18 max = max(val, max); 19 return max; 5 AlphaBeta Alpha-Beta Max Min 8

= 1; 4 if depth 0 then 5 return sign[color] Evaluate(board); 6 if! CanMove(board, color) then 7 if!

9 2. LIST OF ALGORITHMS 2.4 Alpha-Beta Alpha-Beta MinMax history[2, 65, 65] historye[black, 15, 1] Black 15 history[black, 15, 2] history Black step 5 64 depth step + depth move FloatMove(Black, step + depth, move) move move AdvantageMove(Black, step + depth, move) move 6 Input: board board, alpha α, beta β, side to move color and remain depth depth Output: useful maximum of its children notes 1 max ; 2 sign[my color] = 1; 3 sign[opp color] = 1; 4. 5 foreach move history do 6 MakeMove(board, move, color); 7 val -AlphaBeta(board, β, α, my color + opp color color, depth 1); 8 UnMakeMove(board, move, color); 9 if val > α then 10 if val β then 11 FloatMove(color, step + max depth depth, move); 12 return val; 13 AdvantageMove(color, step + max depth depth, move); 14 α = max(val, α); 15 max = max(val, max); 16 return max; 6 AlphaBeta( with history) Transposition Table

AdvantageMove(Black, step + depth, move) move 6 Input: board board, alpha α, beta β, side to move color and remain depth depth Output: useful maximum of its children notes 1 max ; 2 sign[my color] =

10 2. LIST OF ALGORITHMS Black W hite hash hash HashKey(S) = 8 8 mask[ s[i, j] + 1, i, j] (4) i = 1 j = 1 mask hash key hash key flip flip f lip[old, new, i, j] = mask[new, i, j] mask[old, i, j] (5) HashKey(S) = HashKey(S ) flip[ s[i, j] + 1, s [i, j] + 1, i, j] (6) i = 1 j = 1 hash key S (i, j) old new hash key hash key = hash key + f lip[old, new, i, j] (7) hash key hash key hash max depth score nodes 2 NO BOUND α UP BOUND β LOW BOUND 3 Ubuntu Linux , AMD x MHz, 1011M RAM 4 Hash Alpha-Beta History Alpha-Beta HashHistory Alpha-Beta 10

mask[old, i, j] (5) HashKey(S) = HashKey(S ) + 8 8 flip[ s[i, j] + 1, s [i, j] + 1, i, j] (6) i = 1 j = 1 hash key S (i, j) old new hash key hash

11 2. LIST OF ALGORITHMS total time exact hash part hash Alpha-Beta max depth score nodes total time exact part MinMax 5 4:60 339, AlphaBeta 8 12:51 908, Hash 8 19:45 375, ,3714 4,7596 History 9 11: , HashHistory 10 23: , , ,1421 1: 2 1 ray nodes = 30 max depth i=0 ray i ray [(nodes/30)(ray 1) + 1] 1/(max depth+1) ray time per node time per node = toatl time/nodes time per node time per node time per node exact rate part rate ray ray time per node exact rate part rate MinMax % 0.0% AlphaBeta % 0.0% Hash % 1.27% History % 0.0% HashHistory % 2.28% 2: 2 AlphaBeta MinMax AlphaBeta AlphaBeta MinMax AlphaBeta

428 60,1814 32,1421 1: 2 1 ray nodes = 30 max depth i=0 ray i 30 30 ray [(nodes/30)(ray 1) + 1] 1/(max depth+1) ray time per node time per node = toatl time/nodes time per node time per node time

12 3. LIST OF ALGORITHMS 3 Reinforcement Learning 3.1 [4, pages 263] 5 state action reward policy 5: [7] 6 6: Markov decision process, MDP S A t s t a t r t+1 = r(s t, a t ) s t+1 = δ(s t, a t ) r δ MDP r(s t, a t ) δ(s t, a t ) δ T : S A S [0, 1] T (s, a, s ) s a s s T (s, a, s ) = 1 δ(s t, a t ) [6, page 13] δ(s t, a t ) π : S A s t a t π(s t ) = a t s t R t = r t+1 + r t+2 + r t r T (8) 12

r t+1 = r(s t, a t ) s t+1 = δ(s t, a t ) r δ MDP r(s t, a t ) δ(s t, a t ) δ T : S A S [0, 1] T (s,

13 3. LIST OF ALGORITHMS r t+i s t π Episode task T T = 0 R t = i=0 r t+i+1 γ 0 γ 1 R t = γ i r t+i+1 (9) s π s i=0 V π π π V π (s) = R t = γ i r t+i+1 (10) s V π (s) V π (s) V π V π V π π π π V V π i=0 π (s t ) = arg max V (s t+1 ) (11) a V V V 1, V 2,..., V k,... Bellman equation [8] V (s t ) = r t+1 + γv (s t+1 ) (12) V k+1 (s) max a (r t+1 + γv k (s )), s = δ(s, a) (13) δ r Monte Carlo s R s, a 8 visits[s] s 13

max V (s t+1 ) (11) a 3.2 3.2.1 V V V 1, V 2,..., V k,.

14 3. LIST OF ALGORITHMS 1 foreach s do 2 V [s] 0; 3 repeat 4 s Initial( ); 5 repeat 6 a arg maxv [δ(s, a)]; 7 Execute(a); a 8 r Reward(s, a); 9 s Observe( ); 10 V [s] r + γv [s ]; 11 s s ; 12 until s = terminal; 13 until end; 7 Dynamic Programming λ- Temporal Difference [6] V (s t ) V (s t ) + α [r t+1 + γv (s t+1 ) V (s t )] (14) α 0 1 [6] α = visits[s t ] (15) s λ λ- TD(λ) t δ t = r t+1 + γv (s t+1 ) V (s t ) (16) : V (s) V (s) + αδ t e t (s) (17) 14

15 3. LIST OF ALGORITHMS 1 foreach s do 2 V [s] 0; 3 visits[s] 0; 4 repeat 5 s Initial( ); 6 repeat 7 (S, A) GenerateEpisode(s, π); 8 foreach (s t, a t ) (S, A) do 9 R i 0 γi r(s t+i+1, a t+i+1 ); R V [s t] visits[s t ] + R ; visits[s t ] V [s t ] R; 14 visits[s t ] visits[s t ] + 1; 15 until s = terminal; 16 until end; 8 Monte Carlo e t (s) s t s e t (s) e(s) λ { γλe t 1 (s) + 1 s = s t e t (s) = (18) γλe t 1 (s) s s t 9 λ 3.3 MAS λ- P s P (s) s s 65 s[0] s[0] = 0.0 s[0] = s[k] = 0.0 k s[k] = 1.0 s[k] = 0.5 V (s) 6 { P (s) s[0] = my color V (s) = (19) 1.0 P (s) s[0] = opp color 6 V (s) s V (s) s 15

terminal; 16 until end; 8 Monte Carlo e t (s) s t s e t (s) e(s) λ { γλe t 1 (s) + 1 s = s t e t (s) = (18) γλe t 1 (s) s s t 9 λ 3.

16 3. LIST OF ALGORITHMS 1 foreach s do 2 V [s] 0; 3 e[s] 0; 4 repeat 5 s Initial( ); 6 S ; 7 repeat 8 a π(s); 9 Execute(a); 10 r Reward(s, a); 11 s Observe( ); 12 S S s; 13 δ r + γv [s ] V [s]; 14 e[s] e[s] + 1; 15 foreach s S do 16 V [s] V [s] + αδe[s]; 17 e[s] γλe[s]; 18 s s ; 19 until s = terminal; 20 until end; 9 λ Temporal Difference V (s) s V (s) P (s) λ = 0, γ = 1 P (s) + α(p (s ) P (s)) s[0] = s [0] P (s) + α(1.0 P (s ) P (s)) s[0] s [0] P (s) = 1.0 s s[0] (20) 0.5 s 0.0 s s[0] λ- e(s) V (s) P (s) P (s) s P (s) λ

s ; 19 until s = terminal; 20 until end; 9 λ Temporal Difference V (s) s V (s) P (s) λ = 0, γ = 1 P (s) + α(p (s ) P (s)) s[0] = s [0] P

17 4. LIST OF ALGORITHMS 3.4 λ = 0.7 α = 0.1 γ = 1.0 sigmoid learning_curve : AlphaBeta AlphaBeta AlphaBeta λ- 7 Ubuntu Linux , AMD x MHz, 1011M RAM 17

02 0 0 1000 2000 3000 4000 5000 7: 5000 8 5000 0.5 4.

18 1 init_black win possibility learn time 8: hash key [1] Nils J. Nilsson: Artifficial Intelligence: A New Synthesis, China Machine Press, Beijing, 2000 [2] Hamed Ahmadi Nejad: An Introduction to Game Tree Algorithms, ahmadinejad/gametree/ [3] Bruce Moreland: Min-Max Search: An obvious place to start, brucemo/topics/minmax.html [4] Tom M. Mitchell: Machine Learning, China Machine Press, Beijing, 2003 [5] Richard S. Sutton and Andrew G. Barto: Reinforcement Learning: An Introduction, MIT Press, Cambridge, MA,

http://ce.sharif.edu/ ahmadinejad/gametree/ [3] Bruce Moreland: Min-Max Search: An obvious place to start, http://www.seanet.com/ brucemo/topics/minmax.

19 [6] [7] 25(7): , S, 2003 [8] Mance E. Harmon and Stephanie S. Harmon: Reinforcement Learning: A Tutorial, Wright-Patterson AFB, OH, D 19

20 1 Input: board board, alpha α, beta β, side to move color and remain depth depth Output: useful maximum of its children notes. 2 best move = 0; 3. 4 switch MatchType(color, alpha, beta) do 5 case EXACTLY 6 return MatchEvaluate( ); 7 case PARTLY 8 best move MatchBestMove( ); 9 if best move 0 then 10 MakeMove(board, best move, color); 11 val -AlphaBeta(board, β, α, my color + opp color color, depth 1); 12 UnMakeMove(board, best move, color); 13 if val > α then 14 if val β then 15 FloatMove(color, step + max depth depth, move); 16 return val; 17 AdvantageMove(color, step + max depth depth, move); 18 α = max(val, α); 19 max = max(val, max); 20 foreach move history move best move do if val > α then 23 if val β then 24 FloatMove(color, step + max depth depth, move); 25 Because we use nega-method, no LOW BOUND wanted 26 Insert(color, val, move, UP BOUND); 27 return val; 28 AdvantageMove(color, step + max depth depth, move); 29 α = max(val, α); 30 Insert(color, max, move, NO BOUND); 31 max = max(val, max); 32 return max; 10 AlphaBeta( with hash, history) 20

-AlphaBeta(board, β, α, my color + opp color color, depth 1); 12 UnMakeMove(board, best move, color); 13 if val > α then 14 if val β then 15 FloatMove(color, step + max depth depth, move); 16 return

21 1 repeat 2 s Initial( ); 3 S ; 4 while true do 5 if CanMove(s, Black) then 6 a ChooseAction(Black, s, S); 7 Execute(a); 8 if CanMove(s, W hite) then 9 a ChooseAction(W hite, s, S); 10 Execute(a); 11 if! CanMove(s, Black)! CanMove(s, W hite) then 12 break; 13 until end; 11 Reversi Learning Input: side to move color, current state s and state list S Output: the best action a 1 mark[black] = 1.0; 2 mark[w hite] = 0.0; 3 4 a arg maxv [δ(s, a)]; a 5 max V [δ(s, a)]; 6 S S s; 7 δ m max V (s); 8 δ o δ m ; 9 f lag mark[color]; 10 s 0 s; 11 foreach s S do 12 e λ dist(s, s0) ; 13 if s[0] = f lag then 14 train P (s) + αδ m e; 15 else 16 train P (s) + αδ o e; 17 TrainNetwork(s, train); 18 return a; 12 ChooseAction 21

Figure 1: Game Tree 为了方便讨论, 我们这里设这里讨论的博弈树是一棵有限树, 设有两个棋手甲与乙进行这场博弈, 这样, 博弈树分为三类结点 : 1. 奇数层的非叶子结点 :

Figure 1: Game Tree 为了方便讨论, 我们这里设这里讨论的博弈树是一棵有限树, 设有两个棋手甲与乙进行这场博弈, 这样, 博弈树分为三类结点 : 1. 奇数层的非叶子结点 : 从极大极小算法到主要变例搜索孙锴 1 综述人机对弈在计算机诞生前就开始了发展, 时至今日, 人机对弈领域提出的搜索算法数目已经非常之多, 但从根本上看, 许多搜索算法之间的内在的核心思想是一致的本文介绍将从极大极小搜索