Я все еще новичок в более продвинутой оптимизации ИИ, но я поделюсь тем, что узнал. Две из ссылок псевдокода (1 и 3) являются Negamax, что хитрее, чем минимакс, потому что он менее интуитивно понятен. Две разные реализации Negamax в 1 и 3 требуют разных функций оценки, и это является основной причиной их различий (подробнее ниже). Вторая ссылка, которую вы разместили, относится к MTD (f), которую я раньше не реализовывал, но я считаю, что она все еще отличается от Minimax и Negamax. Я считаю, что MTD (f) считается более быстрым . Наконец, единственный ресурс, который я когда-либо видел для Minimax с таблицами транспонирования, находится здесь , и я действительно не уверен, что это даже правильно. Negamax в значительной степени стандарт, и если вы можете использовать Minimax, вы, вероятно, можете использовать Negamax вместо этого.
Хотя Negamax и Minimax выглядят по-разному, по сути, они делают одно и то же. Это сообщение в блоге дает довольно хорошее описание того, как они связаны, но не объясняет различия. Я постараюсь объяснить, почему они отличаются ниже.
Почему минимакс и негамакс выглядят по-разному, но, по сути, одинаково, становится немного более очевидным, если подумать о нескольких вещах, связанных с минимаксом:
- Минимакс работает только для игр на двух игроков, один из которых является максимизатором, а другой - минимизатором. Tic Tac Toe - простой пример.
- Типичная функция оценки для Minimax вернет +100, если Х выиграл в состоянии терминала, вернет -100, если О выиграл в состоянии терминала, и вернет 0 для ничьи.
- Обратите внимание, что оценки являются обратными друг другу. Каждое очко, полученное игроком 1, является потерянным для игрока 2. Это игра с нулевой суммой.
И несколько замечаний о Negamax:
- Negamax также работает только для двух игроков с нулевой суммой. Каждое очко для игрока 1 - это потерянное очко для игрока 2.
- Negamax использует немного другую функцию оценки, чем Minimax. Требуется, чтобы оценка всегда проводилась с точки зрения текущего игрока. То есть, если в состоянии терминала Х выиграл и настала очередь Х, оценка должна быть +100. Если он находится в терминальном состоянии, где Х выиграл, но настала очередь О, оценка будет равна -100. Это отличается от того, что ожидает Minimax (Minimax всегда хочет, и победа X будет стоить +100). Псевдокод 1 ожидает этот тип функции оценки.
- Некоторые псевдокоды Negamax, такие как статья в Википедии в 3, пытаются использовать ту же функцию оценки, что и Minimax, отрицая значение функции оценки, используя цвет в этой строке «возвращаемый цвет × эвристическое значение узла». Это также работает, но я никогда не делал это таким образом (ссылки на то, как я делаю это ниже). Обратите внимание, что значение цвета будет только -1 для мин игроков. Я считаю, что этот способ все больше сбивает с толку.
- Теперь, когда функция оценки описана ... обратите внимание на эту строку «значение: = max (значение, −negamax (дочерний элемент, глубина - 1, −β, −α, −color))» в псевдо- код 3 . Обратите внимание, что возвращаемое значение (некоторое оценочное значение), которое всегда с точки зрения текущего игрока, инвертировано. Это потому, что ходы чередуются, а eval происходит из дочернего состояния, из-за хода другого игрока. Значения альфа и бета также инвертированы.
С Minimax мы получаем положительные и отрицательные оценки. С Negamax мы всегда создаем положительные оценки и затем инвертируем их по мере необходимости, следовательно, Nega. Это возможно, потому что игра с нулевой суммой, очко для игрока 1 - это потеря очка для игрока 2.
Зачем использовать Negamax? Потому что это проще. Это сложнее реализовать в первый раз, но делает вещи более краткими. Я также считаю, что записи таблицы транспонирования должны обрабатываться по-разному (более сложно) для Minimax, чем для Negamax. Самое главное, все остальные его используют. Я бы хотел лучше объяснить, почему.
Вотлучший ресурс, который я нашел для реализации таблиц транспонирования с Negamax (большинство псевдокодов не так уж и полезны):
- Итеративное углубление NegaScout с альфа-бета-отсечкой и таблицами транспонирования
- Я также реализовал ванильный Negamax с таблицами транспонирования, но больше не могу найти ресурсы, которые использовал.Чтобы преобразовать вышеупомянутое в ванильный Negamax, вы просто заменяете строки 504 (начиная с // поиска нулевого окна) до 521 на "goodness = -minimax (state, глубина - 1, -beta, -alpha);"Дополнительные строки в этом блоке кода являются частью «разведчика», которая начинается с узкого поискового окна alphaBeta и расширяет его по мере необходимости.Обычно NegaScout лучше, чем NegaMax.Я мог бы поделиться своим полным источником, но мне нужно время, чтобы подготовить что-то подходящее для публикации в SO.
Если по какой-то причине вы не можете внедрить Negamax, это единственныйресурс, который я нашел для реализации таблиц транспонирования с минимаксом .
Наконец, я хочу выбросить пару вещей:
- При использовании таблиц транспозиции вы, вероятно, захотите использовать Итеративное углубление , поскольку оно обеспечивает естественную отсечку, когда время является вашим ограничением
- При использовании таблиц транспозиции вы захотите рассмотреть изоморфные доски.То есть вы захотите рассмотреть ту же доску в отражающих позициях.Пример: Оценка этой доски в крестики-нолики XOX | --- | X-- аналогична оценке X-- | --- | XOX (вертикальное отражение).Не уверен, будет ли это применяться к Пакману, но это огромное улучшение, если оно доступно.В Tic Tac Toe это приводит к тому, что 70-90% состояний поиска сбрасываются с таблиц транспозиции.Ответьте в комментарии, если хотите обсудить.
- Если вы реализуете свою игру на JavaScript, обратите внимание, что стандартные ключи Zobrist не будут работать, потому что бинарные операторы JS работают с 32 битами вместо 64. Естьнесколько разных способов сделать это, но я предлагаю начать с использования строк в качестве ключа в объекте {}.
- Если вы ищете многопользовательский ИИ, вы должны посмотреть на Hypermax / Макс-Н.Минимакс и Негамакс терпят неудачу за пределами 2 игроков.