CODEVS 5.0の本戦用のソースコード提出期限が本日の昼の12時でしたので提出しました。12時がすぎたので、たぶんCODEVS 5.0のプログラム的な詳細を書いてもいいと思うので、予選期間中には書けなかったことをいくつか書いておきたいと思います。

1ターンごとに半ば自動的に(ゲーム内の)マネーが増えるゲームがあったとします。そうするとこのマネーを評価関数に組み込むと評価値は自ずと1ターンごとにインフレしていきます。

こういうゲームにおいては、N手先同士の局面の評価値の比較はできますが、5手先の局面と10手先の局面との比較が成り立たなくなってしまいます。

CODEVS 5.0のゲームで言うと、相手が忍者ソウルを取るごとに自分のフィールドに犬が出現します。これがインフレ(デフレ？)要因であり、犬の数だけ評価値をマイナスするような評価関数ですと、1ターンごとに自然とマイナスになっていきます。

つまり、Nターン目とN+1ターン目の評価値の比較というのがあまり意味をなさなくなってきます。

将棋やチェスでもこの問題はあるにはあるのですが、評価関数が長年の研究により非常にうまく設計されていて、そして非常に精度の高い機械学習によって、この問題がうまく回避されていてほとんど顕在化しないです。しかし、将棋やチェスがとても特殊なケースであって、世の中にあるゲームのほとんどは、こんなにうまく評価関数を用意できません。

私は当初、CODEVS 5.0のゲームでも評価関数をうまく調整すればこの評価値のインフレ(デフレ)は抑えられると思って数日間、頑張ってみたのですが、どうも簡単ではありませんでした。それをやるには本格的な機械学習が必要っぽい気がしました。

そこで探索部をbeam searchで書き直すことにしました。たぶん、この手のゲームではbeam searchと相場が決まっているのでしょう。この点において競技プログラミング勢に完全に遅れを取った形でのスタートとなりました。

普通のbeam searchでは、1手ごとに評価値が良い順にm個ずつ局面を保存していきます。(詳しくはggrks。) 結局、評価値を見て、1手ごとに大胆に枝刈りしていることに相当するのですが、評価関数の設計が悪いと質の悪い枝しか生き残らないことがあります。

そこで、例えば、1手ごとに枝刈りするのではなく2手先まで展開してから(そのあと評価関数を呼び出してから)、評価値の良いものを選ぶという形にすれば評価関数が多少悪くとももう少しマシにはなるのですが、このへんのコストが馬鹿にならないので「2手先のよさ気な枝だけ展開してから」だとか、何らか工夫が必要になります。

しかし、そのへんのコードを書いて調整するのが結構大変なので、たぶん、今回の参加者は誰もそこまでやってないような気はします。単純なbeam searchでbeam幅(上位何手残すか)の調整と、評価関数の改善で頑張るのが本筋なのでしょう。

ところが、このゲーム、なかなかそのへんが難しく、beam searchと結構相性が悪い気はします。

具体的に言うと、忍者ソウルを取ると次のソウルが出現しますし、相手のフィールドに犬が発生しますので、ソウルを取るのがこのゲームの攻略の鍵なのです。そこで、ソウルを取っていないと評価値上、大きくペナルティを課すようにします。ところが、そうすると「落雷で石を壊して1ターン先にソウルを取る」という変化と、「石を迂回して2ターン後にソウルを取る」という変化があった場合、前者のほうが1ターン後の評価値は良くなります。なぜなら、ソウルを取らないと評価値上、大きなペナルティを課せられるからです。(後者の変化では、この時点では(評価関数では)このソウルが取れるかどうかまで判定できていません。)

ところが、落雷のコストが高いとき(消費コストはステージごとにランダム化されています)、このような選択は間違いであることが多いです。

なのに、石を割ってソウルを取り、そのあと相手からの落石のリスク回避のためにさらに石を割って脱出、みたいな変化を選んでしまうことがあり、スキルポイントを無駄遣いして大損をします。2手先まで読んでから評価関数を呼び出せばこの問題は多少回避されるのですが、今度はそのコストとの兼ね合いで…。

