今週のまとめ
- AHC019後半戦。いつものようにラスト2日で怒涛の追い上げ？
です。(前半編からの続きです。)
3/26(Sun)
AHCも後半戦ですがこの日は家族とお出かけ。大阪 万博記念公園にある「NIFREL(ニフレル)」に行ってました。
その間に厳密解法を制限時間15分/問で回してD=5は174/200問が解けました。ただ、D=6以上はまったく動かず、D=5も制限時間内だと間に合わないのでそのまま使うのは難しそうです。
1週間以上、進捗がないのでBeam Searchに戻って高速化。
「ブロックの回転を決めて貪欲に大きくする」を24通り試していたのを「順次ブロックを大きくしながら有効な回転をbitsetで管理」ようにしたら4倍以上速くなりました。
厳密解法側もそのままだと厳しいのでラスト1個のブロックでシルエット制約を満たせるか？を全探索ではなく貪欲で見ることに。これで15%くらいで最適解がでなくなったものの10倍以上高速化。
3/27(Mon)
厳密解法の緩和を色々試していました。ただ、誤算だったのは[math]D\geq 6[/math]だと緩和しても全然時間が足りなさそうということ。
さらに自己ベストをもとに相対スコアを出したら苦手なのは
- Dが大きい
- 少ないブロックで作れる問題で多数のブロックを使ってしまう
でこれを見るとここ数日、厳密解法をいじっていたのは方針としてまずかったかも…。
3/28(Tue)
「少ないブロックで作れる問題で多数のブロックを使ってしまう」のはBeam Searchの内部で貪欲に大きくしているのが一因でアプローチを変えて
- 使うブロック数を決め打つ
- 2フェーズに分けて前半はできるだけ少ないサイズでシルエットを作り切る
- 後半は小さいブロックを極力大きくしてサイズを均等化
を山登り（いずれは焼きなまし）法で求めてみることに。
夜に実装して動き出したものの有効な解ができない…。が、眠いのであきらめて就寝。
3/29(Wed)
頑張ってデバッグしてスピードも度外視してとにかく意図した動きになるように注力。
デバッグの過程でブロックのペアの持ち方や回転の管理、立体1, 2を均等に扱うかどうか？を変えたくなってリファクタリング。
3/30(Thr)
実装にイマイチ自信がないところは単体テストを書くようにしているのですが、回転部分のついででテストした平行移動部分でバグを検知。危ない危ない。
これでようやくシルエット制約を満たすブロックを作ってくれるようになりました！
ブロックの大きさの均等化を考慮できていないので使用ブロック数で評価したのですが、Beam searchの結果をなかなか越えられません…。
山登りから焼きなましにしても少し改善したものの大勢は変わらずでダメ元でパラメタチューニングをしてみたもののあまり改善せず。うーーん。
3/30(Fri)
いい加減、見切りをつけてBeam Searchに戻るか焼きなましを頑張るかで悩みます。
会社の行き帰りで焼きなましの遷移をもっと良くできることに気づいて
- セルの追加は1つずつではなく貪欲でまとめて増やす
- 削除する際は削除＆追加をセットにする
- ブロックの起点はランダムではなく次数が小さい「難しい場所」を優先する
- ブロックの移動はブロックが小さいときのみ行う
などなどアイディアが生えてきました。
セルの追加ロジックを書いていたときに立体1, 2の座標を取り違えていたバグを発見。これを直すとグッと良くなりBeam Searchまであと少しのところまできました。
4/1(Sat)
今日は奥さんの実家の方々がうちに来る…ということで掃除＆ご挨拶。
夕方から再開して探索ロジックがバグってないか不安で探索ログを出力して可視化。
Plotlyを使ったのですが2Dに比べて3Dは座標軸の反転ができなかったりZoom in/outで表示が乱れたりと完成度はいまいちですね。(Visualizerの出来が良すぎる？)
一応、意図した動きはしているようでプロファイルを取って細かく高速化したり金曜に生えたアイディアを実装したり。
残り時間も少ないので後半フェーズの「シルエット制約充足後に小さいブロックを極力大きくしてサイズを均等化」を入れます。
シルエット制約を満たすようにしたものを小さいブロックから貪欲に大きくします。
分かりにくいですが茶色と青のブロックを大きくしてスコアを改善できています。
これで平均スコアはBeam searchをついに超えた！長かった…
複雑なロジックを書く元気が残っていなくて簡単にできそうな高速化でvector
（とメモには書いてますが結局、朝方までいじってました）
4/2(Sun)
気が付くと最終日。昨日は結局4時くらいまでやっていたのに8時に目が覚めました。
焼きなましのツメが甘いので頑張って伸ばさないと…と思っていたら高速化の恩恵でBeam search側のスコアも伸びてて全体的にBeam searchのほうが良い結果に。
時間制限いっぱいに回すようにするとさらに差が開いて7-8割Beam searchが良い結果に…。いやーー、Beam search強いな。そっちに賭けていた方が良かったか…。
未練がましく問題サイズや問題の特性(ギザギザっぽさ)で分けたらBeamSearch, 焼きなましの使い分けができるのでは？と淡い妄想をして問題を分類することに。
3/21に作ってた特徴量と自己ベストのブロック数から問題の難易度(必要なブロック数)を決定木でざっくり推定することに。決定木を可視化するパッケージがうまく入らず。直す余裕もなく
テキストで分岐を書き出して手で真心込めて実装することに。
D=8くらいまで実装したところで次女がやってきて
「公園でお花見しよー！」
え？マジ？このタイミングで！？
お父さん、3次元パズル作るのに忙しいからまた来週ね！
と言うわけにもいかず公園へ。出る前にパラメタチューニングをかけておきます。
決定木で頭が一杯でしたが同じ木でも桜は散り始めててシーズンももう終わりですね。
家に戻ってチューニンング結果を確認したら1問目からこけてました…。慌ててやるとダメですね。
チューニンングはあきらめて決定木の実装を頑張ります。15時過ぎに動き出して結果を見ると「D x 複雑さ」のクロスで見ると2割くらいで焼きなましが勝っています。
サンプル数が20くらいなので過学習な気もします[1]この辺りは「仕事だったらNGだよな」と「まぁ趣味だし良いか」で気持ちのせめぎあいがあります。がせっかくなので両方のロジックを使いたくなり再び使い分けのif-thenルールをもりもり書きます。
手元でテストして大丈夫そうなことを確認して16時半過ぎにsubmit。17時から予定があるのでこれが最終提出です。順位は落ちていくだけなので見ずにおきます。
4/3(Mon)
暫定順位は58位、システムテストで1つ落ちて最終59位でした。順位, パフォーマンスともに自己2nd bestなのは良かったのですが
- 最初の「立体1, 2におけるブロックを貪欲に作る」ロジックから改善できなかった
- 厳密解法、その緩和解法に時間を使いすぎた(結局、使わずじまい)
- 終盤に別アプローチ(ブロック数決め打ち)をとったものの意識、労力が分散
と怒涛の追い上げというよりはちょっと不完全燃焼感が残りました。
終わった後のTwitter感想戦を見るとBeam searchでも焼きなましでも上位に行けたようで、両方に手を出して両方とも中途半端になった気がします。
後付けでロジックの使い分け条件を考えるのではなくて先に苦手な問題群を条件付けておいて、その問題群に対する改善ロジックを作る必要がありましたね。反省。
良かったのはThunderさん本こと「ゲームで学ぶ探索アルゴリズム実践入門」
を見ながらちゃんと？Beam searchを書いて[2]AHC013 Server roomで我流Beam searchもどきを書いたけど性能がでなかった…性能を上げられたのは良かったです。
あとiwashi31さんが「AHC019 の Web 版ビジュアライザを手元で動かして実行結果を自動で反映したい」という記事を書かれていて、これはぜひ次回までに使えるようになりたいです[3]毎回、実行結果をコピペして腱鞘炎になりそうになるので。。
と今回も2週間どっぷり楽しんで新たな課題も見つかりました。MC Digitalさん、AtCoder社、参加者の皆さんありがとうございました～！
関連記事
- 前週の週記: 「週記(23/03/19)：AHC019参加記(前半編)」
- 翌週の週記: 「色変記事」
ピンバック: 週記(23/03/19)：AHC019参加記(前半編) | 有意に無意味な話
ピンバック: 週記(23/04/02)：色変記事 | 有意に無意味な話