AHC 013

 

 

AHC 013 でやったことを書きます

 

結論

（時間がない人はここだけ読めば OK です。）

  1. 盤面（ケーブル情報も含む）
  2. Move の履歴
  3. Connection の履歴
  4. 注目しているコンピュータの種類

を持つ山登りで、 1 種類のコンピュータを優先して進める貪欲方式で Pretest 265,366 点取れた（暫定 61 位）。

 

Sample 1 の結果（5350 点）

 

日々の進捗

1 日目（8 月 9 日）

飲み会（チームの歓送迎会）

 

2 日目（8 月 10 日）

飲み会など

 

3 日目（8 月 11 日）

飲み会など

 

4 日目（8 月 12 日）

飲み会（会社の偉い人たち）

 

5 日目（8 月 13 日）

問題を見た感想：

  • 密盤面の調整するときは、 AHC 011 のスライドパズルのライブラリそのまま使える？
  • パラメータによって結構違うゲームになりそう
  • 実装むずそう
  • （例えば山登り・焼きなましなどするとして）どういう情報を持つべき？
  • 別種類のコンピュータを混ぜるのはあまりメリットなさそう
  • まずは 1 種類のコンピュータを全部繋げるのを目指すべき？（これで 4950 点なので 50 ケースで 25 万点弱）

 

最初の方針としてはとりあえずこんな感じが良さげか

 

  • まずは 1 種類のコンピュータのみをつなげる
  • 他の種類はとりあえず無視
  • 長いケーブルを引くと制約が増えるので、各種類について短い方から Move なしで貪欲で引いてみる
  • 一番よさげな種類をひとつ選んで固定
  • とりあえず山登りしてみる
  • 持つ情報は、「盤面（ただしケーブル情報も保持）」「Move の履歴」「Connection の履歴」
  • 「見ている種類のコンピュータを 1 マス動かす」「見ている種類の 2 つのコンピュータの間に異種コンピュータがあり、かつその隣接マスに退避できる場合は退避する」の 2 種類を、得点の増え方が多くなる方を優先でできるだけ行う

 

得点の増分をキーにした理由は、メインクラスタに繋げていく方が有利そうなので。毎回全部選ぶと計算量やばくなるし、結果的に全部繋げられれば変わんないので、これが良いかはよく分かんない。

とりあえず頑張って実装すると RE 。

 

〇 － 〇 － 〇

 

から真ん中のやつを 1 つ下に下げると、左右のはくっつけることができるんだけど、上にくっついてるものがある場合にどちらか片方しか選べないのでその判定をミスっている模様。

バグ探しにいろいろ苦労したけど 2 RE ののち 132,355 点をげっと。実行時間は 3 秒ぎりぎり。

 

まだだいぶサボっていて、

メインの種類以外のコンピュータは見てない（たとえ隣り合っていても結んでいない）

そもそも操作回数のカウントもしていない

 

 

  • 「退避」による接続は、間のコンピュータが 5 台まで増やした
  • 時間チェックを入れるようにした
  • 回数チェックはまだ入れてない

 

これで 196,533 点。

 

5 ～ 6 日目（8 月 13 日 ～ 14 日）

 

「一番大きなグループ」に空マスだけを通って辿り着ける同じ種類のコンピュータは、 BFS で連結マスまで移動するとくっつけられる。

これを入れると 229,710 点。

 

7 日目（8 月 15 日）

 

空マス以外を通る場合も、邪魔コンピュータを移動しながら動かすと行ける可能性がある。

BFS（Dijkstra）を 2 回すると実装できる *1 。これを頑張って実装すると 241,079 点。

この時点でまだ 1 種類しか繋げていない（つまり理論値は 4950 * 50 = 247,500 点）ので、理論値の 97.4% が取れていることになる。

いずれにしても 25 万点超えを目指すには 2 種類目を使うしかない。

 

 

2 種類目

種類数が増えても大丈夫なように実装しようと思っていたけど、一部うまくできていないので変えるのは大変。

苦肉の策として、「今見ているメインの種類をすべて壁マスにする」 *2 という処理を行って、その後はその色は最初からなかったかのように扱うことで既存の関数がある程度そのまま使うことにした *3

 

1 種類目の関数をそのまま使って頑張ると 258,223 点まで出せた！

 

 

 

省スペース

得点が低いケースを見てみると、スペースがなさすぎて 1 種類目すらうまく繋げていないことが分かった *4 。 1 種類目をある程度繋いだ後に、省スペース策として

  • 一方向にしか出ていないマスを上下左右のどこかに動かせるなら動かす

は簡単に実装できる *5 ので入れてみると 264,840 点。

 

