Альфа-бета-порядок перемещения

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

Любые предложения по реализации одного из этих усовершенствований в этом алгоритме?

 public double alphaBetaPruning(Board board, int depth, double alpha, double beta, int player) {
    if (depth == 0) {
        return board.evaluateBoard();
    }

    Collection<Move> children = board.generatePossibleMoves(player);
    if (player == 0) {
        for (Move move : children) {
            Board tempBoard = new Board(board);
            tempBoard.makeMove(move);
            int nextPlayer = next(player);
            double result = alphaBetaPruning(tempBoard, depth - 1, alpha,beta,nextPlayer);
            if ((result > alpha)) {
                alpha = result;
                if (depth == this.origDepth) {
                    this.bestMove = move;
                }
            }
            if (alpha >= beta) {
                break;
            }
        }
        return alpha;
    } else {
        for (Move move : children) {
            Board tempBoard = new Board(board);
            tempBoard.makeMove(move);
            int nextPlayer = next(player);
            double result = alphaBetaPruning(tempBoard, depth - 1, alpha,beta,nextPlayer);
            if ((result < beta)) {
                beta = result;
                if (depth == this.origDepth) {
                    this.bestMove = move;
                }
            }
            if (beta <= alpha) {
                break;
            }
        }
        return beta;
    }
}

public int next(int player) {
    if (player == 0) {
        return 4;
    } else {
        return 0;
    }
}

Ответы

Ответ 1

  • Node переупорядочение с мелким поиском тривиально: вычислить эвристическое значение для каждого дочернего элемента состояния до рекурсивного проверяя их. Затем отсортируйте значения этих состояний [по убыванию для максимальной вершины и возрастания для минимальной вершины] и рекурсивно вызывать алгоритм в отсортированном списке. Идея заключается в том, что если государство хорошо неглубокой глубины, он, скорее всего, будет хорош и в глубоком состоянии, и если это правда, вы получите больше пренебрежений.

    Сортировка должна быть сделана до этой [в предложениях if и else]

    for (Move move : children) {

  • Сохранение ходов также тривиально - многие состояния вычисляются дважды, когда вы закончите вычисление любого состояния, сохраните его [с глубиной расчет! он неэффективен!] в HashMap. Первое, что вы делаете когда вы начинаете вычисление по вершине - это проверка, если она уже вычисляется - и если это так, возвращается кешированное значение. Идея это то, что многие состояния достижимы с разных путей, так что это путь - вы можете исключить избыточные вычисления.

    Изменения должны быть сделаны как в первой строке метода [что-то вроде if (cache.contains((new State(board,depth,player)) return cache.get(new State(board,depth,player))] [извините, из-за отсутствия элегантности и эффективности, просто объясняя идею здесь]. Вы также должны добавить cache.put(...) перед каждым оператором return.

Ответ 2

Прежде всего, нужно разобраться в рассуждениях по поводу упорядочения движения в алгоритме обрезки альфа-бета. Альфа-бета дает тот же результат, что и минимакс, но во многих случаях может делать это быстрее, потому что он не выполняет поиск по нерелевантным ветвям.

Это не всегда быстрее, потому что это не гарантирует обрезание, если в худшем случае он вообще не будет обрезать и искать абсолютно то же дерево, что и минимакс, и будет медленнее из-за сохранения значений в /b, В лучшем случае (максимальная обрезка) он позволяет одновременно искать дерево в 2 раза глубину. Для случайного дерева он может искать в 4/3 раза глубже в одно и то же время.

Порядок перемещения может быть реализован несколькими способами:

  • У вас есть эксперт по домену, который дает вам представление о том, какие шаги лучше. Например, при продвижении в шахматы пешки, захват предметов с высокой стоимостью с более низкой стоимостью, в среднем хорошие ходы. В шашки лучше убить больше шашек в ходу, чем меньше шашки, и лучше создать королеву. Таким образом, ваша функция генерации движений возвращает лучшие ходы перед
  • вы получаете эвристику о том, насколько хорош переход от оценки положения на 1 уровне глубины меньше (ваш мелкий поиск/итеративное углубление). Вы рассчитали оценку на глубине n-1, отсортировали движения и затем оценили на глубине n.

Второй подход, о котором вы говорили, не имеет никакого отношения к упорядочению перемещения. Это связано с тем, что оценочная функция может быть дорогостоящей, и многие позиции оцениваются много раз. Чтобы обойти это, вы можете сохранить значения позиции в хеше, как только вы ее вычислили, и повторно использовать позже.