最初のバージョンでは、ローダー（ロボット）の動きを整理しました。 ループに対する保護のために、深さで再帰的にソートされ、渡されたすべてのオプションが配列に保持されました。 彼は、ゲーム内でボタンを押す順番を示す文字列の形で決定を発行しました。 このシーケンスをMacroExpressプログラムにダウンロードしましたが、既にゲームウィンドウにクリックが送信されています。 クリックの送信間隔を調整することにより、レベルの変化を便利な速度で見ることができます。
ボットは最初のいくつかのレベルを決定し、次のレベルで数日間立ち往生しました。 このレベルは以前のレベルの2倍でしたが、解決策を見つける時間は指数関数的に増加しました。 だから答えを待たずに、私は2番目のバージョンを書き始めました。 ロボットの動きは、箱の動きに置き換えられました。 あるボックスから別のボックスへのロボットパスの動きを保存する必要がなくなりました。 ターンごとに、ロボットがどのボックスに移動できるのか、どの方法でプッシュするのかを決めました。
その後、ボットは次のいくつかのレベルを決定し、再び行き詰まりました。 その後、さらにいくつかのバージョンがありました。
-ほとんどのレベルがボックスの100回未満の移動で解決できると仮定して、再帰の深さに制限を追加しました。
-平らな壁に沿ったコーナーや最初の列など、地図上の静的な行き止まりの場所をマークしました。 そこから箱を引き出すことは不可能です。
-コースの単純な分析を追加し、4つのボックスの正方形をシフトするなどの明らかな動的デッドロックを破棄します。
-以前のすべての動きの座標のストレージがハッシュのストレージに置き換えられ、メモリに収まり、検索が高速化されました。
これにより、さらにいくつかのレベルを進めることが可能になりましたが、ソリューションの複雑さが各レベルで大幅に増加することが明らかになりました。 次に、最大レベルの86を選択しました。ボットが解決すれば、残りは簡単に処理できます。
したがって、レベル86。
46個のボックスと156個のフィールドセルが含まれています。 同時に、40個のセルは静的な行き止まりであり、ボックスを移動できる合計116個のセルです。 したがって、異なるオプションの数は116 ^ 46 = 92271483792519010208299118408158326223759549834325815837590809967385695915673894137078445244416を超えません。はい、これは95桁の数です。 〜= 9.2e + 94です。 この場合、移動の最大数は意味をなしません。 この推定値はさらに大きくなりました：最大移動= 100で、平均して各ボックスが4つの方向の少なくとも1つで各ボックスを押すことができる場合、オプションの数は（46 * 1）^ 100〜= 1.9e + 166を超えません。
ヒューリスティックな追加：
-静的な行き止まり
箱を赤いマーカーでマークされた場所に押し込んだ場合、それを壁から引き裂いて目的地に押し出すことは不可能であることは明らかです。 私は事前に地図上でそのような場所をマークし、ボットはソートの過程でそのような動きをしません。
-動的な行き止まり
4つの引き出しを（引き出しや壁とさまざまに組み合わせて）四角に移動すると、それらを互いに引き離すことは不可能になることは明らかです。 ボットは各動きを分析し、そのような正方形につながる動きはしません。
もっと複雑なものはまだ思いつきません。
もちろん、実際のオプションは、動的な行き止まりのカットオフのため、最初の推定よりもはるかに小さくなります。おそらく数桁です。 ただし、この数のオーダーの半分（92271483792519010208299118408158326223759549834）を取得し、各移動の状態を1バイトだけで格納する場合でも、83920425634022658603テラバイトが必要になります。
そのとき、最初のレベルでは機能しないため、「まだ待機する必要があり、ボットはすべての動きを通過する」ことに気付きました。 アルゴリズムの何かを根本的に変更し、各ターンでより複雑で時間のかかる分析を実行する必要がありますが、オプションのより大きなサブツリーは切り捨てます。 しかし、私はこれを行う方法を正確に知りません...多分あなたは私に助言することができますか？ グラフ、アリアルゴリズム、ニューラルネットワークの分野のテクニックを使用しますか？