Обрезка альфа-беты, похоже, не улучшает мои минимаксные показатели - PullRequest
Новая
       74

Обрезка альфа-беты, похоже, не улучшает мои минимаксные показатели

0 голосов
/ 26 мая 2018 
import java.util.ArrayList;
import java.util.HashMap;

public class MiniMax {
    public static final int SUGGESTIVE_MAX_DEPTH = 10;
    public static int counter;
    //AI (white), depth>0
    public static int[]  getComputerMove(Board b, int depth) {
        ArrayList<ArrayList<Integer>> coloredMoves = b.getAllMoves(true);
        int[] currentMove = new int[4];
        int max = Integer.MIN_VALUE;
        int[] bestMove = new int[4];
        for (int k = 0; k < coloredMoves.size(); k++) {
            ArrayList<Integer> a = coloredMoves.get(k);
            for (int i = 2; i < a.size() - 1; i += 2) {
                currentMove[0] = a.get(0);
                currentMove[1] = a.get(1);
                currentMove[2] = a.get(i);
                currentMove[3] = a.get(i + 1);
                int moveSetValue = min(b.simulateMove(currentMove), depth - 1, max, Integer.MAX_VALUE);
                if (moveSetValue > max) {
                    max = moveSetValue;
                    bestMove = currentMove.clone();
                }
            }

        }
        System.out.println(counter);return bestMove; 
    }
    //maximizer (white)
    private static int max(Board b, int depth, int alpha, int beta) {
        if (depth == 0 || Math.abs(b.getSum()) > 999990) { counter++; 
            return b.getSum(); 
        }
        ArrayList<ArrayList<Integer>> coloredMoves = b.getAllMoves(true);
        for (int k = 0; k < coloredMoves.size(); k++) {
            ArrayList<Integer> a = coloredMoves.get(k);
            for (int i = 2; i < a.size() - 1; i += 2) {
                int[] moveSet = new int[4];
                moveSet[0] = a.get(0);
                moveSet[1] = a.get(1);
                moveSet[2] = a.get(i);
                moveSet[3] = a.get(i + 1);
                int moveValue = min(b.simulateMove(moveSet), depth - 1, alpha, beta);
                alpha = (int) Math.max(alpha, moveValue);
                if (alpha >= beta) {
                    return alpha;
                }

            }
        }
        return alpha;
    }
    //minimizer (black)
    private static int min(Board b, int depth, int alpha, int beta) {
        if (depth == 0 || Math.abs(b.getSum()) > 999990) {
            counter++; return b.getSum();
        }
        ArrayList<ArrayList<Integer>> coloredMoves = b.getAllMoves(false);
        for (int k = 0; k < coloredMoves.size(); k++) {
            ArrayList<Integer> a = coloredMoves.get(k);
            for (int i = 0; i < a.size() - 1; i += 2) {
                int[] moveSet = new int[4];
                moveSet[0] = a.get(0);
                moveSet[1] = a.get(1);
                moveSet[2] = a.get(i);
                moveSet[3] = a.get(i + 1);
                int moveValue = max(b.simulateMove(moveSet), depth - 1, alpha, beta);
                beta = (int) Math.min(beta, moveValue);
                if (alpha >= beta) {
                    return beta;
                }
            }
        }
        return beta;
    }
}

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

Некоторое объяснение:

ColoredMoves получает все возможные шахматные ходы.перемещение определяется как координатная позиция движущейся фигуры и координаты местоположения.

РЕДАКТИРОВАТЬ: Глубина здесь означает каждый отдельный шаг.Могу ли я переоценить эффективность альфа-бета-обрезки с минимаксом?Онлайн показывает, что должно быть как минимум 6. Мой алгоритм работает только в реалистичное время на глубине 4, что довольно жалко.

1 Ответ

0 голосов
/ 17 июля 2018

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

Существует несколько методов сортировки шахматных ходов.Для сортировки ходов в корне вы можете использовать «итеративное углубление».После этого история эвристическая и убийственная эвристика помогают сортировать ходы в древе игры.

Улучшение в дополнение к вашему вопросу может заключаться в сдвиге 

moveSet[0] = a.get(0);
moveSet[1] = a.get(1);

вв начале цикла for, если массив не изменился в функции simulateMove.

...