AI в шашках. Разбор NegaMax и Alpha-Beta алгоритмов

AI в шашках. Разбор NegaMax и Alpha-Beta алгоритмов

Как и обещал недавно, опишу в этой статьей алгоритмы поиска ходов в играх подобных шашкам и шахматам. Т. е. мы напишем AI, с которым потом сможем сыграть.

История развития алгоритмов

Алгоритм поиска лучшего хода впервые был описан Клодом Шенноном. Суть достаточно проста и строится он на рекурсии. Некоторые задачи просто невозможно решить без рекурсии. Шеннон делал перебор всех вариантов в некотором диапазоне. Конечно же, сейчас никто так не делает, вместо перебора используют форсированные ходы (которые требуют немедленного ответа или максимального приращения оценке фигуры).

Одной из основ работы алгоритма есть оценка фигур. Оценка делится на стратегическую и материальную. Каждый игрок должен представлять себе ценность той или иной фигуры.

Также хочу затронуть оптимизацию перебора. Основной алгоритм: alpha-beta, позволяет досрочно прервать перебор и вернуть оценку без погрешностей.

Деревья

Одним из основных алгоритмов почти любой игры – поиск по дереву. Именно Шеннон придумал и реализовал всё это в своих работах. Все возможные варианты (позиции) игровых фигур рассматриваются в виде дерева, ветви – возможные хода, листья – заключительные положения, для которых мы можем точно назвать результат игры.

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

Об алгоритмах перебора

Для шахмат среднее количество возможных перемещений из какой-то заданной позиции = 40. Значит, если нам нужно искать на глубину в 4, мы получим: 40 * 4 = 2560 000 позиций. 5: 10 240 000. Я боюсь далее наводить примеры. Как видите, дерево перебора растёт экспоненциально. В этом и заключается проблема таких игр: нам нужно перебрать все возможные варианты и получить более-менее правильную оценку состояния игры. На сегодняшний день, оптимальная глубина поиска 6-7. Самые популярные алгоритмы перебора: MiniMax и NegaMax. Обнаружение лучшего хода заключается в поиске по дереву всех возможных позиций. В корне дерева мы ищем лучшую последующую позицию для активного игрока. Поиск по шахматному или шашечному дереву – чредование между максимизированием и минимизированием оценок позиций в дереве, от этого и пошло название алгоритма: minimaxing (MiniMax). Чтобы устранить различие между собственной позицией и позицией противника, значение позиции часто оценивается с точки зрения игрока, которому принадлежит ход, поэтому мы берем оценку противника с противоположным знаком (+/-). Название этого алгоритма – negamaxing (NegaMax).

NegaMax

Этот алгоритм основывается на том, что max(a, b) = - min(-a, - b)

NegaMax отличается тем, что более оптимизирован (на счёт этого нужно ещё поспорить) и имеет меньше строк кода. Вот псевдокод реализации этого алгоритма int NegaMax(position, depth)

{ if (depth == 0) return Evalute(position); // Оценка позиции стороны активного игрока int best = - INFINITY; list succ = Successors(position); // Получаем набор позиций, которые могут быть получены в результате одного хода while (succ. size() != 0)

{ position = RemoveOne(succ); value = - NegaMax(position, depth - 1); // Вызываем оценку противника с противоположным знаком if (value > best) best = value;

} return best;

}

Почитать подробней о MiniMax и NegaMax можно здесь: en. wikipedia. org/wiki/Minimax.

Оптимизация перебора: Alpha-Beta алгоритм

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

Алгоритм получает два дополнительных параметра: граница поиска (alpha, beta) – промежуток, в котором мы заинтересованы в точных оценках.

Int AlphaBeta(position, depth, alpha, beta)

{ if (depth == 0) return Evalute(pos); int best = - INFINITY; list succ = Successors(position); while (succ. size!= 0 && best < beta)

{ position = RemoveOne(succ); if (best > alpha) alpha = best; value = - AlphaBeta(position, depth - 1, - beta, - alpha); if (value > best) best = value;

} return best;

}

Выгода в том, что мы раньше выходим из цикла, когда значение beta стаёт больше значения best.

NegaMax via Alpha-Beta

