2015 3

Size: px

Start display at page:

Download "2015 3"

えつとたかはし
5 years ago
Views:

1 JAIST Reposi Title ターン制ストラテジーゲームにおける候補手の抽象化によるゲーム木探索の効率化 Author(s) 村山, 公志朗 Citation Issue Date Type Thesis or Dissertation Text version author URL Rights Description Supervisor: 池田心, 情報科学研究科, 修士 Japan Advanced Institute of Science and

2 2015 3

3 : Copyright c 2015 by koshiro murayama 2

4 1997 IBM DEEPBLUE Poje StarCraft BWAPI RPG DS2 Advance Wars Days Of Ruin FWDS2 6

5 AI AI AI TUrn-Based-STrategy-Academic-Package TUBSTAP JAIST web AI TUBSTAP 4 UCT UCT 63.1% 2

6 Simulation Role Playing Game SRPG Real Time Strategy Arimaa TUBSTAP UCT UCB applied to Tree i

7 7 UCT TUBSTAP TUBSTAP ii

8 IBM DEEPBLUE MinMax Poje StarCraft BWAPI 1.2 MinMax 1

9 2 SRPG RTS Arimaa [16] 1985 PC 80 PC Simulation Role Playing Game SRPG RPG Final Fantasy Tactics[5] Real Time Strategy StarCraft[10] Age of Empire RTS PC RTS 2

10 RTS IEEE-CIG[6] RTS Arimaa Arimaa[1] 2002 NASA Omar Syed 4 3

11 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

12 Bonanza [2] Bonanza JAIST Web Poje[17] FightingICE[4] AI Java 5

13 2.3 Tomas UCT Arimaa [12] UCB UCT Arimaa [15] UCT UCT 6

14 3 3.1 F1 F25 F

15 3.1: 3.2: F2 2 [14] F3 SRPG 1 1 F StarCraft 3.3: 1 3.4: Arimaa [1] 8

16 F5 F6 F7 HP 1 0 F8 HP F9 F10 F11 1 Zone of Control ZoC F12 F13 F14 F15 9

17 F16 F17 HP F18 F19 HP F20 F21 HP F22 F23 F24 F25 10

18 3.2 X Y X Y Z 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

19 3.5: 12

20 R1 R2 R3 R4 13

21 R5. R6 14

22 4.2 R2 R4 R5 R6 DS2 Advance Wars Days Of Ruin FWDS2 FWDS2 3 1 F1 2 F2 F3 F4 F5 F 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

23 4.3 F1 11 F12 25 F1 4.1 F12 4.1: 16

24 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

25 F F5 F6 4.1 HP F R A T U U I 4.1:

26 F7 HP 1 10 HP HP 0 F8 F9 U 4.3 HP 1 U : 19

27 F : 4.2: :

28 HP HP F19 = HP 10 HP F : 4.4:

29 5 VisualStudio C.Net GUI P1 P9 P1 FWDS2 P2 P3 P4 GUI P5 P6 P7 22

30 P8 P9 5.1 R9 TUrn-Based-STrategy-Academic-Package TUBSTAP web [13] 5.1: TUBSTAP 23

31 5.2 P8 TUBSTAP TUBSTAP StarCraft RPG TUBSTAP TUBSTAP 5.2 Map Board 24

32 Unit HP Action 1 Map Action AiTools Spec AI Map.Unit Spec Spec Player AI Action AI PlayerList AI AI Logger RangeController 25

33 GameManager 1 DrawManager GUI SGFManager MainForm 5.2: 26

34 6 TUBSTAP UCT TUBSTAP [15] [18] 6.1: 27

6.2 TUBSTAP TUBSTAP MinMax 1 n r 1 n r r! 6.

35 6.2 TUBSTAP TUBSTAP MinMax 1 n r 1 n r r! n = 10 r = αβ 6.2:

36 6.3 [19] [19] AI

37 6.3: 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

38 7 UCT TUBSTAP TUBSTAP UCT 6.2 TUBSTAP UCT αβ TUBSTAP UCT UCT UCT [15] UCT ProgressiveWidening UCT

39 7.1: 7.2: 32

40 7.2 TUBSTAP TUBSTAP Level1 Level4 7.1 Level Level TUBSTAP 7.1: 4 Level 0 Level Level Level1 Level Level Level

41 : Level0 7.4: Level

42 7.5: Level4 1 35

43 Level Level Level : Level0 Level1 7.7: Level2 36

44 7.8: Level3 7.9: Level4 37

45 UCT UCT UCT UCT LEVEL UCT 8.1 Level1 Level3 UCT Level1 3 Level1 UCT 8.1 UCT 38

46 UCT 8.1: UCT Level1 Level2 Level3 Level4 PO PO PO PO PO : UCT 39

47 LEVEL1 UCT TUBSTAP 40

48 Level1 8.2 Level1 UCT 58.8% % 8.2: 8.2: 1000 UCT Level

49 Level1 Level Level4, Level (Level4, Level4, Level1, Level0, Level0, Level0) ,2, UCT 63.2% % 8.3: 3 UCT

50 8.4: 4 UCT

51 9 9.1 TUBSTAP JAIST Web UCT 4 UCT 44

52 9.2 UCT TUBSTAP Progressive Widening TUBSTAP 45

53 TUBSTAP 7 46

54 [1] Arimaa, [2] Bonanza - The Computer Shogi Program, [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 [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 , [5] FINAL FANTASY TACTICS, [6] IEEE-CIG, [7] Kocsis,L and Szepesvari, C., Bandit Based Monte-Carlo Planning, 17th European Conference on Machine Learning, ECML 2006, LNCS, Vol4212, pp , [8] Mario AI BenchMark, [9] P.Auer,N.Gesa-Bianchi,P.Fischer, Finite-time analysis of the multiarmed bandit problem, Machine Learning, Vol. 47, pp , [10] StarCraft2-homepage, [11] The2K BotPrize : Home, [12] Tomas Kozelek, Method of MCTS and the game Arimaa, Master s Thesis,2009. [13] TUBSTAP-, [14], [15],,,, UCT,

55 [16] -wikipedia, [17],,,,Vol.53, No.11, pp , [18],,, [19],, -,,

Copyright 2008 by Tomoyoshi Yamazaki

Copyright 2008 by Tomoyoshi Yamazaki JAIST Reposi https://dspace.j Title 工程管理から知識創造へ - クリニカルパスによる医療のナレッジマネジメント - Author(s) 山﨑, 友義 Citation Issue Date 2008-03 Type Thesis or Dissertation Text version author URL http://hdl.handle.net/10119/4260