ゲーム検索ツリー、最初にツリーを構築する必要がありますか？

Question

ゲーム検索ツリーには、Minimaxアルゴリズムのような最適なソリューションを取得するための多くのアルゴリズムがあります。 Minimaxアルゴリズムであるアルゴリズムをクリアして、この問題を解決する方法を学び始めます。しかし、私はツリー自体について混乱しています。TACTOE数のノードのようなゲームではあまり大きくありませんが、チェスのような他のノードには多くのノードがあります。これにはメモリに大きなスペースが必要だと思います。それでは、同時にツリーを評価して構築するアルゴリズムはありますか？

Answer 1

ゲーム状態のツリーは、通常、完全なデータ構造として構築されていません。代わりに、状態は作成されたときに評価され、ほとんどはその過程で破棄されます。多くの場合、ゲームの現在の状態に戻されている州のリンクリストが維持されます。しかし、ある動きが別の動きよりもはるかに優れていることが示された場合、貧弱な動きのためのライン全体が破棄されるため、メモリ内のスペースを占有しません。

チェスのようなゲームのために状態空間を検索する簡単な方法の1つは、特定の深さまで再帰的に検索を行うことです。その場合、一度に実際に存在するゲーム状態はほとんどなく、存在するものはコールスタックで単純に参照されます。より洗練されたアルゴリズムはより大きなツリーを作成しますが、（特にチェスの場合）可能なすべての状態のツリーを維持するものはありません。チェスの場合、スタックではなくキューを使用して、幅広い検索が優れている場合があり、これは木の特定の深さで状態のみを維持します。さらに良いことは、最良の状態がさらなる評価のために保存され、最悪の状態が完全に廃棄される優先キューです。