# Ход class Move: old_row = None old_col = None new_row = None new_col = None move = None jump = None value = None def _negaMax(gameboard, player, maxdepth, depth, alpha, beta): bestValue = -1000; value = -1000; element = 0 row = col = 0 localAlpha = alpha if _gameEnded(player) or depth == maxdepth: # _gameEnded в предыдущей статье, проверяет окончание игры return evalute(player) # Функция оценивает позицию игрока, рассмотрим ниже movelist = [Move() for _ in range(100)] for i in xrange(8): newboard = [gameSquare() for _ in xrange(8)] while movesLeft(movelist, element): # Есть ли какие-либо хода, убранные из movelist row = 0 col = 0 for row in xrange(8): for col in xrange(8): newboard[row][col] = gameboard[row][col] doMove(newboard, movelist[element], player) # Анализ хода, рассмотрим ниже value = -_negaMax(newboard, 3 - player, 5, depth + 1, - beta, - localalpha) if value > bestvalue: bestvalue = value if bestvalue >= beta: break if bestvalue > localalpha: localalpha = bestvalue element += 1 return bestvalue

Оценка позиции активного игрока

Нам нужно немного изменить вид функции piecesLeft, которая проверяет наличие шашек в указанного игрока. Добавим аргумент – board.

Def piecesLeft(slef, board, player): pieces = 0 for row in xrange(8): for col in xrange(8): if board[row][col].validSquare and board[row][col].occupied and board[row][col].occupier. player == player: pieces += 1 return pieces

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

Def evalute(gameboard, player): return piecesLeft(gameboard, player) - piecesLeft(gameboard, (3 - player))

3 – player даст нам номер противоположного игрока (Если игрок под номером 1, то 3-1 = 2, если под номером 2, то 3-2 = 1).

Следующая функция проверяет существования хода в списке сгенерированных.

Def movesLeft(movelist, element): if movelist[element].old_row == -1: return False else: return True

Анализ сгенерированного хода

Опять нам нужно будет изменить уже существующие функции, которые делают перемещения и изменения состояния игры: def movePiece(board, old_row, old_col, new_row, new_col): def jumpPiece(board, old_row, old_col, new_row, new_col): def kingMe(board, row, col, player): def doMove(gameboard, moves, player): if moves. move: movePiece(gameboard, moves. old_row, moves. old_col, moves. new_row, moves. new_col) elif moves. jump: jumpPiece(gameboard, moves. old_row, move. old_col, moves. new_row, moves. new_col) if player == 1 and moves. new_row == 0 or player == 2 and moves. new_row == 7: kingMe(gameboard, moves. new_row, moves. new_col, player)

Оценка только вершины дерева – AiMax алгоритм

Следующий алгоритм существует как дополнение к NegaMax, он будет получать оценку и правильность движений только в вершине дерева.

Def aimax(gameboard, player, maxdepth): bestvalue = -1000 element = 0 row = col = 0 bestmove = Move() if _gameEnded(gameboard, player): return bestmove movelist = [Move() for _ in range(100)] for i in xrange(8): newboard = [gameSquare() for _ in xrange(8)] generateMoves(gameboard, movelist, player) # Генерирует все возможные движения, рассмотрим ниже while movesLeft(movelist, element): row = 0 col = 0 for row in xrange(8): for col in xrange(8): newboard[row][col] = gameboard[row][col] doMove(newboard, movelist[element], player) movelist[element].value = - negamax(newboard, 3 - player, maxdepth, 0, -1000, 1000) element += 1 element = 0 while movesLeft(movelist, element): if movelist[element].value == bestvalue: row = random. random() col = random. random() if row > col and

( not (movelist[element].jump and not bestmove. jump) or not (movelist[element].jump and bestmove. jump) ): row = random. random() col = random. random() if row > col: bestvalue = bestvalue else: bestmove = movelist[element] bestvalue = movelist[element].value elif movelist[element].jump and not bestmove. jump: bestmove = movelist[element] bestvalue = movelist[element].value elif movelist[element].value > bestvalue: bestmove = movelist[element] bestvalue = movelist[element].value element += 1 return bestmove

Генерация всех возможных ходов

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

