p-9-10.eps

Similar documents

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

[1] AI [2] Pac-Man Ms. Pac-Man Ms. Pac-Man Pac-Man Ms. Pac-Man IEEE AI Ms. Pac-Man AI [3] AI 2011 UCT[4] [5] 58,990 Ms. Pac-Man AI Ms. Pac-Man 921,360

世界コンピュータ将棋選手権 [30] CSA CSA 電王戦 [31] Computer Olympiad [32] ICGA コンピュータ将棋対局場 [33],floodgate [34] 24 floodgate floodgate

UCT探索を用いた大貧民クライアント

TD 2048 TD 1 N N 2048 N TD N N N N N N 2048 N 2048 TD 2048 TD TD TD 2048 TD 2048 minimax 2048, 2048, TD, N i

Mastering the Game of Go without Human Knowledge ( ) AI 3 1 AI 1 rev.1 (2017/11/26) 1 6 2

IPSJ SIG Technical Report Vol.2016-GI-35 No /3/9 StarCraft AI Deep Q-Network StarCraft: BroodWar Blizzard Entertainment AI Competition AI Convo

Run-Based Trieから構成される決定木の枝刈り法

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

JVRSJ Vol.18 No.3 September, NPC RTS Real-time Simulation NPC NPC NPC AI NPC 4 AI 2 AI 図 1 ゲームとユーザエクスペリエンス reality a

3.1 Thalmic Lab Myo * Bluetooth PC Myo 8 RMS RMS t RMS(t) i (i = 1, 2,, 8) 8 SVM libsvm *2 ν-svm 1 Myo 2 8 RMS 3.2 Myo (Root

(MIRU2008) HOG Histograms of Oriented Gradients (HOG)

(a) 1 (b) 3. Gilbert Pernicka[2] Treibitz Schechner[3] Narasimhan [4] Kim [5] Nayar [6] [7][8][9] 2. X X X [10] [11] L L t L s L = L t + L s

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

3 2 2 (1) (2) (3) (4) 4 4 AdaBoost 2. [11] Onishi&Yoda [8] Iwashita&Stoica [5] 4 [3] 3. 3 (1) (2) (3)

The 15th Game Programming Workshop 2010 Magic Bitboard Magic Bitboard Bitboard Magic Bitboard Bitboard Magic Bitboard Magic Bitboard Magic Bitbo

2). 3) 4) 1.2 NICTNICT DCRA Dihedral Corner Reflector micro-arraysdcra DCRA DCRA DCRA 3D DCRA PC USB PC PC ON / OFF Velleman K8055 K8055 K8055

2 (S, C, R, p, q, S, C, ML ) S = {s 1, s 2,..., s n } C = {c 1, c 2,..., c m } n = S m = C R = {r 1, r 2,...} r r 2 C \ p = (p r ) r R q = (q r ) r R

　　医　事　法　　　　　　　山口大法医　藤宮龍也

PowerPoint プレゼンテーション

A Japanese Word Dependency Corpus ÆüËÜ¸ì¤ÎÃ±¸ì·¸¤ê¼õ¤±¥³¡¼¥Ñ¥¹

IPSJ SIG Technical Report Vol.2011-CE-110 No /7/9 Bebras 1, 6 1, 2 3 4, 6 5, 6 Bebras 2010 Bebras Reporting Trial of Bebras Contest for K12 stud

1 Kinect for Windows M = [X Y Z] T M = [X Y Z ] T f (u,v) w 3.2 [11] [7] u = f X +u Z 0 δ u (X,Y,Z ) (5) v = f Y Z +v 0 δ v (X,Y,Z ) (6) w = Z +

