Santa 2023 : The Polytope Permutation Puzzleに挑戦| Kaggleチャレンジ記録

Kaggleのコンテストの「Santa 2023 – The Polytope Permutation Puzzle」へチャレンジした記録です。私が行った取り組みを時系列でまとめています。結果は、1067グループ中34位の銀メダルでした。

相変わらず、微妙な順位でしたが、今回のチャレンジも記録に残したいと思います。

他のkaggleチャレンジ記録はこちら

CommonLit（2023）に挑戦| Kaggleチャレンジ記録

惨敗したICRコンペの取り組み内容まとめ|kaggleチャレンジ記録

Santa 2023の概要

cube, wreath, globeという３種類のパズルを解くコンペです。

cubeは、ルービックキューブです。サイズは2×2〜33×33で、一部のキューブはブロックの位置をきちんと揃える必要があります（4×4以上のキューブでは内側のキューブが存在するが、普通のキューブの場合、内側のキューブは色が揃っていれば別の場所においても揃ったとなる）

wreathは、ハンガリアンリングと呼ばれるパズルだと思います。2つの輪があって一部を共有しているパズルです

globeは、地球儀パズルに似ていますが、独自のパズルみたいです。

このコンテストでは、スクランプルされたこれらのパズルを揃える手数の総和を競います（少ない方が上位）

Santa 2023の成績

結果は、３３位の銀メダル🥈でした（３４位でしたが後日繰り上がりました）。

メダルを取れたことは嬉しいですが、もう少し頑張れたんじゃなかったかと悔しさもあります。

以下、取り組み内容です

コンペの内容を理解する

まずは、キャッチアップ

今回は、いつものサンタコンペに比べてルールの理解は難しくありません。与えられたパズルを少ない手数で解くだけです。

ただ、グラフィカルに提示されているわけではなく動かせるパターンが数列で与えられる形です。

数列の情報だけでは難しかったですが、パズルをビジュアル化してくださった方のおかげで、どんなパズルかを簡単に理解することができました。

例えば、４マスあって２マス目と３マス目を交換する操作は、（0, 2, 1, 3）のような数列で与えられます（0→0, 1→2, 2→1, 3→ 3へ移動することを示しています）

また、サンプルの提出ファイルに解法の１つが与えられていました（逆に実行するとスクランプルの手順）。

このサンプルを短縮していくという手法も使えそうだと思いました。

ただ、現実は、サンプルの手数を削減するアプローチではメダルには届きません。なんとかパズルを解く必要がありました。

公開コードを変更してみる

いつものように、公開コードを見つつ変更を加えました。

Brute Forceを最初に見ました（いわゆる総当たりです）。

また、これを拡張したBidirectional Brute Forceという公開コードも公開されていました。

こちらは、初期状態と目標とする状態の双方から探索することで、より深い探索を総当たりする方法です。

このやり方で、2×2のルービックキューブを含めたいくつかのパズルについては、最適解が求められるようです。

コードの中身を見ると、幅優先探索を行なっているだけで特に難しい感じはありませんでした。

この２つを修正して使ってみましたが、それほどスコアが伸びそうにないののと、Pythonでは大きなパズルを解くには速度的に厳しそうな感じがしたので、独自のコードを作ることにしました。

速度面を考慮して、コード作成にはGo言語を利用しました。Goを使ったのは、AtCoderにGo言語で参加しているので、グラフ探索のコードを書くのに慣れている言語だったからです。

Go言語は選んだのは書き慣れていたからです。C++でも良かったのですが、C++は環境を作っていないので面倒でした。

独自のコードを作成

作成した独自のコードは大きく3つになります。

独自コード① bi-directional BSF（ビームサーチの変形）

公開コードにあったbidirectional brute forceをベースに改良したものになります。

初期状態と目標状態（完成状態）からBSFして枝を伸ばしていくところまでは同じですが、次の遷移をするかどうかをルールにより決定することで枝刈りする方法です。

例えば、ルービックキューブの同じ部分を3回回転させるのと、逆回転させるのは同じです。こういった無駄な動作を枝刈りしてBSFを行います（例のやつは、同じノードに行き着くので枝刈りしなくてもよいですが）。

ただ、ルールを追加したことで、「本来は経路になりえたもの」もカットされてしまいますが、これをしないとメモリと処理量の関係上、手数が伸ばせません。

ビームサーチの亜流みたいな感じの実装になっています。枝刈りのやり方がポイントになるのですが、これが難しいです。

