CodinGame FALL CHALLENGE 2020 参加記
CodinGameのFALL CHALLENGE 2020に参加しました。
参加している日本人が多くて、twitterが盛り上がっていて楽しかったです。
結果
世界50位日本12位でした。強い(断言)。
LEGEND入りが目標だったので達成できて嬉しいです。
前回のコンテスト後、3つのゲームでLEGEND入りしたのが良かったのかもしれません。
学校別では世界6位日本5位(!?)でした。前回のコンテストでは4人しか参加してなかった(その内一人は登録しただけでほぼやってない)ので、今回もそんな感じかなと思っていたのですが、7人+OB1人登録してみんなガッツリやっていたので嬉しかったです。
ルール
ツカモさんの記事が分かりやすいです。
序盤(~4日目)
最初はMCTSをずっと考えていました。理由は、ほぼ完全情報ゲーム(分からないのは次の相手の行動だけ)で、ランダム要素があるから(他の探索方法に比べて上手く処理できそう)です。しかし、呪文とポーションの種類数が多くてランダム要素による遷移が多く、各ターンの行動の選択肢が多いことから、横に広がりすぎて深さと各ノードの試行回数が稼げないと思ったのでやめました。他の方のツイートや記事を見る限り、MCTSはそのままのやり方だと上手くいかないみたいです。LEGENDにいった例はあったのですが、かなり工夫がされていました。
2,3日目に、各ポーションにかかるターンを求めて(後で説明するダイクストラを使った)、priceをそれで割ったときの値(1ターンに得られるpriceの期待値のイメージ)が一番大きいポーションを最速の手順でつくりにいくコードを書きました。序盤だからいい順位が取れて気持ちよかったです。このコードには欠点があり、次のポーション作りは考えていないので、ポーションを作った後インベントリがほぼ空になることが多くて、次のポーション作りに悪影響がでていました。なので、ポーションを作った後もインベントリを必ず3個以上残すようにすると、強くなって嬉しかったです。
4日目の夜、「インベントリのtier0~3がポーションのpriceの1~4点に対応している」という超有益情報がTLに流れてきました。これをベースにして探索を組み直そうと思いました。
組み直した後は大改造をすることなく、付け足したり、少し変更したりという感じだったので、最終的に提出したコードの内容を説明します。最終的には約1200行になりました。
最終提出コードの内容
相手の各ポーションの作成に必要なターン数を求める
「LEARN、新しく出現するポーション」を考慮してないのでたまに間違います。探索時のスコア計算に使うためのものであり、7ターン以上かかる場合は必要ないので求めませんでした。
「インベントリの組み合わせ(tier0-3の数を4bitごとに持たせたbit列)、使用できる呪文の組み合わせ(各呪文がcastableか否かを表すbit列)」を頂点としたダイクストラを行いました。高速化のためにpriority_queueは使わず、queueを7個用意しました。
RESTはcastableではない呪文を使おうとしたときにそれのCASTとまとめて行わせました(これの行動だけ他と違って2ターンかかっており、BFSではなくダイクストラと言っている理由です)。
BREWはRESTで回復しない呪文として解釈しました。
あるインベントリの組み合わせにターン数dで到達できる場合、その後にRESTをして、呪文が全回復した状態になることを考えると、そのインベントリの組み合わせにターン数d+1以上で到達した場合、呪文の組み合わせに関わらず無視して良いことが分かるので枝刈りをしました。ブログを書いている途中で思ったのですが、この探索ではBREWを呪文に入れており、RESTをしても全回復しないので間違いですね。BREWは終わりの方に加えたのがあってか、今まで気づきませんでした……
7ターン全探索(LEARNは考慮しない)
さっきのとやっていることは本質的には同じです。
以下の①〜④の組み合わせを頂点としたダイクストラをしました。
①インベントリの組み合わせ(tier0-3の数を4bitごとに持たせたbit列)(16bit)
②使用できる呪文の組み合わせ(各呪文がcastableか否かを表すbit列)(多く見積もって20bit)
③作ったポーション(作ったか否かを表すbit列)(5bit)
④探索中に与えたスコア(ポーションを作ったら与える。作ったポーションの作成に相手が必要なターン数と比べて早かったら5点、同じだったら4点、遅かったら3点)(最高で5*6点なので、5bitあれば十分)
全部の状態値を64bit整数に詰めて、map<long long int,int>で各頂点までかかるターンを保存しました。先程のと違って、ポーションを表すbit列を追加しているので、BREWを呪文に追加してないです。①で行った枝刈りと同様なものをここでも使用しました(ある頂点にターン数dで到達できる場合、それと①③④が同じでd+1ターン以上かかった場合は捨てる感じです)。ここでは、BREWと呪文を区別しているのでバグってないと思います。
さらに、ある頂点にかかるターン数がdのとき、それよりスコアが小さく、他が同じ状態でかかるターンがd以上の場合、不必要なので使わないようにしました。
最初④がなかったのですが、なんとなく入れたら強くなったので採用しました()。
評価は素直にインベントリのtier0-3を1~3点とみなしたときの合計点+④のスコア+作ったポーションのpriceとしました。
また、時間が残っている場合(大抵残っている)、1ターン目にLEARNをした場合の最高評価点を求めて、LEARNをしなかった場合と比べて高くなっていたらLEARNを行うようにしました。LEARNをした呪文は、先読みした後のターンに活躍してくれる可能性もあるので、max(自分の作成ポーション数、相手の作成ポーション数)=0のとき、LEARNをした場合の評価に+2をして、max(自分の作成ポーション数、相手の作成ポーション数)<=4のとき、+1をしました。これをtomeの一番下から順番に行いました。
序盤のLEARN
追記
盛大にバグっていて、実際には最初の6ターンに書庫の一番下をLEARNしていました。
この章は飛ばしてください。
何もわかりませんでした。他の人も分かってないらしい。
強い人のをパクるか!ｗと強い人のを眺めていたところ、生成呪文と、さらにその生成呪文から唱えることのできる呪文を先読みして取る動きを見て、「復帰重視かな。なんか強そうだな〜」と思ったのでこれを参考にして考えました。
最終的に採用したものを説明します。
1~6ターン目は必ずLEARNを行うことにする。
相手の動きを考えず、max(3、6-今のターン)ターンでLEARNできる呪文の組み合わせに対して、先ほどの方法で6ターン全探索をして、最高評価点が一番高い呪文の組み合わせを取れるように動かしました。6ターン全探索をする際は、インベントリが空な状態から始まり、BREWを考えない縛りを加えました。
他には以下のことを試してみたのですが、↑のが一番強そうでした。
②↑のを2ターンでLEARNできる組み合わせに対して行う
③全探索せず、+4の生成呪文を1つ優先的に取って後は全部下からLEARN
終盤戦
自分の行動の探索時、負ける可能性があるなら減点、勝ち確定の手があるならそれを採用、ということをしました。
最終的には自分の作ったポーションの数>=4 or 相手のポーションの数>=5で少し探索を変えました。
相手の行動に対しても全探索を行うことで、各ターンの(そのターンにゲームが終わると仮定した時の)最高得点、各ターンの、そのターンにポーションiを作って相手がゲームを終了させるときの最高得点を求めることができます。
自分のある手が負ける可能性があるかを求めたいとき、自分が相手の作りたいポーションを先に作っており、相手の最高得点を不可能にしている場合があります。相手の探索時に、今まで作ったポーションは何ターンに作ったかを状態値に加えたら可能になりますが、状態空間が広くなるのでとても遅くなりそうだと思いました。仕方ないので、相手が現時点でポーションを5個持っている時だけこれを考慮することにしました。相手が現時点でポーションが4個で、最初のターンでポーションを作った場合(これは防ぐことができない)は負ける可能性を考慮することも考えたのですが、実装が間に合いませんでした。
以下の①～③を全て満たしているときに勝ち確定の手としました。
①自分の探索時に取得したポーションを、ゲームが終了したターンまでに相手は作ることができない
②ゲームを終了させたターンの得点が相手の最高得点より大きい
③負ける可能性があるターンがなかった(減点されていない)
③の減点されていないかを確認したいので、ゲーム終了時までに得点を与えることをなくすために現時点で自分のポーションが5個以上の時だけ考えるようにしました。
尚、以下のことを考慮してないので厳密には勝ち確定ではないです。
①現時点で相手のポーションが4個以下で、素早く複数個のポーションを作ってゲームを終了させてくる
②左にある場合にポーションに付加されるボーナスの影響でpriceが変わる
③途中で引き分けになるパターン
最初は負ける可能性があるときに探索を打ち切っていて、探索が浅くなり勝ち試合を落としていることがあったので、「1ターン後に負ける可能性があるなら打ち切り、それ以外は減点」としました。
実際よりも厳しい条件を付けているので、勝ち確定の手を見つけるときは大体1、2ターン後に勝つ場合ばかりでした。勝ち確定も厳密ではないので、相手の行動も含めた2ターン全探索とかでよかったなと思いました。
評価はゲーム終了時の計算方法を使って、インベントリのtier1-3を1点とみなしたときの合計点+④のスコア+作ったポーションのprice+(ゲームを終わらせていた場合、7-ターン数)×4としました。
4ターン以内に勝つことを確信したおばあちゃん
感想
状態数が少ないことを利用してダイクストラを用いているので、融通が効かなくて厳しかったです。例えばスコアを取得するタイミングを増やせばそれだけでとても遅くなりそうです。ビームサーチは早い段階で実装候補に上がっていたので、面倒くさがらずに書いておけばよかったと思いました。とは言っても、今あるコードの改善をしっかり考えることができたから結果がでた面もあると思うので難しい……
食事や睡眠などをないがしろにしてコドゲをやっていたせいで、最後らへんは体力が残ってなく、頭も回らなくて最悪でした。寝ようかとも思ったのですが、「パラメータガチャを続けていればLEGEND入りの可能性がある！」という状況で寝るという選択肢は取れませんでした。次からは気をつけようと思います。