あとは 3 種類目を入れるなどして 265,227 点。

 

 

 

 

8 日目（8 月 16 日）

「同じ種類のみを繋ぐ」縛りでやってきたが、狭い盤面のときなど 1 マス挟んで大きなブロックが結合できない場合もあるので、無理やり繋ぐのを実装した。

これも実装を一から変えるのは大変なので、実装上は強制的に色を変える（ 3 - 4 - 3 - 3 みたいになってたら 4 を 3 に塗り替える）ことにした。これでもその後の最適戦略は（ほとんど）変わらない *6 。得点は変わるが、何点下げるかの調整を入れればよい *7 。

主に狭いケースで改善がみられて、 Seed 9, 25, 37 などでは 1000 ～ 2000 点近く上がった。 15 ケースに 1 ケースで、 1500 点上がるとすると、 Pre-test の 50 ケースでは 5000 点ぐらい上がるかな？と思って出してみたが 100 点ぐらいしか上がらず・・・。該当ケースがなかっただけなのかも。

 

 

アニメーション

 

方針的に、疎の方が動きに余裕がなくて困りがち（点数が低くなりがち）。

Seed 0 / Seed 7 （密バージョン） / Seed 1 （疎バージョン） それぞれこんな感じ

 

 

できなかったこと

本当は 1 種類目のコンピュータを固定して 2 種類目にいくのではなくて、 2 種類同時に動かせればより柔軟性が上がる *8 。

その場合、データの持ち方を変えないといけないのはもちろんだけど、評価関数をどうするかも結構難しそう *9 。あと近傍への移動を実装するのも結構難しそう。少なくとも「ケーブルの繋ぎ変え」は考慮する必要がありそう。

逆に「繋ぎ変え」さえうまくできれば、あとは適当に焼きなましに乗せることもできるかもしれない。

 

 

 

 

デバッグ環境について

コンテスト中、言及されていた模様 *10 。

 

 

これはその通りで、今回も PyPy 環境構築もたくさんループして確認するのも諦めていました。実際、手元環境はいつも通り Jupyter Notebook なのでめちゃくちゃ遅いです（Visualizer 用の出力も合わせて、 1 つ回すのに 1 分ぐらいかかる）。

 

まあでも一般的には

  • たくさん回して得られる情報は最後の調整以外は大したことない
  • 早いうちからパラメータチューニングをやりすぎると良くない *11

ので、環境構築については特に意識していなかった。

結局、まじめに考察をして新規アイデアを出さないと抜本的な改善は見込めないんですよねー。 1000 ケース、 10000 ケースの平均得点を正確に出すより、特徴的な数ケースの結果を正しく分析・考察する方がよほど大事 *12 。

 

デバッグは

  • Jupyter による実行
  • Jupyter の結果を Visualizer に貼りつけて実行 *13
  • コードテストによる実行 *14
  • 本番提出

 

をうまく使う感じで。

目的ごとにコードを変えるのはめんどくさいので、 Jupyter の実行と本番提出は全く同じコードでできるようにした *15 。コードテストと本番提出は区別できないので、コードテスト時には 1 文字だけ変えるようにした *16 。

 

 

ランダム要素

 

乱数は使ってないので、時間打ち切りの影響の差のみ出るはず。

同じコード *17 で 2 回出し直してみると 3 点しか変わらなかった。

 



 

 

 

 

 

 

 

 

 

 

 

*1:１ 回目は空マス以外に 20 の重みを付ける重み付き Dijkstra 、2 回目は邪魔マスを空マスに移動させる BFS

*2:実装上はもう動かせないマスを 7 として実装した

*3:若干きもいけど仕方ない

*4:サンプルの 9 など

*5:既存の関数がそのまま使えた

*6:Move や Connection の出力にも影響しない！

*7:ちょっとはしょった

*8:実際、デバッグ画面を目視で確認すると、最初の種類が邪魔をして点数が伸びない状況が多かった

*9:一番大きいところを優先するのでだいたい良さそうだが

*10:コンテスト中なので反応できなかったけど

*11:局所最適になりがち

*12:もちろん、ある程度のレベルになってくると平均得点を正確に把握することで有利になるのは間違いないんだけどね。特に入力条件別の得点を把握することでパラメータ調整が正確にできる。ただ今回だと私が 26 万点台でもがいているとき、トップ層は 38 万点台とか出していて、パラメータ調整とかしようとも思えないレベル。

*13:途中経過も保持しているのでアニメーションになる

*14:得点とステップごとの時間を出力している

*15:Local で流すときは LOCAL = 1 を事前にしておくことで判定できる

*16: "if 0" を "if 1" に変える

*17:最終の 1 回目のバージョン