#python #minimax #alpha-beta-pruning
#питон #минимаксный #альфа-бета-обрезка
Вопрос:
РЕДАКТИРОВАТЬ 30/03/2021: Вопрос был действительно плохо сформулирован, переформулировав его
Я внедрил алгоритм альфа-бета-обрезки в Python, и мне было интересно, нормально ли для него не идти по самому быстрому маршруту победы (иногда он одерживает победу за 2 хода, в то время как мог бы выиграть за 1).
import math
from collections import Counter
from copy import copy, deepcopy
""" Board Class Definition """
class Board:
""" constructor """
def __init__(self):
# init data
self.data = [ "." for i in range(9) ]
""" copy constructor equivalent """
@staticmethod
def copy(board):
return deepcopy(board)
""" play at given coordinates """
def play_at(self, position, color):
# check if you can play
if self.data[position] == ".":
# make the move
self.data[position] = color
return True
# did not play
return False
""" get coordinates of empty pieces on the board """
def get_playable_coord(self):
# define coordinates of empty tiles
return [ i for i in range(9) if self.data[i] == "." ]
""" board is full """
def is_full(self):
# define tile counter
c = Counter( [ self.data[i] for i in range(9) ] )
return ( c["x"] c["o"] == 9 )
""" get winner of the board """
def get_winner(self):
# straight lines to check
straightLines = [ (0, 1, 2) , (3, 4, 5) , (6, 7, 8) , (0, 3, 6) , (1, 4, 7) , (2, 5, 8) , (0, 4, 8) , (2, 4, 6) ]
# check straight lines - 8 in total
for i in range(8):
# get counter of line of tiles
c = Counter( [ self.data[j] for j in straightLines[i] ] )
# different scenarii
if c["x"] == 3:
return "x"
elif c["o"] == 3:
return "o"
# if board is full, game is a draw
if self.is_full():
return "draw"
# return None by default
return None
""" get heuristic value of board - for "x" if 'reverse' == False """
def get_heuristic_value(self, reverse):
# init variable
value = 0
# straight lines to check
straightLines = [ (0, 1, 2) , (3, 4, 5) , (6, 7, 8) , (0, 3, 6) , (1, 4, 7) , (2, 5, 8) , (0, 4, 8) , (2, 4, 6) ]
# check straight lines - 8 in total
for i in range(8):
# get counter of line of tiles
c = Counter( [ self.data[j] for j in straightLines[i] ] )
# different scenarii
if c["x"] == 3:
value = 100
elif c["x"] == 2 and c["."] == 1:
value = 10
elif c["x"] == 1 and c["."] == 2:
value = 1
elif c["o"] == 3:
value -= 100
elif c["o"] == 2 and c["."] == 1:
value -= 10
elif c["o"] == 1 and c["."] == 2:
value -= 1
# return heuristic value
if reverse:
return -value
else:
return value
""" Model Class Definition """
class Model:
""" constructor """
def __init__(self, color):
# define parameters
self.color = color
self.other = self.get_opponent(color)
# define board
self.board = Board()
# define winner
self.winner = None
# 'x' plays first
if self.other == "x":
self.make_ai_move()
""" get opponent """
def get_opponent(self, player):
if player == "x":
return "o"
return "x"
""" player makes a move in given position """
def make_player_move(self, pos):
if self.winner is None:
# get result of board method
res = self.board.play_at(pos, self.color)
# check end of game <?>
self.winner = self.board.get_winner()
if res and self.winner is None:
# make AI move
self.make_ai_move()
""" AI makes a move by using alphabeta pruning on all child nodes """
def make_ai_move(self):
# init variables
best, bestValue = None, - math.inf
for i in self.board.get_playable_coord():
# copy board as child
copie = Board.copy(self.board)
copie.play_at(i, self.other)
# use alpha beta amp;amp; (potentially) register play
value = self.alphabeta(copie, 10, - math.inf, math.inf, False)
if value > bestValue:
best, bestValue = i, value
# play at best coordinates
self.board.play_at(best, self.other)
# check end of game <?>
self.winner = self.board.get_winner()
""" alpha beta function (minimax optimization) """
def alphabeta(self, node, depth, alpha, beta, maximizingPlayer):
# ending condition
if depth == 0 or node.get_winner() is not None:
return node.get_heuristic_value(self.other == "o")
# recursive part initialization
if maximizingPlayer:
value = - math.inf
for pos in node.get_playable_coord():
# copy board as child
child = Board.copy(node)
child.play_at(pos, self.other)
value = max(value, self.alphabeta(child, depth-1, alpha, beta, False))
# update alpha
alpha = max(alpha, value)
if alpha >= beta:
break
return value
else:
value = math.inf
for pos in node.get_playable_coord():
# copy board as child
child = Board.copy(node)
child.play_at(pos, self.color)
value = min(value, self.alphabeta(child, depth-1, alpha, beta, True))
# update beta
beta = min(beta, value)
if beta <= alpha:
break
return value
Мой вывод по этому вопросу:
Альфа-бета-обрезка — это алгоритм поиска в глубину, а не алгоритм поиска в ширину, поэтому я думаю, что для него естественно выбирать первый найденный маршрут, независимо от его глубины, а не искать самый быстрый…
Комментарии:
1. Разве начальный альфа / бета-вызов не должен быть True для maximizing_player?
2. Да, так и должно быть, если вы переходите от текущего состояния доски, но то, что я сделал, это подсчитал счет для каждого возможного хода ИИ, а затем выбрал лучший из них
3. Вы пытались распечатать выведенный результат? Вы когда-нибудь выигрывали или выигрывали?
4. Я добавил несколько примеров оценки в сообщение
5. На пустой доске вы должны получить счет 0 (равный), поскольку всегда идет равная игра, если оба игрока играют правильно.
Ответ №1:
Я знаю, что это не ответ на вопрос, но я хотел бы предложить, возможно, более простой подход для игрока в крестики-нолики с искусственным интеллектом, который включает в себя вычисление того, является ли позиция выигрышной или проигрышной. Это потребует рассмотрения всех допустимых позиций, которые могут произойти в любой момент игры, но поскольку поле 3×3, количество допустимых позиций меньше 3 ^ 9 = 19683 (каждая позиция равна либо ‘x’, ‘o’, либо ‘ ‘). Это не жесткая привязка, поскольку многие позиции недопустимы с точки зрения правил игры. Я предлагаю вам начать отсюда, потому что алгоритм, о котором вы говорите, в основном используется в более сложных играх, где полный поиск невозможен.
Следовательно, все, что вам нужно сделать, это рассчитать показатель выигрыша / проигрыша для каждой позиции один раз после запуска программы, а затем принять решение в O (1). Это приемлемо для поля 3×3, но, возможно, не намного больше.
Общий подход описан здесь: https://cp-algorithms.com/game_theory/games_on_graphs.html . В двух словах, вы строите дерево возможных ходов, помечаете листья как выигрышные или проигрышные и продвигаетесь вверх, рассматривая все дочерние переходы (например, если каждый переход приводит к выигрышной позиции для противоположного игрока, позиция в проигрыше).
На случай, если вы понимаете по-русски, вот ссылка на оригинальную страницу: http://e-maxx.ru/algo/games_on_graphs
P.S. Я также играл с этой игрой в какой-то момент в прошлом и применял этот подход. Вот мое репо на случай, если вы захотите провести расследование: https://github.com/yuuurchyk/cpp_tic_tac_toe . Справедливое предупреждение: он написан на C , и код немного уродливый
Комментарии:
1. «вы строите дерево возможных ходов, помечаете листья как выигрышные или проигрышные и продвигаетесь вверх, рассматривая все дочерние переходы (например, если каждый переход приводит к выигрышной позиции для противоположного игрока, позиция в проигрыше)» Может быть, я был неправ с самого начала, но разве это не такпринцип минимакса (и, соответственно, альфа-бета-обрезка)?
2. В любом случае, спасибо за ссылки, я собираюсь проверить это и посмотреть, смогу ли я адаптироваться к ним
3. @Tartempion Я предполагаю, что это немного по-другому, поскольку графический подход не вводит никакой эвристической оценки для узла. Что касается обрезки, я не знаком с этим методом, но мне кажется, что он не исследует все пространство выборки. Поэтому я предполагаю, что его следует запускать более 1 раза (здесь я могу ошибаться). Для такой простой игры, как крестики-нолики, было бы приемлемо пройти все дерево раз и навсегда. Вы даже можете попробовать отправить предварительно рассчитанное игровое дерево и получить полностью обученного агента с самого начала (конечно, это должно быть профилировано).