artificial-intelligence - ゲームプログラミングで、使用されるヒューリスティックが一貫しているかどうかをテストするにはどうすればよいですか？

Question

私は、大きな（高次元の）三目並べゲームのヒューリスティックをいくつか考えました。それらのどれが実際に一貫しているのかを確認するにはどうすればよいですか？

とにかく一貫性とはどういう意味ですか？

Answer 1

ヒューリスティックは、特定の状態に対してある種のコスト値を生成します。このコンテキストでの一貫性とは、ある状態の見積もりに次の状態に移動するためのコストを加えたものが、その新しい状態の見積もり以下であることを意味します。これが当てはまらない場合は、ヒューリスティックが正確である場合、ある状態から次の状態に移行すると、通常は不可能または不正確な負のコストが発生する可能性があることを意味します。

パスファインディングに関しては、パスに沿ったすべてのステップに時間がかかることが予想されるため、これを直感的に証明できます。したがって、ステップ1の推定値は、どのステップ2の推定値よりも低くする必要があります。システムの「コスト」を構成するものを任意に決定する必要があるため、三目並べ。移動をプレイした結果、ヒューリスティックが上下両方に移動できる場合-たとえば。良い動きを正の数でエンコードし、悪い動きを負の数でエンコードするため、ヒューリスティックは一貫性がありません。

ただし、一貫したヒューリスティックの欠如が常に問題になるとは限りません。最適なソリューションがないと保証されない場合がありますが、ブルートフォース状態の検索と比較して検索が高速化される可能性があります。

Answer 2

編集済み:この回答は、許容性と一貫性を混乱させました。許容性を参照するように修正しましたが、元の質問は一貫性に関するものであり、この回答は質問に完全には答えていません。

すべての異なるケースを区別し、それによってヒューリスティックが実際に許容できることを証明することにより、分析的に行うことができます。

情報に基づいた検索の場合、適切な状態までの「距離」を過小評価する場合に限り、ヒューリスティックは検索問題 (たとえば、ゲームでの最良の動きの検索) で許容されます。

例: 都市間のハイウェイのネットワークを介して、目的の都市への最短ルートを検索します。ここで、ユーリスティック距離をヒューリスティックとして使用できます。ゴールまでの直線の長さは、可能な限り最良の方法よりも常に短いか、同じ長さです。

許容性は、 A*などのアルゴリズムによって必要とされ、最適であることを検疫します (つまり、目標状態が存在する場合は、目標状態への最適な「ルート」を見つけます)。

AI の教科書でトピックを調べることをお勧めします。