新しいことをやろう - Santa 2025 振り返り -

新しいことをやろう - Santa 2025 振り返り nagiss AI 技術開発部 株式会社ディー・エヌ・エー © DeNA Co., Ltd. 1

自己紹介 サンタに縛られている人です © DeNA Co., Ltd. 2

目次 1 コンペ概要 2 新しいことをやろう 3 上位解法 © DeNA Co., Ltd. 3

1. コンペ概要 © DeNA Co., Ltd. 4

サンタコンペとは 1 ● Kaggle で年末年始 パッキング 単語の並べ替え 恒例の変わったコンペ ● 最適化っぽい問題が出る ルービックキューブ 巡回セールスマン ここしばらくタイトルで頭韻踏ん でたのに今年は踏んでいない 超置換 多腕バンディット © DeNA Co., Ltd. 5

2 今回の問題 ● ツリー (15 角形) をなるべく小さい正方形に詰めてね！ ● ツリーの数 N は 1 から 200 まで。全部解いてね！ N = 10 の例 © DeNA Co., Ltd. 6

3 Public Notebook の解法 / Discussion などで既知だったこと ● 焼きなまし法は強い ○ 木を少しずつずらし続けるシンプルなもの ● sparrow というツールが使えそう 順位表 ○ LB 上位に sparrow の開発者 誘導局所探索法で多角形の配置を求めるツール ただし高さを固定して幅を最小化するものなので目 的関数がちょっと違う ツリー数 ● N > 50 くらいになると中央を規則的に敷き詰めた解が強い ● 偶数の N は点対称な解がそこそこみられる ● なんか異様に参加者が多い ● 上位に AHC 勢が多い 規則的な敷き詰め AHC: AtCoder Heuristic Contest Santa と同じように最適化の問題が出る この手の問題に慣れていないならまずは AHC の方が期間短くて参加しやすい © DeNA Co., Ltd. 7

2. 新しいことをやろう Try something new! © DeNA Co., Ltd. 8

最高の post 1 LLM を活用したコーディングについて既に言及している人もいると 思いますが、これは本当に素晴らしいと言わざるを得ません。 これで必ずしも金圏内に入れるわけではありませんが（中略）、構 文エラーや単純な符号ミスに悩まされることなく、色々と試したり いじったりするのはとても楽しいです。最初にコードを書いてから 10 年以上経ちますが、それでも LLM は大きな助けになっていま す。 私は template chainging、さまざまな GUI、基礎モデル空間への表現 の埋め込み、強化学習 (GRPO を初めて試し、現在は報酬の形成と 機能の表現のさまざまな方法を模索しています) を試しました。 他のやり方では、ここまで楽しんで取り組むことはできなかったで しょう。 Happy Kaggling everyone and happy Hollidays! 引用: https://www.kaggle.com/competitions/santa-2025/discussion/664574 © DeNA Co., Ltd. 9

• https://www.kaggle.com/competitions/santa-2025/discussion/664574

2 サンタコンペをやるときはね 自由で なんというか救われてな きゃあダメなんだ ● 自分も AI の力を借りて新しいことをいっぱいやったので紹介します ○ まあここに書いたのは最終的なスコアにほぼ寄与していませんが…… ● これが✨AI 時代の戦い方✨です © DeNA Co., Ltd. 10

1. ツリー型物理タイル発注編 1/5 3 ● 11 月末ごろ ● 物理ツリーを実際に並べて考察したい…… ○ 作るしかない！ ● 寸法の精度が十分高い条件に絞ると 金属加工か 3D プリントが有力らしい 11 月末ごろの ChatGPT の履歴 © DeNA Co., Ltd. 11

4 1. ツリー型物理タイル発注編 2/5 ● 発注するには図面やら 3D データやらを作る必要があるらしい…… ● FreeCAD をダウンロードしてきて入門 ○ かなり悪戦苦闘した (この辺りも AI に聞いたけど微妙に役立たなかった。FreeCAD のバージョンによる差異もありそう) 資料「3D プリントは包含する直方体の体積が小さいほど安い」 自分「敷き詰めが役立つじゃん！」 資料「複数プリントする場合は 5mm 以上の間隔を開けてください」 自分「😇」 © DeNA Co., Ltd. 作った図面と 3D データ 12

