投稿のタイトルにある「タワー」とは、サイトbashni.orgにあるパズルゲーム「Sarov Towers」を意味し、その存在はHabrapost タワーの建設方法から学んだことをすぐに言わなければなりません 。
このゲームとこのサイトに精通している場合、これ以上の説明は不要です。そうでない場合は、両方のリンクを調べて内容を理解できます。
まあ、あるいは、怠laなプログラマーがパズル解決プロセスを自動化したかったのか、圧倒的なIQを持つ人が何時間も苦労していたレイアウトと、その結果について読んでいただけます。
エントリー
だから、2011年10月に、私は前述の記事を偶然見つけました。そして、さまざまなパズルへの欲求のために、このゲームに「夢中になりました」。 ゆっくりとタワーを収集し、時間の経過とともにどんどん良くなりますが、多くの場合、経験豊富な対戦相手であることが判明したか、すでに達成した結果を再現できませんでした。
もちろん、私が提供したリンクからそれについて学ぶ時間がなかった場合、ゲームの競争力のある要素について言及する時が来ました。 要するに、タスクはパズルを解くだけでなく、他のプレイヤーよりも少ない動きでそれを行うことです。 なぜなら 各レイアウトには一意の番号があり、すべてのアセンブリの統計がサイトに保持されているため、すべてが非常に明確に表示され、完全に競争力のある雰囲気を作り出しています。
そして今、再び追い越しに失敗するか、タワービルで名誉あるスポーツの達人に追いつくことさえできなかったので、私は「ドーピング」、すなわち パズルを解くためのプログラムを書いてください。 結局のところ、ロボットは進歩的な第三千年紀で人間の代わりに機能するべきではないのですか？
追加のインセンティブは、PapaBubaDiop ハブで有名なゲームの作成者であるという事実でした彼は、ほとんどの塔を数分で解決できるボットをすでに作成したと主張しました。
一般に、問題を遅らせることなく、コードを書き始めました。
なぜなら 私の主な作業ツールはJavaScriptであり、ゲームはブラウザベースであるため、この言語でプログラムを作成することは自然なソリューションになりました。 もちろん、多くの人は、解釈されたスクリプト言語は大量の情報を処理するのに最適ではないと主張するかもしれません。これをすべてC（またはAsmで「本当に」）で書く方が良いでしょうが、 。
私はプログラムからブラウザーのプラグインユーザースクリプトのようなことをするのが面倒で、開発コンソール（FFとChromeのF12ボタンによって呼び出されるもの）にコードをコピーアンドペーストするだけでした。 実際、私が知っている最速のJavaScriptエンジンを備えたChromeがテストサイトになりました。
この場所の読者がゲームのルールを少なくとも流fluentに読んでいない場合は、 この素晴らしいページでそれを行う必要があります。すべてが非常にアクセスしやすく、アニメーションの例もあります。 幸いなことに、これらのルールは非常にシンプルで簡潔です。
知り合いになりましたか？ いいでしょう
最初のパンケーキはゴツゴツしている
プログラムの最初のバージョンは非常に原始的で、すべての可能な解決策を左から右に（列の順序で）単純にチェックしました。 最初のレイアウトが取られ、最初の列が検索され、ルールによって許可された移動が可能になり、移動が（仮想的に）行われた後、アルゴリズムの最初のポイントに再帰的に戻りましたが、ベースはタワーの初期位置から取得されませんでしたが、移動後に何が起こったのかがわかりました。
そして、非常に多く、何度も、ありふれた決定木です。
次の動きでパズルが解決された場合（つまり、すべての塔が組み立てられたことが判明した場合）、決定は記憶され、移動に費やされた回数が示されました。 プログラムの結果によると、見つかった移動の数が最も少ないソリューションが使用されました。
基本的な最適化の1つは、すでに見つかった解を超える長さの動きの枝を切り落とすことでした。 そのようなブランチからの使用はありません。
2番目の最適化は、「隣接ブロック」のチェックでした。 隣接する番号を持つ同じ色のブロック、例えば このようなブロックは折りたたみ後に結合され、同時に移動できるため、機会が生じたらすぐにすべての「隣人」を接続し、オプションの余分な分岐を作成しないことを決定しました。 その結果、プログラムがたとえば赤3と4を検出した場合、常に4の上に3を配置してから、検索を続行します。 これにより、スクリプトの実行時間が大幅に短縮されました。 より多くのブロックが「スタック」するほど、残っているオプションは少なくなります。
このスクリプトは、「アフリカ」の塔（最小レベルの難易度）で十分に機能し、1〜2分で解決策を見つけましたが、それより短い場合もありました。 しかし、「ハノイ」では、彼はすでに15〜30分間遅れており、「サロフ」については、私も怖がっていました。
さらに、数回、プログラムは、可能なすべてのオプションを通過した後でも、プレーヤーによって達成された結果を繰り返すことができず、1〜2ステップ遅れていることに気付きました。 後で判明したように、この理由は、「ブロックネイバー」の最適化でした。 それは私の経験的仮定のみに基づいており（「頭」で遊んだときに自分でこれを行いました）、客観的な議論には基づいていません。
ただし、この最適化を完全に無効にすると、パズルを解く時間が屋根を通り抜け、アフリカの塔でさえ15分を超えました。
何かを変える必要がありました。
エラー処理
まず、「隣接ブロック」を接着する問題に対処する必要がありました。 問題は、それらが結合したときに、より小さなブロックの「シート」を失うことでした。 たとえば、同じ色の異なる列に「接着されていない」4と5がある場合、それぞれに0〜3の値を持つブロックを配置し、これら2つのセットを並行して操作できます。 多くの場合、これは最適なソリューションにつながった1-2の動きを保存するために重要でした。
一定の結論を出した後、私は、トップブロックのトップブリックが0または1であるブロックのみを確実に接着できるという結論に達しました。 なぜなら この場合にのみ、「シート」の損失に悩まされないことが保証されています（とにかくレンガがゼロのブロックには他に何も置くことはできませんが、ユニットのあるブロックにはゼロのみを置くことができるため、2つの「シート」を保存する必要はありません。 「着陸ブロック」の唯一の可能なバリアント）。
第二に、オプションの回避の順序を最適化する必要がありました。 最適なオプションが右側にある場合、ツリーを左から右にソートすることは非常に効果がありません。
各移動の後、その時点で行われた移動の合計数と「弱い」移動の数の差として、タワーの現在位置の「コスト」を評価し始めました。 私は弱い中間移動を呼び出しますが、それはすぐに目的の結果になりません（たとえば、5に赤い3を置いた場合、後で4にシフトする必要があるため）。 したがって、ソリューションの全体的な進捗状況に関連する弱い動きの数が最も少ないオプションが、最高の評価を得ました。
オプションは、コストを考慮してキューに入れられます。まず、最高の評価を持つオプションが決定されます。 それらは最適なソリューションになる可能性が最も高いものです。 この最適化自体は無意味です。 最良の結果を保証するために、すべてのオプションをソートする必要がありますが、すでに見つかった長さ（およびコスト）を超える決定ブランチを破棄することと組み合わせて、検索時間を桁違いに短縮できました。 短い（常に最良とは限りませんが）ソリューションは、通常は最初の数秒で非常に迅速に見つかりました。その後、最適なものを見つけることに集中して、「長い」ソリューションの巨大なブランチをすぐに破棄できました
さて、成功の3番目のクジラは、オプションのさまざまなブランチ（移動数が異なる場合でも）がタワーの同じ位置につながる可能性があるという偶然の観察でした。 明らかに、これらのオプションをさらに開発しても、ブランチごとに個別に考慮する理由はありません。 初期位置が同じであれば、決定ツリーは同じになります。
各移動後に各位置のテキストナゲットを作成し、ハッシュテーブルに配置し始めました（ご存知のように、これは私が使用したJSのオブジェクトの動作の基礎です）。 そのような重複ブランチは予想よりもはるかに多く、それらを破棄することで、検索時間を数倍短縮することができました。
ここで言及する価値のないマイナーな最適化がいくつかありました。たとえば、ループの動きに対する保護や、空の場所から別の場所へのブロックのブロックなどです。 これはすべて明白であり、アルゴリズムに大きな影響はありません。
ロボットに栄光を！ すべての人を殺します！
最終結果は私の期待をすべて上回りました。 このスクリプトは、ほとんどのアフリカの塔をわずか数秒（平均1〜3）で解決しました。ハノイ-10秒以内、ロシア人（サロフ）-ほとんどの場合30秒から10分、最も難しいレイアウトでは20-30分最初の100の「複雑な」レイアウトを含む。
結局のところ、ほとんどの中規模で複雑なタワーは、競争力の要素を考慮しても（つまり、プレイヤーがお互いの結果を打ち負かすために数回試行した後）、人々によって最適に解決されません。 通常、スクリプトは解決策1-2を見つけ、場合によっては3-5の動きが人間の最良の結果よりも短くなります。
もちろん、解決策を見つける速度の観点から、鉄の脳は人間の脳よりもはるかに先を行っています。
しばらくの間、私はメガブレインを装って楽しんでいましたが、以前は知らなかったプレイヤーからの1週間または2日間の勝利の後、「ミツバチは何かを疑い始めました」、そしてプロセスは非常に退屈になりました。 。
2日間の脳の努力の結果が無駄にならないように、私はこの話をハブでここに伝え、プログラムコードをパブリックドメインに置くことにしました。
なぜそうするのかを説明します。
このゲーム自体は素晴らしいものであり、その創造者PapaBubaDiopに感謝を表明したいと思います。 ただし、そのハイライトになるために呼び出された非常に競争力のある要素も問題になる可能性があります。 現時点では、最適なソリューションを迅速に見つけるボットを作成できることは明らかであり、これはかなり短時間で実行でき、多くの（すべてではありませんが）実行できます。 これは、ボアになれるかどうかを理解するために、明らかに、ロアのハブレライザーが最近私のボットより悪くない（または速度が優れている）独自のボットを作成したという事実によって証明されています。
私はこの記事を書いてコードを投稿しているので、このゲームの競争要素に真剣な人たちは、私がボットになれる、ロアがボットに、誰もがボットになれる、ということを理解しています。 そして、ボットの所有者がそのような目標を設定した場合、あなたはそれについて決して知ることはできません（あなたがボットであっても、人のように見える方法はたくさんあります）。 そして、純粋に技術的な意味では、ボットを検出せず、停止しないでください。
競争の概念やその結果との関係を再考することしかできません。
PSもちろん、私はコードをサポートしません。たとえば、ゲームのウェブサイトで何かが変更されて塔の初期位置が読み取れない場合は、自分で修正したい人に許可してください。
PPS私はほとんど忘れていました:) pastebin.com/AJyR2E71-ここにコードがあります