- ステップバイステップ。 サプレックスとは異なり、反応は重要ではありません。
- 決定論。 偶然の要素はありません。どんな位置でも心の中で計算できますが、通常は非常に困難です。
- 概念のさまざまなパズル。 このおかげで、ゲームは、たとえば数独よりもずっと遅くなります。
- プロセスに意味を与える冒険的な環境（メインミッションでは、DRODの仮想世界を少しきれいにします）。
パズルは、38x32のセルルームにいるすべてのモンスターを殺すことです。 プレイヤーは、1つのセルを占有し、剣を持ち、8つの隣接するセルのうちの別のセルを占有するキャラクターを制御します。 ターンごとに、8つの隣接するセルの1つに行くか、剣を回すか、待つことができます。 その後、生き残ったモンスターは順番に交代します。 プレイヤーが立っているセルを占領できる場合、プレイヤーは負けて部屋の最初に戻ります。
ゲームへの追加の関心は、部屋の通路の速度記録の表（動きの数による）によって与えられます。 彼女は私たちの目標です。 しかし、概念的に異なるパズルと天文学的な数のオプション（毎回11の移動オプションがあり、可能な部屋の状態の総数はチェスよりもはるかに多い）で、コンピューターをゲームにどのように適用できますか？！ 唯一の方法があります-タスクの知的部分を人に転送し、計算された部分（移動回数によるソリューションの最適化）をコンピューターに転送することです。
タスクを開始したとき、私は成功を期待していませんでした。 最終的に、DRODの部屋は非常に複雑なので、1か月間考える必要があります。 しかし、それでも私はチャンスをとることに決めました。
最初に行わなければならなかったのは、ゲームモデルを単純化して動きのシミュレーションの速度を上げることでした。 この単純化のため、多くの要素は、この状況で同等の要素または類似の要素に置き換える必要があります。または、パズルパーツのソリューションのみを最適化する必要があります。 第二に、部屋の状態を保存するコンパクトなスキームを考え出し、アーカイバを使用する必要がありました。そうしないと、ハードディスクのスペースがすぐに消えてしまい、IO速度がパフォーマンスに著しく影響します。 その後、次の単純なイテレータが作成されました。
- 現在の位置のセットからすべての可能な移動を行います。 この場合、ハッシュテーブルを使用して同一の位置が削除されます。
- いくつかの評価関数に対してN個の最適なオプションを選択します。 （評価関数の値の離散性により、それらはNよりわずかに小さいことが判明する場合があります）
- 最適なオプションを印刷して、最初のステップに戻ります。
最初の部屋の最初の評価関数として、プレイヤーの部屋にいるモンスターの数、プレイヤーのy軸に沿った座標が選択されました（これは部屋の仕様によるものです）。 N = 100,000オプションのみで開始した後（これは5移動後のオプションの数に対応し、300移動の典型的なソリューションの長さである）、数時間の操作の後、プログラムが部屋を通過することができなかったときの驚きを想像してください（より正確にその主な部分は、残りのモンスターを簡単に終わらせることができます）、その間、私は1日以上戦闘に失敗しましたが、この部屋に最適な人間のソリューションよりもほぼ2倍速くしました！ その結果、タンデムの「私が発明した評価機能」とピッカーが非常に大きな割合の部屋を通過することができました。 サポートされていない要素、合理的な評価機能とトラップを思い付かない部屋（同様の問題を抱える「汚れ」が残っている）によってのみ停止できました。
トラップドールは、一度だけ立つことができるセルです。 あなたが彼女を離れるとすぐに、trapが倒れ、虚空が形成されます。 各trapdorはオプションの数を2つ増やしますが、通常はエリア全体を埋めるため、10 ^ 5も10 ^ 8のオプションも役立ちません。 プログラムは、多くの本質的に同じオプションを計算し始めます。その間、素晴らしい瞬間に、正しいオプションは計算されません。 状況は絶望的だと思われます。 だから、私は必死にそのような部屋の解決策を見つける必要があるまで、考えました。 アルゴリズムを簡単に修正することで問題が解決することがわかりました。 評価関数fに関してN個の最適なオプションを選択する代わりに、ランダム* exp（-const * f）に関してN個の最適なオプションを選択する必要があります（このアイデアのアニーリング方法のおかげです）。constは天井をよく見る人によって決定されます。 。 実際、constが無限大になると、通常の選択スキームが得られます。 ただし、ボードとして、新しい方法では評価関数をより正確に選択する必要があります（以前は、評価関数fが定義する状態のセットを注文することが重要でしたが、現在は値自体が重要です）。 私が必要とする部屋で、このアプローチは良い解決策を見つけることができました。 評価関数として表現できない残りのトラポドールのトポロジーはしばしば重要であり、ランダム性の使用は合理的な分岐の程度が大きくないソリューションオプションを傷つけるため、トラポドールの一般的な問題は未解決のままであることが認識されるべきです。