SamurAI Coding 2019-20 参加記
第８回 情報処理学会 国際人工知能プログラミングコンテスト [ SamurAI Coding 2019-20 ]に参加しました。
ゲーム概要
SamurAI Dig Hereというゲームで戦いました。ゲームの雰囲気は以下のリンク参照↓
https://samuraicoding.info/final-viewer/tournament.html
ピンクの○をクリックしてGame1かGame2を選択し、再生ボタンを押すと対戦結果が見られます。
ルール概要
・侍と犬を操作して埋蔵金をたくさん掘ったほうが勝ち。
・犬は周囲に隠された埋蔵金を探知することができる。埋蔵金の上に乗ることで犬は吠え、侍に埋蔵金の位置を伝えることができる。ただし埋蔵金の情報は敵にも伝わる。
・侍は周囲の地面を掘ることができる。埋蔵金がある地面を掘ると埋蔵金を獲得できる。
Dig Hereの名の通り、ここほれワンワンを上手にやったほうが勝ちみたいなゲームです。ルールの詳細は以下の公式ページを参照↓
結果
優勝しました。やったー！ 賞金50,000 JPYと以下の賞品を得ました。
SamurAI Coding 2019-20の賞品が届きました！まさかの軍配！#samuraicoding pic.twitter.com/0t1Z8sqWEl
— ヴァル (@ValGrowth) 2020年3月20日
最終提出プログラムの内容
１．戦略
侍の動き
ゲームに勝つためには埋蔵金をたくさん掘らないといけないので、埋蔵金を効率的に掘ることを考えればよいです。埋蔵金を掘っていく順番を巡回セールスマン問題として解けば、効率のよいルートを計算することができます。
マップ上に埋蔵金が無いときは、手当り次第地面を掘っていって運良く埋蔵金を掘り当てることを狙います。これも埋蔵金を掘るのと同様に、どの地面から掘っていくかを巡回セールスマン問題として解けばよいです。
犬の動き
犬はマップ上をうろうろして埋蔵金を探し出して侍に伝える、……と最初は考えましたが、実はこの方針はあまり強くないです。犬は侍より移動能力が高いので、それを活かして敵の侍の妨害をしたほうが圧倒的に強いです。犬が最適な移動をすれば敵の侍をほぼ完封することができます。よって犬は敵の侍の妨害に特化したほうが良く、埋蔵金探知能力はおまけ程度にとらえてよいです。
２．アルゴリズム
深さ２ターンのαβ探索を使用しました。（自分１ターン、相手１ターンで深さ２ターン）
工夫した点としては、min値が等しいときは平均値を比較して高い方を使うというのをやりました。例えば自分の行動Aと行動Bが両方とも敵に体当たりで無効化される可能性があるとき、どちらもmin値が同じになってしまい優劣をつけられません。そういうとき、敵の全ての行動に対する平均値を計算することで、有利な状態へ遷移する可能性が高い手を選ぶことができました。
あとは高速化のために、手をいい感じにソートしておくやつをやりました。敵の行動を固定して自分の各行動を評価して良い順に並べ替えておく、というのをやったらけっこう速くなりました。
３．評価関数
評価値は以下に挙げる複数の値を持った配列です。先に書いてあるものほど優先的に評価します。
(1) 犬を助ける
先述のとおり犬は強いです。犬が穴に囲まれている場合は何よりも優先して助けたほうが良いです。具体的には、自分の犬が他の３キャラ全てと穴で分断されているときに、侍から犬への最短距離を評価値としました。決勝戦でもこれがかなり役に立ちました。
マップによっては、犬２匹 / 侍２人というように犬と侍が分断されているマップもありましたが、この場合は犬を助けると敵の犬も助かってしまいメリットが無いため、犬を助ける評価は0としました。
(2) 埋蔵金を掘る、掘りに行く
埋蔵金の回収に関する評価。先述のとおり埋蔵金を巡る巡回セールスマン問題を解きます。厳密に解くととんでもない時間がかかるので、かなり大雑把に解いてます。最も近い埋蔵金を無視して遠回りするような経路は全て枝刈りで消しました。最大で５つの埋蔵金のみを巡回し、６つ目以降は無視。
回収対象にする埋蔵金は『敵のいかなる妨害が入っても確実に回収可能な埋蔵金』のみに絞りました。敵のほうが先にとれる埋蔵金に向かって行っても無駄足になる可能性があるからです。敵の侍と犬からそれぞれ幅優先探索をして各マスへの最短距離を計算しておき、それより自分が速く到達できるような移動のみを可としました。
ちなみによくあるDPで高速化、みたいなのは難しいです。侍は４近傍を掘れるので、同じ埋蔵金に到達するのでも上下左右の４パターンあり、さらに穴を掘ったり埋めたりしながら進むので通った経路によって盤面の状態が異なり、そう簡単にはDPできません。これら全部（掘った埋蔵金の座標群、盤面の状態、侍の位置、距離など）をすべてZobrist hashに突っ込んでメモ化、というのをやりましたが、ハッシュテーブルの処理時間がかかりすぎてむしろ遅くなってダメでした。
この評価値は自分視点と敵視点それぞれ計算し、対称な評価値としました（対象な評価値＝自分視点の評価値 - 敵視点の評価値）。そうすると『敵が安全に獲得できる埋蔵金を最小化』するように、犬が敵の侍を妨害するようになりました。
また、この評価値は『すでに掘った埋蔵金＋これから掘れる埋蔵金』という形で扱う必要があります。すでに掘った埋蔵金を考慮しないと、いい位置をとるけど一切掘らないという残念な動きになります（なりました）。
(3) 未知の地面を掘る
『埋蔵金の存在が未知』な地面を掘る評価。これは(2)で巡回セールスマンを解く処理の『埋蔵金のあるセル』を『未知のセル』に置き換えればだいたい同じように計算できます。
埋蔵金の存在が未知のセルは、以下の３つ条件を全て満たすセル全てです。
１．ゲーム開始時に侍や犬がいない
２．一度も穴が掘られていない
３．一度も犬が乗っていない
(4) 犬で敵の侍を妨害
敵の侍の行動可能範囲の小ささ。自分の犬と敵の侍から幅優先探索で計算できます。
(5) その他
侍はできるだけ中央へ行くとか、犬はできるだけ敵の侍に近づくとか諸々ありますがあまり重要でないので省略します。
４．小技
侍の行動を決定してから、犬の知識を足して犬の行動を決定する
このコンテストでは侍と犬のプログラムが別々に動いているので、互いに別のことをやろうとして邪魔し合わないように注意が必要です。
犬は隠された埋蔵金の位置を知っていますが、その情報を使ってしまうとシミュレーションの結果が侍と食い違ってしまい、うまく連携した動きができなくなってしまいます。
しかし、犬だけが持つ情報も使いたいので、以下のような手順でシミュレーションすることにしました。
【侍】
『侍、犬の最適な行動の組み合わせ』をシミュレーションし、出力する。
【犬】
①『侍、犬の最適な行動の組み合わせ』を、犬だけが持っている情報は使わずにシミュレーションする。これは侍のシミュレーション結果と一致する。
② 侍の動きを①で計算した行動で固定して、犬が持つ情報も使って『犬の最適な行動』を考える
こうすることで、互いに邪魔し合うことなく犬が持つ情報を活用することが出来ました。
侍は同じ行動を連続でとらないようにする
リプレイを見ていて、侍の以下の動きが気になりました。
①行動が敵に妨害された場合に、次のターンも同じ行動を繰り返して永遠に敵とぶつかり合っている
②同じ場所にとどまったり、その周辺をうろうろしたりする
これらは無駄にターン数を消費する行為なので、出来るだけ減らしたいです。
これらを解消するために、過去数ターン(15ターンぐらい)で侍が同じ場所で同じ行動をとらないようにしました。（これはわりと強硬手段で、本当にこれでいいのか疑問はありましたが、結果的に強くなったので良しとしました）
犬と侍の暗黙の情報伝達
犬は埋蔵金の存在を敵にも伝えてしまうので、自分の侍だけに伝える方法があると便利そうに思います。例えば、埋蔵金を感知したら１ターン立ち止まるとか、あらかじめ決めておいた方向へ移動するとかです。
しかし、実はこれはあまり重要ではないです。なぜなら
・吠えると敵に知られる→そのまま乗っていれば絶対に取られないからあまり問題ない
・侍に伝えた後、侍が取りに行く→敵の犬に妨害されてそこまで行けないことが多い
となるからです。暗黙の情報伝達にターン数を消費するぐらいなら敵の侍を妨害することに徹底したほうが良いと感じたので、これらの方法は使いませんでした。
ただし、ターン数を消費せずに伝えられるならデメリットが無いのでやったほうが良いです。例えば私がやったのは『犬がその場に立ち止まるのが最適と判断した場合に限り、代わりに無効なプレイプランをとることで侍に情報を伝える』です。無効なプレイプランとは、犬の場合は
①他のキャラクターがいるマスに移動しようとする
②画面外に移動しようとする
③穴のあるマスに移動しようとする
の３種類です。『無効なプレイプランをとった』という情報は次のターンの入力に含まれるため侍も知ることが出来ます。また、ゲームの進行上はその場に立ち止まるのと同じなので、立ち止まるのが最適な行動の場合はノーコストで侍に情報を伝えることが出来ます。
どんな情報を伝えるかはいろいろ考えられますが、私の場合は『犬が無効なプレイプランをとった場合、犬の周囲８マスに埋蔵金が１つも無いことを伝える』としました。これをやっておくと侍が手当り次第地面を掘るときに少し楽になります。
逆に埋蔵金があることを伝えるというのも考えましたが、犬の８近傍のうちどこにあるのかも伝えなければならず複雑になりそうなのでやめました。
マップごとに序盤の行動を決め打ち
決勝で使用する候補のマップはあらかじめ全て公開されているため、全てのマップでテストプレイをして、あまり上手い動きをしてくれないマップについては初手３ターンぐらいの動きを決め打ちしました。（決め打ちしたマップは決勝では使用されなかったのであまり関係なかったです）
４．強さの測定
自分の過去のボットと対戦させ、勝率を計算することで強さを計測しました。
上の画像は、予選前に公開された62のマップ＋予選で使用した38のマップを使って対戦を行い、勝率を計算している様子です。
自分に対して過学習してしまわないか心配でしたが、今回のゲームでは大丈夫でした。
『改善したつもりが弱くなっていた』ということを回避できたという点で、これはとても重要でした。また、弱いボットに負けている試合を調べることでバグや致命的な弱点を見つけることが出来たのも良かったです。
感想
ゲームの内容
ルールがシンプルで良かったと思います。ゲームの見た目もスッキリしているので、ルールを知らない人でも試合を見てればなんとなく雰囲気で分かり、参加者以外の人に見てもらうのにも良いと感じました。
初心者救済のため(?)の運要素がほどよく入っており、ガチガチのガチじゃない人でも勝てる見込みのあるゲームになっていてよかったと思います。
コンテスト全体
他の参加者と対戦できる機会が練習会・予選・決勝の３回しかなく、みんなでやっている感があまり無くて寂しい感じもしました。しかしそのぶん他の人の強さや戦略が不明なため、予選や決勝の結果を見るときはドキドキ感があり楽しかったです。
長期コンテストなので、もうやり残すこと無いってぐらいまできっちりやれるのが良い点でした。ただし気合を入れすぎて生活を捨てがちだったので、次回はもっと計画的に取り組めるよう工夫したいです。
新型コロナウィルスが流行が心配されている中、決勝大会を中止せずにオンライン開催という形で成功させたのは本当にすごいと思います。運営の方々ありがとうございました。
