はじめに
先日Postmortemとして投稿したSamurAI Codingについてですが、そのゲーム性についてもう少し検討したいと思います。以下文体が敬体ではなくなりますが、今回は私の脳内の再現ということでご理解のほどお願いいたします。
SamurAI CodingのPostmortemはこちら
昨年度とのゲーム性の違い
このタイトルはPostmortemでも挙げたが、より具体的にはどう違っていたのだろうか。
このため、一度具体的なマップを用意してみる。
※以下Visualizerの画像は公式様Visualizerよりお借りします
上のほうの犬、侍と穴は考えないとして、この4×4のマスを今回考慮する範囲とする。
昨年のルールでの検討
このマップ、昨年のルールでは侍は一切埋蔵金を掘ることができない。自身を犬として操作し、侍がどう動こうと絶対に守れるか実際に動かしてみる。
一手目
一手目は対称性からおおよそこのような形になる。侍は休息するという手もあるが、昨年のルールでは休息したところで機動力は変わらないので、より敗着になるだけに思われる。実際取れないのだが、それはかなり自明なので省略する。
二手目
今回犬は一個も取らせないことを目標とするので、犬は次に相手が掘りうる埋蔵金の上に移動するほかない。もし侍がその埋蔵金を掘ろうとしていたら、失敗してかつ犬が真横につくので、機動力の問題から今後絶対に取ることができない。犬が埋蔵金を防御することが分かっていたとして相手の侍を行動させるなら、おそらく上の画像のようになるだろう。
三手目以降
三手目以降も自然な流れで考えることができる。犬は相変わらず次侍が掘りうる埋蔵金の上に乗るのみである。もし侍がその埋蔵金を掘ろうとしていたら、失敗してかつ犬が真横につくので、機動力の問題から今後絶対に取ることができない。侍が犬が防御することを察知して移動していたとしても以降千日手のような手順となる。
今年のルールでの検討
これに対し今年のルールでは、一手目に斜めで早速一個とることができる。
さすがにこれだとつまらないので、一手目に斜めを使わなかった場合について考える。その場合、同じ理論で二手目まででこのような状態にできる。
三手目、四手目
三手目、侍はRESTすることで優位に立てる。犬は駒の衝突判定の特性上、自分が今いるマスと、自分が次移動した先のマスの二つの二つしか守ることができない。それに対し、上の場面でRESTした侍は、その次のターンで三つの埋蔵金を見据えている（画像では見えないが、マップの設定としては犬がいるマスにも埋蔵金がある）。したがって、侍を完全に防ぐことはできない。犬がこのターンで侍横の埋蔵金に移動すると、その次のターン防げるかは相手がとろうとした埋蔵金と自分が守りに行った埋蔵金が一致するかの確率問題となり、その確率は50%と言って差し支えない。まして、侍が掘りに行くのではなくその埋蔵金の上に乗ろうとしてきたら、防衛陣の崩壊はより大きくなる。
少しマップを一般化した検討
上記のような特定のマップではなく、少し一般化して考えてみる。なお、ここでも穴については考えない。考えるとおそらくコーナーケースが多量に出てくるため、一般的に話しづらいからである。
以下の画像は昨年のルールでの主な犬の妨害戦略を示した図である。犬は侍のそばについているとき、四方向中の二方向を防ぐことが可能である。よって下の画像で右上方向に目標地点がある場合、この構図ではいつまでたっても目標に到達することができない。正確には一マス退くことで戦場を移動できるが、犬の斜め動きを延長した直線の反対側には到達できない。
これに対し、今年度の侍はRESTすることで8方向に進める。下に二枚の画像があるが、一枚目は右上方向に目的地がある場合、二枚目は右方向に目的地がある場合である。
マスの色は、オレンジが目的地に2マス近づくマス、濃い黄色が1マス、薄い黄色が変化なしに該当する。一枚目において薄い黄色になるべきマスが塗られていないが、今回の検討には使わないので省略する。
一枚目、二枚目ともに最善のマスは犬は必ず押さえるべきである。犬はあともう1マス守ることができるのだが、どちらも、色付きのエリアを完全に守ることはできない。二枚目の写真では、薄い黄色のエリアなので目的地には近づいていないが、この次の試行が一枚目のパターンになるので詰められてしまう。よって、穴のないマップでは任意のマスについてその一マス手前までは到着できることが保証されている。
では、実際にはどれくらいかかるのか。これは相手の犬がどれほど最適な動きをしているかが問題であるので、まずは犬の最適な行動を考える。私の出す結論としては、犬はこのようなにらみ合いでは「どうせ守れないなら二枚目の場面を最も多く経験させる方向に妨害失敗する」というのが平均所要ターン数が伸びる。実際は犬がその三マスのうちのどこにいるかによっても違うが、概算ということで誤差とする。
「どうせ守れないなら二枚目の場面を最も多く経験させる方向に妨害失敗する」が良いというのは、二枚目は防げなかったとしてもそのターンで目標地点との距離が縮まるわけではないからだ。なお、二枚目は右隣に犬がいるとすると、どちらかにヤマを張って防げなければ、その次のターンに侍は一マス確実に近づけてしまうのだが、犬は侍の右隣にいる際はあえて守りに行かないことで、一枚目の状態に遷移させることができるので、こうすれば一枚目+2ターンと考えられる。
また、この犬との駆け引きを成立させるには侍は基本斜め移動でなくても毎度RESTしなければならない。RESTしなければ動きの選択肢は昨年度と同じであり、近づくことは許されない。なお、実は決勝で提出したAIでは相手の犬が妨害する犬かどうかを最初に判定したうえで、犬と隣接する際は毎度RESTを置いている。
これを踏まえて必要ターンを計算してみる。仮の状況としては、侍が10マス右の地点を目指し、すでに右隣に犬がいることとする。二枚目については、一回の行動には2ターンかかるとし、それぞれの場面で相手の犬を回避できる確率を50％とする。一枚目、二枚目ともに場合によっては切り抜けたのちにもう1マス接近できるが、それをなしにすると、最長は
二枚目⇒一枚目⇒二枚目⇒・・・
を繰り返しジグザグに進むことだといえる。二枚目はあえて防御せず右隣に居座るのが総合的に一番長くなるので、2ターンで切り抜けられ、一枚目は平均4ターンで切り抜けられると考えられる。（なお、上の戦術を相手の侍がプレイ中の情報から推定していた場合は一枚目を100%で切り抜けられるので一枚目も2ターンである）これを9回繰り返すので平均ターンは54ターン（戦術を知っていれば36ターン）と求められる。
妨害なしならば9ターンであったのが犬の妨害で54ターン、およそ6倍となる。100ターンでゲーム終了であることをふまえると、侍の動きは強化されたとはいえ埋蔵金エリアが偏っている場合には犬の妨害は十分に有効である。
決勝で使われたマップでよりうまく動く戦法
一方、決勝でよく見られた、秘匿埋蔵金が多いマップだとどうなるのかというと、あまり効果を発揮しない。というのも、開始時点で穴のないマスに50%程の確率で秘匿埋蔵金のあるマップの場合、序盤は8箇所に平均4か所程度埋蔵金が存在する。検討の最初で述べた通り、犬は高々2箇所しか守れないので、埋蔵金のありうる地面を掘り起こし続けるだけで得点は十分に得られる。
では、そのようなマップではどのようなAIが良いのかというと、よく分からない。実際に試したわけではないが、個人的には犬に侍近辺の探索をさせてみるのがよいように思われる（し、実際にそれに全力な犬を見てみたいところがある）。相手の近くで妨害する犬には、その妨害と引き換えに相手に近辺の埋蔵金を見せてしまう欠点が存在する。よって、埋蔵金率が高い場合は、犬は自分の侍近辺のマスを踏んで確認しつつ、自分の侍の妨害に来た敵犬もうまく迂回させるなどして、最大限自分の侍の役に立ってもらう。犬の妨害が有力だっただけに見落としがちだったが、ゲーム名の一部にもなっている「Dig here」というのはそもそもそういう意味ではないか。
今回の提出AIの反省
私のTeamが提出したAIは上の「決勝で使われたマップでよりうまく動く戦法」について全く考慮していなかった。一度は考えないではなかったが、計算時間的にすべて考慮するのは無理だと諦めていた。これについて、一つに見落としていたのが、今回のAIプログラムはサイズ制限に余裕があるので、たくさんのモードをつけても問題なかったことである。このゲームは秘匿埋蔵金総量や、これまでの行動からどの位の割合で埋蔵金を得られるかを取得することができる。当然だが、最初の20ターンほどで相手の戦術を見ることもできる。最初の20ターンほどで情報を収集し、それに相性の良い戦術のAIを呼び出せばよかったのである。たしかに毎ターンあらゆる場面に対応するには時間が足りないが、この方法では最初の情報集計時間を除いて計算時間はほとんど変わらない。
特に一番後悔したのは、相手の戦術をあまり見なかったことである。「相手の犬が自分に向かって直進してきているか」「自分の犬が妨害成功したときに次の動きを変えているか」「二つの埋蔵金と敵の犬がそばにいる場合、埋蔵金量の多いほうを狙うのか」など、これらの動きはAI同士の相性が存在する。先ほどの検討で同じ地点に36ターンで行けるのか54ターンで行けるのでは大きく話が違うし、相手の侍の序盤の動きから戦術を推測でき防御率90パーセントならば先ほどの検討の結果は198ターンに膨れ上がる。50パーセントで埋蔵金を掘れることが80パーセント、100パーセントでできるようになるのも大きな差になる。今回のトーナメント戦ではそこまでの柔軟性を持つAIはいないような気がしたので（たまたま実戦にわかりやすく表れてなかっただけかもしれない）、もしそのようなチームがいればマップ選出、対戦相手にかかわらず高順位間違いなしだったことだろう。あえて苦戦するとすれば、どちらが良いとも言い切れない二択に対しては乱数を使用して選択しているようなプログラムだろうか。
私のTeamの提出した決勝AIは、プログラムを修正する際に過去の自分との試合結果を参考にしている。このため、どうしても相手の行動を過去の自分で仮定したプログラムの戦績がよくなってしまっていた。また、マップもGithubに上がっているマップ候補でしか戦わせていなかった。結果、想定と違うような場面に対応できずにいた。いわゆる特定の条件下での「過学習」を手動で行ってしまったというところだろうか。
おわりに
おそらくここを見ている人はいないと思いますが、見てくださった方はありがとうございます。今回の反省を通じて遠くから広い視野で見つめることの重要性に気づきました。「プログラムの提出に関する制限」「バリエーションのある実験マップやAI」「ゲームをみづからの手で動かして考え直すこと」など、それぞれ広く今後の開発に生かせることだと思いますので、今回の失敗だけで終わらせずにしっかりと活用していきたいと思います。
それでは。
