C++ Negamax alpha-betaの間違ったカットオフ？

Question

私は4つの接続を再生するためにnegamaxを使用してきました。私が気づいたのは、アルファ・ベータを追加すると、時には「間違った」結果が出るということです。失われた動きのように、私が探している深みではないと信じています。私がalpha-betaを削除した場合、それは想定されているように再生されます。実際に実行可能なブランチをアルファベータで切り捨てることはできますか（特に深さに制限がある場合）？ここで念のコードは次のとおりです。

int negamax(const GameState& state, int depth, int alpha, int beta, int color) 
{ 
    //depth end reached? or we actually hit a win/lose condition? 
    if (depth == 0 || state.points != 0) 
    { 

     return color*state.points; 
    } 

    //get successors and optimize the ordering/trim maybe too 
    std::vector<GameState> childStates; 
    state.generate_successors(childStates); 
    state.order_successors(childStates); 

    //no possible moves - then it's a terminal state 
    if (childStates.empty()) 
    { 
     return color*state.points; 
    } 
    int bestValue = -extremePoints; 
    int v; 
    for (GameState& child : childStates) 
    { 
     v = -negamax(child, depth - 1, -beta, -alpha, -color); 
     bestValue = std::max(bestValue, v); 
     alpha = std::max(alpha, v); 
     if (alpha >= beta) 
      break; 
    } 
    return bestValue; 
} 

Answer 1

は、α-βは、いくつか実際に実行可能な枝を（深さが限られている場合は特に）に切断することはできますか？

アルファベータアルゴリズムは（おそらく最終決定に影響を与えることができない枝を削るより速い時間に（しばしば）ミニマックス（ルートノードおよびプレイのラインで評価）が、同じ結果を返しますが読むことができますH.Fuller著、1973年のAnalysis of the alpha-beta pruning algorithm by Samuel）。

あなたはNegamax Alpha-Betaプルーニングを使用していますが、それはアルゴリズムの実装を簡略化するための単なる変形です。

またfail-softギミックは、状況は変わりません。

もちろん、浅い深度での検索では悪い動きを選ぶことができますが、Minimaxでも同じ結果が得られます。

したがって、実装エラーである必要があります。

表示されているコードはわかりました。あなたはチェックする必要があります：

1. あなたがルートノードでnegamaxを呼び出す方法。

   negamax(rootState, depth, −extremePoints, +extremePoints, color) 
   

   alpha/betaが可能な最低値と最大値は次のとおりです。それは何かのようにする必要があります。

   あなたはalpha /（例えばaspiration windows）betaと真のスコアは初期ウィンドウの外にあるために異なる初期値を使用している場合は、再検索をする必要があります。

2. あなたが主なバリエーションの移動を収集/保存/管理/伝播する方法（関連コードがありません）。 PVテーブルなどのテクニックは、bestValueの変更にリンクしています。これが問題であれば、（Minimaxに関して）同じポジションを獲得するべきですが、別の最良のポジションを獲得する必要があります。

Answer 2

質問は、ルートノードでアルファとベータを初期化する方法です。私はそれに応じて標準の:: numeric_limits :: min（）とstd :: numeric_limits :: max（）に設定し、alphaパラメータをnegamax（... -a_beta、 a_alpha ...）最小のint値の数学的な否定がint（-214748364 対214748364 ）の範囲外であるため、最小のint値を得られるマイナス演算子を追加することによって、最小のint値を無効にしました。

ただし、アルファを異なる値（たとえばstd :: numeric_limits :: min（）+ 1）に初期化する場合はそうではありません。