問題

今年のお題はパズルゲームでした。（インタラクティブ問題）

入力として N * N のサイズのグリッドと 3 * 3 の固定サイズの手持ちパネルの情報が与えられ、1ターン毎以下の操作を行うことが出来ます。

手持ちのパネルを 1枚選択しフィールド上のフルーツと重ならないように配置する（パネルの回転は出来ない）
手持ちのパネルを 1枚選択し破棄する

また、行動後はパネルが新たに 1枚手持ちに追加されます。（追加されるパネルの内容はランダム）

配置後にフィールドをチェックして横か縦にフルーツが 1列並ぶと消えます。ラインを消した場合はスコアが与えられ、その得点は各ライン毎に 消したラインの数 * 消したラインに含まれるフルーツの最頻出値 ** 2 で計算されます。

例えば以下の画像ではスコアはこのように計算されます。

消したラインの数 : 1

ラインのフルーツの最頻出値 : 4

1 * 4 * 4 = 16点

また、次の画像では以下のようになります。

消したラインの数 : 2

縦のラインのフルーツの最頻出値 : 6

2 * 6 * 6 = 72点

横のラインのフルーツの最頻出値 : 6

2 * 6 * 6 = 72点

合計 144 点。

以下は実際に動作している様子です。

この操作を 1000ターン繰り返しなるべく多くのスコアを獲得することが目的となります。

可変なパラメータとしては以下の通りになります。

フルーツの種類 : C (1 - 5)
手持ちのパネルの枚数 : T (1 - 5)
グリッドサイズ : N (6 - 20)

方針

ビームサーチによる探索を行いました。ただ、探索の深さは手持ちのパネル枚数の T の値を上限にしていたので T が 1のケースでは実質貪欲法になっています。

操作としては以下の 2つです。

任意のパネルを 1枚選択し、任意の場所に配置する
任意のパネルを 1枚選択し、破棄する

多くのスコアを獲得するには「多くのラインを同時に消す + なるべく同種類のフルーツでラインを作る」ことが必要でしたので、評価関数として以下の要素を主に評価しました。

ライン毎の フルーツの最頻出値
ライン毎の フルーツの最頻出値 / ラインに配置されているフルーツの数 (ラインの何割を同じフルーツで占めているのかをチェック)
連続した空白地帯の数 (独立した空白地帯が多いとパネルが置きにくくなるため）
単発消しに対するペナルティ

ライン毎のフルーツの最頻出値

最頻出値は 2乗でスコアに影響しているのでなるべくこの値を大きくなるように評価を行いました。

ラインごとのフルーツの割合

同じ最頻出値でも N の値が 15 だとして 5 / 10 と 5 / 6 では後者のほうが同じフルーツが配置されている割合が高く、より得点が伸びる可能性があるので、割合を計算して評価に加えました。

連続した空白地帯の数

今回の問題では、なるべくパネルを破棄するような自体を起こしたくないため パネルを配置しやすい状態 というのを維持したいです。そのため連続した空白地帯の数を調べてその数が少ない状態の盤面を評価するようにしました。

空白地帯が連続しており、色々なパネルが置きやすい状態。

空白地帯がまばらでパネルが起きにくい状態になっているため良くない。

盤面全体を評価するこの処理はちょっと重かったので T = 1 のケースでしか利用していません。

代わりに、他のケースではライン毎の連続した空白地帯の数を評価しました。

下の画像のほうが他のパネルが置きやすいため良い状態と評価しています。

単発消しに対するペナルティ

なるべく同時消しを行ったほうがスコアが高くなるため単発消しに対してペナルティを与えました。ただ、盤面が埋まってくると単発消しを行って盤面整理を行う必要があるので空白率を調べてその割合が 10% を切ったらペナルティを与えないようにしています。

まとめ

シンプルに 24h でどこまで評価関数の精度を上げることが出来るのかの勝負でしたが上位勢のスコアに追いつくことが出来なかった。provisional のスコアの解析を見た感じ C = 1 のケースでは勝っていて、C の値が大きくなるにつれてスコア差をつけられていたので同一のフルーツを集めて消す処理があまり上手くいってなかったのかなと思われる。去年よりは戦えたがまだまだ実力が足りないと感じた。今年は寝ようと思っていたが、なんだかんだ順位が気になって結局ずっと起きていた。（それでも途中イスの上で 1-2h 寝た）

総括

今年の TCO はオンサイト（ボストン）で開催予定だったが、オンサイト参加者が少ないのでオンライン開催となりました。パスポートの取得とESTAの申請は終わっていたけど無駄になってしまった。それはそれとして、去年の初参加から絶対に改善しようと思っていたのが以下の 2つ

作業マシンの変更
与えられた EC2 環境を利用する

作業マシンの変更

去年は外付けの web カメラが無かったので、メインとは別のノートPC のほうで作業を行っていたのだが「全画面共有」にかなりマシンパワーを取られてローカルでテストを回すのが遅くなってしまったので、今年は外付けの web カメラを購入してメインのほうのマシンで作業できるようにした。

EC2 環境を利用する

去年は競技が終わったあとに EC2 環境に関するメールが届いていたことに気づき「これを利用できなかったのはかなりもったいない」と思ったので今年は利用することにした。今年は c5.9xlarge を与えられていたので手元のマシンよりかなりスペックが高くて便利だった。

スペックが高いとローカルでテストを回すスピードが格段に速くなる。元々テスト自体はマルチプロセスで並列処理出来るようにしているので並列数を 3 -> 30 にパラメータ変更するだけでテストのスピードが 10倍になった。

あとは事前に安いインスタンを使って EC2 上での環境構築の手順を確認して本番のときに手間取らないようにした。

試合の流れ

「問題を読む」-> 「ビームサーチ系の問題だな」→「それっぽい評価関数を書く」 (ここまでで大体 6h ぐらい）

「暫定 2位！ただ、全員提出していないので（仮）だな」

評価関数をどんどん変更する（ビジュアライザを見て色々調査しながら 6h ぐらい）

「暫定 1位！ｷﾀｰ」

この後 6h ぐらい何も思いつかず順位が 8位ぐらいまで落ちる。

「タイルを破棄する評価が割と高かったので、ギリギリまでタイルを破棄しないように評価値を調整したらスコアがかなり上がった」

けどまだ上位には全然届かない。そのまま試合終了。

システムテストで最終的に 2人に抜かれて 5位で今年の TCO は終了しました。 provisional テストの解析結果から 4位には確実に落ちることはわかっていたけど、5位まで落ちてしまった。

感想

去年 8位で今年 5位だったので当初の目標「去年より高い順位を取る」は達成出来てよかった。来年もし参加出来たら 4位以上を狙いたい。2度海外オンサイトの機会があってコロナで全部フイになってしまっているのは少しもったいない感じがする (HTTF もそうだけど）。（飛行機代とか調べたら 30万とかしたので海外行けるだけでもお得感ある）