Ошибка в минимаксе для tic_tac_toe AI - PullRequest
Новая
       19

Ошибка в минимаксе для tic_tac_toe AI

0 голосов
/ 31 августа 2018

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

Вот мой минимаксный код: 

public int minimax(int[] board, char symbol, int alpha, int beta, int depth = 2)
{
    int win = util.checkwin(board);
    int nsymbol = (symbol == 'X' ? 1 : 2);
    int mult = (symbol == compside ? 1 : -1);

    if (win != -1)
    {
        if (win == nsymbol)
            return mult;
        else if (win != 0)
            return (mult * -1);
        else
            return 0;
    }

    if (depth == 0)
        return 0;

    int[] newboard = new int[9];
    Array.Copy(board, newboard, 9);
    int score, i, pos = -1;
    ArrayList emptyboard = new ArrayList();
    emptyboard = util.filterboard(newboard);

    for (i = 0; i < emptyboard.Count; i++)
    {
        if (i > 0)
            newboard[(int)emptyboard[i - 1]] = 0;

        newboard[(int)emptyboard[i]] = nsymbol;
        score = minimax(newboard, util.changeside(symbol), alpha, beta, depth - 1);

        if (mult == 1)
        {
            if (score > alpha)
            {
                alpha = score;
                pos = (int)emptyboard[i];
            }

            if (alpha >= beta)
                break;
        }
        else
        {
            if (score < beta)
                beta = score;

            if (alpha >= beta)
                break;
        }
    }

    if (depth == origdepth)
        return pos;

    if (mult == 1)
        return alpha;
    else
        return beta;
}

Сведения о неопределенных функциях:

util.checkwin(int[] board) = проверяет доску на предмет возможного выигрыша или ничьей за бортом или за неполную доску и возвращает победителя как 1 или 2 (игрок Х или О), 0 за ничью и -1 за неполную доску.

util.filterboard(int[] newboard) = возвращает массив, содержащий все позиции пустых мест на данной доске.

util.changeside(char symbol) = просто переключает X на O и O на X и возвращает результат.

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

Вот вывод (глубина = 2): 

 Turn: X
  |   |
1 | 2 | 3
__|___|__
  |   |
4 | 5 | 6
__|___|__
  |   |
7 | 8 | 9
  |   |
Enter Your Choice:

 Turn: O
  |   |
1 | 2 | 3
__|___|__
  |   |
X | 5 | 6
__|___|__
  |   |
7 | 8 | 9
  |   |
Enter Your Choice: 5


 Turn: X
  |   |
1 | 2 | 3
__|___|__
  |   |
X | O | 6
__|___|__
  |   |
7 | 8 | 9
  |   |
Enter Your Choice:

 Turn: O
  |   |
1 | X | 3
__|___|__
  |   |
X | O | 6
__|___|__
  |   |
7 | 8 | 9
  |   |
Enter Your Choice: 1


 Turn: X
  |   |
O | X | 3
__|___|__
  |   |
X | O | 6
__|___|__
  |   |
7 | 8 | 9
  |   |
Enter Your Choice:

 Turn: O
  |   |
O | X | 3
__|___|__
  |   |
X | O | 6
__|___|__
  |   |
7 | X | 9
  |   |
Enter Your Choice: 9


  |   |
O | X | 3
__|___|__
  |   |
X | O | 6
__|___|__
  |   |
7 | X | O
  |   |
O Wins

Но он все еще не может распознать мой выигрышный ход.

Все остальные функции были протестированы, когда пользователь играл против пользователя, и все они работают нормально. Буду признателен за помощь.

Я рад предоставить свой полный код, если это необходимо, и все остальное, что требуется.

1 Ответ

0 голосов
/ 02 сентября 2018

Пара наблюдений.

1) if (depth == 0) return 0; следует заменить на что-то вроде

if (depth == 0) return EvaluatePosition();,

потому что в настоящее время ваш алгоритм будет возвращать 0 (оценка, соответствующая ничьей) всякий раз, когда он достигает нулевой глубины (в то время как фактическая позиция на нулевой глубине может не совпадать - например, одна из сторон может иметь огромное преимущество). Функция EvaluatePosition() должна отражать текущую позицию на доске (она должна говорить что-то вроде «Х имеет преимущество», «О теряет», «Позиция более или менее равна» и т. Д., Представленная в виде числа). Обратите внимание, что это будет иметь значение, только если срабатывает условие depth == 0, в противном случае оно не имеет значения.

2) Вам действительно нужны эти вещи emptyboard? Вы можете перебрать все квадраты на новой доске и, найдя пустой квадрат, скопировать оригинальную доску, сделать движение на этом пустом квадрате и вызвать минимакс с скопированной и обновленной доской. В псевдокоде это будет выглядеть примерно так:

for square in board.squares: if square is empty: board_copy = Copy(board) board_copy.MakeMove(square) score = minimax(board_copy, /*other arguments*/) /*the rest of minimax function*/

3) Элемент if (alpha >= beta) break; присутствует в обеих ветвях (для mult == 1 и mult != 1), поэтому вы можете поместить его после блока if-else, чтобы уменьшить количество повторений кода.

4) Проверьте правильность вашего алгоритма без сокращения альфа-бета. Результаты простого минимакса и минимаксного сокращения альфа-бета должны быть одинаковыми, но простой минимакс легче понять, кодировать и отлаживать. После того, как ваш обычный минимакс работает должным образом, добавьте такие улучшения, как обрезка альфа-бета и другие.

...