5 1. ツリー型物理タイル発注編 3/5 ● 金属加工はメールで見積もりをお願いしないといけない ○ やはりこれも AI に手伝ってもらう ● 金属加工方面で 2 箇所に問い合わせたが、3D プリントの方が金額が小さそうだった ● DMM.make の 3D プリントサービスに課金💰 © DeNA Co., Ltd. 13

1. ツリー型物理タイル発注編 4/5 6 ● 完成！(12 月中旬) これでもりもり 解を作るぞ💪💪 © DeNA Co., Ltd. 14

7 1. ツリー型物理タイル発注編 5/5 ● 届いてわかったこと: 使いづらい😔 ○ コストを抑えるために小さくしたせいか、かなり軽く滑りやすかった ■ ○ 手で配置して接触させた瞬間に飛んでしまう 数日後にはしまわれてしまう ドンマイドンマイ！次行こう！ © DeNA Co., Ltd. 15

8 2. 手動編集ツール作成編 1/2 ● 解を描画して確認すると明らかに微妙な配置がよく見つかる ● 手動で直したい ○ 多分いろんなチームが同じこと考えたはず ● Codex に半手動で解を修正するためのツールを作ってもらう © DeNA Co., Ltd. 16

2. 手動編集ツール作成編 2/2 9 何が作りたいかは明確だったので 最初にかなり長いプロンプトを 書いて設計させた スコアが良いほど緑に近くなる 懐かしのハル研プロコンスタイル ● 1 日か 2 日そこらできたものがこれ → ○ ツリーを選択して焼くのもできる ● 12 月後半は手動修正に勤しんだ 4 位チームも似たこと やってたぽい ○ 一定効果はあったが 最終的な結果に寄与したかは謎 ● ビジュアライザとしても優秀だったので 最後まで使ってた ○ チームメイトは使って なかったけど……🥺 © DeNA Co., Ltd. 17

10 3. 焼きなまし Triton Kernel 開発編 1/2 ● 問題構造が簡単なので GPU で爆速最適化しやすいのでは？と思っていた ○ 実は 12/9 にてりーさんとチームマージするまで PyTorch で解法を書いていたが あまり速度は出ていなかった ● 長期間 1 位だったさはらさんもこの辺り得意だった気がしていた © DeNA Co., Ltd. 18

3. 焼きなまし Triton カーネル開発編 2/2 11 ● いい機会と思い Triton に入門 ○ Triton: GPU を高速に動かすやつ 焼きなましの Triton カーネルを (Codex が) 書く ● 1 月上旬・中旬を費やして新解法を作り、焼きなましもそこそこ速くなったが 細かい調整の難易度が高くて活用できず😔 ○ © DeNA Co., Ltd. とてもつらい 結局最後 1 位は CUDA で最適化していたので 筋は悪くなかったと思う 19

12 まとめ ● 解法選択で実装コストをあまり考えずに済むようになった ● 詳しくない分野でも短期間でそれなりのものを作れるようになった ○ 詳しくなくて良いので色々な分野を知っていると得 まあ今までもそうなんだけど ● 新しいことをやろう！ © DeNA Co., Ltd. 2 ヶ月半もあるんだから 20

3. 上位解法 興味ある人いるの？ © DeNA Co., Ltd. 21

1 上位解法 ● 今日の参加者そんなに興味ないでしょｗ 今日の参加者＝AIの使い方に興味ある人 Kaggleの上位解法に興味ある人 Santaの上位解法に興味ある人 © DeNA Co., Ltd. 22

2 上位解法 ● なんなら Deep research で良いし ○ ChatGPT は Kaggle を見られないので Gemini を使うと良い ● Santa の上位解法に興味あるなら↓に参加すると良いです ○ https://algo-artis.connpass.com/event/382730/ ■ © DeNA Co., Ltd. なんと 2 位🏅 4 位🏅 5 位🏅の人から直接解説を聞ける！参加しなきゃ！ 23

• https://algo-artis.connpass.com/event/382730/

3 上位解法 ● 喋らなくてもいいんじゃない？ © DeNA Co., Ltd. 24

4 上位解法 ● あっ �� © DeNA Co., Ltd. 仕方がないので 軽く喋ります (時間があれば) 25

5 解法の前に ● 上位解法に興味ある人 AHC 勢でしょ ● AHC と Santa の違いを先に書いとこうね © DeNA Co., Ltd. 26

