SamurAI Coding で考えたこと

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 の成果を試したいというものでした。しかし実際にやってみると、壁にハマるやら逆走するやらで、まともに走らせることもできませんでした。来年がもしあるなら、今度こそ、ディープラーニングを使って人間には及びもつかない手を繰り出してみたいものです。

ソフトウェアの設計・実装がうまく行かなくてお困りではありませんか? 組込屋にお任せください。リモート案件は、常駐の半額でお受けしています。

27 Replies to “SamurAI Coding で考えたこと”

  1. コンテストに参加したものです。

    やっぱり他の参加者の考え方は参考になりますね。せっかくなので、私の採用した方法とかを書いてみたいと思います。

    衝突判定についてですが、確かにここがだめだと全てアウトなので非常に大事な部分だと思います。

    最初はコース内のすべての障害物との衝突判定をチェックするのではなく、障害物の外側の線分をすべて取り出して、それらの線分との衝突をチェックすれば大幅にチェック回数が減らせるのではないかと考えてやってみたのですが、ちょっとした障害物でも外側の線分の数が意外に多く、あまり早くなりませんでした。

    そこで、サンプルを改良するという方法にしました。サンプルの衝突判定のコードでは線分Sとコース内の障害物の衝突判定を、「線分Sを対角線とする長方形内のすべての1*1の正方形内の障害物」と「線分S」の衝突判定を行っていますが、それを以下のように変えました。

    ・「長方形内の線分Sが通る1*1の正方形」と「線分S」の衝突判定に変更。チェックする正方形の数を大幅に削減できました。具体的には、線分Sのベクトルが(x、y)の場合、|x|+|y|-1回(この式はもしかしたら違うかも?)、正方形とチェックすればOKとなります。

    ・サンプルコードの線分同士の衝突判定は内積などを使ったものでしたが、「1*1の正方形の範囲内の障害物」と線分の衝突判定は、正方形の4つの各頂点が障害物であるかどうかだけで衝突判定ができるので、そのように衝突判定を書き換えました。

    判定したい線分Sは馬の速度のベクトルであり、そのx軸方向及び、y軸方向の絶対値は最大でもせいぜい8程度なので、最大でも15回程度の(内積などの計算を必要としない)チェックで済むことになりました。最初に試した障害物の外側の線分との衝突判定では、外側の線分の数が15以上になることが頻繁におきるので、こちらのほうが高速でした。

    だた、上記の工夫より、そちらの記事にもある、衝突判定のキャッシュ化が私の場合は一番高速化に寄与したと思います。私の場合は、unordered_mapではなく、馬の座標はルールから、x座標に5ビット、y座標に8ビットの計13ビットで表現できるので、馬の移動を線分の両端2点分の26ビットで表現してテーブルを作ってキャッシュ化しました。

    あまり長くなるのもあれなので、とりあえず今回はここまでとします。そちらの衝突判定のほうが高速かもしれませんが、参考にしていただければ幸いです。

    1. おおっ、エーアイテイオーさん! 打ち上げの場でお会いしましたね。解説ありがとうございます。とても興味深かったです。あの場で何人かに聞いたんですが、やっぱり衝突判定が面倒くさかったという意見はちらほらありましたね。

      エーアイテイオーさんの、衝突判定の正方形を最小化するという考えまでは、私も同じです。でも、線分の交差判定をしていないというのは凄い。私もそれを目指しましたが、できませんでした(斜めの壁の存在が厄介だった)。

      それと確かに、unordered_map より配列のほうが速そうですね。というか、C++ の unordered_map は構造体やタプルをキーにできないので、そのために私はわざわざ座標のビット圧縮をしてるんですよ。なら、普通に配列を使えばよかった。

      今回は詳細なコメントありがとうございました。思考ルーチンの工夫などあれば、またぜひ教えてください。

  2. どこかに参加者同士の感想戦みたいな場所があったらいいなと思ってたところ、
    ここしかsamuraicodingの記事が見当たらなかったのでお邪魔させてもらってます。

    衝突判定は、やはり正方形を最小化するところに落ち着きますか。
    今回は馬の速度をあまり上げられないのでやっぱりそれが一番速そうですね。

    評価値を計算するために、ゴールまでの距離を計算するところは同じだと思います。そちらの記事を見る限り、距離は縦横のみのいわゆるマンハッタン距離的なものを計算されているようですが、実際には斜めにも移動できるので、私の方は斜め移動も考慮に入れました。

    ただ、全ての点と点の距離を計算するのは計算量が爆発するのと、そこまで正確に計算してもほとんど意味がないと思い、各点からx,y座標が±3以下で、障害物に遮られない点との間の距離を考慮に入れてゴールまでの距離を計算しました。

    1. 確かに、感想戦の場は欲しいです! 苦労しただけに自分が考えたことは吐き出したいし、それ以上に他の人が考えたことを聞いてみたいですよね。私が知る限りだと、あとは KPCC さんと traP さんが記事を書いています。

      http://albicilla514.hatenablog.com/entry/2018/03/16/021251
      https://trap.jp/post/291/

      エーアイテイオーさんの戦略は、私のとだいぶ似てそうですね。詳しくは聞いてないですが、私を負かした sc-samurai さんは、コース上に予選と同じパターンが現れたら思いっきり先読みするように作ったと言ってました。

      そんな話を全員分聞けたら、きっと面白いでしょうね。

  3. おお、他にも記事書いてるところあるんですね。どっかに集まって感想戦とかできると確かに面白そうですね。
    私自身はブログとかは持ってないので場所の提供はできないので、迷惑でなければしばらくここにお邪魔させてもらおうと思います。

    紹介してもらったHPの一つはソースコードも出してるようですが、私もそのうち今年のコードをコメントとか入れたりしてから公開しようかと思ってます。ちなみに2015年度のはsamuraiの決勝のページで、2016年度のはgitで公開済です。

    評価値の続きですが、ゴールからの距離だけでなく、壁からの距離も考慮に入れました。その心は壁に近いルートより遠いルートを通ったほうがその後の行動で障害物にぶつかりにくくなると思ったからです。

    具体的には以下のようにしました。

    ・基本の評価値として視界の先の格子点の評価値をすべてy座標*10とし、視界内の各格子点の評価値を一つ前のコメントで説明した方法で計算する(ただし、距離を10倍して考える)。

    ・視界の範囲内の格子点の場合は左右と進行方向の最も近い障害物までのマンハッタン距離を評価値に足す。一つ前で評価値を10倍したのは、ここで足す壁までの距離よりも、ゴールまでの距離の評価値の影響を高めるためです。また、進行方向と逆方向の障害物に関しては戻ることは基本的にないので無視しました。

    ・視界の先の格子点の場合は、視界の先には障害物がないと仮定し、左右の端と進行方向の逆の最も近い障害物までのマンハッタン距離を評価値に足す。こちらは、それより先には障害物がないと仮定しているので、先程と違って格子点の左右とそれより前の障害物の距離を測りました。

    これでなるべくコース障害物から離れるようにコース取りをするようにしてみました。コースによってはもちろん逆効果になる場合もあるのですが、基本的にはこの方針でうまくいく感じでした。

    1. コメント欄での解説、大歓迎ですよ! 他の人にもやってほしいぐらい。

      壁からの距離は、私も意識しましたねー。でも、評価関数にうまく盛り込めませんでした。左右の端と進行方向に絞るわけですか。なるほど……。

  4. ゲーム木に関しては、ほぼサンプルそのままのミニマックス木+αβ枝刈を採用しました。サンプルと違うのは前回説明した葉の部分の評価値の算出方法と、いろんな枝刈りを使って深くまで読めるようにした点ですが、枝刈については次回以降に書きます。

    本当は、このゲームは同時着手なので、ミニマックス木では表現できないはずなんですが、色々やってみたところ、サンプルの手法である程度深いゲーム木を作って探索すれば結構強いAIができそうな感じがしたので、細かいところは目をつぶりました。

    ただし、敵の着手をあまり先まで読んでも仕方がないと思い、敵に関しては最大7手先まで読んで、そこから先は敵は動かないと仮定してゲーム木を作りました。

    決勝の2回戦で相手のAIに競り負けたのは細かいところに目をつぶったのが良くなかったのかもしれませんが、まあ、実際の所はよくわかりません。

  5. 枝刈りその1です。

    まず、y軸方向の最小速度ですが、最初は0を最小値としていましたが、
    予選であった左右にくねくねまがるコースだと、相手を追い抜くために-1まで速度を減らしたほうが良い場合があったので、最小値を-1としました。

    最大速度についてですが、サンプルだと視界/2となっていましたが、それだと、予選のコースでよくあった、ゴール前に障害物が全くないコースで不利になります。ただ上げ過ぎても良くないので、以下のように考えました。

    サンプルコースにあった、ゴールのすぐ次がすべて障害物になっており、ゴールにぴたりと止まらなければならないコースを考慮に入れ、まず以下の3つの条件のすべての組み合わせにおいて、下記の方針で馬を走らせた時の、最短のゴール時間を計算しました。ただし、コースはゴールまで障害物は一切存在せず、ゴールの次のマスはすべて障害物で埋まっているものとします。

    条件:
    ・視界:5~30
    ・ゴールまでの距離:10~30
    ・y軸方向の速度:3~視界

    馬を走らせる方針
    ・x軸方向の速度は0とする。
    ・ゴールが見えていない場合は、上記のy軸方向の速度で走る。
    ・ゴールが見えている場合は、y軸方向の+1,0,-1の加速の全ての組み合わせを試し、最も早くゴールする組み合わせを計算する。

    その上で、各視界の各y軸方向の速度におけるゴール時間の合計が最も短い最大速度を求めました。その結果、y軸方向の最大速度は以下のように設定しました。

    視界が5~7:5
    視界が8~10:6
    視界が11~19:7
    視界が20以上:8

    結局のところ、決勝戦のコースでは、ここで想定したようなコースが存在しなかったのが残念でしたが、視界が12以下の場合は、最大速度を視界の1/2より早くできる点と、視界がいくら広くても速度9以上にすると色々問題が出そうな感じでしたので、この方針は結果的にそれほど間違っていないような気がしています。

    1. 私は最大速度=視界としてました。これにリミットをかけるなんて頭をかすめもしませんでしたが、そのほうが強くなったかもしれないということですか。結構ショックです。

  6. あまりy軸方向の速度を上げ過ぎると、くねくねしたコースなどで曲がり切れずにひどい目にあいそうな感じだったのでリミットをかけました。

    y軸方向ですが、後は予選のコースでよくあった、ゴール前に障害物が全くないコースへの対策として、視界の後ろ半分に障害物が全くなかった場合にy軸方向の最大速度を+1しました。
    決勝でそのようなコースがなかったので結局この対策は無意味でしたが・・・

    次に、x軸方向に関する枝刈ですが、まず、左右の壁にめり込むような行動を枝刈りしました。
    左右の壁は必ず存在するので、どのような行動を行っても壁にめり込むような場合に、壁の逆方向に
    加速する以外の行動にメリットがないと考えたからです。
    以下、左の壁に対する枝刈についてのみ記します(右の壁も同様なので)。

    具体的には周りに障害物が一切ないと仮定した場合に、その後ずっと右方向に加速したとしても左の壁にぶつかるような場合は、右方向への加速以外の行動を枝刈しました。

    例:あるターンの馬のx座標が3で、x軸方向の速度が-4の場合、その後常に右方向に加速しても次は
    「x座標が0、速度が-3」、その次が「x座標が0、速度が-2で壁にぶつかる」のようになる。

    一方、あるターンの馬のx座標が3で、x軸方向の速度が-3の場合、その後常に右方向に加速すれば次は
    「x座標が1、速度が-2」、「x座標が0、速度が-1」、「x座標が0、速度が0」となり壁にぶつからない行動が可能である。

    従って、x座標が3で、x軸方向の速度が-4以下の場合は、x軸方向へ+1加速する以外の行動は枝刈する。

    上記のような枝刈を行うx座標が0から15までのx軸方向の速度は以下のようになります。

    -2, -3, -3, -4, -4, -4, -5, -5, -5, -5, -6, -6, -6, -6, -6, -7

    ただし、ゴールが視界内の場合は、ゴールさえしてしまえばその後のことは関係ないのでこの枝刈は行いません。最初はその事に気が付かずにゴール手前で変な挙動を行い、ゴールが遅れるような状況に遭遇したりしました。

  7. x軸方向の枝刈りの続きです。当日のパワーポイントに書いた左右の行き止まりについてです。

    視界内の障害物が存在しない各格子点について、以下の計算を行い、その格子点が「左の行き止まり」、「右の行き止まり」、「どちらでもない」のいずれかであるかを計算します。なお、視界外と、ゴール以降の格子点はすべて「どちらでもない」とします。

    1.調べる格子点Pから正のy軸方向の格子点を順番に調べ、最初の障害物Yを見つける。障害物が見つからなければ「どちらでもない」として終了。

    2.調べる格子点Pから負のx軸方向の格子点を順番に調べ、最初の障害物Lを見つける(コース外は障害物なので、必ず見つかる)

    3.調べる格子点Pから正のx軸方向の格子点を順番に調べ、最初の障害物Rを見つける(コース外は障害物なので、必ず見つかる)

    4.障害物Yが障害物Lとつながっている場合は、格子点Pは「左に行き止まり」とみなす。

    5.障害物Yが障害物Rとつながっている場合は、格子点は「右に行き止まり」とみなす。

    なお、ルールから、「左に行き止まり」かつ「右に行き止まり」な格子点Pは存在しないはず。

    上記の計算を実現する具体的なアルゴリズムはちょっと複雑で書くと長くなりそうなので、後に公開予定のソースコード(読みやすいとは言えませんが・・・)を見てください。

    「左に行き止まり」な格子点は、必ずその先でその格子点Pのx座標よりも右に移動しなければならないので、その格子点に馬が存在する場合、その位置から速度がx軸方向に-2以下になるようなx軸方向の-1と0の加速を枝刈する。-1までの速度は、敵をよけたり、その後の移動に有利になる可能性があるので許容するが、-2以下はおそらくほとんど意味がないと考えました。

    補足:左に行き止まりな格子点にx軸方向の速度が-3以下で到達する可能性があるので、+1の加速は枝刈りしない。

    「右に行き止まり」に関しても同様な枝刈を行いました。

    一つ前に説明した枝刈りよりもこちらのほうがより枝刈りを行うことができました。

  8. 残りの枝刈ですが、敵に移動を妨害されない場合で、障害物に阻まれた場合に、加速も減速もしない行動は状況の変化がないので枝刈りしました。でもよく考えると、わざと1ターン加速なしで障害物に当たって移動せず、次のターンで敵の行動を妨害するという行動にも意味がありそうな気がするので、この枝刈はしないほうがよかったのかもしれません。

    敵についてですが、敵が視界外の場合は敵が存在しないものとしてゲーム木を構築しました。なお、そちらのSamurAI Jockey のルールの記事に、「相手の馬の位置と速度に関しては、視界の内外にかかわらず把握できるものとします」とありますが、ルールでは敵が視界外の場合は(0,-1)が返ってくるようになっていたと思います。

    最後は置換表(メモ化)です。自分の位置と速度、敵の位置と速度の情報を64ビットのハッシュ値に変換し、その評価値を置換表(テーブル)に記録しておき、ゲーム木において同じハッシュ値の状況が現れた場合は、テーブルから引いた評価値を採用します。
    これが一番速度に影響すると思います。

    次はゲーム木の葉とその評価値、ゲーム木の深さについて書く予定です。

    1. 視界外の敵については、完全に思い違いをしていました! ありがとうございます。記事も訂正しました。

  9. ゲーム木の深さですが、深さ1からはじめ、後述の設定した思考時間がくるまで反復深化で1ずつ深さを増やしていくという手法を取りました。無駄に思えるかもしれませんが、ゲーム木のように、深さで指数関数的に木の規模が増加する場合はそれほど無駄ではなく、有効だと思います。

    また、上記で設定した深さに関わらず、自身の馬が視界外の場所に到達した時点でそれ以上は計算しても仕方がないと思い、そこをゲーム木の葉としました。葉の評価値の計算方法については次で説明する予定です。

    なお、ここでいう深さとは、「自分と敵」の行動一セットで深さ1としています。前にも述べたように、深さ8以降は敵は行動しないものとしてゲーム木を生成しました。また、15手先くらいまで読めれば充分だと考え、最大の深さを15に設定しました。一般的な木の深さでいうと最大深さ7+15=22です。

    そちらの記事で言及されているめりこみ問題ですが、めり込んだ時の速度の分の深さだけ読めれば回避できるはずで、こちらではy軸方向の最大速度は8としたので、8手先まで読めれば発生しないということになります。深さ8であればほぼ確実に生成できるようなので、特別な対処はしませんでした。でももしかすると運が悪いと発生するかもしれませんので、何か少しは対処したほうがよかったかもしれません。

    思考時間は、基本的には「現在のy座標」と「ターン数」、「ゴールのy座標」からゴールターンを予想して設定しました。ただし、それだけだと、コースの前半は高速に移動できるが、後半で高速に移動できないような場合に、後半で思考時間が少なくなってしまいます。

    そこで、対戦会のコースの大半はコースに設定されているターンの半分のターン以下でゴールできることから以下のように設定しました。最後に5を足しているは実際のゴールターン数が予想ゴールターン数よりも小さい場合を考慮したものですが、必要があったかどうかはよくわかりません。なお、懇親会で優勝した方も同様の方法で思考時間を調整していたという話を聞きました。

    予想ゴールターン数 = 現在のターン数 / (現在のy座標 / ゴールのy座標) + 5
    (ただし 現在のy座標 <= 0 または現在のターン数 <= 2の場合は「制限ターン数/2」とする)

    思考時間 = 残り時間 / (max(予想ゴールターン数, 制限ターン数 / 2) - 現在のターン)

    あと、αβ枝刈を行う際には、なるべく有望な手を最初に探索したほうが枝刈の効率が良いはずなので、深さnのゲーム木を探索する際に、1手目は深さn-1のゲーム木の最善手から探索するようにしてみました。ただ、これは思ったより効果はなかったような気がします。

    上記の条件で、自宅のPCで対戦会のコースでいろいろ試してみた所、平均すると深さ10のゲーム木を生成できました。ただ、おそらく大会で使われたPCのスペックは自宅のスペックよりも低かった気がするので、大会ではどこまでの深さのゲーム木が生成されていたかについてはよくわかりません。

  10. 最後に葉の部分の評価値ですが、葉の深さをdとした場合、

    x手目の位置の評価値を

    (x手目の自分の位置の評価値 * 10 – x手目の敵の位置の評価値)* 10の(x-d)乗

    とし、葉の深さまでの評価値の合計値とました。最初は自分の評価値を10倍せずにそのまま使っていたのですが、それだと敵の位置を気にしすぎてうまくいかない(前にうまく進まない)ことがあったので、敵の位置よりも自分が先に進むことを優先させるためにいろいろ試して10倍することにしました。

    また、最初はd手目の評価値のみを用いてたのですが、上記のように1手目からの評価値を多少考慮に入れることにより、それぞれの手においてなるべく評価値の高いルートを通るようになりました(これをやらないと最高の評価値の葉が複数ある場合に、途中のルートは一切考慮されず、最初にたまたま見つかったものが採用されてしまう)。

    実は評価値を上記のように同じ場所、速度でも、その場所に至るルートによって変動するようにしたため、一つ前で説明した自分と敵の馬の位置と速度を使ったメモ化による探索の省略は本当は正しくないのですが、それを考慮してしまうとメモ化自体がそもそもできなくなってしまうため、そこは誤差の範囲だと考えてメモ化を採用しました。

    あと、同時着手を考慮する方法として、自身の行動が敵に妨害された場合は、妨害されなかった場合の移動先の評価値を加算するという工夫を試してみましたが、これはあまりうまくいかなかったので決勝戦に提出したAIではこの機能はOFFにしました。

    以上、長くなりましたがうちのAIの主な工夫点です。ソースコードを公開したらまたお知らせしようと思います。

    そちらの記事にあった選択の自由度はなかなか面白そうな工夫ですね。私の方ではそこは全く考えていませんでした。

    1. エーアイテイオーさん、今回は詳細な解説をありがとうございました。全部読みました。

      やっぱり勝つ人は勝つべくして勝っているんだなということがよくわかりました。ソースが読めるのを楽しみにしています。

  11. 書き忘れましたが、ゴール付近に障害物が何もないコースと、ゴールの次の
    マスがすべて塞がれているコース以外の、コース予測は全くしていません。
    決勝で予選と全く異なったコースになる可能性が怖くてそこには
    手を出す勇気がありませんでした。でも、優勝した人はやってたみたいですね。

  12. 今更ですがたまたま発見して、興味深く読ませていただきました。参加者同士の感想戦ができる場があると面白いですね。
    本番はサンプルとたまたま同じようなコースだったのでコース予測をしたプログラムは有利になったみたいですね。

    1. 読んでいただきありがとうございます。KPCC さんはベスト4でしたよね。コメントいただけて光栄です。

      ところで来年の大会が SamurAI Jockey の改良版になると発表されましたね。個人的には、今回の知見が「生かせない」展開になることを願いたいです。

      1. お久しぶりです。

        ルール発表されましたね。

        視界がこれまでに到達した場所を基準になったのはいい感じですね。
        前回のルールだと一度後塵を拝するとコースによってはほぼ挽回不可能でしたので、この変更はいいと思いました。

        あと、ぶつかったら速度が0になるのは、スピードを出し過ぎた場合の枝刈が使えなくなるので、その部分は私にとっては今回の知見が行かせない展開になりそうです。

        水たまりは・・・ちょっと実際にやってみないとよくわかりません。

        あとぶつかった時に双方動けなくなる条件が増えましたね。それなりに影響しそうな気がしますが果たして・・・

        1. エイアイテイオーさん、返信遅くなってすみません。私もようやく新ルールを見ました。

          後ろの人が挽回しやすいルールになったのはいいですね。これだけで観戦時の面白さがずいぶん変わりそうです。

          それ以外の変化に関しては、本当に何とも言えませんね。直感的には今のプログラムのままでもそれなりに走れそうな気がしてるんですが、どうなんでしょう……。

  13. 予選提出したんですが、クラスメイトの数50名くらいしかいなくて、今年はなんか盛り上がってないですね・・・
    題材がほとんど同じだった(個人的には似てるけどゲーム性は結構変わったとは思うんですが)のが悪かったのか、それともCMが足りないのか・・・

    1. エーアイテイオーさん、コメントありがとうございます。

      僕も今年は出場を見送りました。12月~2月にかけて他のマラソンマッチが目白押しだったのが理由の一つですが、同じ考えの人が結構いたのかもしれませんね。

      盛り上がりの話でいうと、去年にはすでに前年比でかなり落ち込んでましたよね。サイトの見栄えとか、順位表の見やすさとか、改善の余地はいろいろありそうに思うんですが……。

  14. 今年は出場されないんですか。それは残念です。

    個人的には、昔やってた予選期間中に常時参加者同士の対戦が行えていた環境がなくなったのが痛いんじゃないかなぁと思ってます。
    2年前はそれで相当トラブっていたのでお金と手間がかなりかかるのはわかるんですが、1回しか対戦会が開かれないとやっぱり盛り上がりにかけますよね。

    まあそれだけじゃなくておっしゃるとおり他にも改善の余地は色々ありそうですね。

  15. 今年のテーマが2017年度のと同類だったので、以前公開すると言っていたソースコードの公開は今年のコンテスト終了後にしました。

    すごく今更な感じですが、2017年度のAIのコードをgitに公開しました。

    ついでに2018年度のも公開しております。
    今年はちょっといろいろというかかなり不運(?)もあって1回戦負けでした

    https://github.com/ysgeso/samurai-coding-2017-ysai

    よろしければ参考にして下さい。

    あと、もし許可が頂ければ2017年度のreadmeにここの掲示板に
    考えたことを書いたって書こうかと思っているのですがリンクを貼っても良いでしょうか?

    1. 決勝ラウンドお疲れさまでした。2年続けて決勝に進出したのはすごいことですよ。

      ここへのリンクはもちろん歓迎です。ソースコード、これから見て参考にさせていただきます。

  16. リンクの許可ありがとうございました。早速貼っておきました。

    あまり可読性が高くないコードだと思いますので、気になる点があれば気軽に質問して下さい。

コメントを残す

メールアドレスが公開されることはありません。

日本語が含まれない投稿は無視されますのでご注意ください。(スパム対策)