Def generateMoves(gameboard, movelist, player): row = col = element = 0 for row in xrange(8): for col in xrange(8): if gameboard[row][col].validSquare and gameboard[row][col].occupied and gameboard[row][col].occupier. player == player and moveSingleSpace(gameboard, player, row, col): if (

( not gameboard[row-1][col-1].occupied and not ((row - 1) < 0) and not ((col - 1) < 0)

) and validDirection(gameboard, row, col, row-1, col-1, player)

): movelist[element].old_row = row movelist[element].old_col = col movelist[element].new_row = row - 1 movelist[element].new_col = col - 1 movelist[element].move = True movelist[element].jump = False element += 1 if (

( not gameboard[row -1][col+1].occupied and not ((row - 1) < 0) and not ((col + 1) > 7)

) and validDirection(gameboard, row, col, row-1, col+1, player)

): movelist[element].old_row = row movelist[element].old_col = col movelist[element].new_row = row - 1 movelist[element].new_col = col + 1 movelist[element].move = True movelist[element].jump = False element += 1 if (

( not gameboard[row+1][col-1].occupied and not ((row + 1) > 7) and not ((col - 1) < 0)

) and validDirection(gameboard, row, col, row+1, col-1, player)

): movelist[element].old_row = row movelist[element].old_col = col movelist[element].new_row = row + 1 movelist[element].new_col = col - 1 movelist[element].move = True movelist[element].jump = False element += 1 if (

( not gameboard[row+1][col+1].occupied and not ((row + 1) > 7) and not ((col + 1) > 7)

) and validDirection(gameboard, row, col, row+1, col+1, player)

): movelist[element].old_row = row movelist[element].old_col = col movelist[element].new_row = row + 1 movelist[element].new_col = col + 1 movelist[element].move = True movelist[element].jump = False element += 1 if ( gameboard[row][col].valid_square and gameboard[row][col].occupied and gameboard[row][col].occupier. player == player and jumpAvailable(gameboard, player, row, col, 0,0,0) ): if (

( not gameboard[row-2][col-2].occupied and not ((row - 2) < 0) and not ((col - 2) < 0)

) and validDirection(gameboard, row, col, row-2, col-2, player) and canJump(gameboard, row, col, row-2, col-2, player)

): movelist[element].old_row = row movelist[element].old_col = col movelist[element].new_row = row - 2 movelist[element].new_col = col - 2 movelist[element].move = False movelist[element].jump = True element += 1 if (

( not gameboard[row-2][col+2].occupied and not ((row - 2) < 0) and not ((col + 2) > 7)

) and validDirection(gameboard, row, col, row-2, col+2, player) and canJump(gameboard, row, col, row-2, col+2, player)

): movelist[element].old_row = row movelist[element].old_col = col movelist[element].new_row = row - 2 movelist[element].new_col = col + 2 movelist[element].move = False movelist[element].jump = True element += 1 if (

( not gameboard[row+2][col-2].occupied and not ((row + 2) > 7) and not ((col - 2) < 0)

) and validDirection(gameboard, row, col, row+2, col-2, player) and canJump(gameboard, row, col, row+2, col-2, player)

): movelist[element].old_row = row movelist[element].old_col = col movelist[element].new_row = row + 2 movelist[element].new_col = col - 2 movelist[element].move = False movelist[element].jump = True element += 1 if (

( not gameboard[row+2][col+2].occupied and not ((row + 2) > 7) and not ((col + 2) > 7)

) and validDirection(gameboard, row, col, row+2, col+2, player) and canJump(gameboard, row, col, row+2, col+2, player)

): movelist[element].old_row = row movelist[element].old_col = col movelist[element].new_row = row + 2 movelist[element].new_col = col + 2 movelist[element].move = False movelist[element].jump = True element += 1 movelist[element].old_row = -1

Связка всех алгоритмов

Теперь соединим все функции, которые мы создали, и заставим их корректно работать. Следующую функцию нужно вызывать, когда ход перешёл к компьютеру.

Def aiturn(gameboard, player, depth): old_row = old_col = new_row = new_col = 0 aimove = Move() aimove = aimax(gameboard, player, depth)

# Если простой ход if aimove. move: movePiece(gameboard, aimove. old_row, aimove. old_col, aimove. new_row, aimove. new_col)

# Если движение - прыжок if aimove. jump: jumpPiece(gameboard, aimove. old_row, aimove. old_col, aimove. new_row, aimove. new_col)

# Если шашка достигла противоположного края if player == 1 and aimove. new_row == 0 or player == 2 and aimove. new_row == 7: kingMe(gameboard, aimove. new_row, aimove. new_col, player)

# Меняем номер игрока на противоположный player = (player % 2) + 1 if gameEnded(gameboard, player): print 'The player number ' + str(player) + ' has won the game!'

Заключение

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


Карта сайта


Информационный сайт Webavtocat.ru