0

アルファベータ法でミニマックスを使用する場合、再帰を介して送信する代わりに、クラス変数としてアルファとベータを使用することは可能ですか？

それ以外の：

private ValuedMove AlphaBetaSearch(Board state)
{
    return MaxValue(state, 0, int.MinValue, int.MaxValue);
}

private ValuedMove MaxValue(Board state, int d, int alpha, int beta)
{
    if (d == depth || state.GameRunning == false)
        return new ValuedMove(Heuristic.BoardValue(state, Player));

    ValuedMove v = new ValuedMove(int.MinValue);
    foreach (Move move in LegalMoves)
    {
        ValuedMove minCheck = MinValue(state.ImagineMove(move), d + 1, alpha, beta);
        if (v.Value >= beta)
            return v;
        alpha = Max(alpha, v.Value);
    }

    return v;
}

private ValuedMove MinValue(Board state, int d, int alpha, int beta)
{
    //Minimax and Alpha-Beta logic here
}

私は書くことができます：

int alpha, beta;

private ValuedMove AlphaBetaSearch(Board state)
{
    alpha = int.MinValue;
    beta = int.MaxValue;
    return MaxValue(state, 0);
}

private ValuedMove MaxValue(Board state, int d)
{
    //Minimax and Alpha-Beta logic here
}

private ValuedMove MinValue(Board state, int d)
{
    //Minimax and Alpha-Beta logic here
}

そうすることでコードを最適化しようとすると（各再帰にintを送信する必要がない場合は、少し時間がかかる可能性があると思いました）、チェスプレーヤーが突然馬鹿になり、ポーンを殺すために女王を犠牲にし、他の愚かな過ちを犯しました。

彼は常に「通常のアルファベータ」の対戦相手よりもパフォーマンスがかなり劣っています。これは、対戦相手と比較してツリーのごく一部しか検索しないためだと思います（どちらも同じ深さを使用していますが、変更されたプレーヤーは剪定しているようです）より積極的になり、それによって訪問されるノードの数が減ります）。念のため、これを2回行いました。ここで切り取ったもの以外は、何も変更しません。

アルファベータアルゴリズムが正しいことを理解していれば、これは何の違いもありませんが、私のチェスプレーヤーにとっては違いはあります。私は何か間違ったことをしていますか？

ですから、今の私の主な質問は、それが最適化の観点から、またはコードの実践の観点から良いことであるかどうかではなく、むしろそれが可能であるかどうかです。

4

1 に答える 1

4

あなたは本当にこれを行うことはできません. AlphaBeta は再帰的なアルゴリズムです。つまり、自分自身を呼び出します。自分自身を呼び出すたびに、(おそらく) 異なる値のアルファとベータを使用して呼び出します。各再帰には、異なる値を保持する独自のバージョンの変数が必要です。クラスに変数を含めると、AlphaBeta へのすべての (再帰的な) 呼び出し間で共有される変数のセットは 1 つだけになります。

そうは言っても、関数パラメーターをクラスメンバーに置き換えることは、おそらく適切な最適化ではありません。どちらの手法にもコストがかかります。パラメーターは呼び出しの前にスタックにプッシュする必要があり、メンバーはポインター (隠しthisポインター) を介して間接的にアクセスする必要があります。どちらのコストが高いかは忘れましょう。このマイクロ最適化は、おそらくまったく重要ではないため、まったく違いはありません。

于 2011-11-25T13:16:20.040 に答える