JAIST Reposi https://dspace.j Title ターン制ストラテジーゲームにおける候補手の抽象化 によるゲーム木探索の効率化 Author(s) 村山, 公志朗 Citation Issue Date 2015-03 Type Thesis or Dissertation Text version author URL http://hdl.handle.net/10119/12652 Rights Description Supervisor: 池田心, 情報科学研究科, 修士 Japan Advanced Institute of Science and
2015 3
1210054 : 2015 2 Copyright c 2015 by koshiro murayama 2
1997 IBM DEEPBLUE Poje StarCraft BWAPI 25 17 13 RPG DS2 Advance Wars Days Of Ruin FWDS2 6
AI AI AI TUrn-Based-STrategy-Academic-Package TUBSTAP JAIST web AI TUBSTAP 4 UCT UCT 63.1% 2
1 1 1.1....................................... 1 1.2....................................... 1 2 2 2.1................ 2 2.1.1 Simulation Role Playing Game SRPG............... 2 2.1.2 Real Time Strategy........................... 2 2.1.3 Arimaa................................. 3 2.2........................ 4 2.3........................ 6 3 7 3.1........................... 7 3.2.................... 11 4 13 4.1................................ 13 4.2................................ 15 4.3................................. 16 5 22 5.1...................... 22 5.2................................ 24 5.2.1.............. 24 5.2.2............................ 24 6 27 6.1........................ 27 6.2 TUBSTAP.................. 28 6.3.............................. 29 6.3.1 UCT UCB applied to Tree..................... 30 i
7 UCT TUBSTAP 31 7.1.............................. 31 7.2 TUBSTAP.................. 33 7.3.............................. 34 7.4.............................. 36 8 38 8.1............................ 38 8.2............. 40 8.2.1............... 41 8.2.2................ 42 9 44 9.1...................................... 44 9.2................................... 45 ii
1 1.1 1997 IBM DEEPBLUE MinMax Poje StarCraft BWAPI 1.2 MinMax 1
2 SRPG RTS Arimaa 2.1 2.2 2.3 2.1 [16] 1985 PC 80 PC 2.1.1 Simulation Role Playing Game SRPG RPG Final Fantasy Tactics[5] 170 2.1.2 Real Time Strategy StarCraft[10] Age of Empire RTS PC RTS 2
RTS IEEE-CIG[6] RTS 2.1.3 Arimaa Arimaa[1] 2002 NASA Omar Syed 4 3
2.2 AI StarCraft StarCraft 1988 RTS IEEE-CIG[6] AI BWAPI The Broad War Application Programming interface C++ FPS First Person Shooting Game FPS BotPrize 2012 The2KBotPrize[11] AI Mario MarioAI BencbMark Java StarCraft IEEE-CIG Mario AI Competision[8] AI Fuego[3] 4
Bonanza [2] 2006 16 Bonanza JAIST Web Poje[17] FightingICE[4] AI Java 5
2.3 Tomas UCT Arimaa [12] UCB UCT Arimaa [15] UCT UCT 6
3 3.1 F1 F25 F1 3.1 3.2 7
3.1: 3.2: F2 2 [14] F3 SRPG 1 1 F4 1 3.3 3.4 StarCraft 3.3: 1 3.4: Arimaa [1] 8
F5 F6 F7 HP 1 0 F8 HP F9 F10 F11 1 Zone of Control ZoC F12 F13 F14 F15 9
F16 F17 HP F18 F19 HP F20 F21 HP F22 F23 F24 F25 10
3.2 X Y X Y Z 3.5 17 4 R 2 F3 F4 F4 F6 HP F7 F10 F10 ZoC F11 F13 F14 F15 F18 F22 13 Arimaa SRPG EX StarCraft 3.5 Arimaa 11
3.5: 12
4 4.3 3 25 11 4.1 R1 R2 R3 R4 13
R5. R6 14
4.2 R2 R4 R5 R6 DS2 Advance Wars Days Of Ruin FWDS2 FWDS2 3 1 F1 2 F2 F3 F4 F5 F21 3 2 15 FWDS2 4 Group1 F4 F6 HP F7 F8 F11 Group2 F5 F9 F10 F12, F19. Group3 F13 F14 F16 F17 F18 Group4 F15 F20 F21 FWDS2 ZoC F11 F4 F21 F22 F23 G3 G2 3 2 Arimaa 15
4.3 F1 11 F12 25 F1 4.1 F12 4.1: 16
F2 F3 6 F A P R I U 6 F A 4.2 F A R A P U F R R F A P R U A I U 4.2: 17
F4 1 1 1 1 4 F5 F6 4.1 HP F R A T U U I 4.1: 0 0 85 115 105 105 65 55 0 0 0 0 70 70 45 105 15 50 0 0 3 55 5 10 0 0 75 75 55 70 0 0 65 90 60 75 18
F7 HP 1 10 HP HP 0 F8 F9 U 4.3 HP 1 U 2 3 4.3 4.3: 19
F10 7 4.4 4.2 4.3 4.4: 4.2: 0 0 0 0 0 0 0.4 0.3 0.1 0 0 0.4 4.3: 1 1 1 1 1 1 2 1 1 1 2 1 1 1 1 20
HP HP 4.1 4.2 F19 = HP 10 HP F11 1 4.5 4.4 4.5: 4.4: 7 9 6 3 6 5 21
5 VisualStudio C.Net GUI 5.2 5.1 P1 P9 P1 FWDS2 P2 P3 P4 GUI P5 P6 P7 22
P8 P9 5.1 R9 TUrn-Based-STrategy-Academic-Package TUBSTAP web [13] 5.1: TUBSTAP 23
5.2 P8 TUBSTAP 5.2.1 5.2.2 TUBSTAP 5.2.1 StarCraft RPG TUBSTAP 5.2.2 TUBSTAP 5.2 Map Board 24
Unit HP Action 1 Map Action AiTools Spec AI Map.Unit Spec Spec Player AI Action AI PlayerList AI AI Logger RangeController 25
GameManager 1 DrawManager GUI SGFManager MainForm 5.2: 26
6 TUBSTAP UCT 6.1 1 1 TUBSTAP 1 1 1 1 1 6.1 [15] [18] 6.1: 27
6.2 TUBSTAP TUBSTAP MinMax 1 n r 1 n r r! 6.2 6 6 n = 10 r = 6 1 7 2000 6.1 αβ 6.2: 6 6 28
6.3 [19] [19] AI 6.3 1. 2. 3. 4. 29
6.3: 6.3.1 UCT UCB applied to Tree UCT Upper Confidence Bound applied to Trees 1 [7] UCT UCB Upper Confidence Bound UCB [9] 6.1 UCB x j j n n j j c UCB = x j + c log n (6.1) n n j c c=1 UCT 30
7 UCT TUBSTAP TUBSTAP UCT 6.2 TUBSTAP UCT αβ 7.1 7.2 TUBSTAP 7.1 7.1 UCT UCT UCT [15] UCT ProgressiveWidening UCT 7.2 31
7.1: 7.2: 32
7.2 TUBSTAP TUBSTAP 1 4 3 Level1 Level4 7.1 Level Level0 7.3 7.4 4 TUBSTAP 7.1: 4 Level 0 Level 1 1 2 7.4 Level 2 7.8 Level1 Level 3 7.9 2 7 Level1 1 1 1 Level 4 7.9 1 7.5 33
7.3 3 7.3 9 7.5 9 1 7.4 2 6.2 2 7.3: Level0 7.4: Level1 3 2 34
7.5: Level4 1 35
7.4 4 7.2 7.6 Level0 7 7.7 7 3 Level3 7.8 2 7 2 Level4 7.9 1 7.6: Level0 Level1 7.7: Level2 36
7.8: Level3 7.9: Level4 37
8 7.3 4 8.1 4 UCT UCT 6.2 1000 500 0.5 1 500 1000 2000 3000 4000 5 UCT UCT LEVEL1 4 7.1 UCT 8.1 Level1 Level3 UCT Level1 3 Level1 UCT 8.1 UCT 38
UCT 8.1: UCT Level1 Level2 Level3 Level4 PO500 57.3 560-25-415 51.7 505-24-471 51.6 498-35-467 41.9 391-55-554 PO1000 58.8 581-14-405 54.0 528-23-449 50.9 497-23-480 35.4 338-32-630 PO2000 63.1 620-22-358 60.0 589-21-390 55.4 540-27-433 32.7 321-11-667 PO3000 61.7 609-15-376 58.8 576-24-400 55.5 543-24-433 29.5 287-15-698 PO4000 61.2 600-24-376 57.4 566-16-418 54.4 535-18-447 25.1 244-13-743 8.1: UCT 39
8.2 8.1 LEVEL1 UCT TUBSTAP 40
8.2.1 3 5 8.2 3 8.1 1 1000 Level1 8.2 Level1 UCT 58.8% 3 63.2% 8.2: 8.2: 1000 UCT Level1 58.8 581-14-405 3 63.2 626-11-363 4 62.7 620-13-367 5 55.0 543-14-443 41
8.2.2 8.2.1 7.3 Level1 Level4 3 4 8.2.1 6 1 Level4, Level0 6 441000 (Level4, Level4, Level1, Level0, Level0, Level0) 6 5 4 3,2,1 8.2.1 1000 3 4 8.3 8.4 8.2.1 111100 UCT 63.2% 442100 441000 67.3% 8.3: 3 UCT 111100 63.2 626-11-363 331100 58.3 574-17-409 443200 63.5 619-32-349 442100 65.1 642-17-341 443100 66.2 648-27-325 432100 62.7 611-32-377 333100 59.4 585-17-398 433100 64.3 631-24-345 432100 62.7 611-32-377 42
8.4: 4 UCT 111000 62.7 620-13-367 211000 55.1 510-81-407 311000 54.8 544-8-448 321000 56.5 561-8-431 331000 54.8 541-13-446 332000 58.9 576-26-398 333000 56.1 549-24-427 431000 61.5 609-11-380 432000 63.3 625-15-360 433000 62.3 611-23-366 441000 67.3 635-75-290 442000 63.1 621-20-359 443000 64.6 635-22-343 444000 61.2 599-25-376 43
9 9.1 TUBSTAP JAIST Web UCT 4 UCT 44
9.2 UCT TUBSTAP Progressive Widening TUBSTAP 45
TUBSTAP 7 46
[1] Arimaa, http://arimaa.com/arimaa/. [2] Bonanza - The Computer Shogi Program, http://www.geocities.jp/bonanzashogi/. [3] Enzenberger,M.,Muller,M.,Arneson, B. and Segal, R Fuego-An Open-Source Framework for Board Games and Go Engine Based on Monte Carlo Tree Search, IEEE Trans. Computational Intelligence and AI in Games, Vol.2,No.4,pp.259-270 2010. [4] Feiyu Lu, Kaito Yamamoto, Luis H. Nomura, Syunsuke Mizuno, YoungMin Lee, and Ruck Thawonmas, Fighting Game Artificial Intelligence Competition Platform Proc. of the 2013 IEEE 2nd Global Conference on Consumer Electronics, pp. 320-323, 2013. [5] FINAL FANTASY TACTICS, http://dlgames.square-enix.com/fft/. [6] IEEE-CIG, http://cig2015.nctu.edu.tw/. [7] Kocsis,L and Szepesvari, C., Bandit Based Monte-Carlo Planning, 17th European Conference on Machine Learning, ECML 2006, LNCS, Vol4212, pp.282-293, 2006. [8] Mario AI BenchMark, https://code.google.com/p/marioai/. [9] P.Auer,N.Gesa-Bianchi,P.Fischer, Finite-time analysis of the multiarmed bandit problem, Machine Learning, Vol. 47, pp. 235-256, 2002. [10] StarCraft2-homepage, http://us.battle.net/sc2/en/. [11] The2K BotPrize : Home, http://botprize.org/. [12] Tomas Kozelek, Method of MCTS and the game Arimaa, Master s Thesis,2009. [13] TUBSTAP-, http://www.jaist.ac.jp/is/labs/ikeda-lab/tbs/. [14], http://www.catan.jp/. [15],,,, UCT, 18 2013. 47
[16] -wikipedia, http://ja.wikipedia.org/wiki/. [17],,,,Vol.53, No.11, pp. 2560-2570, 2012-11. [18],,, 8 2014. [19],, -,,2011. 48