simanのブログ

ゆるふわプログラマー。競技プログラミングやってます。Ruby好き

TCO22 Final 参加記

問題

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

入力として 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 / 105 / 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万とかしたので海外行けるだけでもお得感ある)

MM141 TrafficController 参加記

問題

www.topcoder.com

方針

  • 毎ターンごとに5ターン先までの信号機の方向を焼きなましで求める

焼きなましで信号機の方向を決める

  • 遷移としては任意のターン、任意の信号機をランダムに 1箇所選択して変える
  • 実際にシミュレーションを行い評価を行う
    • 前進 +1pt
    • 停止 -1pt
    • スポーン地点での停止 -2pt
    • グリッドロックが発生しうる箇所での停止 -5pt

グリッドロックの回避

グリッドロックは下の画像のように渋滞が連続すると全く前進できなくなる状態のことを指す。

これを回避するために閉路を検出して、閉路の角に対して停止した場合のペナルティを大きくした。(赤色の部分で停止するとペナルティが大)

ただこれだけだと不十分なので他にもっと良い回避方法があったかもしれない。(1方向を完全に止めるとかもやってみたけど回避率が上がっても全体のスコアが下がってしまったのでバランスが難しい)

感想

最後までグリッドロックを効率的に回避する方法がわからなかった。車両にそれぞれポイントが付与されていたが結局どれだけ車両を捌けるかが大事なのであまりスコアに影響なかったように思える(終盤で緊急車両を優先するみたいなことはあるとは思うけど)

最近はわからない問題が多くて何もわからない。

第9回 Asprova プログラミングコンテスト 参加記

問題

atcoder.jp

方針

各設備の稼働パターンを以下の流れで調整しました。

  • 二分探索で基本となる稼働パターンを決める
  • 調整案をいくつか作成しその中からランダムで選択した案を採用する
  • 終盤に稼働が必要なさそうな設備の稼働を止める

二分探索による稼働パターンの探索

稼働パターンを下限値 4 上限値 9で二分探索を行います。この探索で必要な試行回数は最低 2回、最高でも 3回となります。

変更する時はすべての週に対して操作を行います。

下限値を 4 にしているのは、今回は山登り的にスケジュールを改善しているので序盤からキツめに調整してしまうと後の調整の自由度がなくなってしまうのである程度余裕をもたせるようにしているためです。

調整案の作成

基本となる稼働パターンを決めた後は調整案を作成していきます。調整案はいくつかのパターンがありそれに基づいて作成されます。

調整案1

今回の問題では各注文に「納期」が存在するため、合計の稼働時間が同じでも「日程の前半に多く稼働させる」 or 「日程の後半に多く稼働させる」では前者の変更のほうが依頼の達成率が高くなります。

稼働時間が単調減少するパターン

稼働時間が単調増加するパターン

そのため、調整案 1 では稼働スケジュールの 1週目のパターンを「基本パターン」として「2 ~ X - 1」の中からランダムな値を選択し「選択した値 ~ X週」までの稼働パターンを基本パターンからいくつか下げた値に変更します。(この下げ幅もランダムに選択されます)

この変更は「平日のみ適用」「休日のみ適用」「両方に適用」の 3つからランダムに選択され実行されます。

調整案2

調整案 1 が採用され続けると 2週目以降の稼働パターンが完全に下がりきった状態になるので、それを解消するために 1週目の稼働パターンを下げます。

スケジュール変更の流れ

各設備では「二分探索による基本稼働パターンの探索」→「細かい調整」を行っていきます。まず変更を行う設備をランダムに選択し、基本稼働パターンの探索が完了していない場合はその続きを、完了している場合は調整案を作成します。この処理を何回か行いその中で一番コストが削減されるものを採用し、その後は変更後のスケジュールを計画プログラムに渡して評価を受け取ります。

変更が成功したか失敗したかによってその後の処理が変わります。

成功時

