TCO21 Finals Marathon Matchに参加しました。
これはTopcoderMMの2021年決勝で、リモートで監視員に見守られながらの24時間コンテストでした。*1
問題はCoinCollector。ダイスで移動して、グリッド上のコインを集める問題です。
参加者12人中、暫定テスト10位でした。
問題
本文
N*Nのグリッドがあるよ。これは上下と左右でループするトーラスだよ。
グリッドの各セルはコイン、棘、空きのいずれかだよ。
コインを取ると得点が増えるけど、棘を踏むと得点が半減するよ。*2
コインは取ると消えるけど、棘は消えずに残るよ。
方向と手持ちのサイコロを選んで、出た目の数だけ移動するよ。
サイコロは12種類あって、使ったサイコロは無くなってランダムに補充されるよ。(ケースによって2～6個持てるよ)
終了はN*Nターン、もしくは任意にいつでも。得点をたくさん取ってね。
サイコロの種類
- 1～6のいずれかが出る6面ダイス1種
- 0,1,2,3,4,5,6の1つが出る1面ダイス(?)7種
- 奇数、偶数、123、456が出る3面ダイス(?)4種
出る目の種類数が、そのままランダムに補充される確率の比となる。
0のダイスを無視すると、特定の目を含んだダイスを引く確率が約50%となる。
制約
N グリッドの1辺のサイズ 8～30
D 持てるダイスの数 2～6
ratioC コインを生成する確率 0.10～0.60
ratioS 棘を生成する確率 0.15～0.40
実行時間制限 10秒
時系列進捗
これは僅かなメモとgit履歴から復元しているので、時間の正確度は低かったり、没方針を書いていないがちです。
04:00
始まったらしい。まだ寝てる。
07:00
起きた。PC周りの環境最終調整。まだ眠い。
07:30
会場入り。
参加するためのUIが見つからないが、TCOの人に声掛けしてもらって開始。
ゲームAIっぽいので、貪欲法が書けないレベルの破滅はなさそうで一安心。
とりあえず考察だけ。
棘を踏むと得点が半減→これはMM122マインスイーパ。一度踏むとリスク許容ボーダーが変わって、踏み続けて破滅するやつだ…。
棘を回避して移動→これはボードゲームのマラケシュっぽい。複数手読みが大事そう。
あとは、この手の問題ではありがちな、早くコインを取るボーナスが存在しない。安全にじっくり行けということか。
順調でも終盤でミスると最悪0点付近まで落ちる問題なので、綺麗に終局させる処理が必要。動かすロジックと終局の判断は相互に絡むところもあるので、堅実にやるなら両方を少しずつ強化していくしかないか。
サンプルコードを投げて朝食へ。
カメラは切っていいけど画面共有はそのままにしてね、とのことだった。
8:15～9:15
朝食。
9:15
朝食前に投げていたサンプルコードがCE。
解析すると、実行環境に"csc"というコマンドが無いらしい。
これは環境側の問題臭い。フォーラムで報告して、修正を待ちつつ作業開始。
方針はざっくり4つ。MCTS、ビームサーチ、原始モンテカルロ、ルールベース。
・MCTS
MCTSに落とせれば強いんだろうけど、確定ゲームでないことと、実スコア以外を評価にどう盛り込むかがネック。遠くのコインは2,3手では取れないだろうし。
・ビームサーチ
上に同じく。ただMCTSよりは作りやすいかな。
・原始モンテカルロ
頭を使わなくていいのが強み。ただシミュレーション結果が偏って悪手を打つと、1ミスで悲惨なことになるからなぁ…。平均パフォーマンスが高くても、安定していないのは不安が残る。
・ルールベース
1行ずつ順番に取っていけば1次元の問題に落とせる。天才か？
→ratioS=0.40の地雷原を見て絶望。4マス連続の棘とか越せるわけないじゃん。
没ったルールベースはともかく、他3つは全てダイス目をランダムとしたシミュレータが必要そうか。*3
一番簡単そうな原始モンテカルロから始めてみる。1手読み、シミュレーションは各動作100回くらいで、評価関数は手持ちのダイスでコインや棘に到達できる確率(その結果の得点)のbestと、直線上にコインや棘があるかをメインにする。あとは手持ちダイスの多様性と、択が少ないダイスを持っている方が嬉しそう。*4
0のダイスは全く使い道が分からなくて、ここはルールベースで棘の上にいないなら即使うようにする。棘の上で使うと更にスコア半減するのか調べたかったけど、結局最後まで調べなかった。
13:05
原始モンテカルロを書き終えて動作確認。バグで横にしか動かない…。
＞＞反復横跳び＜＜
13:20
ちょうどC#の提出バグを直してもらえたので、提出。CE。
MMのC#ばーじょんでは たぷるは つかえないぞ！（本日1回目）
13:35
サンプル以外で初AC。26.93点。
得点はすこぶる悪いが、終局処理を丁寧にやればある程度上がるのは見えているので気にしない。
今は1手読み*5だけど、制限時間的に軽い2手読みが限度かな。モンテカルロ法でやってたけど、確率で期待値を計算すれば別にランダムにダイス値を決めることはしなくていいですね…。ということで貪欲法に変更。多分最終的にはビームサーチかな。
基本的には、ここからずっと最下位。途中で11位になったけど、12位の人は潜伏してそうだった。
14:10～15:30
お昼休憩。徹夜コースなので、食事は少し遅めにずらしていく。
16:00
何も分からん。ビームサーチを書きかけるが、下手な貪欲を複数手読みにしたところで挙動が分かりにくくなって効率が落ちるだけ。ぐっとこらえて、貪欲を鍛える。
17:00
終局処理に着手。
「これくらい点を取った後に無茶すると破滅しがちだからやめておけ」というお気持ち表明を入れる。*6testerから取った得点をExcelで散布図にして、にらめっこして人の温かみがあるボーダーを設定。
18:40
自明な改善として、高速化やバグの修正。
正常動作するけど結果が悪くなる系のバグがいくつもあってひどい。
19:45
終局処理を追加。「1回棘踏んだらもう回復できないから期待値下がるぞ」という自明なパターンに対応。落とさなくても良い点を落とさなくなっただけで、普段の動きが良くなったわけではない。本質は何処…。
20:30
どう頑張っても手持ちが6面ダイスばかりになる。
なんとなく原因は見えてきて、貴重なダイスを使ってでもコインと軸合わせしたり、安全な場所に逃げ込みたいと思っているようだ。
そこで6面ダイスを使うことに特大ボーナスを付けてみる。
これで大きく動きが改善されたうえ、棘もそこまで踏まないようで得点大幅アップ。視界が開ける。（実装方法は美しくないんだけど…）
提出60.88点。そろそろ貪欲の改良は終わりかな。
21:00
打ち切り基準を再度手調整。
俺、この調整が終わったらビームサーチ撃つんだ…。
23:00～24:00
夕食。28:00まであるので、遅めに調整。
戻ってくると、TCO監視員とのやり取りに使うプラットフォームにエラーが出て、やり取りが出来なくなる。*7
どうせ皆続行してるんだろうから、カメラと画面共有はそのまま付けて作業再開。
向こうからは見えてはいたらしい。
27:00
ビームサーチライブラリを貼って2手読みに。*8
1手目の結果がダイス値や受け取るダイス毎に分かれていて、それぞれに対して2手目を読むので書き方が難しい。
提出。CE。
MMのC#ばーじょんでは たぷるは つかえないぞ！（本日2回目）*9
27:10
2手読みしようとすると恐ろしく重くて、すぐに時間が危険ラインになり結局貪欲モードに戻ってしまう。*10ビーム幅を削ってみるものの、根本的な計算量削減が必要そう。
N>=12では2手目は1面ダイスを入手できないことにして計算量を半減させると、絶対スコアの伸びは地味だが相対スコアが大きく上がった。最下位脱出で、10位くらい。
27:30
評価関数で手持ちダイス射程を覗いている部分が重いので、使いまわせるようにしたいところ。手持ちダイスがちょっと違うだけの状態を何パターンも見ているのだし…。
しかし、ここで違法建築のツケが来てしまい、上手に該当箇所を切り出せない。切り出せるんだけど挙動が変わってしまい、スコアが下がる。
ここの速度が数倍になれば、相対スコアではがっつりスコア上がりそうなんだけどなぁというところで時間切れ。
やり残しメモ
ビジュアライザでは、一度でも到達したセルは色が変わる。
色々な場所を巡回してみろというヒントか？
チャンスは増えるけど、ピンチも増えそう。
感想
ダイス部分の元ネタはDicast: Rules of Chaosらしいです。
不確定ゲームを分岐させる形でシミュレートしたのは初めてで、ぶっつけ本番でしたが最低限なんとかなりました。
多分私は得意なタイプの問題で、本質を大きく見誤っていたわけではないと思うけど、実装速度で負けたかなぁという感じです。評価関数も違法建築の連続で酷いことになっていました。短期（？）マラソンは綺麗な設計と実験/本実装速度とのバランスが難しい…。
そもそも4時からやれば良かったのでは？というのはありますが、その分を同じ覚醒度で長く起きていられたかというと怪しいところ。*11
完敗でしたが、俺だけ出られる隠しマラソン感があり面白かったです。*12
でも監視まで付いちゃうと机に縛り付けられている感が強くて思考力も落ちちゃうし、気軽にやってるいつものマラソンの方が好きかな。
*1:問題以外の部分については、余力があれば別途書いてみたいと思います。
*2:その時点で持っている得点のみ半減。
*3:※必要ではない。
*4:評価関数はこれが最終方針で、方向性は最後まで変わらずでした。
*5:評価関数が1手読みに近いので、実質2手読み。
*6:これは改修するたびに上がっていく値だが、低い値を設定する分には困らない。
*7:実はリロードすれば直ったっぽい。
*8:評価関数が1手読みの性質を持っているので実質3手読み。
*9:MM125のコードで思いっきりタプル書いてるんだけど、これは大丈夫だったのか…？（手元にあるコードを提出してたのかは未確認）
*10:終盤で棘を踏むことを一番避けたいので、終盤に2手読み出来なければ意味が薄い。
*11:そもそも24時間起きている前提のコンテストってなんかおかしくないですか。開始3時間前に開会式があるので3時間しか寝れなくなるし。
*12:だけではない。
