Xmas Rush 参加記 - ヴァルの開発記

概要

CodinGameのXmas Rushというコンテストに参加しました。

ゲームの雰囲気は以下のリンク参照↓
www.codingame.com

結果

世界７位（日本１位）

１．アルゴリズム

コンテスト序盤はMinMax探索を使っていましたが戦績が微妙だったのでモンテカルロ木探索に変更しました。しかしモンテカルロ木探索だけでも微妙だったため、MinMax法で良い手を絞ってからモンテカルロ木探索をするという方法をとりました。

まずMinMax探索はたいていの場合において強いので、とりあえず最初に使うアルゴリズムとしてはテッパンです。ただし、今回のゲームに適用するときは１つ注意しなければいけない箇所があります。

それは、今回のゲームでは『同じ場所を２人でPushすると何も起こらない』というルールがある点です。MinMax探索だと『自分に有利なPushは相手が必ず競合させてきて何も起こらなくなり、自分に不利なPushだけが通る』という世界を探索することになります。これではシミュレーションの中で自分は常に同点か不利になり続けるしかなく、そんなあり得ないシミュレーションをもとに行動を選択してもうまく戦えないのは明らかです。

これを改善するためにMinMax探索中はPushが競合するケースを探索から取り除くようにしてやると良い結果を得られました。

ではここから、MinMax探索よりもっと良い方法はないか？というのを考えてみます。例えば、以下のようなケースを考えます。

		敵
	行動	B1	B2	B3
自分	A1	20	3	12
自分	A2	5	15	7

自分の行動がA1とA2の２通りあり、敵の行動がB1とB2のB3の３通りある例です。数字は自分にとっての評価値で、自分にとっては大きいほうが良く、相手にとっては小さいほうが良いです。このとき、１手先MinMax探索で自分のとる行動を考えます。

		敵
	行動	B1	B2	B3
自分	A1	40	3	12
自分	A2	5	14	6

行動A1を選んだとき、最悪ケースは敵が行動B2を選んだときで、その評価値は3です。
行動A2を選んだとき、最悪ケースは敵が行動B1を選んだときで、その評価値は5です。
MinMax探索ではこのうち評価値の高い方を選ぶので、評価値5の行動A2を選択します。（上の図で緑色に塗った箇所）

１手先のMinMax探索はこれで終わりです。２手先は計算時間が足りないので読めません。このままでもそれなりに強いのですが、今回はもう少しいろいろ考えてみることにします。

今度は逆に同じ状況を敵から見た場合を考えてみます。敵視点でMinMax探索を使うと、敵は以下の赤色で塗った行動をとると良さそうなことが分かります。

		敵
	行動	B1	B2	B3
自分	A1	20	3	12
自分	A2	5	14	6

敵は評価値を下げたほうが良いということに注意して考えると、
行動B1を選んだとき、最悪ケースは行動A1を選んだときで評価値は20です。
行動B2を選んだとき、最悪ケースは行動A2を選んだときで評価値は14です。
行動B3を選んだとき、最悪ケースは行動A1を選んだときで評価値は12です。
敵から見たMinMax探索ではこのうち評価値の低いものを選ぶので、評価値12の行動B3を選択します。（上の図で赤色に塗った箇所）

つまり、敵はB3を選ぶだろうということが予測できますが、もし敵がB3を選ぶなら自分はA2よりA1をとったほうが良いです。（評価値6＜評価値12）

また、敵も自分と同じことを考えて自分がMinMax戦略でA2を選ぶなら敵はB1をとったほうが良いのでB1の行動をとってくるかもしれません、その場合も自分はA1をとったほうが良いです。（評価値5＜評価値20）

…あれ、これってつまり、敵がB3やB1の行動をとってくることが予測できるので、A1の行動をとったほうが良いってこと？でも俺のMinMaxくんはA2が良いぞって言っている。。いったいどうすればいいんだっ…！

とややこしくなってきたところで整理すると、そもそもMinMax法は交互に着手するゲームで有効な戦略であり、同時に着手するゲームに適用しても必ず良い結果を返してくれるとは限りません。あくまで『各行動の最悪ケースのみを考えて』最良の行動を選んでくれます。良く言えば堅実な戦略ですが、悪く言えばビビリな戦略です。

本当の理想は『相手がとってくる行動を完全に読んでそれに対して有利な行動をとる』ことです。しかし相手がとってくる行動を100%正確に当てることは不可能です。それなら、相手はどんな行動をとってくるか分からないので『相手がどんな行動をとってきてもだいたい良い感じに対応できる行動』をとれば良いかも？と考えました。

そこでモンテカルロ法の出番です。モンテカルロ法を使うと勝率が高くなるような行動を返してくれるので、相手がとってきた行動に対して多くの場合でこっちが有利になるような行動を選んでくれます。

モンテカルロ法の中でも今回はモンテカルロ木探索を行い、枝の選択にはUCB1を使いました。

勝敗がつくまでプレイアウトすると計算時間がぜんぜん足りないので、４～５ターンで切って評価値を返すようにしました。プレイアウトは必ずPushターンが終わったタイミングで切り、評価値は取得したアイテム数と歩いてとれるアイテム数、あと自分のクエストアイテムをプレイヤータイルに持っていたらボーナスとしました。歩けるマス数も一応評価に入れましたがほとんど影響ありませんでした。あと、評価値はUCB1との兼ね合いで0～1の範囲に収まるように正規化し、また（自分の評価値＋敵の評価値）＝１となるように設計しました。

