AI 1,a) 1,b) 1,c) , AI branching factor AI AI AI Proposal of Challenges and Approaches to Create Effective Artificial Players for Tur

Size: px

Start display at page:

Download "AI 1,a) 1,b) 1,c) , AI branching factor AI AI AI Proposal of Challenges and Approaches to Create Effective Artificial Players for Tur"

あつみねひらみね
5 years ago
Views:

1 JAIST Reposi Title 戦術的ターン制ストラテジーゲームにおける AI 構成のための諸課題とそのアプローチ Author(s) 佐藤, 直之 ; 藤木, 翼 ; 池田, 心 Citation 情報処理学会論文誌, 57(11): Issue Date Type Journal Article Text version author URL Rights 社団法人情報処理学会, 佐藤直之, 藤木翼, 池田心, 情報処理学会論文誌, 57(11), 2016, ここに掲載した著作物の利用に関する注意 : 本著作物の著作権は ( 社 ) 情報処理学会に帰属します本著作物は著作権者である情報処理学会の許可のもとに掲載するものですご利用に当たっては著作権法ならびに情報処理学会倫理綱領に従うことをお願いいたします Notice for the use of this material: The copyright of this mate retained by the Information Processi Japan (IPSJ). This material is publi web site with the agreement of the a the IPSJ. Please be complied with Co of Japan and the Code of Ethics of t any users wish to reproduce, make de work, distribute or make available t any part or whole thereof. All Right Copyright (C) Information Processing Japan. Description Japan Advanced Institute of Science and

2 AI 1,a) 1,b) 1,c) , AI branching factor AI AI AI Proposal of Challenges and Approaches to Create Effective Artificial Players for Turn-based Tactics Game Naoyuki Sato 1,a) Fujiki Tsubasa 1,b) Kokolo Ikeda 1,c) Received: June 1, 2016, Accepted: August 8, 2016 Abstract: This paper describes characteristics and problems with designing AI players in Turn-based tactics games. These environments of these games provide the designers a similar framework of designing AI players while these provide them some interesting challenges to deal with three major problems described below. Firstly, branching factors of the game tree search often exceed hundreds millions in the games. Secondly, the evaluation of game positions is often difficult in the game because the effectiveness of pieces varies drastically according to the types of opponent pieces in the games. Thirdly, combinations of attack actions in the games have a potentially great effect on game situations. We discussed the effects made by these problems in detail suggesting multiple approaches for the problems, moreover we discussed about the dis/advantages in each approach in example situations. Finally, we made the characteristics of the problems that AI designers face with in the game. Keywords: Game AI, Turn-based Strategy game, Turn-based Tactics game, Monte-Carlo Tree Search 1. AI AI 1 JAIST, Nomi, Ishikawa , Japan a) satonao@jaist.ac.jp b) s @jaist.ac.jp c) kokolo@jaist.ac.jp AI IBM DeepBlue [1] [2][3] c 2016 Information Processing Society of Japan 0

3 AI AI [4] StarCraft[8] 100 [6] 300 Civilization [7] 1 TUBSTAP Fig. 1 An example of turn based tactics, TUBSTAP platform. Each player manipulate their pieces to fight Civilization against each other. AI [10] AI AI [11] AI TBS TBS Turn-Based Strategy AI TBS AI AI AI TBS AI TBS AI TBS AI TBS AI 2. 1 c 2016 Information Processing Society of Japan 1

4 HP 0 AI [12] IX [11] TUBSTAP [13] HP UCT [14] HP AI [28] Civilization ZoC Zone of Control UCT [15] c 2016 Information Processing Society of Japan 2

5 [10] Civilization StarCraft AI Age of Empire Q [16][17] [18] RTS Civilization AI [19] [20] [21] 2.2 RPG SRPG Role Playing Game Santiago RPG [9] RPG 2.4 Arimaa Arimaa 170 Final Fantasy Arimaa Tactics[5] AI TBS Arimaa HP SRPG AI SRPG HP SRPG SRPG TUBSTAP Arimaa 2.3 AI AI [8] F A RTS AoE2 Age of Empire2 FFT Final Fantasy Tacitics T c 2016 Information Processing Society of Japan 3