なお、状態はハッシュ化して管理することでメモリを削減しました（ハッシュ化されない状態を持っているのは次に探索を行う状態のみ）。

公開コードがかなり参考になりました

双方向からBSFをする例については、以下の記事も参考にしてください

両端から幅優先探索（BSF）って演算量を削減する｜高速化の手法

独自コード② BSF+IDA*

ルービックキューブのソルバーについてWebで検索すると反復深化深さ優先探索（iterative deepening depth-first search、IDDFS）というものが見つかりました。

IDDFSは、深さ1から始めて、ルートが見つからなければ2, 3, …と深さを増やしながら探索する方法です。BSFと違って、経路を記憶しておく必要がないのでメモリが節約できます。

ただ、深さを変えながら処理するので処理時間がかかりますが、二分木の場合で深さNを探索するのと比較して1,2,3,…Nを探索する時間は2倍程度に抑えることができるそうです。

bi-directional BSFでは、メモリ制限で探索ができないので、こちらも実装しました。

実装したのはIDA*はそれの改良版で、ルールを加えて探索を打ち切るものです。

今回の実装では、まず目標状態からBSFを一定量しておき、初期状態からIDA*を行う形としてました。こうすることで目標状態が増えるので探索で見つかる確率を上げることができます（運がよければBSFで経路が見つかることもある）

探索をやっていると、たまに深い探索がある場合があって、それ以外はサクサク見つけられることが多かったです。bi-directional BSFの場合は、深い探索の部分でギブアップしてしまいますが、こちらはメモリが少なくても探索は続けられるので時間は少しかかるけど、最後まで探索できた感じです

独自コード③ 経路圧縮のための探索プログラム

最後のコードは、解を見つけるためのものではなく、見つけた経路を圧縮するためのものです。

最初に初期状態から目標状態まで、現在見つけている経路を貼ります（グラフを作ります）

その後、それぞれの状態から遷移可能な状態を、指定した数だけ追加します。

その後、BSFを行うことで最短経路を求めるという方法です。

下図では、灰色のパスが現在見つけているパス、赤い線が最短経路となります。

なお、経路として追加するかどうかにルールを設けており、また、確率的に追加するかどうかを決定する（ランダム要素）を加えることで、同じ制限内で深さを伸ばすことができるようにしています。これにより、偶然距離の長いパスを見つける可能性が発生します（実際、一気に1000手近く短縮したことがありました）。

これを、100手づつなどに区切って行うことでより短い経路を見つけることができます。

実際に使ってみると、IDA*などで見つけたパスを10%くらいカットすることができましたので、かなり効果的だったと思います。

コンペの後半に同様のコンセプトの公開コードがアップされていて、ドキッとしました

ルービックキューブのソルバーを使って解く

ルービックキューブに関しては、公開されているソルバーを使って解ける範囲は解きました。

rubiks-cube-NxNxN-solver

kaggleのdiscussionとcodeで紹介されていた、rubiks-cube-NxNxN-solverを使いました。これを使えば、かなりのキューブを解くことができます。

ターゲットが特殊な配置のキューブについては、公開コードを少し工夫すれば解くことができます。

RCube

RCubeは、ディスカッションで紹介されていた65536のサイズまで解けるソルバーです。

こちらは、入力も結果出力もない状態で（シャッフルして、解を求めるまでの時間が表示されるだけのコード）、これを改変して初期状態を設定して、結果をファイル出力できるようにしました。

小さな規模のキューブでは、イマイチな解しか出力されないのですが、33x33x33については、rubiks-cube-NxNxN-solverが80000前後の解法だったのに対して25000手ぐらいの解を出力できました。

その他ソルバー

これ以外にもいくつかのルービックキューブのソルバーを適用して解を求めました。3x3x3と4x4x4は少ない手数を出せるものもありましたのでそちらの結果を採用しています。

ルービックキューブについてまとめ

基本はソルバーを使いましたが、後半では自作のツールでも一応解けるようになりました（9x9x9まで確認）。33x33x33まで解けないことはなかったのですが、キューブ専用のソルバーではないので、処理時間が遅くて（33x33x33は40時間で半分くらい）諦めました。解としてはそれなりに少ない手数を出力していましたが、時間が足りなかったです。

Wreath、Globeは自作ソルバーで解けた

wreath

bi-directional BSFで、wreathはかなりの部分まで解くことができました。ただ、規模の大きなものが解けない。

これについては、移動パターンを増やすことで解決できました。