6 Santa と AHC の違い ● Santa ○ 他に Santa の特徴として、作問者が解法をあまり想定していな そうというところは大きな違いだし面白いと思っている あと Santa は有名問題をベースにすることが多いので既存ツー ルや論文調査などが有用な場合が比較的多い 実行時間が 2 ヶ月以上 ■ 焼きなましがサチる ■ 1 回の遷移に山登り/焼きなましを含むような、メタ的な最適化が必要になる ● AHC ○ © DeNA Co., Ltd. 実行時間が数秒 ■ 焼きなましがそんなにサチらない ■ 局所探索で十分、解を複数持つのは悪手がち 27

メタ的な最適化のイメージ 7 ※ ⚪は解、→ は kick + 焼きなまし (or 山登り or ?)、数字は探索順 ※ 下にある ⚪ ほど良い解、 ⚪ の分布の広がりは解の多様性 0 1 5 3 2 2 1 4 0 4 5 幅が無限大のビームサーチとも Kick が強すぎる ILS とも解釈できる 3 8 幅 1 のビームサーチに近い ● ILS (反復局所探索) ● 多点スタート焼きなまし 1 8 5 1 2 6 2 0 0 3 6 3 10 9 7 13 10 4 12 11 4 11 個人的にはメタビームサーチって呼んでた © DeNA Co., Ltd. 9 8 5 ● 7 6 ビームサーチ Kick+焼きなましで遷移する 他の解の要素を部分的に 取り込む kick を使った ビームサーチとも言える 9 7 13 12 局所探索を組み込んだものはメメ ● 遺伝的アルゴリズム ティックアルゴリズムと言うらしい 28

8 こっから本当に上位解法です ● 概要だけね 概要だけ読んで同じ強さの解法を実装できるかというとまあ無 理で、細かいところに本質がありすぎる しかしよく知らない人から見るとあまり重要でない話に見える ので話しても面白みがない ● 地味な部分もかなり大事なんですが、省略 上位解法は以下を参考にしています / 以下から画像を引用しています 1st: https://www.kaggle.com/competitions/santa-2025/writeups/1st-place-genetic-algorithm-and-gpu-relaxation https://www.kaggle.com/code/jeroencottaar/santa-2025-1st-place-solution 2nd: https://www.kaggle.com/competitions/santa-2025/writeups/2nd-place-simulated-annealing-iterated-local-sea 3rd: https://www.kaggle.com/competitions/santa-2025/writeups/third-place-solution-a-customized-sparrow-algorit 4th: https://www.kaggle.com/competitions/santa-2025/writeups/4th-place-hybrid-packing-with-sparrow-manual-str 5th: https://www.kaggle.com/competitions/santa-2025/writeups/santa-2025-5th-place-solution © DeNA Co., Ltd. 29

• https://www.kaggle.com/competitions/santa-2025/writeups/1st-place-genetic-algorithm-and-gpu-relaxation
• https://www.kaggle.com/code/jeroencottaar/santa-2025-1st-place-solution
• https://www.kaggle.com/competitions/santa-2025/writeups/2nd-place-simulated-annealing-iterated-local-sea
• https://www.kaggle.com/competitions/santa-2025/writeups/third-place-solution-a-customized-sparrow-algorit
• https://www.kaggle.com/competitions/santa-2025/writeups/4th-place-hybrid-packing-with-sparrow-manual-str
• https://www.kaggle.com/competitions/santa-2025/writeups/santa-2025-5th-place-solution

9 1st Place (Jeroen Cottaar) ● 遺伝的アルゴリズム Kaggle Rank #2 ベイズ推定とか連続最適化とかに強いタイプの Kaggler 単体での探索力 SA > L-BFGS 収束の速さ SA < L-BFGS という感じだと思う 解集合内の最小正方形サイズを更新する毎に 目標正方形サイズを小さくするっぽい ○ 正方形サイズを決め打って衝突を最小化する ○ 局所探索として (焼きなまし等ではなく) L-BFGS を使用 ○ 高速化: 衝突量の Lookup Table 事前計算、CUDA カーネル ○ 多様性確保: L-BFGS の CUDA カーネルは PyTorch の実装をバッチで動く ように改造したらしい 地震波コンペでも BFGS 使ったり CUDA カーネル書いたりしていたらしい ■ 解集合を「島」に分け、島外の解との交叉を特定の条件下のみに限定する ■ 次の世代に残す解を選択する際、既に選択された解に近いものを除外する ■ スコアが停滞した島・最良の解が他島と同一の島をリセットする Writeup / 解法 Notebook には細かい工夫も多く記載されている 敷き詰めを初期解にする話とか N が偶数の時に点対称を試すとか ツリー数 N の解に対してツリーを増やしたり減らしたりして N±1 の解の初期値にするとか パターン敷き詰め系の解なら遷移を端に限定するとか © DeNA Co., Ltd. 30

