SamurAI Coding で考えたこと

2020年1月24日

SamurAI Coding 2017-18 は、あえなく1回戦で敗退しました。3位以上を目標としていたので、ちょっと悔しい結果です。

このような結果でしたが、プログラム開発には相当な時間を費やしたので、ここにその過程や実際に採った戦略などを整理し、記録しておきたいと思います。

なお、今回の開発にいわゆる機械学習は使いませんでした(正確には、使おうとしましたが、うまく行きませんでした)。ですので、この記事にそのノウハウは書かれていないことをあらかじめお断りしておきます。

言語は C++ を使いました。以下、私が提出したプログラムを kumikomiya と呼びます。kumikomiya は大別すると、「衝突判定」の部分と「指し手探索」の部分に分かれます。

衝突判定

私は SamurAI Jockey の最大の難所は実はここだったのではないかと思っています。衝突判定とはつまり、自分の指そうとする手が壁に阻まれるのかそうでないのかを、正しく判断することです。

この処理を実装する手間が、意外と馬鹿になりません。kumikomiya のソースコードは、半分近くがこれで占められています。そしてここを間違うと、プログラムは完走することすらままなりません。実際に私はここにバグを埋め込んでしまい、練習ラウンドで初めてそれに気づきました。ひたすら同じ壁に突進し続けるという現象によって。

もちろんゲームマスター側も衝突判定を行っており、そのソースコードは C++ で提供されています。ですから判定処理を拝借することも可能でしたが、私は自前で実装することにしました。ソースコードを完全に把握した状態でありたいというのも理由の一つですが、それよりも、ここの処理時間がそのまま指し手の探索時間にのしかかってくるという事情があったからです。ここを速くしないと、おそらくプログラムは弱くなるでしょう。

衝突判定の細かいアルゴリズムは退屈なので省略しますが、一つポイントを挙げるとすると、判定結果をキャッシュしておくというのは高速化のために必須です。たとえば、ともに視界の範囲にある点P-Q間の壁の有無が一度判明したなら、その事実は未来永劫変わりません。そこで、1度目の結果を unordered_map に格納しておいて、2度目以降はそこから取り出すのです。

これをメモ化といいますが、このような unordered_map を使ったメモ化は、kumikomiya の中でちょくちょく使っています。

指し手探索

kumikomiya の思考ルーチンはいたってシンプルです。その証拠に、一手あたりの思考時間を1ミリ秒も使いません。本当は思考時間をもっと使って強くしたかったですし、試したことは書き切れないほどたくさんあるのですが、必ずと言っていいほど、事を複雑にするほど弱くなるというパターンに陥りました。

結局その中で最も強かったのが、「敵の手を読まない」戦略でした。kumikomiya は、まるで敵など存在しないかのように、自分がいかに早くゴールにたどり着くかだけを考えます。こうせざるを得なかった背景には、私には解決できなかったある一つの問題がありました。それは、敵の手を思考に入れると局面数が爆発してしまうという問題です。

組み合わせ爆発

コース上に敵がいないと仮定した場合、想定し得る局面(位置と速度の組み合わせ)の数は、コース幅と視界を考慮に入れて、せいぜい400×400=16万程度です。これは10手先を読もうが100手先を読もうが、読むべき局面の総量が16万を超えないことを意味します。同一局面に出くわした場合、その先の思考はカットできるからです。16万局面は、C++ ならミリ秒オーダーで読み切れる量です。

一方、局面を構成する要素に敵の状態を加えると、単純計算でさっきの2乗、すなわち256億局面になります。これは C++ でも数分かかる量に相当するため、当然すべては読み切れません。与えられた持ち時間の範囲で読めたのは、二人の手を1手と数えて、せいぜい4手先でした。この程度しか読めないと、単に弱いというだけでなく、致命的な問題が生じることになります。「めり込み問題」です。

めり込み問題

視界の悪い中で向こう見ずに突っ走っていると、不幸にも次のような状況に陥ることがあります。

上図のケースだと、壁から抜け出すのに最短で5手必要ですよね。しかし、4手先しか読めないプログラムは、この脱出ルートを発見することができません。その結果、永遠に壁にハマり続けることになります。これを「めり込み問題」と呼ぶことにします。

この問題に対して、場当たり的に対処することは可能です。たとえば、壁に当たったときは速度を落とすとか。しかしそれだと、完走は果たせるでしょうが、競争には弱くなります。速度を増して壁を脱出できるケースを見逃してしまうからです。たとえば次のようなケースです。