30~40手くらいまでは、このやり方で見つけることができました。それを超えるとメモリ（8GB）では探索できませんでした。

wreathの場合は、l,rの2手だけなのですが、これをl(n), r(n)のようにn個動かすというパターンを追加して探索しました。

これによりl, l, l, l, l, r, l, l, l, l…のような長いパターンも少ない深さで探索できるようになり、wreathを解くことができました。

このやり方で、wreath_100/100までとりあえず解くことができました（ただし、手数は少し多め）

このやり方だと、lとl,lが同じ手数になるので、出力された手は最短ではないのですが「解けた方が手数が減るのでOK」ということで妥協しています。

なお、このやり方は、globeでも有効でした。

globe

globeもbi-directional BSFで小さなものは解けるのですが、大きなものはメモリがなくなってしまいました。探索時間はかかるけど必要メモリ量が少ないBSF+IDA*を使うことでglobe_6/10までは問題なく解くことができました。

残ったのは、globe_3/33とglobe_8/25です。この２つについては力技で解くことにしました。

やり方はシンプルで、小さいパズルで1..n-1個目までの位置は変更せずにn個目のピースをn以降の位置から持ってくるパターンを列挙して、それを補正してパズルのはめ込みに使うという方法です。

頭で考えるのが大変だったので、小さなパズルで実際にソルバーに解かせて列挙し、大きなパズルに適用できるパターンだけ抽出しました

上位解法をみても、幾つかの駒だけ変化するパターンを見つけて適用するというのは王道の解法だったみたいです

手順は以下のようになります

• globe_1/8で、はめ込みパターンを作成する
• 作成したはめ込みパターンは位置を補正すればglobe_3/33でも使える
• 後半のはめ込み（IDA*で手数が増えすぎて厳しいもの）については、作成したパターンを利用してルールベースで解く

この方法がうまくハマってglobe_3/33とglobe_8/25を解くことができました。

途中まで（簡単に作れる部分）は、経路探索で埋めていって、後半に関してはパターンを使うというやり方は、1位の方もやられていたのでやり方として良かったのかもしれません。ただ、レベルが違いますが・・・

感想とか

cube_33x33x33の１つだけ解けなかった

結局、解けてないのは、33/33/33のスーパーキューブ（各ブロックを正しい位置に配置しなければならないルービックキューブ）だけでした。これについては、自作のIDA*のコードでいけそうな感じでしたが、半分解くまでに40時間ほどかかり、後半はもっと時間がかかりそうな雰囲気でしたのでギブアップしました（コンペ終了3日前）。

公開されているルービックキューブのソルバーを修正して対応させることも考えましたが、根本的な部分から変更しなければならない感じでしたので断念しました。

最後の追い込み

時間がなくなってきたラスト2日は、globeの揃えていく順番の見直しと、経路圧縮のための探索プログラムを使った経路圧縮に専念することにしました。上の順番との差が数万だったので追いつける気はしなかったのですが、とりあえず行けるとこまで削ろうという感じです。

やってみると思ったより削れて、2日で2万弱の手数を減らすことができました。

とりあえず、ここまでやって終了

感想

群論が得意な人、そもそもルービックキューブのソルバーに詳しい人などには有利なコンテストだったのでないでしょうか。

TOPと自分の順位で６倍近い手数の差がついていたので、「解ける人は解けた」感じなのかと思います。

自分は、グラフ探索のコードは慣れているのでかけますが、ルービックキューブなどのソルバーにそもそも触ったことがなかったので結構苦労しました。

始めた時は、今回はメダルは無理だと思っていましたが、最終的には銀メダルまでスコアを伸ばすことができたので良かったです。

今回の課題に取り組んで感じたのは、ルールベースによる枝狩りが重要だったということです。

また、パズルの解法をきちんと理解することも重要だったと思います。解法を理解してパターン化すれば、それをプログラムに組み込むことで探索を減らすことができます。33x33x33のキューブなどは、これなしでは解けない気がします。

不得意だったので逃げていましたが、定石パターンを見つけるのが大切だったと思います

とはいえ、自作のソルバーでも9x9x9のルービックキューブまでは解けたのが嬉しかったです。

最後の１週間はWreathとCubeの2つに注力していましたが、今考えるとWreathの方に注力した方がもう少し成績を挙げられた気がします。

まとめ

以上、santa2023の取り組み内容について書きました。kaggleのコンペでもアルゴリズムよりなコンテストなので、機械学習やディープラーニングが不得意でも参加できます。