THE INSTITUTE OF ELECTRONICS, INFORMATION AND COMMUNICATION ENGINEERS TECHNICAL REPORT OF IEICE {s-kasihr, wakamiya,

Haiku Generation Based on Motif Images Using Deep Learning Koki Yoneda 1 Soichiro Yokoyama 2 Tomohisa Yamashita 2 Hidenori Kawamura Scho

リコー工業所有権紹介｜リコーテクニカルレポートNo.23

RoboCup 1 2D 3D Figre 1 2 2D 3D 2D 2D 3D 2D 2D Earth Mover s Distance Earth Mover s Distance 3.1 (x y ) p i w pi Figure 3 opuscom Uv

IHI Robust Path Planning against Position Error for UGVs in Rough Terrain Yuki DOI, Yonghoon JI, Yusuke TAMURA(University of Tokyo), Yuki IKEDA, Atsus

Convolutional Neural Network A Graduation Thesis of College of Engineering, Chubu University Investigation of feature extraction by Convolution

FINAL PROGRAM 22th Annual Workshop SWoPP / / 2009 Sendai Summer United Workshops on Parallel, Distributed, and Cooperative Processing

IPSJ SIG Technical Report Vol.2013-ARC-206 No /8/1 Android Dominic Hillenbrand ODROID-X2 GPIO Android OSCAR WFI 500[us] GPIO GP

2011 : M Schell Interest curve Schell Chan FPS Schell Interest curve Chan FPS Chan Chan Chan Chan

[1] [2] [3] (RTT) 2. Android OS Android OS Google OS 69.7% [4] 1 Android Linux [5] Linux OS Android Runtime Dalvik Dalvik UI Application(Home,T

MAC root Linux 1 OS Linux 2.6 Linux Security Modules LSM [1] Security-Enhanced Linux SELinux [2] AppArmor[3] OS OS OS LSM LSM Performance Monitor LSMP

[2] 2. [3 5] 3D [6 8] Morishima [9] N n 24 24FPS k k = 1, 2,..., N i i = 1, 2,..., n Algorithm 1 N io user-specified number of inbetween omis

The Plasma Boundary of Magnetic Fusion Devices

非線形長波モデルと流体粒子法による津波シミュレータの開発 I_ m ρ v p h g a b a 2h b r ab a b Fang W r ab h 5 Wendland 1995 q= r ab /h a d W r ab h

149 (Newell [5]) Newell [5], [1], [1], [11] Li,Ryu, and Song [2], [11] Li,Ryu, and Song [2], [1] 1) 2) ( ) ( ) 3) T : 2 a : 3 a 1 :

IPSJ SIG Technical Report Vol.2014-DBS-159 No.6 Vol.2014-IFAT-115 No /8/1 1,a) 1 1 1,, 1. ([1]) ([2], [3]) A B 1 ([4]) 1 Graduate School of Info

Transcription:

Root 08M37189 21 22 1 29

Root Tree Fuego Root Tree Root Root 2 Fuego Root CPU Root 64CPU Chaslot Root Root 1

1 7 1.1................................ 7 1.2................................. 8 1.3.................................. 8 1.4.................................. 9 2 10 2.1.................................. 10 2.1.1.............................. 10 2.1.2............................ 13 2.1.3.......................... 15 2.1.4................... 15 2.2........................... 18 2.2.1............... 18 2.2.2 RAVE.................................. 18 2.3.......................... 19 2.3.1................ 19 2.3.2 Leaf............................... 20 2.3.3 Tree............................... 21 2.3.4 Root............................... 22 2.3.5................ 24 3 Root 26 3.1 Fuego ( ).......................... 26 3.2.................................. 28 3.3...................................... 28 3.3.1................... 28 3.3.2............... 30 3.3.3................................. 30 3.4.............................. 31 4 33 4.1..................................... 33 4.2..................................... 33 4.3................................... 34 4.4 Root..................... 35 4.5 Root Tree...................... 37 2

4.6 Root Tree....................... 38 4.7............................. 40 4.8.......................... 41 4.9 Root...................... 44 4.9.1............................. 44 4.9.2 Root......... 46 4.9.3 Root...................... 46 4.9.4............................. 48 4.9.5.......................... 54 5 56 5.1...................................... 56 5.2................................... 58 3

