The 21st Game Programming Workshop TUBSTAP [2] [3] [4] [5] web HP HP HP HP HP HP HP 1 TUBSTAP UEC-GAT [6] 3 Military, M-UCT, M3Lee

Size: px

Start display at page:

Download "The 21st Game Programming Workshop TUBSTAP [2] [3] [4] [5] web HP HP HP HP HP HP HP 1 TUBSTAP UEC-GAT [6] 3 Military, M-UCT, M3Lee"

ようたみおか
5 years ago
Views:

1 The 21st Game Programming Workshop 216 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 Tsume-go, mating problem of Shogi or Go, are sub-problem of these games. They have been created by many authors, have been played by many players for training, and have been used for evaluating the performance of computer algorithms. Also, benchmark problems are often used in the area of optimization and mathematical programming, for evaluating the specific/total performance of algorithms. We consider such benchmark problems are needed also for TUBSTAP, turn based strategy games. In this paper, we propose many benchmark problems, according to required abilities for these games, and from easy to difficult problems. Finally we show the performance of the existing open-source programs a) kt4887@gmail.com b) kokolo@jaist.ac.jp TUBSTAP [1] TUBSTAP 1 [2] 216 Information Processing Society of Japan

2 The 21st Game Programming Workshop TUBSTAP [2] [3] [4] [5] web HP HP HP HP HP HP HP 1 TUBSTAP UEC-GAT [6] 3 Military, M-UCT, M3Lee TUBSTAP 216 Information Processing Society of Japan

The 21st Game Programming Workshop 216 図 1 逃走マップ run A1 図 3 逃走マップ run A3 図 2 逃走マップ run A2 図 4 追跡マップ chase A1 図 6 追跡マップ chase A3 なければならない今回紹介するようなマップはある意味

ていないプログラムも存在する具体的には Military はモンテカルロシミュレーションの結果評価として合計 HP が相手より 1 でも大きければ勝ちと判定しておりこれはターン上限までに倒しきらないと不正解の問題には不適切な対応である従って Military についてはモンテカルロシミュレーションの結果評価を

1 概要追跡アルゴリズムはゲームアルゴリズムのなかでも重要かつ基本的なものであって教科書 [7], [8] などでも紹介されることが多い戦略ゲームの中でも相手を逃がさないように追跡することが必要な局面は頻繁に出現するまた相手の抵抗を考えながら追跡するアルゴリズムを正しく作るには逃走を正しく行うことも必要である本

2 製作したマップができるターン上限を超えれば引分けすなわち失敗表 1 に制作したマップと搭載 AI の成績を示すどのであるマップでも HP 差閾値は十分高く設定されており上限 run シリーズでは赤軍は戦力的に不利な状況にあるがターン到達時に裁定により勝敗が決まることはないすな

3 The 21st Game Programming Workshop 216 図 1 逃走マップ run A1 図 3 逃走マップ run A3 図 2 逃走マップ run A2 図 4 追跡マップ chase A1 図 6 追跡マップ chase A3 なければならない今回紹介するようなマップはある意味で特殊な能力を明示的に要求するため人間には簡単に解けるようなものであってもこれらのプログラムに解けなかったとしても不思議はないさらにいくつかの問題はターン上限まで逃げ切れれば正解ターン上限までに倒しきらないと不正解といったやや通常とは趣の異なる条件を持つためこれに対応し図 5 追跡マップ chase A2 ていないプログラムも存在する具体的には Military はモンテカルロシミュレーションの結果評価として合計 HP が相手より 1 でも大きければ勝ちと判定しておりこれはターン上限までに倒しきらないと不正解の問題には不適切な対応である従って Military についてはモンテカルロシミュレーションの結果評価を合計 HP が相手よりマップで指定された閾値以上大きければ勝ちに変更して用いた 4. 追跡逃走能力検証用マップ図 7 逃走マップ run B1 図 8 逃走マップ run B3 4.1 概要追跡アルゴリズムはゲームアルゴリズムのなかでも重要かつ基本的なものであって教科書 [7], [8] などでも紹介されることが多い戦略ゲームの中でも相手を逃がさないように追跡することが必要な局面は頻繁に出現するまた相手の抵抗を考えながら追跡するアルゴリズムを正しく作るには逃走を正しく行うことも必要である本稿では２つの異なるテーマを持つ追跡 (chase) および逃走 (run) のマップセットを紹介する chase シリーズでは赤軍が戦力的に優位な状況にあり正しく追いつめればターン上限内で青軍を全滅させること図追跡マップ chase B1 図 1 経路探索マップ path A1 4.2 製作したマップができるターン上限を超えれば引分けすなわち失敗表 1 に制作したマップと搭載 AI の成績を示すどのであるマップでも HP 差閾値は十分高く設定されており上限 run シリーズでは赤軍は戦力的に不利な状況にあるがターン到達時に裁定により勝敗が決まることはないすな障害物を利用して正しく逃走すればいくらでも逃げ延びわち run シリーズならば上限ターンまで逃げ切ればよくることができるターン上限に達すれば引分けすなわ chase シリーズならば上限ターンまでに全滅させる必要がち成功となるある本章以降マップの命名規則としては chase A1 のよう図 1 および図 2 は袋小路に入らぬように逃げ回れば良に目的テーマ記号レベルを用いることにする 216 Information Processing Society of Japan いマップで HP が見にくいことをお詫びする赤の HP

