第32回高専プロコン競技部門の実施に感謝と敬意。ありがとうございました。それはそうとして、競技部門が企業賞を頂けなかったのがかなり悲しかった。
※この記事の日付は git の記録をもとに思い出しています。実際の開発と数日分ずれている可能性があります。
8月以前
チームで開発方針について考える。
- OpenSiv3D で開発することを決める
- 入力形式を扱う構造を始めに作ってヘッダにまとめるのがよいと主張する
- （画像の復元（ジグソー）をしてからが本番のスライドパズルなので）ジグソーを優先的に、ほぼ 100% 片づけるべきと主張する
8/13
チームメイトの first commit を確認。
8/14～16
データ形式を扱うプログラム (data-format) をアップロード。ジグソーパズルソルバ開発のためのもので、課題の入力とジグソーパズルの入出力のみに対応する。ビジュアライザで使いまわすので、ドキュメントを丁寧に書く。
ジグソーパズルのソルバは「隣接コスト関数」「コスト関数を用いて復元」の 2 段階にすべきと考える。
初 Pull Request で緊張する。
8/17～9/17
RGB 差、 Lab 差、貪欲法（端から貪欲に埋めるだけ！）を実装。実装中に見つかった data-format のバグ、改善案を修正
ジグソーパズルの解法を google scholar でググる。
9/17～9/19
こちら(https://arxiv.org/pdf/1711.06768.pdf)に示されている遺伝的アルゴリズムが一番正確性が出そうなので、勢いよく実装。交叉は素直に実装したが、外殻のほうは平衡した 2 分木のようにマージする妥協実装をした（そしてこれが最後まで使われる）。 16×12 分割した写真などが一発で揃って気持ち良くなる。
9/20～9/21
課題の出力を管理する構造体を作る。その直後にたくさんブランチが生えて開発が活発になる。
9/22～9/25
data-format を修正・改善しながらスライドパズルを端から確実に揃える決定的アルゴリズムのソルバを作る。
9/26～9/30
ビームサーチ実装。すぐに chokudai サーチに書き換え。
9/30～10/2
メモリ管理用の構造体を改良して探索のメモリ効率を改善。
他の解法を試行錯誤。
10/2～10/6
他の解法を試行錯誤。
chokudai サーチと決定的アルゴリズムを一体化する。 chokudai サーチを深さで分割し、並列処理にする。
なお、この時点では選択回数が 2 以下に収まるようにしている。
いい感じのビジュアライザができていて感動する。
10/7
局所改善で完全に揃わないか試す。
10/8～10/9未明
10/8 午前に、 chokudai サーチと局所改善で揃わなかった部分は十分手動で揃えられることに気づく。手動編集可能なビジュアライザが必要になる。
それとは別に、小さいサイズの対策をする。交換数が平均 $\Theta(l^2s)$ ( $l$ は長辺、 $s$ は短辺) となると予想したので、交換およそ $0.7l^2s$ 回分を探索するように設定。
日中に設計、夕方～深夜（ほぼ徹夜）にビジュアライザ開発。 1 回戦に備える。
10/9（本番1日目）～10/10未明
対戦よろしくお願いしました。 1 回戦第 5 試合 1 位（全体 2 位）。対戦ありがとうございました。
ポスターの画像（一番難しい）を入手。ビジュアライザの機能を使ってなんとかジグソーパズルを揃えることに成功。この間に徹夜開発のビジュアライザにバグが見つかり、深夜に修正。
初めの選択位置をすべて考慮して探索キューに入れるとした。
選択回数の有効利用を考えたが、失敗した。諦めて交換回数を $(0.55～0.7)l^2s$ くらいで 4 パターン用意。
10/10（本番2日目）
対戦よろしくお願いしました。通信トラブルで困惑。準決勝第 1 試合 1 位（全体？位）。対戦ありがとうございましたぇえええあああああ！！？（発狂）
対戦よろしくお願いしました。決勝 2 位。対戦ありがとうございました。
成果物の自慢
このビーム（chokudai）サーチの特徴として以下を挙げる。
- 評価関数は目的地までのユークリッド距離の平方と $2$ 点スワップの個数で定義したため、差分更新が高速（盤面サイズにかかわらず定数時間）
- 交換 $7$ 回以下をまとめて $1$ 回の操作とみなし、操作 $1$ 回分は全探索し、評価値ベスト $20$ のみキューに入れる
実際、競技で使用したアルゴリズムは $1.5 \times 10^6$ 通りの盤面をキューから取り出して探索し、 $1.4 \times 10^9$ 回、速度にして $10^7$ 回 $/(\mathrm{thread} \cdot \mathrm{s})$ の差分更新を行う。これによる大きめの探索量によって、選択回数を有効に利用したチームの一部よりもよい成績を得られたと考えている。
また、直前に用意したビジュアライザは GUI をジグソー・スライドで $2$ 種類切り替えられる。ジグソーではビットマップが描画されて「指定した矩形範囲を回転/トーラス平行移動」「 $2$ 点スワップ」という操作ができ、スライドではピース番号が描画されて「操作列の末尾に交換/選択を挿入」「操作列末尾を $1$ つ削除」という操作ができる。特にジグソーパズルの操作は前で挙げた遺伝的アルゴリズムの失敗例に即していて、ポスターの画像を揃える際には鍵となる。