Минимакс с альфа-бета-обрезкой; переменные класса или отправка их через рекурсию? - PullRequest
Новая
       13

Минимакс с альфа-бета-обрезкой; переменные класса или отправка их через рекурсию?

0 голосов
/ 23 ноября 2011

При использовании Minimax с отсечкой альфа-бета, возможно ли иметь альфа и бета в качестве переменных класса вместо отправки их через рекурсию?

Вместо: 

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
}

Я спрашиваю, потому что, когда я пытался оптимизировать код, делая это (я думал, что, если мне не нужно отправлять целые числа для каждой рекурсии, я мог бы очистить немного времени), мой шахматист неожиданно стал идиотом, жертвуя своей королевой, чтобы убить пешку, и делая другие глупые ошибки.

Он постоянно выступает намного беднее своего «обычного альфа-бета» противника, что, я думаю, объясняется тем, что он также ищет только небольшой процент дерева по сравнению со своим противником (оба используют одинаковую глубину, но модифицированный игрок кажется, сокращает более агрессивный, и тем самым уменьшает количество посещаемых узлов). Я сделал это дважды сейчас, чтобы убедиться, и я не изменяю ничего, кроме того, что я вычеркнул здесь.

Если я правильно понял алгоритм альфа-бета, это не должно иметь никакого значения, но для моего шахматиста это так. Я что-то делаю не так?

Итак, мой главный вопрос сейчас не в том, является ли это разумной оптимизацией или практикой кода, а скорее в том, должно ли это быть возможно или нет.

1 Ответ

4 голосов
/ 25 ноября 2011

Вы не можете этого сделать. AlphaBeta - это рекурсивный алгоритм. Это означает, что он сам себя называет. Каждый раз, когда он вызывает себя, он делает это с (возможно) разными значениями для альфы и беты. Каждой рекурсии нужна своя версия переменных, которая будет содержать разные значения. Если вы включите переменные в класс, у вас будет только один набор переменных, общих для всех (рекурсивных) вызовов AlphaBeta.

При этом замена параметров функции членами класса, вероятно, не является хорошей оптимизацией. Оба метода имеют свою стоимость. Параметры должны быть помещены в стек перед вызовом, и к элементам необходимо обращаться косвенно через указатель (скрытый указатель this). Давайте забудем о том, какая стоимость выше. Эта микрооптимизация, вероятно, слишком незначительна, чтобы вообще что-то менять.

...