一般的に、N手先まで読めば簡単な評価関数で解決する問題を、1手しか読まずに解決しようと思うと、N手先の評価値を予測できるような評価関数が必要になります。将棋で言うと駒得だけでもN手先まで読むと結構強いですが、これをN手先まで読まずに1手読みで解決しようと思うと、駒得になりそうな駒の位置関係に加点するような評価関数が必要となります。

同じく、このゲームでもソウルを取ると大きく加点(あるいは取らないと減点)されるとして、N手先まで読まずに、1手読みでこれをなるべく正確に評価しようと思うと、「ソウルが取れそうなら加点」ということになり、「ソウルが取れそう」というのは「(忍者が)犬より先にそのソウルに到達できそう」だとか、「犬を分身で簡単にどかせそう」だとか、「ソウルのまわりに犬がいなさそう」だとか「ソウルへの道のりが拓けてる」だとかが必要になってきます。

あとは超加速という1ターンで3歩歩けるスキルがあるわけですが、この使用コストが低いときはこのスキルを使うことも考慮して、「犬より先にそのソウルに到達できるか」を考えていく必要があります。

このように、N手読めば簡単な評価関数で解決するはずの問題を、N手読まずに1手読みで解決しようと考えるととても複雑な評価関数が必要となります。

単純なbeam searchでは、1手読みで枝刈りをバサバサとしていくため、とても高精度な評価関数が必要となります。

他のランキング上位の人たちがどうやっているのかは知りませんが、おそらく単純なbeam searchをベースにかなり苦心して評価関数を調整したのだと想像します。

ただ、takaptさんのAIだけはこのへん他の人たちのAIと比べるとはるかに賢くて、評価関数がよほど優秀なのか、それともbeam searchを何らか改良してあるのか、そのへんは私にはよくわかりません。takaptさんならではのミラクルがあるのでしょうね。

また、このゲームの別の性質として、忍者が二人いるということです。このどちらか一方が捕まるとゲームオーバーですから、将棋で言うと自分の「王様」が２つあるようなものです。

CODEVS 5.0は1ターンごとに(将棋で言うところの)指し手は、スキル使用(分身や落石、落雷は各升指定)×忍者二人の移動で何千通りという組み合わせがあります。

まともな評価関数を考えたとき、おそらく1Mnps程度しか出ませんから、これらの組み合わせを馬鹿正直に調べていたのでは、2ターンすら読めません。

そこで、生成される指し手を制限するだとか、それぞれの忍者を個別に動かすことを考えて、それぞれの忍者のベストの動きを合成する(分割統治法)だとか、色々なテクニックが必要になってきます。

ただ、分割統治法がどれくらい出来るかは難しくて、忍者が完全に離れたところにいるならそこそこ有効そうに思えるのですが、二人の忍者が協力して石をうまく移動させて防波堤を築いて…みたいな展開を私は想像していたので、その方針は採用しませんでした。

分割統治法でいくら先まで読めても、忍者二人をうまく連携させることが出来ないとその部分で不利になりますから、どちらがいいかは正直よくわかりません。

このへん、このゲームのゲーム性をどう捉えるかという部分でプログラムの設計が大幅に変わってきます。

マシンパワーが潤沢にあるのであれば、かなり網羅的に読めるわけで、(分割統治法で)細く深く読むよりは、広く浅く(忍者二人が連携する手順を)読んだほうが有利になると私は考えました。

ただ、最終的な本戦用の動作環境がまさか1論理コア、2.2GHz相当という超ロースペック環境だとは想像すらしていなかったので、このへんにおいて、少し誤算がありました。

あと、相手を攻撃したほうがいいのかという問題があります。(将棋で言う)相手の詰みが読みきれているなら当然攻撃するほうが得なのですが、相手の詰みを読み切るのはなかなか大変です。それというのも、分身があるからで、例えば犬に囲まれているとしても、相手から敵分身が来るというのが100%わかっていれば、自分が分身をうまい場所に出すことで詰まないからです。

