1

ネガマックスでコネクトフォーをプレイしています。私が気付いたのは、アルファベータを追加すると、「間違った」結果が得られることがあるということです。アルファベータを削除すると、想定どおりに再生されます。アルファ-ベータは、実際に実行可能なブランチをいくつか切り取ることができますか (特に深さが制限されている場合)? 念のためのコードは次のとおりです。

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;
}
4

2 に答える 2

2

アルファ-ベータは、実際に実行可能なブランチをいくつか切り取ることができますか (特に深さが制限されている場合)?

Alpha-Beta アルゴリズムは、Minimax と同じ結果を返します (ルート ノードとライン オブ プレイでの評価) が、(多くの場合) 最終決定に影響を与える可能性のない枝をより高速に除去します ( Analysis of the alpha-beta で証明を読むことができます)。 H. Fullerによる Samuel による剪定アルゴリズム- 1973)。

Negamax Alpha-Beta プルーニングを使用していますが、これはアルゴリズムの実装を簡素化するための変形に過ぎません。

フェイルソフトギミックも状況は変わらない。

もちろん、浅い深度での検索は悪い動きを見つける可能性がありますが、同じことがミニマックスにも当てはまります。

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

示されているコードは私には正しいようです。以下を確認する必要があります。

  1. ルート ノードで negamax を呼び出す方法。次のようになります。

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

    alpha/betaは、可能な最小値と最大値です。

    alpha/に異なる初期値を使用しておりbeta(例: aspiration windows )、真のスコアが初期ウィンドウの外にある場合は、再検索する必要があります。

  2. 主要なバリエーションの動きを収集/保存/管理/伝播する方法 (関連するコードが欠落しています)。PV テーブルなどの手法は、 の変更にリンクされていますbestValue。これが問題である場合、(Minimax に関して) ポジションに対して同じスコアを取得する必要がありますが、ベスト ムーブは異なります。

于 2016-06-25T13:21:38.943 に答える