Kaggle Santa 2022 参加記

2022年年末から2023年年始にかけて開催されていたKaggleのサンタコンに参加して72位になり銅メダルを取得しました。

最終提出の解法は象限の分割+分割した領域ごとにTSPに帰着させて最適化をしました。TSPの最適化には LKH を使用しました。

サンタコンは毎年行われているコンテストで、機械学習系のコンペとは異なり競プロマラソンマッチ系の問題が出題されている。時間もあり、せっかくだったので出た。

Kaggleのアカウントは2022年の6月ごろから持っていたが、コンテストへの参加はしていなかった。アカウントを取った理由はリーダーボードを見るためだった気がする。

問題のDescription、Evaluationにはあまり詳しいことが書かれておらず、ノートブックに問題概要・初期解法が書かれていた。

大体の詳細は以下

毎ターン取れる行動：
- 8つあるアームそれぞれで1マス動かすか動かさないが選べる
- チェビシェフ距離が一定のマスで右回転か左回転か動かないの3通り

達成すべき条件：
- 257 * 257のすべてのマスをアームの先端が踏む
- 最後のターンにはアームが初期状態と同じでなければならない

評価値：
- 各ターンの移動のコストの総和の最小化
- reconfiguration cost: √(1ターンに動かしたアームの数)
- color cost: (前のマスの色と移動先のマスの色の差の絶対値) * 3

解決すべきこととして2点悩むところがあった。

1. アームの動きが厄介で、常に隣のマスに移動できるとは限らないし、あるマスに対して表現できるアームの状態数が大きい。

2. グリッドマップ上のハミルトン閉路の作り方が不明。

1については象限を分割すると、アームの縦移動担当、横移動担当で分けることができるため解決。

2は "2dgrid hamilton" などで検索して出てきた code forcesの記事を参考に最小全域木を求めて構築した。

記事中ではランダムコストとしているところを変更していた。

繋がなかった場合のコスト (図中の C1, C2の隣接している2マスのコスト * 2)から、繋いだ場合のコスト (図中の青の点線のコスト * 2)を引いた値を辺のコストと置いた。

この解法で76931点が出て当時は10~20台に入れていたので本腰を入れることにした。

本腰を入れるといいつつ中盤はほとんどスコア改善ができていなかった。

グリッドのまま山登りの操作を考えていたが、ほぼ効果なし (全体で-100程度)だったのと、最小費用流で最適なパスを探していたがコーナーケースを解消できなかった。

考察供養

偶奇で頂点を分けて流量2のフローを流せば巡回路が取れるが、下のような例が取れると解消できない。

コンテスト終了1週間前にリーダーボードを見たらメダル圏外に落ちていたため、やる気を出した。

グリッドマップのまま経路の最適化を行うのではなく、全点間に十分大きいコストを設定することでTSPに帰着させた。

本来のコストを1000倍に、移動不可能なマスのコストを10000とした。

始点と終点には特殊な頂点を導入してコストを1で接続させた。

ついでに斜め移動も可能にしておき、LKHに解いてもらい回答をデコードして提出した。

象限ごとにLKH解法を導入していったときのスコア遷移

結局最終提出ではマス目のエンコードとデコードしかしてない、、