※上の画像は公式様Visualizerよりお借りしました
はじめに
今回、2021/3/19に日本情報処理学会様主催で行われました、SamurAI Coding 2020-21にTeam「monk1」として参加いたしました。結果は準々決勝敗退でした。今回はその感想、戦術について書こうと考えております。私はプログラムを始めてまだ間もない者で、あまり深く難しいことには突っ込むことができませんので、主に戦術に関して述べていきます。
SamurAICoding公式サイトはこちら
追記:今回同じTeamでお世話になったstatiolakeさんが参加日記を投稿したそうです！早速一読しましたが、私のブログの内容を前提知識にするとより一層楽しめる物語となっております。
ゲーム概要
このゲームは、二人のプレイヤーのうちどちらがより多くの埋蔵金を掘り当てられるかを競うゲームです。 このゲームでは、それぞれのプレイヤーに、
自分の周囲の地面を掘ることができる「侍」という駒
と
自分の周囲の埋蔵金を知ることができる「犬」という駒
がそれぞれ一つずつ存在します。
同じマップに対して、Player1とPlayer2のゲーム開始時の駒の位置を入れ替えた試合を続けて行い、その二試合の合計点で一点でも多くの埋蔵金を掘り当てたほうの勝ちとなります。
より詳細なルールについては、こちらを参照ください。
昨年度とのゲーム性の違い
この犬と侍を動かして埋蔵金を得るゲームですが、実は昨年度の大会でも似たような趣旨のゲームが行われていたようです。私は参加しておりませんが、昨年の予選、決勝を観戦し、それを踏まえて今年度の違いを考えてみました。
実は、ルールはほとんど同じです。一点違うのは、侍が直前1ターンに休憩をとることで斜めにアクションをとれるようになったことでした。また、それに付随して、斜め移動同士で交差するような行動の場合は侍が優先的に動けることになりました。昨年度の大会では侍の機動力の低さから犬を妨害に用いることで相手の侍がほとんど掘れないようにすることが可能でしたので、その修正だろうと思われます。
ルールの変更で侍が強化されたにも関らず、依然として妨害してくる犬を相手に埋蔵金を獲得するのは難しい問題でした。しかし、しっかりと休憩をすることで昨年度のような盤面の隅に追いやられる姿は見られなくなりました。
逆に、犬にとっての最適な戦術が敵の妨害であるかどうかも疑わしくなりました。昨年度はほぼ確実に封じ込められるからこそ有効であったこの戦術ですが、今年度は、敵が遠くにいる場合、わざわざ向かうよりも自分の侍周辺の埋蔵金捜索を行ったほうが良い場合もあり得ます。
そういった点で、今年度は昨年度のゲームルールに比べて最適が見つかりにくく、また、相手のAI、マップの相性もあるので、決勝でも上位陣の間ではどちらが強いともいえず、どちらが勝つかわからないような戦いや予選の順位表をひっくり返すような戦いが見られたと思います。
決勝AIで使用した主な戦術
今回の基本アルゴリズムとしては（準）貪欲法を利用しており、侍は各ターンどのマスを掘りに行くかを決め、その最短ルートにあたる行動をとります。
また、今回挑戦した言語がPythonで、高速化も十分に行っていないため断念した戦術も多く存在します。それらについてはまた下のほうにまとめておきます。
犬は敵の妨害役
多くの方々がお気づきだとは思いますが、犬を無策で散歩させ、埋蔵金を見つけ次第踏んで知らせるのは自分にとってほとんどプラスになりません。
というのも、このゲームは犬が踏んだ場合、同じく埋蔵金の情報が相手に伝わってしまい、見つけ次第踏んだ場合自分と相手のどちらがその埋蔵金に近いかは50:50です（使用されるマップの候補は上がっているので正確にはそうではないですが、戦術的にその犬はどちらにも与しない中立的な動きになってしまいます）。
上の問題を解決するには、犬の動きはおおよそ
・衝突判定を利用して敵の動きを阻害する
・自分の侍に近いマスを捜索する
・自分の侍にしか分からないような特別な合図をする
に分けられます。これらの動きを場面によって使い分けるという方法もありますが、実装の単純さから今回は一番上のみを採用しました。敵のうちでも、敵の侍に焦点を当てて、敵が移動しそうな方向を潰すように妨害しています。
侍は相手の犬のほうが近い埋蔵金は避ける
上にあった犬を妨害に使うという戦術ですが、練習会の段階ですでに複数の方が使っていらっしゃいました。そのため必然的に既に存在の知られている埋蔵金は妨害をされて取りに行くのが難しいです。
その対応策として、自分の侍の行動を決める際、相手の犬のほうが近い埋蔵金はその埋蔵金量を低く見積もりました。
あり得るマスに埋蔵金を仮定する
このゲームでは、毎ターンまだ掘られていない埋蔵金の量を取得することができます。そこで、埋蔵金があるかわからないマスにその埋蔵金を分配しておくことにしました。すでに存在が知られている埋蔵金を犬が死守するであろう上位陣の方々を考えると、上位陣との対戦でより効果のある戦術だろうと思われます。
ここで、埋蔵金があるかわからないマスというのは以下の条件すべてを満たすもののことを言います。
- 駒の初期位置になっていない
- 一度も犬が上を通っていない
- 一度も穴ができていない
- そのマス埋蔵金があることが知られていない
この戦術によって、博打要素はありますが、平均で一試合に得られる埋蔵金の量が多少増加します。
掘った次を考える
基本的に貪欲法ではありますが、例外があります。それは、掘ろうとしているマスの目の前まで来た時です。そのまま貪欲に掘ってしまうと、その次に掘りたい場所へ移動するために掘った場所を埋めなおして移動しなければならない可能性が出てきます。
今回提出したAIでは、自身の侍が1ターンで行ける場所とそうでない場所の2グループでそれぞれ最大評価の埋蔵金を探し、上に述べたような事象が発生する場合は先に上を通過してから掘るようにしています。なお、敵の犬がある程度近いときは悠長なことはしていられないので貪欲に掘ります。
その他
そのほかの戦術としては
などになります。
実装を断念した戦術
AIの実装に完成はないとはよく言われますが、今回の実装は様々な改善点の残るものとなってしまいました。中にはそもそも処理速度的にどの言語でも間に合わないだろうものもあれば、ただただ手間を惜しんだだけのものもあります。
埋蔵金への最短ルート複数取得
今回のゲームはボードが格子状で、移動は前後左右や斜めに一マスだったために、同率でたくさんの最短ルートが出てきます。このうち、敵の犬をできるだけ避ける最短ルートを取得できると、確実に強化されると思いました。
敵の侍に近づけない犬を補助
大会で使用されるマップの候補の中には、マップの状態が恣意的に用意されているものが多く、中には犬が穴で閉じ込められているものがありました。そういったマップ以外でも、ゲームの過程で自分の犬と相手の侍の間に穴で隔たりが生じている場合がしばしばみられました。
これらの場合において、穴を埋めて犬を自由に動けるようにするのが有効かどうかはケースバイケースであり、特にこの先のターンが少ない場合や出だしの積極さで勝敗が決まりそうな場合は、この戦術はマイナスに働きます。その判定は非常に難しく、生半可な判定は弱体化につながるため断念しました。
シミュレーションによって全行動を試し盤面を評価する
少々戦術というよりはアルゴリズムの話になるので私からは控えますが、これについては、高速化処理を十分に行っていないため断念いたしました。駒から各埋蔵金への距離を求めるのに想像以上に時間がかかり、一手全探索も叶いませんでした。
狙って埋蔵金が取れるかの判定
埋蔵金は、その立地によっては犬が妨害してきても強引にとることができます。基本的に埋蔵金が単体で存在しているとき（マップ内に一個しかないときを想像すると分かりやすいです）、その埋蔵金は犬が上に乗り続けた場合にいつまでたっても掘ることはできません。その埋蔵金の隣接するところにもう一つ埋蔵金が存在した場合でも、同様に犬が二つを行き来しているといつまでたっても掘ることはできません。
ただし、かたまって三つ存在する場合、あるいは一つとびで埋蔵金が存在する場合は妨害を受けつつも一つとることができます。そのため、この判定方法でとれると判定したものは相手の犬が近くても押し通すのも有効だと考えました。
しかし、この戦術は各埋蔵金ごとにその周辺のマス状態を確認して判定する必要があるため、断念しました。また、この判定を用いた戦術は100ターンでは掘り切れないほどのマスがあるこのゲームでは弱体化になりうるとも考えました。実際、当日のマップではこれまでにないほど多量の秘匿埋蔵金が用意されているマップもあり、実装しないで正解だったようです。
大会登録開始から今までの流れ
この大会を知って参加登録をしたのは2020年の12月だったと思うのですが、一番最初に感じたのは、最低限のプログラム提出までが難しそうということでした。Windowsで開発するにはWSLが必須でしたし、このゲームのルールも少しややこしいと感じました。このゲームは前大会に修正を加えたもののようで、前大会から出場している方はすんなりと入ったかと思います。
ゲームのルールで一番の難関は犬と侍の衝突判定でした。動線が交差した際の優先度などが与えられてはいましたが、練習会開催時期はまだゲームマネージャー、ビジュアライザーともに誤判定があり、満足な開発ができずにいました。
誤判定の中で開発していたこともあり、monk1は練習会の段階では一位を取っていましたが、中にはマップ運で勝っていた試合も存在しました。
実は、練習会の段階でAIがそれなりの思考時間を使用していたために、以降大きな追加はできなくなっていました。予選ではmonk1と同じく妨害型の犬が多数見られ、かなりの接戦で二位となりました。この時の所感ですが、このように本番でいきなり大きな進化を遂げるチームが出てくるのも面白いですが、一日ごとなど短い間隔で提出ファイルで対戦を行い、その結果が逐次公開されるのも面白いのではないかと思いました。
予選のAIはほぼ完成だったのですが、犬に違和感があったので締め切り間際に大きく改善し完成版となりました。
決勝については、一回戦でこちらの環境では起きなかったタイムアウトが発生し焦りつつも勝利しました。二回戦については僅差で負けてしまいましたが、聴講者の方々が楽しめるような熱い戦いを提供できていたならば幸いです。
おわりに
ここまで読んでくださってありがとうございます。
今回出場した大会ですが、私の中で初の大会だったのですが協働開発してくださった方の支援もあり、個人的には満足しております。
あわせて、練習会、予選、決勝で対戦してくださった方々、この情勢の中オンラインでの大会の運営を行ってくださった方々に心から感謝いたします。
来年以降については開催はしない予定とのことですが、また似たような機会があればぜひ参加したいと思いました。何かご存じの方がいらっしゃったらご連絡ください笑
それではまた。
ぜひstatiolakeさんのこちらも。ここまで読んでいただいた方ならきっと面白いです。