6 1 2 Table 1 Defference among basic rules of representative turn based strategy games. HP ZOC Arimaa TUBSTAP F EX A CivilizationV IX RT RTS AoE 2 RT Star Craft 2 RT SRPG FFT T RT RT AI 1 AI 3. TBS AI AI 1 TBS TUBSTAP HP AI c 2016 Information Processing Society of Japan 4

7 2 2 Fig. 2 Cluster analysis of rules of existing turn based strategy games. The distance between two plots shows the difference of their rules. In case two plots would locate in ZOC the same coordinate, one of them was slightly shifted. HP TBS RTS TBS [22] TBS AI 3.3 TUBSTAP TBS TUBSTAP TUBSTAP Table 2 The relationship of competitiveness between every two units in TUBSTAP. The value shows a coefficient to decide the combat damage. F A P U R I F TBS 2 1 TUBSTAP DS2 2 3 RT RT HP RT HP SMPP ver Arimaa HP A P U R I SRPG TBS 3 c 2016 Information Processing Society of Japan 5

8 4. AI TBS AI AI TUBSTAP 3 Tubstap HP [23] 4 TBS HP Fig. 3 Screenshot of TUBSTAP. Color of unit shows its side. The number on each unit shows its HP value. The character on each unit shows its unit type. Each tile has its {( ) ( HP)} land type. T {( ) ( HP)} 3 TUBSTAP Table 3 Land effect values in TUBSTAP F,A P,U,R,I TUBSTAP F, A, P, U, R, I 9, 7, 6, 5, 6, 3 Table 4 Cost values for movement actions in TUBSTAP. The values for moving capacity are also assigned. That is, 1 Min-Max 9 for F, 7 for A, 6 for P, 5 for U, 6 for R, 3 for I 4.1 F,A P,U,R I MCTS 1 MCTS HP ( HP) (1) F, A, P, U, R, I UCT Upper Confidence Bounds applied to Trees[24] U MCTS U Min-Max Min-Max Min-Max 4.2 UCT TUBSTAP UCT MCTS UCB [25] UCB c 2016 Information Processing Society of Japan 6

9 C 2 5. ln( ) ( )+C (2) TBS AI TBS AI AI PW UCT 5.1 Progressive Widening PW TBS Turn-Based War a Chess game Nan [29] n, r b c (n r r!) a < b < c 10 6 TBS UCT DLMC 5.2 AI [26] Min-Max TUBSTAP AI [13] 10 [27] AAS (a) [13] N L (L N) (N L) ! AI c 2016 Information Processing Society of Japan 7

10 (b) AI Min-Max Min-Max 4 HP F U Fig. 4 The position where a shallow and naiive tree search 100 *1 cannot find winning moves of red player. If the unit R attacks the F unit with higher HP than the other F, the 1000 R should be destroyed by U in the following turn. *2 AI 1 HP { AI }! 4 (c) (b) =60 R I *3 F HP F F HP (d) UCT AI F UCT U R F U U UCT U (b) (c) TBS (a) : * = *2 Knuth [30] 2 1! ! 103 * = 210 c 2016 Information Processing Society of Japan 8

20.0, 226, 388 100 5 U 13, 69, 100 UCT I Fig. 5 A position where a movement action is needed to win for red player. Red player must move his U at first. 2 I U (b) 2 F 3 6 3 6 3 6 10 6 6.

11 20.0, 226, U 13, 69, 100 UCT I Fig. 5 A position where a movement action is needed to win for red player. Red player must move his U at first. 2 I U (b) 2 F TBS 6! 3 6 6! U (c) 1 F F 6 TBS TBS U UCT UCT 4 A.2.1 UCT AI 4 Min-Max HP , 1000, TBS (d) UCT : UCT F F R c 2016 Information Processing Society of Japan 9

12 TBS HP TBS 6 F A 7 A position where assigning larger value to F than A results in win. TBS TBSTAP P A A P P A 8 7 A F 9 A position where assigning larger value to A than F results 6.2 AI AI TBS TBS AI in win. Min-Max AI c 2016 Information Processing Society of Japan 10

