トヨタ自動車 プログラミングコンテスト2022（AHC015）に参加して、 142,839,445点の 17位/778人 でした。
考察内容や解法について書いていきます。
考察と方針
パズルゲームの2048をベースにした問題でした(のはず)。 操作方法とブロック*1の出現の挙動は一緒だが、ブロックの融合が無しでゲーム目標も違うといった感じでした。
昔に会社でのお遊びで2048のソルバーを書いたことがあって、その時の所感が活かせないかをひとまず考えました。 本コンテストとルールが共通している箇所で、関係がありそうな要素として具体的には以下がありました。
- ルールベースで十分クリアできる
- 四隅のどこかを決めて、そこでブロックを育てるのが良い*2
- ランダム要素のせいで(?)探索の工夫はあまり上手く決まらない
- 一操作について考えるとき、移動前よりも移動後に出現するブロックの方が、それに対する影響が大きい*3
良い感じのルールベースがこの問題でも作れるかは懸念だったのですが、Webビジュアライザのマニュアルモードで遊んでみたところ、 2 の応用で「端に特定のキャンディを集める」はある程度できそうに感じました。
3 に書いたように、2048では探索はいまいちどう工夫したら良いのか分からなかったので、 本問題でもここは割り切って工夫せず、間に合う範囲で単に全探索をする、と決めました。
以上を踏まえて、「基本的にルールベースで進め、残ターン数が減って全探索できるようになったら全探索に移行する。」という方針を取りました。
解法
94ターン目までルールベースで進めて、最後6ターンだけ全探索。
ルールベース部分
一番個数が多いキャンディをA、他２つをB,Cとする。 Aが右側全般、Bが左上、Cが左下に寄るように方向づけるイメージで操作する。ただし、Aを右に寄せるのを最優先する。
具体的には、Aが次に出現するときは 'L' をし、出現ブロックが既存のブロックの右側に配置されるように誘導する。 Aの出現が切れたタイミングで 'R' をし、他のブロックが既存のブロックの右側に現れないようにする。
また、'L''R' の内、最後に使われたものが 'R' である場合、Aの配置への悪影響が少ないため上下操作を許して、B,Cの配置誘導を目指す。 具体的には、次にBが来るときは 'B' 、C が来るときは 'F' をする。
全探索部分
ゲーム終了まで、MiniMax的なゲーム木探索をする。
遷移は、傾け操作4種と、キャンディの出現全パターン が交互に行われる。 終了盤面でスコアを算出し、傾け操作の遷移を辿るときは子ノードの最大値を、キャンディの出現の遷移を辿るときは子ノードの平均値を、親ノードのスコアとした。
テストケース0000のビジュアライズ結果
イチゴが一番多いケースで、イチゴを右に、カボチャを左上に、メロンを左下に集めています。
提出コードはこちらです。 Submission #36094840 - TOYOTA MOTOR CORPORATION Programming Contest 2022（AtCoder Heuristic Contest 015）
感想
過去最高順位が取れて、とても満足でした。 2048パズルの知見があったのがまずまず有利に働いたように感じます。
もう少しで黄コーダーにいけそうなので、もう一押し頑張っていこうと思います。
*1:キャンディに相当
*2:e. g. 右上を選んだなら、L, D の操作は極力しない。
*3:chokudaiさんのツイートに良い感じの説明がありました https://twitter.com/chokudai/status/1586668572457082880
