1

私のプログラムには、作業中の negamax アルゴリズムがあります。ただし、時間内に可能な限り最良の動きを見つけるプログラムが必要kMaxTimePerMoveです。いくつかの調査を行ったところ、ネガマックス アルゴリズムで反復的な深化を使用することが最善の方法であると思われました。現在、検索を開始する関数は次のようになっています。

// this is a global in the same scope as the alpha-beta functions, so they can check the elapsed time
clock_t tStart;

int IterativeDeepening(Board current_state)
{
    bool overtime = false;
    int depth = 0;
    tStart = clock();

    MoveHolder best_move(-1, kWorstEvaluation);

    while ((static_cast<double> (clock() - tStart)/CLOCKS_PER_SEC) < kMaxTimePerMove)
    {
        MoveHolder temp_move = AlphaBetaRoot(kWorstEvaluation, -best_move.evaluation_,++depth, current_state, overtime);          
        if (!overtime)
            best_move = temp_move;
    }

    return best_move.column_;
}

以前の最良の動きを子リストの先頭に並べ替える必要があると思いますが、基本バージョンが機能するまでそれを実装するのを待っています. 実際の Alpha-Beta 関数は次のようになります。

MoveHolder AlphaBetaRoot(int alpha, int beta, int remaining_depth, Board current_state, bool &overtime)
{
    MoveHolder best(-1, -1);
    if (overtime)
        return MoveHolder(0,0);

    std::vector<Board> current_children;
    current_state.GetBoardChildren(current_children);

    for (auto i : current_children)
    {
        best.evaluation_ = -AlphaBeta(-beta, -alpha, remaining_depth - 1, i, overtime);
        if ((static_cast<double> (clock() - tStart)/CLOCKS_PER_SEC) > kMaxTimePerMove)
        {
            overtime = true;
            return MoveHolder(0,0);
         }
        if (best.evaluation_ >= beta)
            return best;
        if (best.evaluation_ > alpha)
        {
            alpha = best.evaluation_;
            best.column_ = i.GetLastMoveColumn();
        }
    }
    return best;
}

int AlphaBeta(int alpha, int beta, int remaining_depth, Board2 current_state, bool &overtime)
{
    if (overtime)
        return 0;
    if ((static_cast<double> (clock() - tStart)/CLOCKS_PER_SEC) > kMaxTimePerMove)
    {
        overtime = true;
        return 0;
    }

    if (remaining_depth == 0 || current_state.GetCurrentResult() != kNoResult)
    {
        return current_state.GetToMove() * current_state.GetCurrentEvaluation();
    }


    std::vector<Board> current_children;
    current_state.GetBoardChildren(current_children);
    for (auto i : current_children)
    {
        int score = -AlphaBeta(-beta, -alpha, remaining_depth - 1, i, overtime);
        if (score >= beta)
        {
            return beta;
        }
        if (score > alpha)
        {
            alpha = score;
        }
    }
    return alpha;
}

デバッグしようとすると、すべてが期待どおりに機能しているように見えます。ただし、反復的な深化バージョンを通常のアルファベータ実装に対してプレイすると、一貫して負けます。時々「動かなくなった」ように見え、ひどい動きを返します。

例として、このプログラムが次のターンに移動するよう「強制」されている場合、または対戦相手が勝つ場合、勝利をブロックしません。その動きで、深さ 38 まで検索していると報告されました。実行を中断すると、タイミングが台無しになるため、アルゴリズムのデバッグが非常に難しいことがわかりました。

アルゴリズムの実装が間違っているのか、それとも単にトリッキーなバグがあるだけなのかはわかりません。誰かが私を正しい方向に向けることができれば、本当に感謝しています.

4

1 に答える 1

3

-best_move.evaluation_検索のベータ値として使用してbest_moveいます。これは、前の深さからの最良の動きです。これは正しくありません。深さ = 2 では動きが良さそうに見えますが、それ以上の深さではうまくいかないことが判明したとします。この方法は引き続き良いと判断し、他の手では起こらないはずのベータ カットオフを引き起こします。

これを修正するには、(-infinity, infinity) で各反復を検索する必要があります。吸引ウィンドウを使用して、アルファ ベータ範囲を制限することもできます。

前の反復を使用して次の反復の移動順序を改善するわけではないため、反復の深化はわずかに悪い結果になることに注意してください。理想的には、転置表および/または前の反復の主要なバリエーションから最良の移動を選択する移動順序が必要です。

于 2012-11-25T09:51:25.867 に答える