Разрабатывая браузерную игру Гомоку (5 в ряд) на языке JavaScript, я столкнулся с необходимостью реализации компьютерного противника (ИИ). В данной статье кратко описаны основные компоненты ИИ, а также приведено сравнение алгоритмов поиска: NegaMax, NegaScout и MTD-F.

Основные компоненты ИИ: функция оценки состояния игры, генератор ходов, алгоритм поиска, алгоритм определения победы.

Алгоритм определения победы

Тут все просто. Минимаксные алгоритмы ходят по очереди за минимизирующего и максимизирующего игрока. При в ходе в функцию поиска, мы проверяем, выиграл ли наш противник. Если он не выиграл, то мы продолжаем выполнение функции, иначе возвращаем значение отражающее его победу.

function negamax(newBoard, player, depth, a, b, hash, restrictions, last_i, last_j) {
  ...
   if (checkwin(newBoard, last_i, last_j)) {
        return -2000000 + (MaximumDepth - depth) //Прибавляем текущую глубину, чтобы мотивировать алгоритм выигрывать более быстрым способом/проигрывать более медленным
    }
  ...
}

function checkwin(Board, x, y) {  
    const Directions = get_directions(Board, x, y)
    for (let i = 0; i < 4; i++) { //Проверяем все 4 направления
        if (check_directions(Directions[i])) {
            return true
        }
    }
}

function get_directions(Board, x, y) { //Генерируем направления
    const Directions = [[], [], [], []];
    for (let i = -4; i < 5; i++) {
        if (x + i >= 0 && x + i <= Rows - 1) {
            Directions[0].push(Board[x + i][y])
            if (y + i >= 0 && y + i <= Columns - 1) {
                Directions[2].push(Board[x + i][y + i])
            }
        }
        if (y + i >= 0 && y + i <= Columns - 1) {
            Directions[1].push(Board[x][y + i])
            if (x - i >= 0 && x - i <= Rows - 1) {
                Directions[3].push(Board[x - i][y + i])
            }
        }
    }
    return Directions
}

Если последний ход противника был для него выигрышным, то мы сможем найти ряд из 5 повторяющихся значений хотя бы на одном из 4 направлений.

function check_directions(arr) {
    for (let i = 0; i < arr.length - 4; i++) {
        if (arr[i] !== 0) {
            if (arr[i] === arr[i + 1] && arr[i] === arr[i + 2] && arr[i] === arr[i + 3] && arr[i] === arr[i + 4]) {
                return true
            }
        }
    }
}

Представление доски

Так как мы пишем на JS, используем обычный двумерный массив. (Я экспериментировал с TypedArray, он не удобен и не дает прироста производительности).
1 - наша фигура, -1 - фигура противника.

Таблица транспозиций (Transposition Table)

Таблица транспозиций — это кеш ранее посещенных состояний доски и связанных с ними оценок в игровом дереве. Если позиция повторяется через другую последовательность ходов, извлекается полезная информация. Для идентификации состояния доски используется хеширование Зобриста (Zobrist hashing).

Zobrist hashing

Для того чтобы получить хэш текущего состояния доски необходимо:

1. Заранее сгенерировать таблицу, содержащую N больших случайных чисел, где N=Количество столбцов*Количество Строк*Количество игроков

2. Применить операцию xor к элементам таблицы, соответствующим определенным позициям на доске

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