4 The 21st Game Programming Workshop AI Military M-UCT M3Lee run A1 3 6 run A2 3 2 run A3 1 2 chase A1 1 1 chase A chase A3 1 2 run B run B3 3 chase B chase A AI Map Military M-UCT M3Lee path A path A path A M3Lee run A run A1 Military 8 run B1 2 run B chase A MINMAX TUBSTAP path 3 AI Information Processing Society of Japan - 3 -

The 21st Game Programming Workshop 216 図 11 経路探索マップ path A2 図 12 経路探索マップ path A3 図 15 封鎖マップ block A3 図 16 歩兵 HP は 1 図 13

4 封鎖マップ block B2 歩兵 HP は 4 戦車 6 封鎖能力検証用マップにおける搭載 AI の成績ターン制限封鎖マップ block B1 歩兵 HP は 1 M3Lee その間に自走砲が 2 回遠距離攻撃して倒すというテーマの

側に逃走して引分けを試みるような挙動が多く見られたあるマップである非常に単純であるが敵との距離をマ図 15 は足止めを 2 回にわたり行うテーマのマップであンハッタン距離で詰めるような移動アルゴリズムの場合り

体が戦車の上下左おり成績も若干低下している右を封鎖する必要があるマップであるこれには Military 図 12 は歩兵が遠路経由して目的の敵に到達する必要がが全正解したがその理由は HP1 の歩兵が戦車を攻撃すあり

17 では封鎖して 1 回攻撃するだけでかはともかくとして正解手順を見つけることは難しくな深さ 3 まで読むだけで正解するにも関わらず搭載 AI い特にモンテカルロシミュレーションを使うような手法では正解できなかった

選択能力検証用マップ将棋や囲碁でもうまく相手の活動を邪魔するような行動は必要になるがターン制戦略ゲームでは駒の移動範囲が攻撃できる範囲や相手さらには行動順が多いター広いだけに周囲を取り囲んで封鎖する重要地点を押さ