2.1 3 3.......................... 10 2.2 MiniMax................................. 12 2.3.................................. 14 2.4....................... 17 2.5.............................. 18 2.6 Leaf............................ 20 2.7 Tree............................ 21 2.8 Root........................... 23 2.9 Root.................... 24 3.1 fuego....................................... 26 3.2 fuego [5]...................... 27 3.3 Bonanza............ 29 3.4.............................. 31 3.5.................................. 32 4.1 9 :Root ( 4 64 ) vs Fuego....... 35 4.2 9 :Root ( 4 64 RAVE ) vs Fuego(RAVE )...................................... 36 4.3 9 :Root ( 4 64 ) vs Mogo....... 36 4.4 19 :Root ( 4 64 ) vs Fuego...... 37 4.5 19 :Root ( 4 64 ) vs Mogo...... 38 4.6 9 :Root ( 64 )vstree (1 8 )..... 39 4.7 19 :Root ( 64 )vstree (1 8 )..... 39 4.8 F tree ( )................. 43 4.9 F tree ( )................. 43 4.10 9 :F80s : Fuego,Root ( ),Tree...................................... 45 4.11 19 :F80s : Fuego,Root ( ),Tree...................................... 46 4.12 19 :F80s : Root ( 64-512....... 47 4.13 19 :F80s : Root ( 1-512 )...... 47 4.14 9 (0 0.2)............... 49 4.15 9 (0.2 0.4).............. 49 4.16 9 (0.4 0.6).............. 50 4.17 9 (0.6 0.8).............. 50 4.18 9 (0.8 1.0).............. 51 4

4.19 19 (0 0.2).............. 51 4.20 19 (0.2 0.4)............. 52 4.21 19 (0.4 0.6)............. 52 4.22 19 (0.6 0.8)............. 53 4.23 19 (0,8 1.0)............. 53 4.24 9...................... 54 4.25 19..................... 55 5.1 19.......................... 60 5.2 19.......................... 61 5.3 19.......................... 61 5.4 19.......................... 62 5.5 19.......................... 62 5.6 9........................... 63 5.7 9........................... 63 5.8 9........................... 64 5.9 9........................... 64 5.10 9........................... 65 5

2.1 ( )............................ 11 2.2 10000 Single-Run Multiple-Runs GnuGo3.6 (T.Cazenave et al. 2006)....... 24 2.3 13 1 Root Tree GnuGo3.7.10 (G.Chaslot et al. 2008)...................... 25 2.4 9 Root Tree GnuGo3.7.10 (G.Chaslot et al. 2008)................................... 25 4.1 9 (%)(8 8Root )......... 39 4.2 19 (%)(8 8Root )........ 40 4.3 9 8 8Root 64 Root vs (%)................................. 40 4.4 19 8 8Root 64 Root vs (%)................................ 40 4.5 9 64 200 ( 3.4% (187/5500 )).. 42 4.6 9 8 8 200 ( 2.3% (159/6759 )).. 42 4.7 19 64 200 ( 8.7% (2277/26064 )) 42 4.8 19 8 8 200 ( 4.9% (1314/27032 )) 43 4.9 4.8 ( 5 ).......... 44 4.10 4.9 ( 5 ).......... 44 4.11....................... 48 6

1 1.1 50 1994 [12] 1996 [17] 1997 IBM Deep Blue Kasparov [11] 2009 4 19 3,4 70 ( ) 19 10 171 GnuGo ( ) 7

1.2 CPU ( ) Tree [6, 7] CPU Root [1] CPU Tree Tree [7, 5] Chaslot Root Tree [2] [2] Root Root Root 1.3 3 Tree Root CPU Chaslot Root [2] (2 ) Chaslot RAVE[22] Chaslot 16CPU CPU Root Root Tree Root 64 CPU Fuego Fuego RAVE 8

Tree Chaslot Root [25] Root CPU Root Root Root 512 1. 2. Root 1.4 2 : 3 : 4 : 5 : 9

2 2.1 UCT 2.2 2.3 2.1 2.1.1 ( ) ( 3 3 ( 2.1)) ( ) 2.1: 3 3 2.1 10

1 10 171 2.1: ( ) 10 20 10 28 10 50 10 71 (9 ) 10 38 (19 ) 10 171 minimax minimax ( ) Max Min ( 2.2) 2.2 (Mini ) ( 2.2-1) (Max ) (Mini ) ( 2.2-2) (Mini ) (Max ) ( 2.2-3) Max ( ) (Mini ) ( 2.2-4) 55 A 1 2007 [21] 11

Minimax Minimax [4] 2.2-1 C 65 D D 65 (Max ) 65 (Mini ) 55 2.2: MiniMax 4 [10] minimax GunGo[20].GnuGo GnuGo 5 2,3 2 / / 2 12

/ 1. 2., 2.1.2 minimax A B B A ( i s i X i 1 0 X i X i = X i (2.1) s i X i i 2.3 1. 2. ( ) 3. 1 4. 1 3 13

2.3: 14

2.1.3 ( ) [23]. ( A ) ( B ) A B B ( ) 2.1.4 UCT UCB1 [16] Auer 15

UCB1 [19] UCB1 ( ) UCB1 UCB(i) = X i + c 2log(n) n i (2.2) 2.2 UCB1 X j j n j j n ( )+( ) c c c = 2 UCB UCT(UCB applied to Trees) L.Koscis UCB1 UCT(UCB applied to Trees) [15] UCT UCT 2.4 UCT,UCB1 UCB1 UCB1 UCB1 2.5 1. UCB1 ( ) UCB1 (UCB1 ) 2. ( ) 16

3. 2 4. UCB1 3 ( ) UCB1 1 4 ( ) 2.4: 17

2.5: 2.2 UCT 2.2.1 MoGo CrazyStone[3, 9] UCT MoGo 3 3 [9] 3 3 2.2.2 RAVE UCT-RAVE(Rapid Action Value Estimate)[8] RAVE i i 18

RAVE X E UCT X uct UCT-RAVE X value X value = βx RAV E + (1 β)x uct (2.3) k β = (2.4) 3s + k s k 2.3 CPU 2.3.1 1. 2. ( ) 19

3. 2.3.2 Leaf Leaf ( 2.6) Leaf [1, 2] ( ) UCT ( ) p1 p4 2.6: Leaf Leaf 20

16 10 6 Leaf Leaf [13] 2.3.3 Tree Tree ( 2.7) Tree ( ) UCB [9] Tree CPU Tree [6, 7]. 2.7: Tree Tree UCB Chaslot [2] 21

4 Enzenberger Tree C++ volatile IA-32 Intel-64 CPU [6] UCB, 9 2,19 3, 9 19 8 PC PC Gelly [7] Tree Chaslot (Virtual Loss) [2] Virtual Loss ( ) Chaslot Virtual Loss 2.3.4 Root Root ( 2.8) Root [1] ( ) (p1 p4) Root Root. Cazenave Chaslot [1, 2], Cazaneve 22

2.8: Root Chaslot 3. UCT 2.9 1 4 A,B,C 3 B Root Root Root 3 23

2.9: Root Cazenave Root [1] Root 4 8 16 Zen Zen Root [14] Zen 2.3.5 Cazenave [1] Single-Run(Root) At-the-leaves(Leaf) Multiple- Runs( ) 10000 1 16 At-the-leaves Multiple-Runs 16 Multiple-Runs Single-Run 16 ( 2.2) 2.2: 10000 Single-Run Multiple-Runs GnuGo3.6 (T.Cazenave et al. 2006) 1CPU 2CPUs 4CPUs 8CPUs 16CPUs Single-Run(Root) 45.0 62.0 61.5 65.5 66.5 Multiple-Runs 49.0 58.5 72.0 72.0 68.0 Chaslot 16CPU Leaf Root Tree 24

[2] 2.3: 13 1 Root Tree GnuGo3.7.10 (G.Chaslot et al. 2008) 1CPU 2CPUs 4CPUs 16CPUs Leaf 26.7 26.8 32.0 36.5 Root 26.7 38.0 46.8 56.5 Tree 26.7 33.8 40.2 49.9 2.4: 9 Root Tree GnuGo3.7.10 (G.Chaslot et al. 2008) (s) Root Tree 0.25 60.2 63.9 2.50 78.7 79.3 10.0 87.2 89.2 13 Root Tree ( 2.3) 9 Root Tree ( 2.4) [2] 13 Root Tree 9 13 Leaf 16 1 9 13 19 1 10 Root Tree 25

3 Root Root 3.1 Fuego 3.2 Root 3.3 Root 3.4 3.1 Fuego ( ) fuego Fuego[5] 3.1: fuego 2009 5 Computer Olympiad 9 1 19 2 [18] 1 Fuego GtpEngine GTP(Go Text Protocol) 1 C++ 26

3.2: fuego [5] 27

SmartGame Go Minimax GoUct UCT Fuego RAVE UCT MoGo [9] Fuego [6], MPI 2 Tree Virtual Loss 3.2 Root 2.9 B 3 2 1 2 B 19 3.3 3.3.1 3.3.2 3.3.1 [25] ( ). 2 28

3.3: Bonanza 29

1. 2. Bonanza[?] 1 [26] 2 Bonanza [24] 3.3.2 Root ( 3.4). Root 1 ( ) 2.9 2.9 B A A 2 3.3.3 Root ( 3.5) Fuego0.3.2 MPI 1 (p1) (pe) MPI 2 ( ) p1 3 p1 4 p1 pe GoGui-twogtp 30

1. 5 pe p1 GoGui-twogtp 3.4: 2.9 B 4 A 2 B 1 C A Root 3.4 Root 2.9 B 2 31

3.5: 32

4 4.1 4.2 4.3 4.1 Fuego version 0.3.2 PC 8 16GB CPU CPU Xeon E5410 2.33GHz 2 MPI MPICH2 1 C++ Mogo release3 4.2 9, 19 ( ) 1 10 9 200 19 100. Fuego Root MPI Fuego PC 64 Root 4.9 64 8 512 Root Root Tree LockFree Fuego 16 [6]. PC 8 Tree 4.8 4.9 F t ree Tree 8 1 http://www.mcs.anl.gov/research/projects/mpich2/ 33

Fuego 30 F80s Fuego 80 4.3 Root Root Tree Root Tree Root 34

4.4 Root 4.1: 9 :Root ( 4 64 ) vs Fuego 4.1 4.5 9 19 CPU Root ( ) 4.1 4.4 Fuego Fuego Root Fuego Root 19 Root MoGo 4.3,4.5 CPU Fuego 9 MoGo CPU 32 64 19 CPU 32 64 Root Chaslot RAVE Root Chaslot Root ( ) 35

4.2: 9 :Root ( 4 64 RAVE ) vs Fuego(RAVE ) 4.3: 9 :Root ( 4 64 ) vs Mogo 36

4.2 Root Fuego RAVE 9 RAVE Chaslot Root RAVE Fuego 4.4: 19 :Root ( 4 64 ) vs Fuego 4.5 Root Tree Root Fuego Tree Root (64 ) Tree Virtual Loss 4.6, 4.7 9, 19 Tree 1 8 64 Root Chaslot 64 Root 9 6 Tree 4 19 4 Tree Enzenberger Fuego Tree 7 8 7 [6] 9 8 2 2 Martin Müller 16CPU Fuego 8 37

4.5: 19 :Root ( 4 64 ) vs Mogo Tree UCB1 (2 ) [6] 4.6 Root Tree Root Tree Tree Root 8 Tree Fuego F tree F tree 8 Root ( 8 8 Root ) 4.6,4.6 19,9 8 8 Root F tree MoGo F tree 9 4.6 Fuego 64 49.5 64 CPU 8 8 Root 67.0 ( 4.6 ) 4.3 64 MoGo 67.5 8 8 Root 77% 19 8 8 Root Fuego 4.6 9 8 8 Root 2 19 4.6 3 38

4.6: 9 :Root ( 64 )vstree (1 8 ) 4.7: 19 :Root ( 64 )vstree (1 8 ) 4.1: 9 (%)(8 8Root ) 8 8 Root vs F tree vs Mogo 67.0 77.0 68.5 79.0 39

4.2: 19 (%)(8 8Root ) 8 8 Root vs F tree vs Mogo 76.0 62.5 73.0 59.0 4.7 Root 4.7,4.7 8 8 Root 64 Root 9 8 8 Root 3 19 64 Root 7 4.3: 9 8 8Root 64 Root vs (%) 8 8 Root 47.0 64 Root 56.5 4.4: 19 8 8Root 64 Root vs (%) 8 8 Root 59.0 64 Root 70.0 40

4.8 Root 9, 19 Fuego 64 Root (64 Root ) Fuego 200 Root 8 8 Root 8 8 Root F tree (4.6 ) 200 9 64 Root 8 8 Root 97 ( 4.5,4.6 ) 19 92 95 ( 4.7,4.8 ) (30 ) F tree F tree F tree F tree 4.5 4.8 F tree F tree F tree (( )-1 (F tree 1) (4.1) F tree A Root A 1 Root A 3 0 2 9 F tree 19 64 4 0.5 64 Root 9 MoGo 8 8 9 1,2 19 64 Root 10 20 4.5 9 64 Root F tree F tree 4.8 4.9 41

4.8 A7 A4 (F tree ) A7 A4 5 4.8 5 4.9 A4 CPU 64 9 A4 A7 3 28 A7 4.9 D1 E8 F tree D1 E8 4.9 4.10 E8 E8 CPU 16 D1 22 4.5: 9 64 200 ( 3.4% (187/5500 )) Root F tree 74 1.52 37 1.83 4.6: 9 8 8 200 ( 2.3% (159/6759 )) Root F tree 62 1.54 36 1.75 4.7: 19 64 200 ( 8.7% (2277/26064 )) Root F tree 593 2.92 137 3.40 42

4.8: 19 8 8 200 ( 4.9% (1314/27032 )) Root F tree 328 2.65 189 2.85 A B C D E F G H J 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D E F G H J 4.8: F tree ( ) A B C D E F G H J 9 9 8 8 7 7 6 6 5 5 4 4 3 3 2 2 1 1 A B C D E F G H J 4.9: F tree ( ) 43

4.9: 4.8 ( 5 ) 1 A4 29,416 2 H5 25,984 3 A7 25,917 4 H4 20,460 5 H6 2,618 1 A7 25,917 28 2 H4 20,460 14 3 H5 25,984 13 4 A4 29,416 9 5 H6 2,618 0 4.10: 4.9 ( 5 ) 1 E8 24,637 2 B2 23,276 3 D1 20,910 4 E9 10,894 5 B1 7,535 1 D1 20,910 22 2 B2 23,276 21 3 E8 24,637 16 4 E9 10,894 5 5 B1 7,535 0 4.9 Root Root 80 Fuego ( F80s ) F80s 9, 19 400 ( Fuego Mogo( 10 ) ) F80s (9 10591 19 46193 ) A A = F80s A (4.2) 4.9.1 4 F80s 1. Fuego( 1 64 ) 2. Root Fuego( 1 4 64 ) 3. Root Fuego( 1 4 64 ) 4.Tree Fuego( 1 2 8 ) 44

4.10,4.11 Root 9 19 32 64 Tree 4 64 Root Tree 1 1 10 4.10: 9 :F80s : Fuego,Root ( ),Tree 45

4.11: 19 :F80s : Fuego,Root ( ),Tree 4.9.2 Root 19 Root 512 ( 4.13 4.11 1 Root 32 4.9.3 Root Root 19 Root F80s ( 4.13) 1 0.28 64 0.64 512 0.76 46

4.12: 19 :F80s : Root ( 64-512 4.13: 19 :F80s : Root ( 1-512 ) 47

4.9.4 (2 ) Root = (4.3) F80s 512 4.11. 9 19 9, 19 4.14 4.23 9, 19 (0.6 ) Root ( 4.16 4.18, 4.21 4.23 ) 0.8 ( 8 ) Root 9, 19 ( 0.4) 9 0.2 19 ( 4.14 4.15, 4.19 4.20 ) 0.5 0.4 0.4 4.11: 919 0.0-0.2 0.0418 0.1266 0.2-0.4 0.0795 0.2542 0.4-0.6 0.2253 0.2715 0.6-0.8 0.2047 0.1832 0.8-1.0 0.4483 0.1642 48

4.14: 9 (0 0.2) 4.15: 9 (0.2 0.4) 49

4.16: 9 (0.4 0.6) 4.17: 9 (0.6 0.8) 50

4.18: 9 (0.8 1.0) 4.19: 19 (0 0.2) 51

4.20: 19 (0.2 0.4) 4.21: 19 (0.4 0.6) 52

4.22: 19 (0.6 0.8) 4.23: 19 (0,8 1.0) 53

4.9.5 Root A n L (A) = [ x L ] (4.4) 100 30 [30/100] = 0.3 9, 19 4.24,4.25 9 K 0.2 0.8 K 1.0 19 K 0.2 19 Tree Root ( 1 ) 4.24: 9 54

4.25: 19 55

5 5.1 Fuego 3 Tree Root 2 Chaslot Tree 9 64 Root Tree 4 19 4 9 Tree 4 64 Root 19 Tree 8 64 Root (4.9.4) Root Tree Root 10 1 Fuego Root Tree 64 8 Tree 1 8 Root ( 8 8 ) 64 64 Root 8 8 8 Tree 8 8 Root (4.6 ) Root 9 19 (4.4 4.7 ) 64 Root 8 8 (4.6 ) 56

F tree F tree 8 Tree Fuego F tree 30 F tree F tree Root CPU Root Root Fuego Mogo Root 4 64 (4.4 ) 64 512 32 Root (4.9.3 ) 64 512 64 Root Root 19 1 4 64 ( 4.19) Root 9 0.2 9 0.8 19 Root 57

5.2 1 Fuego 10 Root 4.9.3 Root 4.13 Root Root Root 58

59

5.1: 19 60

5.2: 19 5.3: 19 61

5.4: 19 5.5: 19 62

5.6: 9 5.7: 9 63

5.8: 9 5.9: 9 64

5.10: 9 65

[1] T. Cazenave and N. Jouandeau. On the parallelization of UCT. In Proceedings of the Computer Games Workshop, pp. 93 101, 2007. [2] G. M. J-B. Chaslot, M. H.M Winands, and H. J. van den Herik. Parallel Monte- Carlo tree search. In Proceedings of the 6th International Conference on Computer and Games, Vol. 5131 of Lecture Notes in Computer Science, pp. 60 71, 2008. [3] R. Coulom. Computing Elo ratings of move patterns in the game of Go. ICGA Journal, Vol. 30, No. 4, pp. 198 208, 2007. [4] D.E.Knuth and R.W.Moore. An analysis of alpha-beta pruning. In Artificial Intelligence, pp. 293 326, 1975. [5] M. Enzenberger and M. Müller. Fuego - an open-source framework for board games and Go engine based on Monte-Carlo tree search. TR 09-08, University of Alberta, 2009. [6] M. Enzenberger and M. Müller. A lock-free multithreaded Monte-Carlo tree search algorithm. In Advances in Computer Games 12, 2009. [7] S. Gelly, J. B. Hoock, A. Rimmel, O. Teytaud, and Y. Kalemkarian. The parallelization of Monte-Carlo planning. In Proceedings of the 5th International Conference on Informatics in Control, Automation, and Robotics, pp. 198 203, 2008. [8] S. Gelly and D. Silver. Combining online and offline knowledge in UCT. In Proceedings of the 24th International Conference on Machine Learning, pp. 273 280, 2009. [9] S. Gelly, Y. Wang, Remi Munos, and O. Teytaud. Modification of UCT with patterns in Monte-Carlo Go. Technical Report 6062, INRIA, 2006. [10] GPSshogi. http://gps.tanaka.ecc.u-tokyo.ac.jp/gpsshogi/. 2009. [11] J.Schaeffer and A.Plaat. Kasparov versus deep blue: The re-match. In International Computer Chess Association Journal, pp. 95 101, 1997. [12] J.Scheaffer. One jump ahead: Challenging human supremacy in chechkers. In Springer-Verlag, 1997. [13] H. Kato and I. Takeuchi. Parallel Monte-Carlo tree search with simulation servers. In Proceedings of the 13th Game Programming Workshop, pp. 31 38, 2008. 66

[14] H. Kato and I. Takeuchi. Zen. In Proceedings of the 14th Game Programming Workshop, pp. 22 26, 2008. [15] Kocsis.L and Szepesvari.C. Bandit based monte-carlo planning. In 17th European Conference on Machine Learning(ECML 2006), pp. 282 293, 2006. [16] Lai.T.L and Robbins.H. Asymptotically efficient adaptive allocation rules. In Advances in Applied Mathematics, pp. 4 22, 1985. [17] M.Buro. The othello match of the year: Takeshi murakami vs logistello. In International Computer Chess Association Journal, pp. 189 192, 1997. [18] M. Müller. Fuego at the Computer Olympiad in Pamplona 2009: a tournament report. TR 09-09, University of Alberta, 2009. [19] P.Auer and N.Cesa-Bianchi.P.Fischer. Finite-time analysis of the multiarmed bandit problem machine learning. pp. 235 256, 2002. [20] GNU Go GNU Project. http://www.gnu.org/software/gnugo/. 2009. [21] Jonathan Schaeffer, Neil Burch, Yngvi Bj?rnsson, Akihiro Kishimoto, Martin M?ller, Robert Lake, Paul Lu, and Steve Sutphen. Checker is solved. In Science 14 September 2007, pp. 1518 1522, 2007. [22] S.Gelly.Y.Wang, R.Mumos, and O.Teytaud. Modification of uct with patterns in monte-carlo go. In RR-6062-INRIA, pp. 1 19, 2006. [23] Yoshimoto.H, Yoshizoe.K, Kaneko.T, Kishimoto.A, and Taura.K. Monte carlo go has a way to go. In Twenty-First National Conference on Artificial Intelligence(AAAI-06), pp. 1070 1075, 2006. [24],,,. :? In Proceedings of the 14th Game Programming Workshop, pp. 51 58, 2009. [25],,. -. 22, 2009. [26],,,,. -. In Proceedings of the 14th Game Programming Workshop, pp. 59 65, 2008. 67