13 5 UCTAI100 TBS Table 5 Win rate againt UCT AI over 100 matches with different ways of unit evaluation UCT AI 7 (%) 9 A F UCT HP 7 A F F F A A F A F 9 F A TBS F F A A 30 F P HP 1 0 F F2 F P A 1 F P A A P Min-Max UCT 3 (1) A Min-Max 4.1 A 100 F 1 1 Min-Max (2) F Min-Max F 100 A 1 1 Min-Max (3) UCT UCT 1000 A.2.1 UCT AI A HP HP F A A AI A F UCT c 2016 Information Processing Society of Japan 11

14 6 100 Table 6 The success ratio of finding the best move over 100 times in a position where the combination of attack actions have large effect. AI (%) ms UCT 17 1,720 PW UCT 89 1,500 AAS DLMC 0 1,779 Min-Max 100 4, Fig. 10 A position where search that focuses on attack actions works effectively. Red player must decide carefully the 7.2 AI AI AI 4 PW UCT UCT AAS 1 Min-Max DLMC 1 PW UCT UCT Min-Max 5 1 AI AI AI A.2 PW UCT UCT PW UCT AAS 4.3 DLMC 6 L = N HP Min-Max [13] AAS 1 Min-Max order in which his units make actions and the target units of attack actions. DLMC AAS DLMC c 2016 Information Processing Society of Japan 12

11 A Fig. 11 A position A where defensive formations have large effect. 13 C Fig.

12 A position B where defensive formations have large effect. 1 UCT PW UCT DLMC PW TBS UCT 7.

against UCT with PW over 1000 matches. The values between blankets show the 95% confidence intervals.

15 11 A Fig. 11 A position A where defensive formations have large effect. 13 C Fig. 13 A position C where defensive formations have large effect. 12 B DLMC 50.0(±4.4) 57.8(±4.3) 68.1(±4.1) Fig. 12 A position B where defensive formations have large effect. 1 UCT PW UCT DLMC PW TBS UCT : PW UCT AI % Table 7 Win rate values on positions in which forming defensive formation is important, against UCT with PW over 1000 matches. The values between blankets show the 95% confidence intervals. A B C DLMC DLMC 48.6%(±6.2%) 55.5(±6.2) 73.7(±5.5) DLMC DLMC 51.4(±6.2) 60.0(±6.1) 62.4(±6.1) DLMC PW UCT 500 PW UCT DLMC DLMC PW UCT c 2016 Information Processing Society of Japan 13

16 PW UCT DLMC AI Zoc PW UCT DLMC A.2 3 PW UCT 6000 DLMC AI 2 AI DLMC 2 AI TBS Intel(R) Core(TM) i CPU 3.40Ghz RAM 8.00GB OS Windows 7 Service Pack DLMC DLMC Leaf 8. TBS A.2.1 UCT UCT C N allsim n myu 1 TBS TBS AI n myu 1 TBS 16 AI HP A.2.2 PW PW UCT UCT n sim AI (n sim 3000 ) A.1 TUBSTAP 1.07 A.2 AI N allsim n myu N allsim n myu log n sim c 2016 Information Processing Society of Japan 14

