Logistello 1) playout playout 1 5) SIMD Bitboard playout playout Bitboard Bitboard 8 8 = black white 2 2 Bitboard 2 1 6) position rev i

Size: px

Start display at page:

Download "Logistello 1) playout playout 1 5) SIMD Bitboard playout playout Bitboard Bitboard 8 8 = black white 2 2 Bitboard 2 1 6) position rev i"

ぎんとにばし
5 years ago
Views:

1 SIMD playout playout Cell B. E. SIMD SIMD playout playout Implementation of an Othello Program Based on Monte-Carlo Tree Search by Using a Multi-Core Processor and SIMD Instructions YUJI KUBOTA, 1 YOSHIKUNI SATO 1 and DAISUKE TAKAHASHI 1 Recently Monte-Carlo Tree Search is attracting attention in Computer-Go. Because the performance of Monte-Carlo Tree Search is related to the execution speed of playouts, programs become stronger by executing playouts faster. In this paper, we aim to accelerate playouts of an Othello program based on Monte-Carlo Tree Search. We implemented an Othello program based on Monte-Carlo Tree Search by using Cell B. E. that is a multi-core processor and SIMD instructions and evaluated the speed-up of playouts. We accelerated the processing to reverse pieces by using SIMD instructions and parallelized playouts by using a multi-core prosessor. Furthermore our experiments showed that the speed-up of playouts raised win rate. 1. 1)2) playout playout Playout playout playout playout PC Single Instruction Multiple Data SIMD playout playout SIMD Cell Broadband Engine Cell B. E. playout Logistello 3)4) Graduate School of Systems and Information Engineering, University of Tsukuba 1 c 2009 Information Processing Society of Japan

2 Logistello 1) playout playout 1 5) SIMD Bitboard playout playout Bitboard Bitboard 8 8 = black white 2 2 Bitboard 2 1 6) position rev invert Bitboard Bitboard. 8 Bitboard 1 reverse left( position, color) co invert(color) & 0x7e7e7e7e7e7e7e7e e1 (position >> 1) & co e2 (e1 >> 1) & co e3 (e2 >> 1) & co e4 (e3 >> 1) & co e5 (e4 >> 1) & co e6 (e5 >> 1) & co b1 (color << 1) & co b2 (b1 << 1) & co b3 (b2 << 1) & co b4 (b3 << 1) & co b5 (b4 << 1) & co b6 (b5 << 1) & co rev e6 & b1 rev rev (e5 & (b1 b1 b2)) rev rev (e4 & (b1 b1 b3)) rev rev (e3 & (b1 b1 b4)) rev rev (e2 & (b1 b1 b5)) rev rev (e1 & (b1 b6)) return rev 1 Bitboard check left( color) w invert(color) & 0x7e7e7e7e7e7e7e7e t w & (color << 1) mobility blank & (t << 1) return mobility 2 Bitboard 2 7) playout 1 playout playout 3 1 UCT Upper Confidence bounds 2 c 2009 Information Processing Society of Japan

3 黒の手番白の手番黒の勝利白の勝利 3 探索シミュレーション Playout applied to Trees 8) UCB1 9) UCB1 (1) 2 log n x i + (1) n i x i i n i i n i (1) SIMD SIMD Bitboard SIMD playout 1 playout SIMD co invert(color) & 0x7e7e7e7e7e7e7e7e e1 (position << 1) & co e2 (e1 << 1) & co e3 (e2 << 1) & co e4 (e3 << 1) & co e5 (e4 << 1) & co e6 (e5 << 1) & co b1 (color >> 1) & co b2 (b1 >> 1) & co b3 (b2 >> 1) & co b4 (b3 >> 1) & co b5 (b4 >> 1) & co b6 (b5 >> 1) & co 右方向の反転パターン取得 co invert(color) & 0x7e7e7e7e7e7e7e7e e1 (position >> 1) & co e2 (e1 >> 1) & co e3 (e2 >> 1) & co e4 (e3 >> 1) & co e5 (e4 >> 1) & co e6 (e5 >> 1) & co b1 (color << 1) & co b2 (b1 << 1) & co b3 (b2 << 1) & co b4 (b3 << 1) & co b5 (b4 << 1) & co b6 (b5 << 1) & co 左方向の反転パターン取得 4 SIMD co invert(color) & 0x7e7e7e7e7e7e7e7e vec_color {co, co} vec_pos {position, color} vec_e1 vec_shiftleft(vec_pos, 1) vec_e1 vec_and(vec_e1, vec_color) vec_e2 vec_shiftleft(vec_e1, 1) vec_e2 vec_and(vec_e2, vec_color) vec_e3 vec_shiftleft(vec_e2, 1) vec_e3 vec_and(vec_e3, vec_color) vec_e4 vec_shiftleft(vec_e3, 1) vec_e4 vec_and(vec_e4, vec_color) vec_e5 vec_shiftleft(vec_e4, 1) vec_e5 vec_and(vec_e5, vec_color) vec_e6 vec_shiftleft(vec_e5, 1) vec_e6 vec_and(vec_e6, vec_color) vec_pos {color, position} vec_b1 vec_shiftright(vec_pos, 1) vec_b1 vec_and(vec_b1, vec_color) vec_b2 vec_shiftright(vec_b1, 1) vec_b2 vec_and(vec_b2, vec_color) vec_b3 vec_shiftright(vec_b2, 1) vec_b3 vec_and(vec_b3, vec_color) vec_b4 vec_shiftright(vec_b3, 1) vec_b4 vec_and(vec_b4, vec_color) vec_b5 vec_shiftright(vec_b4, 1) vec_b5 vec_and(vec_b5, vec_color) vec_b6 vec_shiftright(vec_b5, 1) vec_b6 vec_and(vec_b6, vec_color) SIMD 演算を用いた左右方向の反転パターン取得 1 3 c 2009 Information Processing Society of Japan

