連載講座 : 高生産並列言語を使いこなす (3) ゲーム木探索問題田浦健次朗東京大学大学院情報理工学系研究科, 情報基盤センター目次 1 概要 17 2 ゲーム木探索必勝必敗引き分け盤面の評価値 αβ 法指し手の順序付け (mo

Size: px

Start display at page:

Download "連載講座 : 高生産並列言語を使いこなす (3) ゲーム木探索問題田浦健次朗東京大学大学院情報理工学系研究科, 情報基盤センター目次 1 概要 17 2 ゲーム木探索必勝必敗引き分け盤面の評価値 αβ 法指し手の順序付け (mo"

みいかたにしき
4 years ago
Views:

1 連載講座 : 高生産並列言語を使いこなす (3) ゲーム木探索問題田浦健次朗東京大学大学院情報理工学系研究科, 情報基盤センター目次 1 概要 17 2 ゲーム木探索必勝必敗引き分け盤面の評価値 αβ 法指し手の順序付け (move ordering) 20 3 Andersson の詰み探索およびその並列化 Andersson の詰み探索コード指し手の順序付け局面の表現末端付近の最適化 23 4 並列化のための準備 : 逐次の基本コード作成次の局面の生成法コピー方式に伴う問題並列化のもととなるコード 25 5 逐次性能の測定 26 6 まとめ 28

2 1, [6] (End Game Solver)., ( ),,,., ( ).,, (move ordering).,,., Zebra[2] Gunnar Andersson End Game Solver [1],,. 2.,,.,,,. 2.1,,,,,.,,,.. g win(g), lose(g), win(g) g : g (1) g : g h lose(h) (2) lose(g) g : g (3) g : g h win(h) (4). h g, g ( ) h, g h.

3 2.2,. g, E(g), E(g) = E leaf (g) =. g, E(g).,, E(g) 1 max h:g h ( E(h)) 1 1 : 0 : 1 : E(g) = max ( E(h)) (6) h:g h g h h, E(h) 1 g h h, E(h) 1, E(g) 1 max ( E(h)) 1 h:g h g h h, E(h) 1 g h h, E(h) 1 (5), 2 E(g) 1 win(g), E(g) 1 lose(g) (2.1). E(g), g,,,.,,, E leaf (5),, E(g). E leaf (g) =,, E(g),,,,..,,., g ( ), E leaf (, ), (6) E(g), g., (6),.

4 2.3 αβ E(g),. eval(g) { if (g ) { return eval leaf(g); /* */ else { E = {; /* */ for (g h h) { E = E { eval(h) ; return max(e); eval(g), g h h eval,,, g h ( )., ( ) ( ),., E(g), g E(g) = max h:g h ( E(h)), E(g), g ( ). 2. E(g), g h, E(h) = e.,, E(g) e. g h h, E(h ) < e, E(g) ( )., E(h ) e E(h ).,, g a, g, a, g.. αβ. eval(g, α, β),. 1. E(g) β : β 2. E(g) α : α ( α)

5 /* E(g), E(g) α α E(g) β β */ eval(g, α, β) { if (g ) { return eval leaf(g); /* */ else { for (g h h) { α = max(α, eval(h, β, α)); if (α β) return α; /* E(g) β */ return α; 1: αβ 3. α < E(g) < β : E(g) eval(g, α, β), α < E(g) < β,, [α, β]. 2., E(g) α,. 1. α,. 2.4 (move ordering) αβ,,., g, E(g) β,. (= = )..,., [5, 4]. l ( : 2 ) d. 1 + d d l 1 = (d l 1)/(d 1). ( ), E(g) ( ).,,, eval(g,, ), 2d l/2 1., αβ,., αβ,,,. Andersson 3.

6 : 3 Andersson 3.1 Andersson, Zebra Basic End Solver [1], Basic endgame solver: When I started working on computer Othello I downloaded an endgame solver created by Warren Smith and later improved by Jean-Christophe Weill. I then improved it myself, the resulting solver is found here.., Zebra Basic endgame solver, Zebra. Basic endgame solver. 3.2, 3.,,,,. (1) 4 : 2, ( : NoParEndSolve).,,. (2) 4< 7 :. 3 5 (,, ).,,,., (1) ( : ParEndSolve). (3) >7 :., (1) ( : FastestFirstEndSolve).

7 3: 5. (5 ), (5 ), (2 ), (3 ), (8 ).,,,., ( ).,,.,,.,, (, ). 3.3, 3. Andersson C. ( unsigned char board[91]) ( ; int color) (int prevmove),,,., , 1, 64,,,. Andersson,. 3,,. = (int discdiff) (int empties)

8 d d d d d d d d d d 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 d 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7 d 2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7 d 3,0 3,1 3,2 3,3 3,4 3,5 3,6 3,7 d 4,0 4,1 4,2 4,3 4,4 4,5 4,6 4,7 d 5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7 d 6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7 d 7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7 d d d d d d d d d d 4:., d,,, EmHead Ems. struct EmList { int square; /*. board index */ int hole_id; /* */ struct EmList *pred; /* */ struct EmList *succ; /* */ EmHead, Ems[64]; ( int RegionParity) 1 3.4, (leaf). d (d 1)/d.., 1, 1 ( ), 1 for,.,. Andersson. 4 : 4.1 g h. : g, h i 1 64, bit

9 Undo : g h i ( g ), h i h i g (undo). undo, undo. Andersson undo.,.,,..,. OpenMP tasks, Cilk spawn, TBB,, eval. ( ),,.,. Cilk [3].,,, undo,.,,, + undo. MPI UPC SPMD, Pthreads,,, undo Andersson,,,., (board), (EmHead Ems), (RegionParity),,,.,.,.,,,., 3 (NoParEndSolve, ParEndSolve, Fastest- FastEndSolve),,,,.

10 4.3.. typedef struct game_state { char color_to_move; /* ( )*/ char last_move_was_pass; /*? */ char n_empties; /* */ char disc_diff; /* - */ unsigned int region_parity; /* */ square_list_node empty_squares[maxempties]; /* */ unsigned char board[91]; /* */ game_state, * game_state_t;,,, empty square. typedef struct square_list_node { char square; /* */ char hole_id; /* */ char pred_idx; /* */ char succ_idx; /* */ square_list_node;, g, g game state, *g = *g,., eval ( 4.3),, move and eval. 4.3, int n_moves = gen_moves(g, moves);, moves, ( 1),. eval, int e = -move_and_eval(*g, i, moves[i], -beta, -alpha);,., g i moves[i].. /* es_idx -1 ( ).,. */ int move_and_eval(game_state gg, int move_idx, int es_idx, int alpha, int beta) { game_state_t g = &gg; apply_move(g, es_idx); return eval(g, alpha, beta);

11 /* g */ int eval(game_state_t g, int alpha, int beta) { int moves[maxempties]; int n_moves = gen_moves(g, moves); if (n_moves == 0) { return g->disc_diff; else { int i; for (i = 0; i < n_moves; i++) { int e = -move_and_eval(*g, i, moves[i], -beta, -alpha); if (e > alpha) { alpha = e; if (e >= beta) break; return alpha; 5: eval apply move g. 3.4, (leaf). move and eval, eval., Andersson,,.,,. 6., (base code).. 5 Andersson.. CPU: Intel Nehalem-EX (E7540) 2.0GHz (6 core/12 4 ) L3 cache: 18MB memory: 24GB DDR3, Andersson, The FFO endgame test suite ( 7. 1, Andersson 10 6, 1.,

12 /* gg, (es_idx) */ int move_and_eval(game_state gg, int move_idx, int es_idx, int alpha, int beta) { game_state_t g = &gg; apply_move(g, es_idx); if (g->n_empties!= 1 g->last_move_was_pass) { return eval(g, alpha, beta); /* */ /* */ if (apply_move(g, first_move(g))) return -g->disc_diff; /* */ apply_move(g, -1); /*, */ if (apply_move(g, first_move(g))) return g->disc_diff; /*, */ return -g->disc_diff; 6: move and eval : ( )..

13 1: ( 10 6 ) elapsed time (sec) andersson base problem number 8: Andersson (andersson), (base) eval, 3.4, eval. 8 (. ), 9., Andersson 600 /, 400 /, 50%.,,,. 4.1,,,, undo,,. 6,,

14 2 base/andersson elapsed time ratio problem number 9: Andersson (andersson) (base) Andersson move ordering αβ, ( ),., Andersson 50%.,,,. [1] Gunnar Andersson. Andersson s endgame.c. [2] Gunnar Andersson. Zebra. [3] Don Dailey and Charles E. Leiserson. Using cilk to write multiprocessor chess programs. In Advances in Computer Games 9, [4] Donald E. Knuth. An Analysis of Alpha-Beta Pruning, chapter 9. Cambridge University Press, [5] Donald E. Knuth and Ronald W. Moore. An analysis of alpha-beta pruning. Artificial Intelligence, 6(4): , reprinted as [4]. [6] Wikipedia. ( ).

連載講座 : 高生産並列言語を使いこなす (4) ゲーム木探索の並列化田浦健次朗東京大学大学院情報理工学系研究科, 情報基盤センター目次 1 準備問題の定義 αβ 法 16 2 αβ 法の並列化概要 Young Brothers Wa

連載講座 : 高生産並列言語を使いこなす (4) ゲーム木探索の並列化田浦健次朗東京大学大学院情報理工学系研究科, 情報基盤センター目次 1 準備 16 1.1 問題の定義 16 1.2 αβ 法 16 2 αβ 法の並列化 17 2.1 概要 17 2.2 Young Brothers Wait Concept 17 2.3 段数による逐次化 18 2.4 適応的な待機 18 2. 強制終了

連載講座 : 高生産並列言語を使いこなす (3) ゲーム木探索問題 田浦健次朗 東京大学大学院情報理工学系研究科, 情報基盤センター 目次 1 概要 17 2 ゲーム木探索 必勝 必敗 引き分け 盤面の評価値 αβ 法 指し手の順序付け (mo

連載講座 : 高生産並列言語を使いこなす (3) ゲーム木探索問題田浦健次朗東京大学大学院情報理工学系研究科, 情報基盤センター目次 1 概要 17 2 ゲーム木探索必勝必敗引き分け盤面の評価値 αβ 法指し手の順序付け (mo