CODINGAME FALL CHALLENGE 2020
CodinGameのコンテストに参加しました。
2020/11/13~11/23の期間に開かれたCodinGame Fall Challenge 2020に参加しました。
コンテストの内容については例によってツカモさんのブログをどうぞ。
結果は世界626位/7011で、日本103位/320でシルバーでした。
今回はいつにもまして日本人参加者が多く、Twitterなどでも解法等の情報交換が活発にされていて、お祭りみたいな感じで非常に楽しかったです。
できればゴールドにも昇格したかったんですが、自分のプロフィールを見直してみたらゴールドに行けたコンテストはCrystal RushとCoders Strike Backだけだったのでまあまあそんなものかなという気もしています。ただ、開催期間の前半にハル研のプロコンが重なっていたのは少し痛かったです。本腰を入れてこちらに参加できたのが終了の三日前くらいだったので。
やったこと
基本的にはビームサーチをしました。ただ今回、構造体を使ってガチガチに書くぞと思ってやったら、処理がすごく重い(ノードに盤面の情報が全部乗っている)ものができてしまって、ビーム幅10で5,6ターンしか読めないような感じになってしまいました。日本人TOPだったichyoさんなんかはビーム幅1000の20ターン読みとかだったそうなので、全然ダメだとわかります(もちろん、ichyoさんのこれはTOP勢からしてもすごい読みらしいけど)。
時間について、盤面による差が激し過ぎたので、時間を計測しながら探索深度を増やして行って、途中で時間切れになったらそこまでの深度で打ち切るというのをしました。時間ギリギリまで回すビームサーチとしてはchokudaiサーチの方が一般的なのかもしれませんが、そこまでの実装はできませんでした。
盤面の評価関数は、自分のインベントリと自分の呪文、それから作ったポーションについてそれぞれ評価した和にしていました。各要素の評価は次のような感じ。
1.自分のインベントリ
各素材に1,2,3,4点を割り振ってその点数の合計。
素材が多過ぎても少な過ぎても嬉しくないので、それぞれの素材についてabs(5-数)。
種類が複数あると嬉しいので、それぞれの素材数の積をいい感じにしたもの。
これらの線形の結合。
2.自分の呪文
呪文自体の点数増加を計算。繰り返し使えるものは可能回数*0.7くらいで補正(書いていて気付きましたが、呪文の内容は固定なのでこれは前計算しておけばよかったですね……)。
持っている呪文の平均的なスコアを算出。
想定終了ターン数を40ターンくらいにしておいて、現在ターンから終了までのおおよそのターン数の目安を計算。それを上の呪文の平均点数にかけることで今持っている呪文で大体どれくらいの点数が得られるのかを算出。
3.作ったポーション
上記二つだけだと全然ポーションを作ってくれなかったので、ポーションを作るとスコアの増加に加えて5点分の価値を持たせた。
あとは、ポーションを5つ集めてリーチになったときは評価関数を変更して、勝利できるか否かだけを見ていました。この最後のところ以外は相手のことは少しも考慮しませんでした。
やりたかったこと
Twitterでも度々話題に上がっていましたけれど、インベントリのありうる状態数が14C4=1001(入試でよくある仕切りの位置を動かす組み合わせ)だったり、呪文の種類が50個以下、ポーションの種類が40個以下だったりしたので、手元の環境で全探索をバリバリ回して、その結果を埋め込むとか考えていました。
ときどきよくわからないところでTimeOutして負けるみたいなことがあって辛かったので、その辺をどうにか解消したかったです。自分のプログラムのバグなのか、でも、他の人も変なところでTimeOutすると言っている人がいるし……で正直よくわかりません。コドゲの時間周り難しい。
やるべきだったこと
ビームサーチという大まかな方針は決して間違ってはいなかったと思いますが(上位勢もわりとビーム撃っていたらしいので)、やっぱりあまりにも探索範囲が狭過ぎた。探索ノードについて必要最低限の情報を持たせながら探索するということが大切だなと思いました。この辺はビームサーチに慣れていなかったのもあるのかなーなんて思います。
よかったこと
多分初めてビームを撃った気がします。今までのマラソンマッチは大体焼きなましを使っていた気がするので。
今回ビームサーチを初めて書くにあたって、ツカモさんの以下のブログを大いに参考にさせてもらいました。先人の知恵は本当にありがたい。
次に向けて
今回の結果を受けて、ビームサーチやりたいなーと思っていたら、さんだーさんがこんなことを言ってらっしゃいました。
今回のコドゲで「やべぇぇ、ビームサーチやchokudaiサーチ勉強しなきゃ！」って思ったそこのあなた！ビーム系アルゴリズムのうってつけのゲーム、HyperSonicをやろう！題材もボンバーマンで、日本人になじみが深いぞ！https://t.co/34FUnr1B3u
— thunder≦4 (@thun_c) 2020年11月23日
やります。
やっています。
