参加しながら考えたこと試したことの源泉かけ流し。
問題文はこちら
1 日目
問題文を読む。
へ～今回はカジノが題材かぁ。
学生時代オンライン学習の研究やってた身としてはスロット → 多腕バンディット問題を連想するよね～……って、エッこれまんま多腕バンディットやん！！（ここで取り乱す）
僕の卒論は「部分的なフィードバックに基づくオンライン離散最適化」って題目だったんですが、まさにこういう問題だよねっていう。
えー勝たなきゃ恥やろコレ…。
多腕バンディット問題とその考え方については下のスライドにすごく分かりやすくまとまっているのでそちらを読めば良いと思います。
ひとまずスタートダッシュということで、C++ でのテスタ作成と以下のアルゴリズムを実装して提出した。
- 総時間の 1/3 で notePlay をして、各スロットの報酬期待値の推定に使う。
- 得られた wheel 情報はスロットごとに連結させていき、その連結したものが真の wheel だと仮定して報酬期待値を計算。
- 報酬期待値の計算方法は公式のコードと同手法。
- 回すスロットは順繰りに選ぶ。
- 残りの時間で quickPlay をして、期待値最大のスロットを回し続ける。
notePlay については 3 * 3 = 27 通りの出目が調べられるので、たとえコスト 10 だろうが期待値推定目的ならコスパ◎。たぶん。
逆に時間効率なら quickPlay がコスパ◎なので、ある程度スロットの期待値が推定できれば quickPlay に切り替える必要がある。
ということで、上記の作戦に。
上記のを初日の深夜に提出して 3 位 / 30 人程度 だったはず。
2 日目
上記のアルゴリズムだと報酬期待値の如何にかかわらず同じ回数各スロットを回して推定してしまうので、ひとまず Upper Confidence Bound (UCB) を用いたアルゴリズムでやってみようと思う。
このアルゴリズムでは以下の手法で回すスロットを決定する。
- $gain_i +$
の値が最大となるスロット $i$ を回す。
- $gain_i$ ：$i$ 番目のスロットの報酬期待値の推定値
- $t_i$ ：$i$ 番目のスロットを回した回数
- $t$ ：スロットを回した総回数
- $\alpha$ ：適当な定数（色々試して最適なものを探す）
- 2 項目は UCB と呼ばれる項。回していないスロットほどこの値が大きくなるので、基本的に報酬期待値の大きなスロットを選びつつあまり正確な推定ができていないスロットもいい感じに選んでくれる。
上記の手法を使って notePlay を行い、その後は同様に期待値最大のスロットで quickPlay をする。
動いてる様子はこんな感じ。
exp が推定期待値、ucb が UCB 値で、これらを足し合わせた sum が最大のスロットを回していく。
これを 2 日目深夜に提出して 810k くらい。
ちなみに 1000 ケース回してときのスコア平均が 7631 。
3 日目
期待値推定フェーズの長さを調節したり細かい修正を続けてスコア平均
7900 くらいまでは上げられるも、1 位の kurenai3110 さんとの間の 5 万点の距離が縮まらず、多分別の何かが必要なんだろうなぁ…と考え始める。
ということで、ここまで放ったらかしにしておいた期待値推定ロジックの修正にかかる。
今は得られたスロット文字列を単純に連結させているだけなのだが、それだと 'A' を含む部分が多めに出ちゃったときとか等に推定値が大きく外れてしまう。
そこで、wheel ごとに得られた 3 文字を記憶させておき、既に出現済みの 3 文字については連結をさせない、ということをやってみた。
これに合わせて推定フェーズの終了タイミングや UCB の値の調整を行い、スコア平均 8003 本番スコア 850k 2 位まで持っていけた。
4 日目
アイデアが付きたのでこの参加記を書き始める。
細かい修正をして手元ではスコア平均 20 くらい上がったんだけど、本番では 5000～7000 点くらい下がった。
pretest のテストケースと相性が悪い or 本番のスコア方式では前のほうが優れている…？
とりあえず見栄を張りたいので前日の 850k の方を出しておく。
5 日目
推定フェーズ切り上げるタイミングとか UCB まわりの調整はもう限界な感じがあるので、期待値推定ロジックの再考を始める。
得られた文字列をもとに焼き鈍して wheel の復元するみたいなのやったけどがっつり スコア下がったので諦めた。
6, 7 日目
わからない。
8 日目
quickPlay フェーズに突入する前、コイン数と報酬期待値の推定値に応じて exit する処理を真心 if 文してたんだけど、冷静に考えたらプレイアウトするべきやんつって書き換えたら本番 300 点くらい伸びた。
もうちょっと伸びてくれても良いと思ってたんだけど…真心力の為せる業か。
最後に
暫定順位だと 7 位なのでこのままだと自身の最高順位記録を更新できそうで嬉しい。
でもちょっと変更加えたらがっつりスコア下がったりしてたので不安だな～～とは思ってます。