17 log n sim pp (2013) (n sim > 3000 ) [12] Bergsma, M. and Spronck, P.: Adaptive Spatial Reasoning for Turn-based Strategy Games, Proc. AIIDE, pp (2008). [13] 19 pp (2014). [14] 20 pp (2015). A.2.3 AAS [15] 30 AAS L [16] Wender, S. and Watson, I.: Using reinfocement learning for city site selection in the turn-based strategy game 4.1 Civilization IV, Proc. CIG, pp (2008). [17] Amato, C. and Shani, G.: High-level Reinforcement A.2.4 DLMC Learning in Strategy Games, Proc. AAMAS, pp (2010). DLMC I 0.2 [18] Branavan, K.R.S., Silver, D. and Barzilay, R.: Learning 1.0 HP 4.1 to win by reading manuals in a monte-carlo framework, 2 Proc. ACL, pp (2011). [19] Ulam, P., Goel, A., Jones, J., et al.: Using Model-Based DLMC Reflection to Guide Reinforcement Learning, Proc. IJ- CAI, (2005). [20] Houk, A.P.: A Strategic Game Playing Agent for FreeCiv, Master thesis, Northwestern University (2004). [21] Hinrichs, R.T. and Forbus, D.K.: Analogical Learning in a Turn-Based Strategy Game, Proc. IJCAI, pp , (2007). [22] Perla, P. P.: The art of wargaming: a guide for professionals [1] Campbell, M., Hoane, J.A. and Hsu, F.: Deep blue, Artificial intelligence, Vol.134, No.1, pp (2002). and hobbyists, Naval Institute Press, Annapolis (1990). (1993) [2] [23] Hoki, K. and Kaneko, T.: Large-Scale Optimization for Evaluation Functions with Minimax Search, Journal of Artificial Intelligence Research, Vol.49, pp [3] Silver, D., Huang, A., Maddison, J.C., et al.: Mastering the game of Go with deep neural networks and tree search, Nature, Vol.529, No.7587, pp (2016). (2014). [24] Kocsis, L. and Szepesvari, C.: Bandit based monte-carlo planning, Machine Learning: ECML, pp (2006). [4] Mizukami, N. and Tsuruoka, Y.: Building a Computer Mahjong Player Based on Monte Carlo Simulation and Opponent Models, Proc. CIG, pp (2015). [25] Auer, P., Cesa-Bianchi, N. and Fischer, P.: Finite-time analysis of the multiarmed bandit problem, Machine learning, Vol.47, pp (2002). [5] SQUARE ENIX FINAL FANTASY TACTICS [26] Kloetzer, J.: Monte-Carlo Techniques: Applications to SQUARE ENIX the Game of the Amazons, Ph.D. thesis, Japan Advanced Institute of Science and Technology (2010). [6] [27] Magic Bitboard 15 pp (2010). [7] Sid Meier s Civilization Beyond Earth, [28] Fujiki, T., Ikeda, K. and Viennot, S.: A platform for turn-based strategy games, with a comparison of Monte- Carlo algorithms, Proc. CIG, pp (2015). [8] Buro, M. and Churchill, D.: Real-time strategy game competitions, AI Magazine, Vol.33, No.3, pp (2012). [29] Nan, H., Fang, B., Wang, G., et al.: Turn-Based War Chess Model and Its Search Algorithm per Turn, International Journal of Computer Games Technology, Vol.2016, [9] Ontanon, S., Synnaeve, G., Uriarte, A., et al.: A survey of real-time strategy game AI research and competition in StarCraft, Computational Intelligence and AI in Games, Vol.5, No.4, pp (2013). Article ID (2016). [30] Knuth, E.D. and Moore, W.R.: An Analysis of Alpha- Beta Pruning, Artificial Intelligence, Vol. 6, No. 4, pp (1975). [10] Turn-basedtactics-Wikipedia, thefreeencyclopedia, tactics [11] UCT 18 c 2016 Information Processing Society of Japan 15

18 2012 AI 2013 AI c 2016 Information Processing Society of Japan 16

1,a) 1,b) TUBSTAP TUBSTAP Offering New Benchmark Maps for Turn Based Strategy Game Tomihiro Kimura 1,a) Kokolo Ikeda 1,b) Abstract: Tsume-shogi and Ts

1,a) 1,b) TUBSTAP TUBSTAP Offering New Benchmark Maps for Turn Based Strategy Game Tomihiro Kimura 1,a) Kokolo Ikeda 1,b) Abstract: Tsume-shogi and Ts JAIST Reposi https://dspace.j Title ターン制戦略ゲームにおけるベンチマークマップの提案 Author(s) 木村, 富宏 ; 池田, 心 Citation ゲームプログラミングワークショップ 2016 論文集, 2016: 36-43 Issue Date 2016-10-28 Type Conference Paper Text version author