例えば次図は犬に囲まれていてどう見ても詰みなのですが、分身があるととりあえず2ターン詰みを引き延ばすことができます。

そこで、これを1手詰めにするため、相手はいまこの忍者のいるところに敵分身を出します。ところがこちらもここに敵分身が来るというのがわかっていれば、いまの忍者がいる升の真下とかに自分身を出すことにより、右下に空間が出来てここに抜けられることがあります。(下図)

このように敵分身がどこに来るかわかっているときにそれでも詰むようにするというのは条件的にきつすぎて、現実的にはなかなかそんな局面は出現しません。つまり、mate solverのようなものを作るとしても、そのmate solverが本当に100%完全な詰みしか検出しないとしたら、そのmate solverは活躍の機会がほとんどないということになります。

そこで、敵分身はこないと仮定してmateを検出しないといけません。ところが、これでも条件としてきつすぎてなかなかこれが成立する機会がありません。

ゆえに、もっと投機的に攻撃をするべきなのですが、上位のAIはプリセットAIであるHiretsuAIとの勝率を上げるようにチューンしてあるはずで、すなわち敵落石や敵分身では死なないように移動しているので、こちらが攻撃しても当たることはまずなくて、スキルポイントをいたずらに消費しただけの結果となります。

すなわち、このゲームでは投機的に攻撃をするのには向かなくて、「長いターン耐え忍ぶゲーム」であると言えます。ぶっちぎり強いtakaptさんのAIが、この方針であるのは、このためです。

私が最初にレビュー記事を書いたときに、takaptさんから次のような反応があったのも、もしかするとこの部分(を書いたから)に関してなのかも知れません。

やねうらおさんの記事がちょっと言いすぎかなと感じるくらい
どこまでオープンにしていいかルールにあったっけ

— ぷち＠ぷよぷよAIを作っています (@takapt0226) March 5, 2016

相手を攻撃するスキルコスト、いまの1/3ぐらいだとこの状況が変わって面白かったと思うのですが、現状のバランスだと、下手に使うよりは一切使わないほうがマシでしょう。この点は(現在のゲームバランスを)少し残念に思います。

さて、私のAIが予選からどれくらい強くなったのかについても書いておきます。

私のAIのほう、並列化して6コアでやっと予選4位タイ(この時点でtakaptさんとはR70程度の差)でした。1コアと6コアとで対戦させると8,9割ぐらい負け越していたので1コアだとR200ぐらい低めのようでした。

さすがにこれはまずいだろと思い、予選期間が終わってから頑張って評価関数を改善して、ようやく1コア動作で予選通過の6コア動作のものに勝てるようになりました。

しかしそれでもまだtakaptさんの予選通過バージョンとはR70の差。そこで、さらにnpsを極限まで上げて(ピーク時 2.5Mnps)、どうにか、その(自分の)予選通過バージョンに7割勝てるぐらいになりました。これで、おそらく予選通過バージョンのtakaptさんには並んだはず。

そこから、探索部とかいじくり回して(npsは1/4ぐらいにダウン)、前バージョンに7割勝てるぐらいの調整をしました。すなわち、takaptさんの予選通過バージョンに7割勝てるぐらいの水準にはなったはずです。…が、

予選最終submitに19-1だった

— ぷち＠ぷよぷよAIを作っています (@takapt0226) March 22, 2016

な、、なんですと…。

それでは皆様、決勝のニコ生配信をお楽しみに！

【生放送のご案内】
3/26(土)に行われる決勝の二コ生配信ページのご案内です。
是非、下記ページからタイムシフト予約して当日視聴してみてください！https://t.co/gCUWZ89Rv4#codevs

— CODEVS_OFFICIAL (@codevs_official) March 22, 2016

関連記事

CODE VS 5.0予選通過しました！
CODEVS 5.0 準優勝しました！