1

Cでチェッカーの最適なゲームを実装しようとしています.

マシンが実行できるチェッカー ボードの最適な動きを見つけるために、現在のチェッカー ボードの状態に基づいて、C の (GLib) を使用して深さを固定してn-ary ゲーム ツリーを生成しました。

そして、ゲーム ツリーに存在するすべてのリーフ ノードについてヒューリスティック値が計算されます。これは、ボードに残っているマシンのピースの数からプレイヤーの対戦相手のピースの数を差し引いたものとして定義されます。これは、キングがポーンよりも強力な能力を持っているためです。各キングは 2 つの通常のポーンとして使用され、アルファ ベータ検索が適用されます。

ゲーム ツリーの深さを増やすと、最終的に最適化された動きが生成される可能性が高くなります。深さを増やそうとすると、ツリーの生成とヒューリスティック検索に時間がかかります。

私の考えは、ツリーの最初のレベルを個別に生成し、MPI を使用してさらに実行するために、使用可能なプロセッサ間で子ノードを分散することですか?

出来ますか？はいの場合、MPI を使用してツリー生成とヒューリスティック検索を並列化するにはどうすればよいですか?

また、効率的でない場合は、それを実装する方法について他の方法を提案してください。ありがとう。

4

1 に答える 1

0

まあ、それは並列化できますが、問題は、どれだけの改善が期待できるかです。おそらくループで初期状態の子を生成しています。最初のレベルでは、子の作成をスレッドn間で分割することで並列化できます。kこれらのタスクは非常に計算量が多いため (さらにサブツリーを再帰的に作成する)、かなりスレッド効率が良いはずです。

ただし、ツリーの分岐係数がコアの数よりも大きい (または同様の) 可能性が高いため、並列化が線形に効果的であっても (実際には効果的ではありません)、レイヤーを 1 つだけ多く生成することができます。 .

アルファ・ベータ・プルーニングを使用していますか? このような並列化よりもはるかに大きなメリットがあると思います。

于 2013-12-21T09:58:57.583 に答える