問題タブ [alpha-beta-pruning]

私は先月 C# で単純なチェス エンジンを作成しており、いくつかの素晴らしい進歩を遂げました。単純なアルファ ベータ アルゴリズムを使用しています。

Horizo​​n-Effect を修正するために、Quiescence Search を実装しようとしました (機能するまでに数回失敗しました)。エンジンの力強さはそれで少し静かになったようですが、ものすごい遅い！

以前は、約 160 秒 (ゲーム中の状態のどこか) で 6 層の深さまで探索できましたが、静止探索では、コンピューターが探索深度 3 で移動するのに約 80 秒かかりました!

ブルート フォース ノード カウンターは深さ 3 で約 20000 ノードですが、静止ノード カウンターは最大 2000 万です!

これは私の最初のチェス エンジンなので、これらの数値が正常なのか、それとも静止アルゴリズムでミスを犯したのか、よくわかりません。より経験豊富な方が、BF ノードと静止ノードの通常の比率を教えていただければ幸いです。

ところで、ちょっと見てみましょう: (このメソッドは、searchdepth が 0 のときはいつでも BF ツリーによって呼び出されます)

MiniMax ツリーとアルファ ベータ プルーニングの概念は理解していますが、アルファ ベータ プルーニングに関する多くのリソース (ウィキペディアなど) で α​​ >= β のような条件が存在する理由がわかりません。具体的には、等号は紛らわしいです。私が理解しているように、アルファ ベータは minmax が返す動きを返しますが、ほとんどの場合は高速です。しかし、この例はそれと矛盾しています:

上は元の最小最大ツリーです。ご覧のとおり、スコア 3 の 1 つの手が選択されます。では、アルファ ベータを実行してみましょう。

3 >= 3 であるため、最も右の手を切り捨てます。しかし、アルゴリズムは同じスコアを持つ 2 つの手のどちらかを選択できますが、min-max で見たように、正しい選択はわずかに悪いです。アルゴリズムが単純に α > β を指定した場合、これは発生しないため、2 も検索する必要があります。

それはウィキペディアの疑似コード (および他の多くのリソース) のタイプミスでしたか? または、ここで本当に大きなことを誤解していました。

次の構造体を使用して、C でチェス ゲームを実装しました。

move - char board[8][8] (チェス盤) 上の (a,b) から (c,d) への動きを表します

動き - 頭と尾を持つ動きのリンクされたリストです。

変数: playing_color は 'W' または 'B' です。minimax_depth は、以前に設定されたミニマックス深度です。

これは、以前に設定された特定の minimax_depth の Minimax ツリーで移動のスコアを返す必要がある、アルファ ベータ プルーニングと getMoveScore 関数を使用した Minimax 関数の私のコードです。

同様に、ここにもリストする getBestMoves 関数を使用しています。これは基本的に、Minimax アルゴリズム中に最適な動きを見つけて、それらを後で使用できるようにグローバル変数に保存します。

ここに追加する 3 つの関数内にリストされている関数はすべて正常に動作し、テストされていることを付け加えなければなりません。したがって、問題はalphabetaMax アルゴリズムの論理的な問題か、getBestMoves/getMoveScore の実装のいずれかです。

主な問題は、深さ N で最高の動きを取得し (これも何らかの理由で正しく計算されません)、getMoveScore 関数を使用して同じ深さでスコアをチェックすると、スコアと一致しない異なるスコアが得られることです。それらの実際のベストムーブ。これをデバッグするのに何時間も費やしましたが、エラーが表示されませんでした。誰かが問題を見つけるためのヒントを教えてくれることを願っています.

コードは次のとおりです。

Eugene が指摘したように、ここに例を追加します: http://imageshack.com/a/img910/4643/fmQvlm.png

私は現在白のプレーヤーで、キング-K とクイーン-Q しか持っていません。反対の色にはキング-K とルーク-R があります。明らかに、ここでの私の最善の動きは、ルークを食べるか、少なくともチェックを引き起こすことです。ピースの動きがテストされ、正常に動作します。深さ 3 で get_best_moves 関数を呼び出すと、その深さで多くの不要な動きと負のスコアが得られます。多分今それはもう少し明確です。ありがとう！

EXC_BAD_ACCESS メッセージに関する他のスレッドからのアドバイスを適用しようとしましたが、成功しませんでした。の横にメモが表示されNode Create_Child (Node Parent_Node, int item) {ます。

洞察はありますか？メモリ割り当ては問題ではないようですが、おそらく何かが表示されていません。

ミニマックスアルゴリズムがどのように機能するかをよりよく理解するために、私は三目並べプログラムに取り組んできました。次の実装は、コンピューターがゲームに負ける可能性があるため、正しく機能していません。プログラムが正しく動作している場合、理論的にはこれは不可能なはずです...

ミニマックスの実装、または最善の手の取得で間違いを犯しましたか?

私は以前にアルゴリズムを実装したことがありません:s

評価関数

ミニマックス

最善の動きを見つける

ありがとうございました。

主変動 (PV) の結果を解読しようとすると問題が発生します。

「プリンシパル バリエーションは、ルートからリーフ ノードへのパスであり、すべてのノードが同じ値を持ちます。値がルートのミニマックス値を決定するこのリーフ ノードは、プリンシパル リーフと呼ばれます。」

PV (move,eval) の下のゲーム デモは、次の行を示しています。

すべての評価ノードが同じ値を持つわけではないのに、どうしてこれが有効な PV になるのでしょうか? AIは絶対に負けませんが、めまいがするPVは嘘っぽいので、AIのロジックに暗い影を落とします。:(うまくいけば、それは単なるPVのバグです！

誰かが私のコードにバグを見つけたら、私に知らせてください。ありがとう。