結局のところ、考えに特殊な条件を加えれば加えるほど、思いもよらない弱点を抱えるリスクが高くなってしまうものです。そこで私は、めり込み問題にはあくまで先読みで対処することにこだわりました。敵を無視すれば視界の範囲内はすべて読み切れるので、めり込み問題が発生することは理論上ありません。

枝刈り

プレイヤーの指し手には常に9つの選択肢がありますが、中には「どう考えても最適なわけがない」指し手が含まれます。このような手を読みから外してやることで、探索スピードを100倍や1000倍といったレベルで高速化することができます。これは「枝刈り」と呼ばれる重要なテクニックですが、諸刃の剣でもあります。下手な枝刈りは、意外性のある手を見逃すことにつながるからです。

テスト対戦をさせて結果を確認しながら慎重に枝刈りを試してみたところ、次のような手は読みから外しても強さを損なわないことがわかりました。

  • 速度の x 成分を増加させながら右側にコースアウトするような手
  • 速度の x 成分を減少させながら左側にコースアウトするような手
  • 速度の y 成分が -2 以下になるような手

これらを切るだけでも、読むスピードは圧倒的に速くなります。

直感的には、わざわざ壁に当たりに行くような手なども避けたくなりますが、どうやらこのゲームは壁に当たることを嫌がると弱くなってしまうようです。このように、指し手というのは何が功を奏するかわからないようなところがあるので、枝刈りしたくなる気持ちはなるべく抑えるように心がけました。

最深部までの距離

ゲームの思考ルーチンにとって最後の味付けとなるのが、局面の良し悪しを数値化する「評価関数」です。このゲームの場合、y 座標を大きくしたいという目標が明確ですから、y 座標をそのまま評価関数の戻り値にすることも当初は考えました。しかし、次のようなコースでは、その考えが通用しないことがわかります。

上図の A と B の y 座標は同じですが、明らかに A のほうが優勢です。つまり y 座標だけでは局面の良し悪しを測るには不十分だということです。

そこで私は、マップが更新されるごとに「最深部までの距離」を算出することにしました。つまりこういうことです。まず、視界の範囲で y 座標が最も大きい地点の距離を 0 と定義します。このように。

この定義を出発点として、待ち行列を使った最短経路探索(いわゆるダイクストラ法)で、移動可能なすべての地点の距離を求めます。そんなに難しいアルゴリズムではないですし、計算も一瞬で終わります。上の例だと、結果はこのようになります。

あとはこの値にマイナス符号をつけたものを、その局面の評価とするだけです。このアルゴリズムは思った以上によく動いてくれました。予選を勝ち抜いたのは、このプログラムでした。

選択の自由度

最深部までの距離も重要ですが、距離が同じなら、その局面において選べる手の幅が広いほうが有利だろうということは、何となく察しが付くところです。

そこで、そのような手の広さを評価できる指標の導入を考えてみましょう。たとえばある局面における9つの選択肢に対して、コース上に次のような壁が立ちはだかっているとします。

上図の場合、壁に当たらずに移動できる選択肢は3つですね。この数のことを「選択の自由度」と呼ぶことにします。

選択の自由度を評価関数に盛り込んだところ、プログラムが明らかに強くなりました。最深部までの距離を d、選択の自由度を f とおいて、いろいろと調整してみたところ、最終的には

$$ eval(d,f)=f-4d $$

という評価関数に決まりました。これが決勝で戦ったプログラムです。係数の 4 は結果論ですので、明確な根拠はありません。ですが結果的にこのプログラムは、予選のバージョンに対して7割勝てる程度の強さを手に入れました。

まとめと反省

結局のところ kumikomiya は、上の評価関数に照らして、数手先の利益が最大になるような手を指しているに過ぎません。

2つの指標しか使わないシンプルさが kumikomiya の特徴だと思いますが、逆に言うと、ありとあらゆる指標を試して、明らかに強さに寄与したのがこの2つだけでした。提出後、本当にこれで大丈夫なのかと心許ない気分になったのは事実です。これについては他の人のアプローチをぜひ聞いてみたいところです。

敵の手を読まないというのも、妥協の産物でしかありません。この点を突いてくるプログラムに遭遇したら、負かされるだろうことは覚悟していました。予選でも、巧みに進路を塞がれて負けたパターンがあったからです。それなりに時間を費やして対策を考えましたが、残念ながら打つ手がありませんでした。

それから、機械学習がうまく行かなかったのも心残りです。そもそも SamurAI Coding に応募した動機が、独学で身につけた TensorFlow と Keras の成果を試したいというものでした。しかし実際にやってみると、壁にハマるやら逆走するやらで、まともに走らせることもできませんでした。来年がもしあるなら、今度こそ、ディープラーニングを使って人間には及びもつかない手を繰り出してみたいものです。