RaceTrackの鉛筆と紙のゲームの AI に適したアルゴリズムを知っている (または提案できる) 人はいますか?
各ステップには 9 つの可能な選択肢があり、適切な戦略を決定するには少なくとも 6 ～ 10 ステップ先を見る必要があるため、ブルートフォースは、境界との交差のためにいくつかの選択肢を除外できたとしても、非常にコストがかかります。
現在、どの選択肢を除外するかを決定するために、各選択肢に何らかの品質値を割り当てようとしていますが、そのような品質値を割り当てる方法に関する適切なルールはまだわかりません.
ここに快適に収まるには少し長すぎる (187 行) C++ ソルバーを作成したので、代わりにペーストビンに入れました: http://pastebin.com/3G4dfTjR。プログラムは、最適な (最小可能な移動数) ソリューションを計算するか、不可能であると報告します。
プログラムをracetrack startX startY goalX goalY [circleX circleY radius]として実行します。
プログラムは、100x100 のグリッドを想定しています。このグリッドには、オプションで、中心と半径を指定した単一の円形障害物が含まれる場合があります。さらに、車の初期位置と 1 つのゴール位置を指定する必要があります。これらの制約は幾分制限的ですが、コードを見れば、一般にアルゴリズムを制限していないことが明らかになるはずです。関連するすべてのロジックはisMoveValid()およびisGoalState()ルーチンにカプセル化されているため、より一般的なバージョンのこれらのルーチン (たとえば、ユーザーがグリッド位置のビットマップを指定できるようにする、および/または複数のゴール位置を指定できるようにする) を使用すると、問題なく組み込むことができます。
わずかな複雑さは、ゴールの場所を開始場所と同じ (または近くにあるが、「反対側」) にすることです。これは、トラックをサーキットにしたい場合に必要なものです。この場合、ソルバーが単純に車を方向転換させたり、すぐに停止させたりするのを避けるために、目に見えない「スタート ライン」を指定し、isMoveValid()このラインを横切る「後方」移動を禁止するように変更する必要があります。
各移動のコストは正確に 1 であるため、4D 状態空間で幅優先探索を使用して最適解を見つけることができます。dx と dy が (x, y) に到達するために使用した速度ベクトルである 4 タプル (x, y, dx, dy) で構成される特定の状態 s にアクセスするときはいつでも、9 つの状態すべてを考慮します。 s から一手で届く。まだ見られていないそのような状態 t について、BFS は常にルートからの最小距離の順にノードを訪問するため、t へのこのパス (つまり、s 経由) は最適であることが保証されます。状態の最適なパスを決定するたびに、前の状態を記録し、最後に完全なパスのトレースバックを生成できるようにします。
BFS はダイクストラのアルゴリズムや A* 検索よりも単純で、おそらく高速です。これらは、移動にさまざまなコストを持たせることができる、より一般的なアルゴリズムです。柔軟性はここでは必要ありません。ヒューリスティックを混乱させる障害がほとんどない場合、A* はより高速になる可能性がありますが、各ステップで最小コスト ノードを検索する必要があり、これは通常ヒープを使用して行われますが、BFS の場合、最小コスト ノードは常に行列の先頭。
ストップウォッチ競馬場 30 3 90 10
Starting at (30, 3).
Goal is (90, 10).
Grid size is 100*100 (W*H).
No obstacle.
11-step solution:
(90, 10) (dx=10, dy=4)
(80, 6) (dx=9, dy=3)
(71, 3) (dx=8, dy=2)
(63, 1) (dx=7, dy=1)
(56, 0) (dx=6, dy=0)
(50, 0) (dx=5, dy=0)
(45, 0) (dx=5, dy=0)
(40, 0) (dx=4, dy=0)
(36, 0) (dx=3, dy=-1)
(33, 1) (dx=2, dy=-1)
(31, 2) (dx=1, dy=-1)
(30, 3) (dx=0, dy=0)
128113 states were examined in the process.
stopwatch: Terminated. Elapsed time: 343ms
stopwatch: Process completed with exit code 0.
ストップウォッチ競馬場 30 3 90 10 50 20 25
Starting at (30, 3).
Goal is (90, 10).
Grid size is 100*100 (W*H).
A circular obstacle of radius 25 is centred at (50, 20).
22-step solution:
(90, 10) (dx=5, dy=-8)
(85, 18) (dx=5, dy=-7)
(80, 25) (dx=4, dy=-6)
(76, 31) (dx=4, dy=-5)
(72, 36) (dx=5, dy=-4)
(67, 40) (dx=6, dy=-3)
(61, 43) (dx=7, dy=-2)
(54, 45) (dx=8, dy=-1)
(46, 46) (dx=7, dy=0)
(39, 46) (dx=6, dy=1)
(33, 45) (dx=5, dy=2)
(28, 43) (dx=4, dy=3)
(24, 40) (dx=3, dy=4)
(21, 36) (dx=2, dy=5)
(19, 31) (dx=1, dy=6)
(18, 25) (dx=0, dy=6)
(18, 19) (dx=-1, dy=5)
(19, 14) (dx=-2, dy=4)
(21, 10) (dx=-3, dy=3)
(24, 7) (dx=-3, dy=2)
(27, 5) (dx=-2, dy=1)
(29, 4) (dx=-1, dy=1)
(30, 3) (dx=0, dy=0)
949565 states were examined in the process.
stopwatch: Terminated. Elapsed time: 3076ms
stopwatch: Process completed with exit code 0.
円形の障害物がグリッドの底をずっと越えて伸びているため、ここでの最適な解決策は、最初に「2 倍に戻る」必要があることに注意してください。
小さなバグ: ゴールの場所を最初の場所と同じに設定すると、投稿されたコードは短い (ただし長さがゼロではない!) 回答を返します。明らかに、これは特別なケースとしてチェックできますが、これに気付いたとき、私はすでにコードをペーストビンに入れていました... :)
A* を推奨する人もいますが、これがおそらく正しい方法ですが、そのアプローチには問題があります。最初に、あるノードから別のノードに移動するための「コスト」は常に 1 であると言いましょう。これは、ステップ数を最小限に抑えたいため、他のコストは関係ありません。
しかし、私が言いたい重要な点は、位置 (x,y) は A* の検索グラフで一意のノードではないということです! ノードは x と y によって特徴付けられますが、車が来るノードの x 座標と y 座標によっても特徴付けられます (または、必要に応じて速度コンポーネント vx と vy によって特徴付けられます)。したがって、2 次元グリッド上で A* アルゴリズムをトラバースすることはできません。実際には 4 次元である必要があります。とはいえ、A* はおそらくまだ道のりです。
ヒューリスティックに関しては、それについて本当に創造的になることができますが、通常の2Dグリッドの各ポイントの距離が事前に計算されている場合、ゴールまでの距離から現在の速度を差し引いたようなものをお勧めします(そのためにダイクストラアルゴリズムを使用します)。これにより、A* アルゴリズムは最初にフィニッシュラインに向かって検索し、できればできるだけ速く検索します。そのようなアルゴリズムは、ルート全体をすぐに計算するのに非常にうまくいくと思います.
ただし、1 つの問題は、A* が常に最適なルートを生成することです。そのため、そのようなアルゴリズムを使用する AI は、対戦するのが楽しくないということです (開始位置が公平であると仮定すると)。
これまでのところ、あなたの質問の重要なポイントに取り組んでいる人は誰もいないと思います。つまり、どうすれば良い「質の値」を思いつくことができますか? AI では、参照する品質値は通常「ヒューリスティック」と呼ばれます。理想的には、ヒューリスティックは、現在の位置/速度を考慮して、フィニッシュに到達するために必要な最小移動数を正確に教えてくれます。実際には、計算がより簡単な方法で解決する必要があります。
重要なガイドラインの 1 つは、優れたヒューリスティックは許容できるものであるということです。つまり、ゴールに到達するためのコスト (あなたの場合、フィニッシュに到達するまでの移動数) を過大評価してはなりません。A* アルゴリズムは、許容できるヒューリスティックがあるかどうかに依存します。
許容可能なヒューリスティックを考え出すための一般的な手法は、元の問題を緩和することです。ゲームでは、ゲームをより簡単になるように変更することでこれを行うことができます (たとえば、ルールを削除するなど)。たとえば、RaceTrack では、トラックをまっすぐにして、より簡単なゲームにすることができます。まっすぐな道では、最善の戦略は明らかに継続的に加速することです。したがって、容認できるヒューリスティックは、現在の位置からゴールまでの距離 (つまり、まっすぐになったトラックの長さ) を計算し、一定の加速度を仮定してその距離を移動するのに必要な移動数を計算することです。
さまざまなルールを緩和することで、他のヒューリスティックを考え出すことができますが、ヒューリスティックの精度と必要な計算量との間にトレードオフが生じることがよくあります。
このドキュメントはあなたを助けるかもしれません
問題を逆にすることから始めることをお勧めします。逆行分析 (チェスのエンドゲームhttp://en.wikipedia.org/wiki/Retrograde_analysisで行うように) を使用して、最後から逆方向に計算し、自分が唯一のプレーヤーであると仮定して、フィニッシュ ラインを通過するために必要なステップ数を確認します。 、与えられた位置と速度。私の考えが正しければ、これを計算する時間は位置の数に比例するはずです。非常に迅速なはずです。
競合他社があなたの道を邪魔しているので、それは絶対的な真実ではありませんが、検索アルゴリズムに非常に優れたヒューリスティックを提供します.
あなたは「各選択肢に何らかの品質値を割り当てる」という考えに言及しています - これはヒューリスティック関数と呼ばれます。多くの AI アルゴリズム (他の人が言及した A* や alpha-beta pruning など) は、プラグインするヒューリスティック関数と同じくらい優れています。
ただし、優れたヒューリスティック関数を作成できた場合、これらのアルゴリズムは自動的に「無料で」はるかに優れたパフォーマンスを発揮します。そのため、優れたヒューリスティック関数の開発に時間を費やす価値は十分にあります。
もう 1 つの角度は、レース全体を最初から事前計算することです。次に、フィニッシュ ラインを通過するまでのターン数を最小限に抑えることが問題になります。便利な最小値検出アルゴリズムの 1 つにシミュレーテッド アニーリングがあります。
それはさておき、このようなゲームに対する遺伝的アルゴリズムの解決策を見るのもクールです. それがぴったり合っているかどうかはわかりませんが、さまざまな入力 (将来の数ターンで予想される壁からの距離、速度、他のレーサーとの距離など) を受け取る「頭脳」を作成し、そのロジックを進化させることは想像できます。遺伝的アルゴリズムを使った脳。コツは、問題を意味のある変更が可能な部分に分解することです。
実際には、それらを組み合わせて、遺伝的アルゴリズムを使用することもできます。標準の AI 検索アルゴリズムにプラグインされるヒューリスティック関数を開発します。
正直なところ、クラッシュした場合にサブツリーを破棄できるため (クラッシュは悪いパスでよくあることです)、制約のあるトラックではブルート フォースはおそらく問題なく機能します。