5 The 21st Game Programming Workshop 216 図 11 経路探索マップ path A2 図 12 経路探索マップ path A3 図 15 封鎖マップ block A3 図 16 歩兵 HP は 1 図 13 封鎖マップ block A1 図 14 封鎖マップ block A2 歩兵は移動済み表 4 Map 名 block A1 block A2 block A3 block B1 block B2 図 17 Military 1 M-UCT 封鎖マップ block B2 歩兵 HP は 4 戦車 6 封鎖能力検証用マップにおける搭載 AI の成績ターン制限封鎖マップ block B1 歩兵 HP は 1 M3Lee その間に自走砲が 2 回遠距離攻撃して倒すというテーマのマップである図 13 はさらに初手の歩兵の移動を完了させてある簡易バージョンであるがこれでもこの問題を正解するアルゴリズムは少なかった逃走マップでも述べたように相手の移動や攻撃を読み切れておらずマップ下側に逃走して引分けを試みるような挙動が多く見られたあるマップである非常に単純であるが敵との距離をマ図 15 は足止めを 2 回にわたり行うテーマのマップであンハッタン距離で詰めるような移動アルゴリズムの場合りこの程度であれば人間は簡単に正解を導くが搭載 AI 失敗してしまうには解けなかった図 11 は遠回りをしなければいけない上にターン数上限もぎりぎりに設定されており比較的難易度が上がって図 16 は障害物のないマップで歩兵 4 体が戦車の上下左おり成績も若干低下している右を封鎖する必要があるマップであるこれには Military 図 12 は歩兵が遠路経由して目的の敵に到達する必要がが全正解したがその理由は HP1 の歩兵が戦車を攻撃すありターン数上限もきつく既存プログラムではなかなると HP を 1 減らせるため封鎖ではなく有効な攻か正解できない撃としてこの行動が選択されるためであるようだ一方これらの問題は人間であれば正解手数を正しく読める HP 値の異なる図 17 では封鎖して 1 回攻撃するだけでかはともかくとして正解手順を見つけることは難しくな深さ 3 まで読むだけで正解するにも関わらず搭載 AI い特にモンテカルロシミュレーションを使うような手法では正解できなかったではこういった問題は課題であると言える block シリーズに限らず自走砲の扱いは苦手とする AI が多い印象を受けた 5. 封鎖能力検証用マップ 6. 選択能力検証用マップ将棋や囲碁でもうまく相手の活動を邪魔するような行動は必要になるがターン制戦略ゲームでは駒の移動範囲が攻撃できる範囲や相手さらには行動順が多いター広いだけに周囲を取り囲んで封鎖する重要地点を押さン制戦略ゲームではどの順序でどの相手を攻撃するのかえて侵攻を免れることは必須の能力になるを適切に読む必要がある select A,B シリーズでは正し表 4 に製作したマップと搭載 AI の成績を示すく行動を選択できれば開始ターンで直ちに敵を全滅できる図 14 は青戦車の出口を歩兵が犠牲になって足止めしように設計してある相手番を読む必要がない代わりに 216 Information Processing Society of Japan - 4 -

6 The 21st Game Programming Workshop select A1 HP 4,6,8,1 2,3,4,5 1 select C1 HP 3,1 HP 1,1,1 22 guard A1 23 guard B1 HP 6,4,4 24 guard B2 25 guard B3 2 select B1 21 select B2 5 AI Map Military M-UCT M3Lee select A select B select B2 1 2 select C AI 18 HP M-UCT 2 M-UCT 21 6 M-UCT 1 AI HP guard C1 27 guard D1 28 tag A1 2 tag B1 6 AI tag A1 3 Map Military M-UCT M3Lee guard A1 4 guard B guard B2 1 2 guard B3 1 guard C guard D1 1 3 tag A tag B1 guard tag 6 AI 216 Information Processing Society of Japan

The 21st Game Programming Workshop 216 図 3 パズルマップ puzzle A1 図 31 パズルマップ puzzle A2 図 32 パズルマップ

C1 図 37 パズルマップ puzzle C2 図 38 パズルマップ puzzle C3 図 22 は戦闘機同士のにらみ合いであり先制した側が勝利する移動力が同じなので

歩兵を壁にして自走砲が戦車を追い詰めることをテーマとするテーマとしては同じであるにも関わらずマップが広くなるにつれ探索空間も広くなるためか搭載 AI の正解率は低下している

似た傾向となった図 27 は guard A1, guard C1 をやや発展させたものと言える対空戦車と攻撃機は移動力が 2 異なるので 1 人

2 1 マスナナメや上下左右 2 マス先にならないように進行することで歩兵の逃げ先である死角を作らず全滅できるマップである正しく操作すれば 3 ターンで青歩兵を全滅させられるこ

自走砲の扱いは必ずしも上手ではない図 2 は相手が移動力 5 の対空戦車に変わったものであるこれは追いつめ方を間違えると包囲をすり抜けられ上限ターンでは倒せなくなる最短は 5

パズル型マップこれまでの問題もある意味でパズル性の強いマップであった本章ではやや必要能力の分類が困難なマップについて紹介するいずれもこれまで同様人間には簡単表 7

C3 パズル型マップにおける搭載 AI の成績ターン制限 1 1 2 2 2 5 5 5 Military 1 1 M-UCT 1 1 8 2 3 M3Lee 1 1 1 1 7 1

