sparrow_tree.pyが単純に木を初期配置するプログラムで、今回使ったのは、sparrow_tree2.pyの方になります。こちらは、init.csvに定義して置いた配置を１つの塊として固定するもので、init.csvによりいろいろな形状を設定できます。どれを使うかはプログラム中で定義して、例えば以下のように書かれている場合はn=116~124はn=80の木を１つ、回転角を制限して配置するという設定になります。なお、sparrowでは高さを指定しなければなりませんが、こちらは現状のベスト+εを設定しています（ベストを設定すると自由度が足りず難しかったので）。

(116, 124,  80, 1, True),

こんな感じで、一部にすでに詰まっている木をはめ込んで、空以外の部分だけ木を配置していくという方法です。

これで新たな解のシードを見つけて、後の最適化ソルバーで詰め込む感じになります。

この一連の処理をするスクリプトがsparrow/doing.shになります。

元々は試行錯誤用のコードでしたが、sparrowを使って塊を作る検討は締切２週間前くらいに思いついて、時間もなかったのでコードに直接埋め込む形で、試行錯誤が滲み出たコードになってます。

② 物理シミュレーションによるパッキング

物理ソルバーを使った方法です。do_all.shが物理ソルバーを使ったパイプラインになります。

物理ソルバーについては、以下のグラレコがわかりやすいかと思います。パイプラインでは、物理的挙動を変えた３つのパターンで圧縮を試みます。

物理ソルバーは、重なり解消と正方形への押し込みを行うので、①で見つけた解をまずは正方形にするのに使いました。

また、振動することで、うまく詰め込むことができた感じです。後に説明する詰め込み処理を行うパイプラインとは違った動きをするので、交互に動かすことでじわじわスコアを上げることができました。

③ 焼きなまし法をベースにしたパイプライン

ALNS (Adaptive Large Neighborhood Search)

do_sa.shというスクリプトがこれを行うものです。solver2がメインのアニーリングのソルバーで、成功率に基づいて、さまざまな移動オペレータの重みを自動的に調整するALNS (Adaptive Large Neighborhood Search)を使い、多様なオペレーターを種々選択するようにしています。

オペレーターの例

BoundaryPush: ハルをコンパクトにするための、境界の木に対するターゲットを絞った移動。
ChainMove: 詰まりを解消するために、木とその隣接木を一緒に押します。
GlobalSqueeze: 配置全体を一様に中心に向かってスケーリングします。
LevyFlight: 局所解を脱出するための時折の大きなジャンプ。
PairMove、180Flip、60Snap など。

焼きなましはあと１つchaos_optimizer.cppを使っていますが、こちらは公開されていたものをそのまま流用しました（なるべく違う方法の詰め込みを回したかったので）。

ビームサーチ

焼きなましでは、ある程度から動かなくなったので、ビームサーチソルバーも追加でさくせいしました（squeeze_v3s)。こちらは、ぎりぎりまで詰める処理として結構重宝しました。こちらも思いつく限りの手法を詰め込みました。

なお、ビームサーチは物理シミュレーションの後の最適化でも使っています（do_all.sh）。

②と③の連携

基本は①のspyrrowで作成した初期値を、②と③で最適化し、その結果スコアがの更新されたものをマージするという作業を行いました。

AIを使ったプログラミング

今回は、AI（Gemini）をプログラミング支援として使いました。新しい方法を考えるのにははっきり言ってAIはポンコツです。今回、どのような使い方をしたかを書いておきます。

公開コードの解析

公開コードをAIに読み込んで「このコードは何をしているの？」という問い合わせをして、内容を要約してもらいます。これにより、公開コードを読まずに内容を把握できます。また、気になった部分は追加で質問することで詳しく説明してもらうことができるので、重宝しました。これが一番AIが便利だった部分です。

ベースコードの作成

アニーリングやビームサーチ、物理シミュレーションについては、テンプレ的な書き方があるので、ベースとなるコードを書いてもらうのには役にたちます。ただ、最適化の処理の部分については、いまいち信用できない（コードがおかしいことがある）ので、以下のような対策をしました。

物理シミュレーションについては、ビジュアル表示機能をつけて意図通りに動いたか確認する
焼きなましとビームサーチについては、スコア計算の部分と選択部分だけ細かくチェック。あとはAIまかせ

物理シミュレーションは、ビジュアライズがかなり役に立ちました。思ったように動いていない、壁を木がすり抜ける、壁があさっての方向に移動する・・・などなど、いろいろなバグがありました。可視化することで一目でエラーが見つかりました。修正はAI＋人です。

それ以外の手法については、「選択される候補は正しい」という部分だけ担保して、あとはAI任せで作成しました。このおかげで思いつたオペレータをたくさん実装することができたと思います。オペレーターの正しさはアバウトにしかチェックしていませんが、「スコアが低い」オペレータは選択されないし使われないので、処理速度低下はあるけど結果に影響を与えないのでOKとしました。

AIまとめ

この手の問題について、アイデア自体をAIに出させるのはかなり難しいと感じました。「アイデア」をプログラミングさせるのは良いですが、AIの出してくるアイデアは「テンプレ」的で問題にフィットしなかったというのが感想です。ただ、うまく使うことで、検討速度を加速することが可能です。

結果

結果は、29/3397で銀メダルでした。メダルは取れるけどあと一歩が足りないというのが自分の実力かなと思いました。

#kaggle

毎年恒例のSanta2025に挑戦｜Kaggleチャレンジ記録

Santa2025

ルール