function Table_init() {
  for (let i = 0; i < Rows; i++) {
    Table[i] = [];
    for (let j = 0; j < Columns; j++) {
      Table[i][j] = []
      Table[i][j][0] = random32(); //1
      Table[i][j][1] = random32(); //2
    }
  }

function hash(board) { //Хеширование всей доски с нуля
  let h = 0;
  let p;
  for (let i = 0; i < Rows; i++) {
    for (let j = 0; j < Columns; j++) {
      const Board_value = board[i][j];
      if (Board_value !== 0) { //игнорируем пустые клетки
        if (Board_value === -1) {
          p = 0  //игрок 0
        } else {
          p = 1 //игрок 1
        }
        h = h ^ Table[i][j][p];
      }
    }
  }
  return h;
}

function update_hash(hash, player, row, col) { //Обновляем хэш
    if (player === -1) {
        player = 0
    } else {
        player = 1
    }
    hash = hash ^ Table[row][col][player];
    return hash
}

Генерация ходов

function BoardGenerator(restrictions, Board, player) {
  const availSpots_score = []; //c is j  r is i;
  const min_r = restrictions[0];
  const min_c = restrictions[1];
  const max_r = restrictions[2];
  const max_c = restrictions[3];;
  for (let i = min_r - 2; i <= max_r + 2; i++) {
    for (let j = min_c - 2; j <= max_c + 2; j++) {
      if (Board[i][j] === 0 && !remoteCell(Board, i, j)) {
        const move = {}
        move.i = i;
        move.j = j;
        move.score = evaluate_move(Board, i, j, player) //С помощью функции оценки мы определяем насколько ход перспективен, присваиваем ему score. 
        if (move.score === WIN_DETECTED) {
          return [move]
        }
        availSpots_score.push(move)
      }
    }
  }
  availSpots_score.sort(compare) //Затем сортируем ходы по score
  //  return availSpots_score.slice(0,10)
  return availSpots_score;
}

Алгоритм генерации ходов:

1.    Вписываем все фигуры на доске в минимально возможный прямоугольник (черный прямоугольник)

2.    Начинаем поиск в радиусе двух клеток от этого прямоугольника (синий прямоугольник)

3.    Если рассматриваемая клетка не имеет соседей в радиусе двух клеток, клетка считается неперспективной и отбрасывается (оранжевый квадрат)

Move ordering

В алгоритмах с использованием альфа-бета отсечения, чем раньше будут исследованы хорошие ходы, тем больше будут отсечения в дереве и тем быстрее будет проходить поиск. Для определения score хода, оцениваются 4 направления: горизонтальное, вертикальное, диагональное и анти диагональное. Итоговый score хода - это сумма score всех направлений.

function evaluate_move(Board, x, y, player) {
  let score = 0;
  const Directions = get_directions(Board, x, y);
  let temp_score;
  for (let i = 0; i < 4; i++) {
    temp_score = evaluate_direction(Directions[i], player);
    if (temp_score === WIN_DETECTED) { //если данный ход выигрывает игру, сразу же возвращаем его
      return WIN_DETECTED
    } else {
      score += temp_score
    }
  }
  return score;
}

function evaluate_direction(direction_arr, player) {
  let score = 0;
  for (let i = 0; (i + 4) < direction_arr.length; i++) {
    let you = 0;
    let enemy = 0;
    for (let j = 0; j <= 4; j++) {
      if (direction_arr[i + j] === player) {
        you++
      } else if (direction_arr[i + j] === -player) {
        enemy++
      }
    }
    score += evalff(get_seq(you, enemy));
    if ((score >= 800000)) {
      return WIN_DETECTED;
    }
  }
  return score
}

function evalff(seq) {
    switch (seq) {
        case 0:
            return 7;
        case 1:
            return 35;
        case 2:
            return 800;
        case 3:
            return 15000;
        case 4:
            return 800000;
        case -1:
            return 15;
        case -2:
            return 400;
        case -3:
            return 1800;
        case -4:
            return 100000;
        case 17:
            return 0;
    }
}

function get_seq(y, e) {
    if (y + e === 0) {
        return 0;
    }
    if (y !== 0 && e === 0) {
        return y
    }
    if (y === 0 && e !== 0) {
        return -e
    }
    if (y !== 0 && e !== 0) {
        return 17
    }
}

Функция оценки

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

function evaluate_state(Board, player, hash, restrictions) {
    const  black_score = eval_board(Board, -1, restrictions);
    const  white_score = eval_board(Board, 1, restrictions);
    let score = 0;
    if (player == -1) {
        score = (black_score - white_score);
    } else {
        score = (white_score - black_score);
    }
    StateCache.set(hash,score); 
    StateCachePuts++;
    return score;
}

eval_board оценивает состояние доски с точки зрения определенного игрока. Функция проходит по всей доске и вычисляет score, который зависит от количества открытых с обеих сторон (Live) и полузакрытых (Dead) линий для определенного игрока.

Например: _xx_ - открытая двойка, _oxx_ - полуоткрытая двойка.

const LiveOne = 10;
const DeadOne = 1;
const LiveTwo = 100;
const DeadTwo = 10;
const LiveThree = 1000;
const DeadThree = 100;
const LiveFour = 10000;
const DeadFour = 1000;
const Five = 100000;

Iterative Deepening

Основная проблема минимаксных алгоритмов, это невозможность остановить вычисления до достижений заданной глубины и получить результат. Решение - искать до глубины N, сохранять результат и затем искать до глубины N+2. (Мы увеличиваем глубину на 2, т.к последним должен ходить наш противник). Когда нам понадобится вернуть результат (например, когда истечет время, выделенное на вычисления), мы возвращаем последний готовый ход. Данный подход не вызывает значительного снижения производительности, так как информация хранящаяся в кеше значительно ускоряет поиск.

NegaMax, NegaScout, MTDF

Имплементацию данных алгоритмов рекомендую взять из проверенных источников, например chessprogramming.org, и постепенно модифицировать её. Это связано с тем, что баги в алгоритмах поиска не всегда легко обнаружить и они могут значительно снижать силу алгоритма.

Negamax с альфа-бета отсечением и таблицей транспозиций

Достаточно простой алгоритм, рекомендую начинать с него.

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

этого нам помогает достичь хороший move ordering).