7 The 21st Game Programming Workshop 216 図 3 パズルマップ puzzle A1 図 31 パズルマップ puzzle A2 図 32 パズルマップ puzzle A3 図 33 パズルマップ puzzle B1 図 34 パズルマップ puzzle B2 図 35 パズルマップ puzzle B3 図 36 パズルマップ puzzle C1 図 37 パズルマップ puzzle C2 図 38 パズルマップ puzzle C3 図 22 は戦闘機同士のにらみ合いであり先制した側が勝利する移動力が同じなので単独では先制できず手詰まりとなるが壁役の攻撃機ユニットがあるため戦闘機が 2 歩右に進み攻撃機がその直上を護衛すれば勝利することができる図 23 から図 25 は歩兵を壁にして自走砲が戦車を追い詰めることをテーマとするテーマとしては同じであるにも関わらずマップが広くなるにつれ探索空間も広くなるためか搭載 AI の正解率は低下している図 26 は意味合いとしては guard A1 と似ており同種ユニット同士のにらみ合いで相手の進路を妨害することで先制するマップである搭載 AI の結果も guard A1 と似た傾向となった図 27 は guard A1, guard C1 をやや発展させたものと言える対空戦車と攻撃機は移動力が 2 異なるので 1 人の歩兵で対空戦車を護衛することはできない 2 人の歩兵をうまく配置することで先制することができるこれも搭載 AI には難しかったようである図 28 は自走砲がマンハッタン距離 2 1 マスナナメや上下左右 2 マス先にならないように進行することで歩兵の逃げ先である死角を作らず全滅できるマップである正しく操作すれば 3 ターンで青歩兵を全滅させられるこれを搭載 AI に解かせた場合上限ターン数をとした場合は全 AI が毎回青を全滅させたが上限ターン数を 7,5,3 と厳しくしていくうちに正解率は下がった何度か述べている通り自走砲の扱いは必ずしも上手ではない図 2 は相手が移動力 5 の対空戦車に変わったものであるこれは追いつめ方を間違えると包囲をすり抜けられ上限ターンでは倒せなくなる最短は 5 ターンそれなりに正しい先読みが必要で搭載 AI には解けなかった 8. パズル型マップこれまでの問題もある意味でパズル性の強いマップであった本章ではやや必要能力の分類が困難なマップについて紹介するいずれもこれまで同様人間には簡単表 7 Map 名 puzzle A1 puzzle A2 puzzle A3 puzzle B1 puzzle B2 puzzle B3 puzzle C1 puzzle C2 puzzle C3 パズル型マップにおける搭載 AI の成績ターン制限 Military 1 1 M-UCT M3Lee に解けるが既存のコンピュータには難しいものが多い表 7 に製作したマップと搭載 AI の成績を示す機がスペースを空ける必要がある問題である select B シ図 31 は歩兵が敵の自走砲を倒すために邪魔な戦闘リーズでも攻撃の順番が重要になったがこのマップでは 216 Information Processing Society of Japan

The 21st Game Programming Workshop 216 3 AI puzzle A2 32 AI puzzle B 2 tag 33 34, 35 AI puzzle C 38 2 AI 37 36 puzzle B 8.

$3 48 [5] : 26 [6] GAT (Game AI Tournaments @UEC) http: //minerva.cs.uec.ac.jp/gat_uec/wiki.cgi?page=\% C2\%E81\%B2\%F3GAT216 216--28 [7] : 26 [8] Bourg, D.M.$

8 The 21st Game Programming Workshop AI puzzle A2 32 AI puzzle B 2 tag 33 34, 35 AI puzzle C 38 2 AI puzzle B 8.1 AI (7,5) 3 4 AI AI AI HP TUBSTAP [1] GPW213 pp [2] TUBSTAP labs/ikeda-lab/tbs/ [3] TSPLIB mp-testdata/tsp/tsplib/tsplib.html [4] Huang, S.-C., Muller, M.. Investigating the limits of Monte-Carlo tree search methods in computer Go. CG 213,pp [5] : 26 [6] GAT (Game AI http: //minerva.cs.uec.ac.jp/gat_uec/wiki.cgi?page=\% C2\%E81\%B2\%F3GAT [7] : 26 [8] Bourg, D.M. and Seemann, G. : AI Information Processing Society of Japan

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