成功したスケジュールを採用し、変更を行った設備の「最低設備コスト」の値を 0 にリセットします。ここでの「最低設備コスト」とは「その設備における最低限必要なコスト」を指し、この値を下回る変更を行わないようにします。(このコストを下回ると必ず依頼に失敗するというしきい値

失敗時

変更を行った設備のスケジュールを元に戻し、「最低設備コスト」の値を更新します。

最低設備のコストの計算は (a * updated_cost + b * cur_cost) / (a + b) で行っており、a: 4, b: 1 を基本として失敗した注文の数が多い場合は a: 2, b: 1 に設定して計算を行いました。(例 - 現在のコストが 100、更新後のコストが 0の場合 (4 * 0 + 1 * 100) / 5 = 20 となる

序盤はまとめてスケジュールを変更する

序盤はほとんどのクエリが成功するので複数まとめてスケジュールの変更を行いました。まとめる件数は最初 M件からはじめて成功失敗に関わらず半分にしていきます。(例: M が 8 の場合は 1ターン目: 8件まとめて変更、 2ターン目: 4件まとめて変更, 3ターン目: 2件まとめて変更 といった感じです)

終盤のスケジュール作成

終盤では今まで送ったスケジュールの中で一番スコアが良かったものをベースに稼働が必要なさそうな部分を「稼働させない」パターンに変更する作業を行いました。稼働が必要かどうかについてはクエリを送ったときの返り値の 負荷率 を調べてその値が 0 の部分を「稼働させない」に変更します。

休日のみ稼働を停止させる

負荷率が 0 でない場合でも「休日」は停止できる可能性が残っています。というのも 1週間の構成は「day1 ~ day5 が平日で day6, day7 が休日」となっているので、画像のように day1 ~ day5 の間だけ稼働していて day6, day7 は何もしていないという可能性があるからです。

「負荷率 Y を下回った場合は休日の稼働を停止させる」という処理を行いますが、この Y の値については二分探索で求めました。今回は ok: 0, ng: 80 を初期値として設定しています。(例: 1回目は 40% が基準となる。2回目の値は失敗した場合は 20%、成功した場合は 60%) もし、最後のターンまで 1回も成功しなかった場合は Y = 0 にして処理を行います。

この処理は E = 50 のケースでは終盤の 2ターン、それ以外では終盤の 4ターンで行っています。

感想

問題文が複雑そうだから理解するのに時間かかるかなと思ったけど、やってみたら思ったよりやることが少なかった印象。テストケース生成のコードと調整プログラムのコードを調べようかと思ったけど 1週間コンテストだし気合が足りなかったので結局ふわふわした感じの理解で問題を解いていた。時間があれば TPE とか調べて参考にしていたかもしれない。

雑感

ジャッジプログラムの日本語が文字化けしていたので英語のコメントを読んでいた。

クエリの結果から得られる情報がほぼないのでクエリを工夫して注文の内訳を調べるとかそういう感じの問題ではなかった。(ブラックボックスなものをいい感じにパラメータ調整する問題なのでそれはそう)

工程自体は複数に分けられていたけど注文が特定の設備に依存している感じだったので工程がM個あるのとあまり変わらない感じがした。(工程 a を行う設備 b が今使えないから代わりに工程 a を行う設備 c を使おうみたいな処理があると思っていた - ちゃんと把握しているわけではないので違う可能性もある)

最終日付近でジャッジプログラムに最適化オプションつけるのを忘れていたことに気づいて直したら 4倍ぐらい速くなって感動した。C++ 使っていたから気づけたけどそうでない人はハマってそう。

インタラクティブ問題ではクエリの結果に「今このぐらい時間を使用していますよ」というのを含めたほうが良いと思っている。

後いろいろ細かい調整は入っているけどスコアにクリティカルに影響あったのは書いたつもり。

Marathon Match 137 StoneSeries 参加記

問題

www.topcoder.com

方針

2種類のビームサーチによる探索

  • 通常のビームサーチ
  • 最長パスを見つけるためのビームサーチ

ビーム幅がある程度確保出来る場合は通常のビームサーチをそうでない場合は最長パスを見つけるためのビームサーチを使用しました。

最長パスの探索

今回の問題ではなるべく大きな値の石を置くことで獲得出来るスコアが増えるので、大きな値の石を置くために最長パスを探索しました。

パスの伸ばし方

パスを伸ばすのは 1の石を使うことで可能となります。

任意の石の周辺の空きマスに対して +1 した石を置きます。

このままでは「2以上の石を設置する場合は周辺に 2個以上の石が必要」という条件に反するので、さらに周辺のマスを探索して 1が置けるマスを探して設置します。

条件に反していない場合はそのまま +1 した石を置き続けることが出来ます。

このように 1の石の周辺は +1 した石が置きやすくパスを伸ばすのに非常に役に立つので、この動作を続けることで長いパスを作成することが可能になります。

ビームサーチによるパスの探索

パスの伸ばし方はわかりましたが適当に探索してもいい感じのパスを見つけてはくれないので 2つほど大きな指標を与えてなるべく大きなパスを見つけてくれるようにしました。

  • 石を置く際にはなるべく斜め置きを避けるようにする
  • なるべく外側からマスを埋めるようにする

探索については以下の通りです

  • 画面端の任意の位置を選択してそこから開始
  • 周辺 8マスの空きマスを探索し「現在の値 + 1」の石を置く
    • 周辺に 1の石がない場合は 1の石を置ける場所を探して置く

斜め置きを避ける

石の影響範囲の関係上、斜めに移動するよりは縦 or 横に移動するほうが 1の石をより効率的に利用出来るので斜め移動に対してペナルティを与えています。

斜め移動と横移動を比べると横移動のほうが効率よく 1の石を利用できている。

外側のマスを埋めるようにする

長いパスを作ってもらうためになるべく端を詰めながら移動して欲しかったので、グリッドの中央からどれだけ離れているのかを各セルに対してスコア化してその合計値を評価しました。

こうすることでなるべく端のマスを通りながら移動する経路を評価することが出来たと思います。

この探索で見つける経路は以下のようなイメージになります

パスの反転

この探索で見つけたパスは基本的に「外側 -> 内側」へと向かうのですが、この状態だと値の大きな石が中央付近に来ることになります。値の大きい石の周辺は周辺の合計値が大きくなってしまうので利用が難しく空きマスを多く無駄にしてしまう可能性があります。そのため、なるべくブロックの多いマスに追いやって影響を弱くしたいです。

幸い、見つけたパスは始点と終点をちょっと変更すれば逆向きに出来ます。逆向きにすることで「内側 -> 外側」に向かう経路となり大きい値の石を画面端に追いやることが可能となり影響力を弱めることが出来ます。

逆向きにした経路

最初から「内側 -> 外側」に向かう経路を探索すればよいのではと思うのですが、自分の評価関数だと「内側 -> 外側」の経路を作ろうとするとうまく画面端にピッタリくっつくような経路が出来なかったのでこのような反転処理を入れています。

残った空きマスを探索して石を置く

経路を作り終わった後は残りのマスをビームサーチで探索して得点が大きくなるように石を置きます。

時間制限まで処理を繰り返す

ここまでの処理が 1セットで、後は制限時間の間「経路の初期位置」「斜め移動のペナルティの値」「画面端ボーナスの値」をランダムに変えながら繰り返して一番高いスコアが得られたものを採用します。

通常のビームサーチ

「グリッドのサイズが小さい」 or 「ブロックの比率が高くて最長経路の探索が困難」な場合は普通のビームサーチで探索を行いました。

こちらに関しては特筆することも無く。評価としては主に以下の通り

  • 盤面の石の値の合計値
  • 画面端に値の大きい石が存在しているかどうか

後は zobrist hash による重複排除を行っています。

感想

問題自体はシンプルだったが、シンプルが故に評価が難しかったです。小さいサイズでのビームサーチの結果を見るに最長経路を作るよりかはいかにして空きマスを少なくするのかが重要っぽい感じではあるのだが、いい感じの評価関数を見つけれられずに終わった。最長経路を作らずにビームサーチをしたほうが得点は高くなるのでなるべくビームサーチに置き換えたかったがどうしてもグリッドサイズが大きくなるとビーム幅が十分に確保できなくなってしまうので諦めた。

そのビームサーチも評価関数があまり良くなさそうなので改善する余地はいくらでもありそう。「評価関数を良くする」->「ビーム幅が少なくても高スコアが取れる」->「ビームサーチ出来るグリッドのサイズが増える」->「得点がUP」という感じになるはずなので後半は評価関数の改善に主に力を入れてたけどダメだった。

Seed 1: 263.0
Seed 2: 289489.0
Seed 3: 154934.0
Seed 4: 174324.0
Seed 5: 154501.0
Seed 6: 10181.0
Seed 7: 1289.0
Seed 8: 5684.0
Seed 9: 11545.0
Seed 10: 97828.0

TCO22 Final に進出しました

TCO22 Final に進出

公式の順位表が更新されて Stage 4 のポイント集計に自分がカウントされていなかったので、去年に引き続き今年も TCO Final に出れるっぽいです(やったー)、去年は 4 -> 2 -> 4 の 200pt での突破でしたが、今年は 3 -> 7 -> 4 の 175pt での突破になりました。

TCO22 - Marathon

4位 とは 5pt 差でギリギリの戦いでした。

MM132

1, 2位とかなり離されたので結果としては残念だったがポイント的には 75pt 取れてラッキーだった回。3回のうち 1回でも高順位を取れると Final がぐっと近づくので本当によかった。

MM133

苦手な推定系の問題。当時流行っていた wordle を題材にした問題で、方針が全くわからず右往左往してたがなんとか 7位で耐えることが出来た。

MM134

比較的得意なマルチエージェント回。 Daiver19 さんより順位を上回らないといけない状況だったので個人的には絶望していたがなんとか勝てた(勝率 1割ぐらいだったので)

感想

方針を 2回外して突破できたので本当にラッキーという感じ。去年は 8位という下馬評通りな感じの順位で終わったので今度はそれより上の順位を目指したい。

AHC011 Sliding Tree Puzzle 参加記

問題

atcoder.jp

方針

主に 3つのパートで構成されています

  • 与えられたパネルから木を構築する
  • 構築した盤面の各パネルに対して数字を割り振る
  • (N * N - 1) puzzle を解く

木の構築

木の構築は盤面を焼き鈍して作成を行いました。木の条件が厳しそうなイメージだったので「パネルの交換だけで出来るのか?」と疑問だったのですが実装してみたら意外と速く構築出来て驚きました。

近傍としては「2つのランダムなパネルを選択して入れ替える」の 1つでしたが選択時に色々と制限をかけています。

同じ種別のパネルを選択しない

同じ種類のパネルを入れ替えても状況は変わらないのでそれは行わないようにします

確実に悪い配置とわかる場合は除外する

「確実に悪い配置」というのは「そこにパネルを置くと絶対に木が完成しない」状態を指します。

図のように画面端に向かって枝が伸びているようなタイルが存在する場合は絶対に木が完成しないので、このような配置にならないように選択を行っています

どちらかは必ず接続状態を維持するようにする

タイルを交換する際にどちらのパネルも接続状態が途切れてしまう場合は交換を行いません。

例えば緑のマルで囲まれた部分を交換すると両方のパネルとも周辺のパネルと接続状態が途切れてしまいます。このような場合は交換を行わず再度タイルの選択をやり直します。

評価値

盤面状態の評価は「連結成分の個数 + 元の盤面からどれだけ近いか」で計算を行いました。

連結成分の計算は盤面全体を DFS で探索して計算を行っています。

元の盤面状態からどれだけ近いか

今の位置から元のパネルの種類の最短距離を計算してその合計値が少ない状態を良しとしています。

評価値については事前に計算しておきます。図は評価値の事前計算の一例です

種別 9 のタイルについて評価を行います

各マスについて種類 9 のパネルとどれだけ離れているのかを計算し dy * dy + dx * dx の最小値をテーブルに保存しておきます。

盤面評価の際はすべてのマスについてこの値を合計したものを利用しています。(この値が大きいほど元の盤面から乖離している ≒ 元に戻す手数が多いと考えられます)

(コンテストの途中、元の位置の距離 (dy * dy + dx * dx) をコストにしてみましたが、特にスコアに変化がなくただ試行回数が減っただけなのでこの評価値をそのまま採用しています)

焼きなましの打ち切り

盤面構築の際にどんなに試行回数を重ねても連結成分が減らない局所解に陥ることが多々あったので、 10万回スワップを行って 1回もスコアの更新が発生しなかった場合は処理を打ち切りました。

破壊的な近傍を用意して局所解からの脱出を行うよりも再実行のほうがコスパが良かったのでそうしています。

複数繰り返して色々な盤面を得る

1回の焼きなまし処理はだいたい 0.1 sec で終わって、盤面が得られる確率が大体 50% ぐらいだったのでこの処理を設定した時間 (今回は 1.7 sec) が来るまでに複数回実行して、様々な盤面を取得します。

構築した盤面の各パネルに対して数字を割り振る

完成した盤面に対して数字を割り振っていきます。割り振りには最小費用流を使用し、辺のコストには元の盤面からの距離 dy * dy + dx * dx と 1 ~ N のランダムな値で計算しています。ランダムな値を追加しているのは距離だけの評価だと毎回同じ数字の割り振りになってしまい、もし出来上がったものがパズルとして達成不可能な場合に数字を振り直したいのでランダムな値を追加して別の割り振りパターンになるようにしています。

パズルの達成が可能な盤面でコストが一番低くなるものを最終的に解く盤面として採用します。

完成可能かどうかの判定は以下のサイトを参考にしました。

manabitimes.jp

外周に近いマスのコストを高くする

n-puzzle は真ん中を先に揃えても後で壊される可能性が高く、基本的には端から揃えていきたいのでコストを計算するときに端のほうのコストが高くなるように設定しました。

配置コスト 5 + 9 = 14

配置コスト 4 + 10 = 14

画像では両方とも同じコストになるので距離のみの評価だとどちらを選んでも良いのですが、実際にはこの距離コストに係数を掛けたものを利用しています。

係数の値は端に近いほど高くなるように設定しています。(実装的には max(y, N - y + 1) みたいな感じです) この係数を使った場合は以下のような結果になります。

配置コスト(new) (4 * 5) + (6 * 9) = 74

配置コスト(new) (6 * 4) + (4 * 10) = 64

結果として、端のタイルはなるべく短い手数で済むような配置になります。(スコアとしては 2 ~ 3000 点ぐらいの向上)

(N * N - 1) puzzle を解く

盤面構築が終わったら後はパズルを解くフェーズになります。今回はビームサーチを利用しました。序盤は高速化が足りてなくて N が大きいケースでは外堀を埋めるルールベースを書いていましたが明らかに手数が多くて悪手だと感じていたので最低限のビーム幅が確保できる状態まで高速化しました。

評価関数

盤面の評価としては主に元の盤面からの距離から計算されるコストと Linear Conflict を少し改造したものを使用しました。(あと端が揃っているかどうか)

距離による評価

元の位置との縦軸の距離の差分 (dy) 横軸の距離の差分 (dx) を調べて、 dy * dy + dx * dx をコストとして計算します。 dy + dx のマンハッタンディスタンス (MD) の場合だと同じ評価値で揃える難易度が全く異なるものが発生しそうだったので2乗の方を採用しています。

特定のパネルを任意の位置に移動させたい場合に「同じ方向に連続で移動する」という動作がかなり手数を使ってしまうので、それを避けるようになるべく「縦の差分」と「横の差分」の差が少ないほうがコストが低くなるように設定しています。

端を揃えた状態の評価

n-puzzle では端が完成するとそれ以降は端を操作する必要がなくなるので、端が揃った場合はボーナス得点を与えています。

ただ、画像のように一部の端だけが完成し続けると最終的に端を崩さないと完成しない状況になりうるのでこのボーナスは「画面端から距離 Xの場合に有効とする」 といった感じで変数を使って制限を加えていました。(変数の値としては盤面のサイズの半分を超えないように設定しています)

隣接マスの関係性の評価

盤面全体をみて評価出来たほうがより精密に評価を出来るようになるとは思いますが、今回は高速化の都合上 1回の移動で変動したタイルの隣接マスだけを見て評価を行いました。

Linear Conflict

Linear Conflict についてはこちらのページを参考にしました。

michael.kim

隣接マスをみて完成図の同じ行 or 列に所属していて番号が逆転していた場合はペナルティを与えています。

特に、お互いが後 1手で完成する同士であった場合はより重いペナルティを与えています。(角でこれをやられるとかなりの手数を消費するので)

後はお気持ち程度の評価ですが、同じ列 or 行に所属していない場合でもゆるくペナルティを与えています。

本来であれば 97 の左側に来るべきなので減点する。

あと 1手同士が隣接している場合にボーナス

15 puzzle の攻略サイトを調べていると「後から車庫入れ」という形になっているとパズルがスムーズに解けるということだったので「残り 1手同士が隣接している」状態にボーナスを与えました。

studio-boiler.com

なので画像のような盤面状況が評価されることになります。

ボーナスとしては小さい値でしたが外すと 2 ~ 3000 下がったのでそれなりに有効だったみたいです。

zobrist hash による重複排除

同じ盤面を探索しないように zobrist hash による重複排除を行っています。重複排除の処理を外すと得点が 10000 下がったのでかなり効果があったみたいです。

Zobrist hashing - Wikipedia

感想

方針自体は maspy さんが初日に 38,307,047 を叩き出していたのでかなり早い段階で決まりました(n-puzzle を構築してそれを解く)あとは、手数を短くするために盤面構築の精度を上げるか n-puzzle solver の精度のどちらを上げるかでちょっと迷っていましたが最終的には solver の精度を上げたほうが良さそうだと思ったので評価関数を色々試してはみましたが 1位に追いつくことが出来ませんでした。

ビームサーチが題材の場合は評価関数を頑張らないとどうにもならないので(ビーム幅を 10倍にしても 1位のスコアに追いつけない)、15-puzzle の資料を色々読んでいましたが 4 * 4 というサイズの小ささに特化した手法が多くて Linear Conflict のような汎用的なものを見つけることが出来ませんでした。(本当はあったかもしれないけどそこは調査力が無かったということで)

ところで 6/23 2:00 から Marathon Match 137 が始まる予定なので興味がある方は是非参加してみてください。(世界大会に向けての予選なので恐らく強い人がたくさん参加する可能性が高いです)

リンクは参加方法についてのガイドラインになります。

www.topcoder.com

今回の問題では「焼きなまし」と「ビームサーチ」というマラソンマッチにおける基本的な探索手法を同時に扱えたのでとても面白かったです。個人的には AHC の時間制限を 10sec あたりまで伸ばしてくれたら時間管理をもっとゆるく行えて気持ちが楽になりそうだなと思っています。(自分の評価関数だとへたにビーム幅を下げると解が見つからない可能性があったのでこのあたりの調整がちょっと面倒でした)

MM136 HungryKnights 参加記

問題

www.topcoder.com

今回のスコア計算では同色の移動を連続で行うことで指数的にスコアが増える仕様となっていたので、出来るだけ長い同色消しの経路を作成する必要がありました。

方針

基本的な方針はビームサーチでの経路探索になります。

スタート地点の選択

長い経路を作りたいので、盤面にあるマスの色をカウントして一番多い色から消していきます。どのマスからスタートするかはランダムに決定しました。

移動先の決定

現在位置からの移動の候補は 8種類あり、移動先が同色かそうでないかで処理を分けます。

同色の場合

同色の場合は特に処理を行わずそのまま移動します。

違う色の場合

色が違う場合は別のマスから対象の色を持ってきて遷移するようにします。

移動先が別の色でこのままだと連鎖が途切れてしまう。

別のマスから同じ色の駒を持ってくる。

移動が可能になる。

この「別の駒を持ってくる処理」については連鎖中に行ってしまうと連鎖が途切れてしまうので、まとめて連鎖用の経路の前処理として実行します。

評価関数

処理後の盤面評価についてですが主に以下の点を重視しました。

  • 残っているマスの個数
    • マスが残っているほど移動に自由が効いて連鎖を作りやすくなる
  • 画面端に近いマスを消していると高得点
    • 画面端のマスは残りやすいため、なるべく残らないように評価を高くしておく
  • 次に消す予定の色を残すようにする
    • 他の色でも大連鎖を組みたいのでなるべく残すようにする
    • その色だけではなくて周辺のマスも消さないようにする

その他

細かいスコアを取るためにやったこと、連鎖スコアに比べると些細なものなのであまり細かく詰めてはいない。

貪欲

連鎖も作れなくなったあとは残った駒を貪欲に消していきます。

挿入

最終的に使われない駒で、その周辺で処理を挿入できそうな箇所があれば変更を行います。

右上の青が最後まで使われなかった場合

「紫」→「黄色」と移動を行っているが、「青」→「黄色」 +「紫」→「青」 のほうがスコアが高くなる場合は「青」→「黄色」の処理を挿入する。

事前同色消し

残った駒の周辺に同じ色の駒がある場合は事前に同色消しを行っておきます。

先程と同様に青が残っている状態

事前に同じ色を使って消しておくことで 1点もらえる

感想

ビームサーチで評価関数勝負かと思ったら 1位は焼きなましだった。2色同時探索はちょっと実装しようかなと思ったけど、焼きなましはちょっと思いつかなかった。とりあえず実装してみてどのぐらいのスコアが出るかは確認したほうが良かったかもしれない。(初手のビームサーチで良いスコア取れたからそれに引きずられた感はある)

2割、3割スコアが離れてたら方針を疑ったかもしれないけど 1割以内で Psyho さんだったしなんかいい感じの評価関数があるのかなと思ってしまった。