MiniMax объяснил идиот
https://stackoverflow.com/questions/3956258
-
08-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я потратил весь свой день, пытаясь использовать алгоритм MiniMax, чтобы сделать непревзойденное тиктакты AI. Я что-то пропустил по пути (обжаренный мозг).
Я не ищу код здесь, просто лучшее объяснение того, где я пошел не так.
Вот мой текущий код (метод miniMax всегда возвращается 0 по какой-то причине):
from copy import deepcopy
class Square(object):
def __init__(self, player=None):
self.player = player
@property
def empty(self):
return self.player is None
class Board(object):
winning_combos = (
[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8],
[0, 4, 8], [2, 4, 6],
)
def __init__(self, squares={}):
self.squares = squares
for i in range(9):
if self.squares.get(i) is None:
self.squares[i] = Square()
@property
def available_moves(self):
return [k for k, v in self.squares.iteritems() if v.empty]
@property
def complete(self):
for combo in self.winning_combos:
combo_available = True
for pos in combo:
if not pos in self.available_moves:
combo_available = False
if combo_available:
return self.winner is not None
return True
@property
def player_won(self):
return self.winner == 'X'
@property
def computer_won(self):
return self.winner == 'O'
@property
def tied(self):
return self.complete == True and self.winner is None
@property
def winner(self):
for player in ('X', 'O'):
positions = self.get_squares(player)
for combo in self.winning_combos:
win = True
for pos in combo:
if pos not in positions:
win = False
if win:
return player
return None
@property
def heuristic(self):
if self.player_won:
return -1
elif self.tied:
return 0
elif self.computer_won:
return 1
def get_squares(self, player):
return [k for k,v in self.squares.iteritems() if v.player == player]
def make_move(self, position, player):
self.squares[position] = Square(player)
def minimax(self, node, player):
if node.complete:
return node.heuristic
a = -1e10000
for move in node.available_moves:
child = deepcopy(node)
child.make_move(move, player)
a = max([a, -self.minimax(child, get_enemy(player))])
return a
def get_enemy(player):
if player == 'X':
return 'O'
return 'X'
Решение
Ваша полная функция не работает должным образом, вызывая объявление игр привязано до того, как все может произойти. Например, рассмотрим эту настройку:
>> oWinning = {
1: Square('X'),
3: Square('O'), 4: Square('X'),
6: Square('O'), 8: Square('X'),
}
>> nb = Board(oWinning)
>> nb.complete
True
>> nb.tied
True
Это должно быть выигрыш для компьютера на следующем ходу. Вместо этого он говорит, что игра связана.
Проблема в том, что ваша логика в полной мере сейчас проверяет, если все квадраты в комбо бесплатны. Если кто-то из них нет, это предполагает, что комбинация не может быть выиграно. То, что ему нужно сделать, это проверять, заняты ли какие-либо позиции в том, что связаны какие-либо позиции, и до тех пор, пока все эти комбинации либо нет, ни один и тот же игрок, что Combo следует рассматривать все еще доступно.
например
def available_combos(self, player):
return self.available_moves + self.get_squares(player)
@property
def complete(self):
for player in ('X', 'O'):
for combo in self.winning_combos:
combo_available = True
for pos in combo:
if not pos in self.available_combos(player):
combo_available = False
if combo_available:
return self.winner is not None
return True
Теперь, когда я правильно проверил это с обновленным кодом, я получаю ожидаемый результат на этот тестовый случай:
>>> nb.minimax(nb, 'O')
-1
>>> nb.minimax(nb, 'X')
1
Другие советы
Шаг 1: Создайте свое игровое дерево
Начиная с нынешней платы, генерируйте все возможные перемещения, ваш противник может сделать. Тогда для каждого из тех, кто генерирует все возможные движения, которые вы можете сделать. Для Tic-Tac-Toe просто продолжайте, пока никто не может играть. В других играх вы обычно остановитесь после данного времени или глубины.
Это похоже на дерево, нарисуйте его на листе бумаги, нынешняя доска сверху, все противники перемещают один слой ниже, все ваши возможные движения в ответ на один слой ниже и т. Д.
Шаг 2: Оценка всех досок в нижней части дерева
Для простой игры, такой как Tic-Tac-Toe, сделайте счет 0, если вы проиграете, 50 галстук, 100 победа.
Шаг 3: размножаться за счет
Это где мин-макс вступает в игру. Оценка ранее ненасысоразрушенного совета зависит от своих детей и которые попадают в игру. Предположим, как вы, и ваш противник всегда выбирают наилучшее возможное движение в данном состоянии. Лучший ход для противника - это шаг, который дает ты худший балл. Аналогичным образом, ваш лучший шаг - это шаг, который дает вам самый высокий балл. В случае поворота противника вы выбираете ребенка с минимальным баллом (который максимизирует его выгоду). Если это ваш поворот, вы предполагаете, что вы сделаете лучший возможный шаг, поэтому вы выбираете максимум.
Шаг 4: Выберите свой лучший ход
Теперь играйте в ходу, который приводит к лучшему размноженному баллу среди всех возможных пьес из текущей позиции.
Попробуйте его на листе бумаги, если начать с пустой доски, слишком много для вас начнется с некоторой продвинутой позиции TIC-TAC-TAC.
Использование рекурсии:Очень часто это можно упростить с помощью рекурсии. Функция «Scaring» вызывается рекурсивно на каждой глубине и в зависимости от того, является ли глубина нечетной или даже она выбирает макс или мин соответственно для всех возможных движений. Когда никакие движения не возможно, это оценивает статический балл доски. Рекурсивные решения (например, примерный код) может быть немного сложнее, чтобы понять.
Как вы уже знаете, идея MiniMax - это глубокий поиск лучшего значения, предполагая, что противник всегда будет играть в движение с худшим значением (худшее для нас, так лучше для них).
Идея в том, что вы постараетесь дать значение для каждой позиции. Положение, где вы теряете, отрицательно (мы не хотим этого) и позиции, где вы выигрываете, является положительным. Вы предполагаете, что вы всегда будете пытаться для самой высокой позиции, но вы также предполагаете, что противник всегда будет нацелен на должность наименьшего значения, которая имеет наихудший результат для нас, и лучшие для них (они побеждают, мы теряем). Таким образом, вы поставите себя на их обувь, попробуйте поиграть так же хорошо, как вы можете как они, и предполагаете, что они сделают это.
Поэтому, если вы узнаете, у вас есть возможные два хода, один дает им выбор, чтобы выиграть или проиграть, один привел к розыску в любом случае, вы предполагаете, что они пойдут на шаг, который будет иметь их выиграть, если вы позволите им сделать это. Так что лучше идти на розыгрыш.
Теперь для более «алгоритмического» взгляда.
Представьте себе, что ваша сетка почти полна, кроме двух возможных позиций.
Подумайте, что происходит, когда вы играете в первом:
Противник сыграет другой. Это их единственный возможный шаг, поэтому нам не нужно учитывать другие движения от них. Посмотрите на результат, свяжитесь с результирующим значением (+ ∞, если выиграно, 0, если рисовать, -∞, если потеряно: для TIC TAC TOE, вы можете представлять те, что +1 0 и -1).
Теперь подумайте, что происходит, когда вы играете в второй:
(То же самое, противника имеет только один ход, посмотрите на полученную позицию, цените положение).
Вам нужно выбрать между двумя шагами. Это наш ход, поэтому мы хотим лучший результат (это «Макс» в MiniMax). Выберите один с более высоким результатом в качестве нашего «лучшего» движения. Это это для примера «2 ходов от конца».
Теперь представьте, что у вас нет 2, но 3 движения осталось.
Принцип такой же, вы хотите назначить значение каждому из ваших трех возможных движений, чтобы вы могли выбрать лучшее.
Итак, вы начинаете с учетом одного из трех шагов.
Теперь вы сейчас находитесь в ситуации выше, только с 2 возможными движениями, но это поворот противника. Затем вы начнете учитывать одну из возможных шагов для противника, как мы сделали выше. Аналогичным образом, вы смотрите на каждый из возможных ходов, и вы найдете значение для них обоих результатов. Это противник движется, поэтому мы предполагаем, что они будут играть в «лучших» двигаться для них, тот, кто с худшей ячейкой для нас, так что это тот, с меньшим значением (это «мин» в MiniMax). Игнорировать другой; Предположим, что они будут играть то, что вы нашли, было лучше для них для них. Это то, что ваш ход будет давать, так что это значение, которое вы назначаете первым из ваших трех движений.
Теперь вы считаете каждый из ваших других возможных 2 ходов. Вы даете им ценность таким же образом. И из трех шагов вы выбираете один с максимальным значением.
Теперь подумайте, что происходит с 4 ходами. Для каждого из ваших 4 ходов вы посмотрите, что происходит для 3 ходов вашего противника, и для каждого из них вы предполагаете, что они выберут тот, который дает вам худший возможный результат лучших из 2 остальных движений для вас.
Вы видите, где это возглавляет. Для оценки перемещения n шагов с конца вы посмотрите на то, что может произойти для каждого из возможных движений, пытаясь дать им значение, чтобы вы могли выбрать лучшее. В процессе вам придется попытаться найти лучший шаг для игрока, который играет в N-1: противник, и выберите шаг с меньшим значением. В процессе оценки движения N-1 вы должны выбрать между возможным перемещением N-2, которые будут нашими, и предполагают, что мы будем играть, а также можно на этом шаге. И т.п.
Вот почему этот алгоритм по своей сути рекурсивен. Независимо от того, на этапе вы оцениваете все возможные шаги на N-1. Промыть и повторить.
Для Tic-Tac-Toe сегодняшних машин достаточно сильно, чтобы вычислить все возможные результаты сразу после начала игры, потому что их всего несколько сотен. Когда вы смотрите, чтобы реализовать его для более сложной игры, вам придется остановить вычисления в какой-то момент, потому что это займет слишком долго. Так что для сложной игры вам также придется писать код, который решает, следует ли продолжать искать все возможные следующие движения или попытаться дать значение в позиции сейчас и вернуть рано. Это означает, что вам также придется вычислить ценность для позиции, который не является окончательным - например, для шахмат, которые вы бы принять во внимание, сколько материалов каждый противник на доске, непосредственные возможности проверки без партнера, сколько плиток вы контролируете и Все, что делает его не тривиальным.
