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

Question

ゲーム探索木には、ミニマックスアルゴリズムのように、最適解を得るアルゴリズムがたくさんあります。この問題をミニマックスアルゴリズムで解決する方法を学び始めました。アルゴリズムは明確です。しかし、私はツリー自体について混乱しています.tic tac toeのようなゲームではノードの数はそれほど大きくありませんが、チェスのような他のゲームでは多くのノードがあります。これにはメモリに大きなスペースが必要だと思います。それで、ツリーを同時に評価して構築するアルゴリズムはありますか?

Answer 1

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

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