4 1 SIMD 4.2 5) 1 playout 5. Cell Broadband Engine 5.1 Cell B. E. Cell B. E. 1 PowerPC Processor Element PPE 8 Synergistic Processor Element 10) PLAYSTATION3 Cell B. E. Cell B. E. 6 PPE 64 PowerPC OS SIMD 256KB PPE Element Interconnect Bus EIB 5 Cell B. E. PPE 5 Element Interconnect Bus Cell B. E. Cell B. E. SIMD PPE Vector Multimedia Extension VMX SIMD Cell B. E. SIMD SIMD SIMD VMX 11) PPE- Direct Memory Access DMA Mailbox DMA CPU 16KB 16B DMA 16B Mailbox FIFO PPE Cell B. E. Cell B. E. Cell B. E. PPE PPE 3 PPE PPE 4 c 2009 Information Processing Society of Japan

5 DMA PPE PPE Mailbox PPE playout uct() 6 PPE 7 while 1 do playsim(root) end while playsim(root) node[0] root while node[i] do if node[i] then createchildren(node[i]) end if node[i + 1] selectnode(node[i]) i i + 1 end while while do check(spe[j]) j j + 1 if j -1 then j 0 end if end while result spe run(spe[j]) update(result, node) 6 PPE 6 7 createchildren(node): node selectnode(node): node (1) check(spe): spe SEP spe run(spe): spe update(result, node): node result Sim spe() loop if PPE then getboard() result randomsim() putresult(result) end if end loop 7 getboard(): DMA randomsim(): putresult(result): result PPE Mailbox SIMD 5.1 SIMD 2 SIMD 2 SIMD SIMD SIMD 4 1 SIMD SIMD (1) Cell B. E. PPE playout 1 PPE 1 playout 5 c 2009 Information Processing Society of Japan

6 Playout 3 Cell B. E PPE 1 PPE playout PPE 1 1 PPE Playouts/sec( 初手 ) sequential SIMD PPE 0 playout 探索ごとのシミュレーション回数 8 SIMD 6.1 Cell B.E. 1 1 Cell B.E. PLAYSTATION3 CPU PPE OS Fedora 9 GNU/Linux fc9.ppc64 C ppu-gcc spu-gcc O3 6.2 SIMD SIMD playout 1 playout SIMD sequential SIMD SIMD SIMD 8 SIMD SIMD SIMD 32 1 PPE 6.3 SIMD playout PPE 6 c 2009 Information Processing Society of Japan

7 Playouts/sec( 初手 ) のコア数探索ごとのシミュレーション回数 1 回 2 回 4 回 8 回 16 回 32 回 64 回 128 回勝率探索ごとのシミュレーション回数 9 10 playout 6.4 Playout SIMD SIMD playout playout 16 playout playout 7. SIMD Cell B. E. playout SIMD Cell B. E. 2 SIMD 7.8 playout playout playout SIMD SIMD playout 7 c 2009 Information Processing Society of Japan

8 1) Coulom, R.: Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search, Proc. 5th International Conference on Computer and Games (vanden Herik, J.H., Ciancarini, P. and Donkers, j. H. H. L.M., eds.), Lecture Notes in Computer Science, No.4630, Springer-Verlag, pp (2006). 2) (Monte- Carlo Tree Search A Revolutionary Algorithm Developed for Computer Go) Vol.49, No.6, pp (2008). 3) Buro, M.: The Evolution of Strong Othello Programs, Entertainment Computing - Technology and Applications (Nakatsu, R. and Hoshino, J., eds.), Kluwer, pp (2003). 4) Buro, M.: LOGISTELLO s Homepage, mburo/ log.html. 5) MC/UCT 12 pp (2007). 6) bitboard pages/48.html. 8) Kocsis, L. and Szepesvari, C.: Bandit based Monte-Carlo Planning, Proc. 17th European Conference on Machine Learning, Lecture Notes in Computer Science, No.4212, Springer- Verlag, pp (2006). 9) Auer, P., Fischer, P. and Cesa-Bianchi, N.: Finite-time Analysis of the Multi-armed Bandit Problem, Machine Learning, Vol.47, pp (2002). 10) Cell Broadband Engine : (,, I, ). ICD, Vol.105, No.569, pp (2006). 11) Sony Computer Entertainment Inc.: Cell Broadband Engine C/C++ Extensions for CBEA v23 j.pdf. 8 c 2009 Information Processing Society of Japan

The 19th Game Programming Workshop 2014 SHOT 1,a) 2 UCT SHOT UCT SHOT UCT UCT SHOT UCT An Empirical Evaluation of the Effectiveness of the SHOT algori

The 19th Game Programming Workshop 2014 SHOT 1,a) 2 UCT SHOT UCT SHOT UCT UCT SHOT UCT An Empirical Evaluation of the Effectiveness of the SHOT algori SHOT 1,a) 2 UCT SHOT UCT SHOT UCT UCT SHOT UCT An Empirical Evaluation of the Effectiveness of the SHOT algorithm in Go and Gobang Masahiro Honjo 1,a) Yoshimasa Tsuruoka 2 Abstract: Today, UCT is the most