Количество рассмотренных листьев при глубине n и b(коэффициент ветвления) = 40

NegaScout

NegaScout – оптимизация альфа-бета-отсечения, использует метод поиска с нулевым окном. Использовался в шахматном компьютере Deep Blue.

MTD-F

MTD(F) - минимаксный алгоритм, надстройка над альфа-бета. Алгоритм очень краток, но он работает быстрее NegaScout, либо наравне с ним (Это утверждение взято из оригинальной статьи, в моем тесте MTD-F работает медленнее чем NegaScout)

Оригинальный псевдокод:

function MTDF(root : node_type; f : integer; d : integer) : integer;
      g := f;
      upperbound := +INFINITY;
      lowerbound := -INFINITY;
      repeat
            if g == lowerbound then beta := g + 1 else beta := g;
            g := AlphaBetaWithMemory(root, beta - 1, beta, d);
            if g < beta then upperbound := g else lowerbound := g;
      until lowerbound >= upperbound;
      return g;

Ограничение количества рассматриваемых ходов

Вы могли задуматься, зачем нужна эта строчка в генераторе ходов.

//  return availSpots_score.slice(0,10)

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

Тесты (глубина=8)

MTD(f) 10 - рассматривает только 10 лучших ходов.

StateCache - количество листьев в кеше.

Турнир (bo3) (60 s)

После каждой игры алгоритмы меняются сторонами.

Все алгоритмы реализованы c помощью Iterative Deepening.

1 – победа, 0.5 – ничья

MTD(f) 10  1.5:0.5  NegaScout 10

Почему микрооптимизации не усилят алгоритм

mtdf(10)

Чтобы усилить алгоритм, нужно искать на большую глубину. Чтобы искать на большую глубину, нужно ускорение в 3-7 раз.

Сравнение с другими алгоритмами(js)

(Сравнение не совсем честное, оппоненты не имели фиксированного времени на ход и на ход тратили меньше 10 секунд)

Что можно улучшить (в теории)

Представление доски

Можно представить доску как 1d массив (пробовал, не дает прироста производительности)

Можно использовать bitboards (не думаю, что даст прирост в js)

Функция оценки/Move ordering

Я взял значения оценки линий из других движков, эти числа в большинстве движков примерно одинаковые. Возможно, что их еще можно улучшить. Если устроить турнир между версиями алгоритма с различными значениями оценки линий, то можно найти более корректные оценки. (Это потребует написания программы для проведения турниров и много вычислительной мощности)
Также можно заменить функцию оценки полностью и натренировать нейросеть, но здесь важно соотношение между скоростью оценки и её точностью. Более медленная функция оценки значительно сократит глубину поиска. (+ Я сомневаюсь, что tensorflow.js работает быстро)

Алгоритм поиска

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

Есть всего 2 варианта: использовать MCTS или очередную оптимизацию альфа-бета отсечения.

Я пробовал использовать MCTS со своей функцией оценки, играет очень плохо. По результатам AlphaZero/MuZero можно увидеть, что MCTS + NN выигрывают у стандартных алгоритмов, но опять же, я сомневаюсь что это можно запустить в браузере с адекватной производительностью, не говоря уже о вычислительной мощности, необходимой для того чтобы натренировать хорошую NN.

Поиграть против ai(mtdf10, поле 21x21) - https://4battle.ru/play_offline

В консоль выводится различная полезная информация, например, текущая оценка ИИ своей позиции.

Код:

js версия(основная)

С++ версия (Я не эксперт в C++, просто скопировал js код и заставил его работать. C++ версия работает в 2-2.5 раза быстрее, скорее всего её можно ускорить ещё сильнее)

(Хорошие статьи по теме: 1, 2)