MinMax探索をやめてモンテカルロ木探索を使うことで順位が100位→6位まで上がりました。がしかし、すぐに追い越されてしまいました。原因は調べたらすぐに分かりました。以下のようなケースを考えてみます。

		敵
	行動	B1	B2	B3
自分	A1	99	0	99
自分	A2	14	8	9

こんなの敵はB2を選んでくるのは明らかですが、私のモンテカルロ木は「A1を選ぶと高い評価値が出る確率が高いぞ！」と返しくるのでA1の行動をとって評価値0の状態に遷移し爆死していました。確率だけで判断してはダメな場合もあるということにここで気付きました。

こういう場合に備えるために、A1のような『酷い結果になる可能性がある行動』をプレイアウトの中でほとんど選択しないようにプレイアウトの行動選択を改善しようといろいろ試してみたのですが、うまくいきませんでした。『A1のような行動』を判定するヒューリスティックの精度があまり上がらなかったのと、その判定処理に時間がかかってしまいプレイアウトの数をこなせなくなってしまったことが原因だったようです。

今回はプレイアウトの改善は諦め、他の方法で対応することにしました。この行動A1のように『いい結果になる確率は高いけれど、もしかしたら最悪な結果になるかもしれない行動』は実は先ほど紹介したMinMax探索で判断することができます。モンテカルロ木探索をする前にMinMaxで最悪ケースの評価値が悪い行動をあらかじめ除外しておき、残った"悪くならない行動"に対してモンテカルロ木探索を行い"良い結果になる確率が高い行動"を選ぶようにしました。

また、敵の行動もある程度絞り込んでおいたほうが良さそうだと思い、最初に6msだけ敵視点でモンテカルロ木探索を行い、ある程度良い結果を返す行動のみに絞り込むようにしました。

ここまでの流れをコードにすると以下のようになります。

int N = 3; // 絞り込む行動数

Action think(GameState& gameState) {
    
    // 1手先読みMinMaxで自分の行動を絞り込み
    int depth = 1;
    vector<Action> myActions = minMax(gameState, depth);
    nth_element(myActions.begin(), myActions.begin() + N, myActions.end());
    

    // 自分の行動を絞った状態でモンテカルロ木探索をして敵の行動を絞り込み
    gameState.turnPlayer = 1; // 敵視点
    uctTimerLimit = 6; // 思考時間を6msにセット
    vector<Action> opponentActions = uctSearch(gameState, myActions);
    nth_element(opponentActions.begin(), opponentActions.begin() + N, opponentActions.end());
    

    // 自分の行動、相手の行動ともに絞った状態でモンテカルロ木探索をして最良の行動を探す
    gameState.turnPlayer = 0; // 自分視点
    uctTimerLimit = 40; // 思考時間を40msにセット
    myActions = uctSearch(gameState, myActions, opponentActions);
    Action bestAction = *max_element(myActions.begin(), myActions.end());

    return bestAction;
}

２．高速化

(1) BFSのvisit配列の初期化

今回のゲームではBFS（またはDFS）が多く発生しますが、BFSする際に意外と無視できないのがvisit配列の初期化です（ここでvisit配列とは、各セル[y][x]をキューに追加したかどうかを表すboolean型の大きさH×Wの配列を指すこととします）。

実際は２、３マスぐらいしか探索できない場合でもvisit配列の初期化は必ずW×H回の処理が必要で、処理時間がもったいないです（探索してみるまで２、３マスで済むかどうかは分からないので、初期化は全部やっておく必要がある）。下手したら探索より初期化のほうが時間がかかる場合もあります。

それを改善するために、今回はvisit配列に定数時間初期化配列を使いました。読み書きに若干のオーバーヘッドがかかる代わりに、初期化をO(1)で出来るというデータ構造です。実装は省略しますが、調べるといろいろ出てきます。（私は独自に実装したものを使いました）

(2) ゲームの状態を少ないバイト数で表現する

ゲーム木探索をするとゲームの状態（この記事では仮にGameStateクラスと呼びます）のコピーが発生することが多くあります。このコピー処理の時間を減らすためにはゲームの状態を出来るだけ小さなバイト数で表現することが大切です。そのために今回はアイテムデータをグローバル領域に確保することにしました。アイテムは以下の５つの情報で表現できます。

プレイヤーID（0 or 1）
種類（1～12）
クエストアイテムか（0 or 1）
ｘ（-2～6）
ｙ（-2～6）

以上の組み合わせを見ると、アイテムのパターンは2×12×2×9×9 = 3,888通りであることが分かります。つまり、グローバル領域に3888個の変数を用意してそこにアイテムの実体を置いておけば、GameStateクラスはその実体へのポインタを１つ持つだけで済みます。アイテムの情報を変更するときは、アイテムの実体の中身は変更せずポインタの指す先を変更するようにします。

３．パラメータ調整

今回はパラメータ調整を念入りにしました。２つのプログラムを対戦できる環境を自分のPC上に用意し、パラメータをいろいろ変えながら繰り返し戦わせてどのパラメータだと勝率が高いかを計測しました。特に強さに影響のあったパラメータとして、モンテカルロ木探索のプレイアウトの深さ（ターン数）は強さに大きく影響しました。最初なんとなく10ターンにしていましたが、これを２ターンにしたところ順位が爆上がりしました（30位→5位）

この対戦環境はパラメータ調整以外に、なにか変更したときに強くなったかどうかを測定するのにも役立ちました。Submitして順位を見ても良いですが、周りの人も強くなっていくため順位が変動してよく分からなくなることもあるので、自己の環境で対戦させたほうが正確でした（しかも速い）。