2nd Place (KiRaRe) 10 nagiss/terry_u16/c-number AHC 勢 ● ILS / ビームサーチ ● 詳しくはてりーさんが明日話してくれるはずです！！！ Kaggle サンタコンペ 2025 振り返り会 - connpass https://algo-artis.connpass.com/event/382730/ © DeNA Co., Ltd. 31

• https://algo-artis.connpass.com/event/382730/

11 3rd Place (🎄 Jingle bins 🎄) Zidmie/Gilles Vandewiele/Kha Vo/Oleh Uhnivenko/Delporte Robbe ● 長方形の組み合わせによる解の作成 ○ 規則的な敷き詰めと無改造 sparrow により 小さい長方形に対する配置を大量に生成 ● sparrow を改造し、解を改善 ○ 幅と高さを同時に最小化できるようにする (sparrow は高さ固定して幅を最小化するツール) ツリー数 ○ N が 2 か 4 の倍数の場合に対称な解を強制して収束を早める ○ 中心に近いツリーを特定の角度に近づきやすくする ○ sparrow を実行する前に座標を 1 +ε倍し、ランダムに回転させる kick を行う ○ 異なる N の解からツリーを増減させてから回したりもする どの N を元にしたりす LLM を使って Python のプロトタイプを C++ に移植したり Rust で書いてある Sparrow を改造したりしたらしい © DeNA Co., Ltd. つまり ILS っぽい るかは主に手動らしい 32

4th Place (bowwowplusa) 12 bowwowforeach/montplusa CodinGame/AHC 勢 ● sparrow を少し改造 ○ 取りうる角度を 22.5, 67.5, 112.5, …, 337.5 の 8 通りに限定 ○ 中心付近はさらに 22.5, 202.5 だけに限定し規則的な敷き詰めが作られやすくする ○ 再実行の際、左右端のツリーを僅かに外側にずらしてから回す ○ 後処理で焼きなまし ● 3 列周期のパターンを使う (右図) どの N を元にしたりす るかは主に手動らしい ● 角付近の配置を異なる N の解のもので置き換える ● 詳しくは MON.T さんが明日話してくれるはずです！！！ https://algo-artis.connpass.com/event/382730/ © DeNA Co., Ltd. 33

• https://algo-artis.connpass.com/event/382730/

Rudolph Prize: 最長 1 位保持賞 13 5th Place & Rudolph Prize (shr) AHC 勢 ※ ここまででのスライドで出てきた焼きなましは 1 回の遷移でツリーを 1 つ動かすものだが、 ここでは 1 回の遷移を Kick + 山登りとしたときの焼きなまし。 ● 温度並列焼きなまし ○ 1st と同様に正方形サイズを決め打って衝突を最小化する ○ 物理シミュレーションで衝突を解消 ○ 8-12 個程度の解を同時に最適化 ■ 時々 best 解で最高温度の解をリセットするっぽい ● 詳しくはさはらさんが明日話してくれるはずです！！！ https://algo-artis.connpass.com/event/382730/ © DeNA Co., Ltd. 34

• https://algo-artis.connpass.com/event/382730/

14 比較？ 最適化手法より初期解の選び方の方が重要説はある © DeNA Co., Ltd. 1st 2nd 3rd 4th 5th N±1解活用 ✅ ✅ ✅ ✅ ✅ 点対称 ✅ ✅ ✅ 最小化対象 衝突量 幅 正方形 幅 衝突量 メタ最適化 GA ILS, BS ILS ILS TPSA 局所最適化 L-BFGS SA Sparrow, SA Sparrow, SA 物理シミュ ✅ 35

15 ● オチ考えてなかった © DeNA Co., Ltd. 36

© DeNA Co., Ltd. 37