3

これは私の最初の質問です。何か間違ったことをした場合は教えてください...

私は現在、Java でドラフト ゲームを作成しています。実際、AI 以外はすべて機能します。AI は現在、ミニマックスとアルファ ベータ プルーニングを使用するシングル スレッドです。このコードは機能しますが、非常に遅いと思います。ゲーム ツリーの深さは 5 しかありません。

  1. メインボード、深さ (0 から開始)、および最大深さを受け取る関数があります。この maxdepth で停止し、ボード上に最も多くのピースがあるプレーヤーの値 (-1、1、または 0) を返し、再帰呼び出しを終了します。
  2. maxdepth にまだ達していない場合は、すべての可能な動きを計算し、それらを 1 つずつ実行して、何らかの方法で変更をメインボードに保存します。
  3. また、私はアルファ ベータ プルーニングも使用します。たとえば、プレーヤーを勝利に導く手が見つかった場合、次に考えられる手は気にしません。
  4. そのメインボードの状態から次の一連の動きを再帰的に計算します。再帰呼び出しから抜け出すときに、これらの変更を (ポイント 2 から) 元に戻します。これらの再帰呼び出しによって返された値を保存し、それらに対して minimax を使用します。

そんな状況ですが、いくつか質問があります。ゲーム ツリーを深く掘り下げたいので、動きの計算にかかる時間を短縮する必要があります。

  1. AI の可能な動き (たとえば、AI が選択できる動き) の値が常に 0 であることは正常ですか? それとも、再帰をさらに深く掘り下げることができれば、これは変わりますか? 現時点では、再帰に 5 深さ (maxdepth) しか入れられないため、そうしないと時間がかかりすぎるためです。
  2. 役に立つかどうかはわかりませんが、この再帰をマルチスレッド再帰に変換する方法を教えてください。これにより、作業時間をある値で割ることができると思います...

誰かがこれで私を助けてくれますか?

4

3 に答える 3

2

1. AIの可能な動き（たとえば、AIが選択できる動き）の値が常に0であるのは正常ですか？

私には奇妙に聞こえます。可能な移動の数が0の場合、そのプレイヤーは自分のターンをプレイできません。これはあまり一般的ではないはずです、または私は何かを誤解しましたか？

参照している値がその動きの「スコア」を表す場合、明らかに「常に0」はすべての動きが同等に優れていることを示しますが、これは明らかに非常に優れたAIアルゴリズムにはなりません。

2.それが有用かどうかはわかりませんが、この再帰をマルチスレッド再帰に変換する方法はわかりません。これで作業時間をある程度の値で割ることができると思います...

特に最近のほとんどのマシンにはいくつかのコアがあることを考えると、これは非常に役立つと確信しています。

それを複雑にしているのは、「移動を試して、記録して、元に戻して、次の移動を試してください」というアプローチです。これは、可変データ構造を使用していることを示しており、アルゴリズムの並列化が非常に複雑になっています。

もし私があなたなら、ボード/ゲームの状態を不変のデータ構造で表現させます。次に、各再帰呼び出しを個別のタスクとして扱い、スレッドのプールを使用してそれらを処理することができます。CPUの最大使用率に近づき、同時にコードを大幅に簡素化します（以前の状態に復元するコード全体を削除することにより）。

マシンに実際にいくつかのコアがあると仮定すると、これにより、ツリーの奥深くに入ることができる可能性があります。

于 2012-05-12T11:10:45.050 に答える
1

この本を読むことを強くお勧めします：

一歩先を行く: チェッカーでのコンピューターの完成度

チェッカー ゲームにおけるコンピューター AI の深い歴史を知ることができ、おそらく評価関数の助けになるでしょう。

異なるピースに対して 1/0/-1 を与えるだけの評価関数を使用する代わりに、すべての通常のピースに 100 のスコアを与え、キングに 200 のスコアを与えます。次に、ピース構造にボーナスを与えます。たとえば、自分のピースがキャプチャできない安全な構造を形成している場合、ボーナスが得られます。私の駒がボードの真ん中に1つだけある場合、マイナスのボーナスが得られます. あなたのプログラムをうまくプレイできるようにするのは、ピース構成のためのこの豊富な機能です。最終的なスコアは、両方のプレーヤーの評価の差です。

また、均一な深さで検索を停止しないでください。静止検索は、ボードが「静止」するまで検索を拡張します。チェッカーの場合、これはボードに強制キャプチャがないことを意味します。これを行わないと、プログラムのパフォーマンスが非常に悪くなります。

他の人が示唆しているように、転置テーブルは検索ツリーのサイズを小さくするのに非常に役立ちますが、プログラムの実行は少し遅くなります。また、履歴ヒューリスティックもお勧めします。これはプログラムが簡単で、ツリー内の移動の順序を大幅に改善します。(これに関する詳細については、Google 履歴ヒューリスティックを参照してください。)

最後に、ボードの表現は大きな違いを生む可能性があります。検索の高速な実装は、移動が適用されるたびにボードのコピーを作成するのではなく、移動を適用して元に戻すためにボードをすばやく変更しようとします。

于 2012-05-13T06:03:36.007 に答える
0

（ドラフトとは、ここ米国でチェッカーと呼ばれるものを意味していると思います。）

ゲーム ツリー内のスコアリング システムを理解しているかどうかわかりません。「プレイヤーの駒が対戦相手よりも多い場合、位置は 1 ポイント、プレイヤーの駒が少ない場合は -1 ポイント、同じ数の場合は 0 ポイントを獲得しますか?」と言って採点していますか?

もしそうなら、あなたのアルゴリズムは最初の 5 つの手でキャプチャーを嫌うだけかもしれません。私はチェッカーに詳しくありませんが、これがゲームの 5 回の動きだけであることは不可能ではないように思われます。また、プライが5 つしかない場合(プライとは、反対の動きの完全なセットではなく、1 人のプレーヤーの動きである場合)、まったく珍しいことではないかもしれません。

これをテストするには、絶対に正しい答えがわかっているボードの位置にフィードすることをお勧めします。たとえば、ボード上にチェッカーが 2 つしかなく、キャプチャする位置に 1 つのチェッカーがある場合などです。

ただし、一般的な原則として、ボード評価関数はあまり意味がありません。ピースとクラウン付きピースの違いは無視され、スリー ピースの利点は 1 ピースの利点と同じように扱われます。

于 2012-05-12T20:39:08.990 に答える