4

非常に大きなツリーのような構造を同時に生成してトラバースする必要があるチェスのようなプログラムのバリアントを作成しています。各ノードには、10 個の bool、int、8 個の ulong、short[64]、および 2 個の ulong[64] があります。ルート ノードはいくつかの初期パラメーターを受け取り、そこから有効な子ノードがプログラムによって (再帰的に) 決定されます。

基本的に、私のプログラムはこのツリーを継続的に成長させ、ユーザーとプログラムは交互に子ノードから子ノードへとトラバースします。新しい子ノードが「選択」されるたびに、その親ノードと兄弟ノードは不要になり、破棄されます。ツリーが (最初のルート ノードから) 約 60 の深さに (平均で) 達すると、有効な子ノードの数は自然に減少し始め、深さが約 75 になるまで、ツリーは 1 つの最終ノードに解決されます。さらに子供たち。

この背後にあるロジックは、最初はかなり単純明快に見えましたが、私は常に OutOfMemoryException にぶつかり、それ以上の進行を完全に止めています。

以下は、「世代」ごとの有効な子供の平均です。

Generation    New Nodes
1             1    
2             20
3             4,000
4             30,000
5             2,200,000
6             > 50,000,000

私の実際のプログラムでは、第 5 世代を完全に展開することさえできません。ノード固有のデータを永続化しない場合 (自分の子ノードを特定するために使用されたノードのデータをクリアします)、第 5 世代を完全に拡張できますが、第 6 世代の途中で非常に堅固な壁にぶつかります。

理想的には、プログラムが最終的に到達し、「現在の」ノードの後の 8 世代のノードを維持することを望みます。これを見れば見るほど、その可能性は低いように思えます。

これを sqlite データベースで実行するのは疲れましたが、ツリーを十分に速く成長させることができませんでした。

非常に大きなツリー構造を処理するための潜在的な代替手段を知っている人はいますか?

4

2 に答える 2

1

あなたの質問に対する一般的な答えはありません。この大きなツリーは、コンピューター プログラムの最適な動きを決定するために計算されると思いますか?

その場合、ゲーム内でこの一連の動きを行うことの価値を測定する、一連の動きの効用関数を定義すると役立つ場合があります。目標が最大スコアなどに到達することである場合、そのスコアは優れた効用関数です。

正確な効用関数を思いつくことができない場合があります。その場合、一般的なアプローチは、効用のヒューリスティックな評価を行うことです。基本的には、概算または最良の推測です。ヒューリスティックが優れているほど、敵は優れています。

ユーティリティの測定が必要な理由は、プルーニングを実行するためです。例として、ツリーの深さ優先を数回トラバースし、最小および最大ユーティリティを計算します。これらの値は、完全なアルゴリズムを整理するのに役立ちます。つまり、これらの境界を使用して、ツリー トラバーサル アルゴリズムが完了前に終了する可能性があるかどうかを判断できます。

繰り返しますが、それはすべてゲームの仕組みとツリーをどのようにトラバースするかによって異なりますが、うまくいけば、これにより正しい方向に考えることができます.

于 2012-06-22T20:36:36.973 に答える
0

通常、ツリーを構築するときに評価があります。これにより、エッジに重みが付けられます。これらの重みを使用して、どのパスが他のパスよりも強力なパスを評価し、どれがより価値があるかがわかるとすぐに、それらのエッジで機能するかどうかを確認します。アルゴリズムの第5世代ですでに問題が発生しているため、重みの高いブランチを詳細に調べて、そのうちの1つを選択し、他の多数のブランチを却下するしかありません。ただのアイデアなので...おそらくこれを第3世代で実行して、どちらに進むかを選択できます。私がチェスを知っている限り、これは、プロバルビーがゲームにより大きな影響を与えるため、より可動性のあるポーンでのみ移動するようになる可能性があります。これは、第5世代の移動と比較して最善の解決策ではない可能性があります。非常に興味深い問題です！

チェスプログラミングについて調査する必要があります：チェスプログラミングwiki

エンジンの詳細は次のとおりです。エンジンに関するチェスプログラミングwiki

さまざまなアプローチが議論されるフォーラムもあります！

于 2012-06-22T20:53:21.063 に答える