Минимаксный алгоритм

Question

У меня есть простой вопрос относительно минимаксного алгоритма:например, для игры в крестики-нолики, как мне определить функцию полезности для каждого игрока?Это не делается автоматически, не так ли?Я должен жестко запрограммировать значения в игре, она не может выучить их сама, не так ли?

Answer 1

Нет, минимакс не учится.Это более интеллектуальная версия поиска методом перебора по дереву.

Answer 2

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

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

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

Answer 3

Крестики-нолики достаточно малы, чтобы довести игру до конца и присвоить 1 за победу, 0 за ничью и -1 за поражение.

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

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

Answer 4

Как определить функцию полезности для каждой игры?

Внимательно ;-) Это Статья показывает, как слегка некорректная функция оценки (одна для напр.который либо недостаточно "углубляется" в просмотр дерева возможных вариантов, либо не учитывает относительную прочность некоторых позиций на доске) приводит к общей слабости алгоритма (тот, который проигрывает чаще).

он не может выучить их сам по себе, не так ли?

Нет, это не так.Однако есть способы заставить компьютер узнать относительную силу позиций доски.Например, заглянув в Дональд Митчи и его программа " УГРОЗА " вы увидите, как стохастический процесс может быть использован для изучения доски без каких-либо априори знание, но правил игры.Забавно то, что, хотя это можно реализовать на компьютерах, все, что требуется, - это несколько сотен цветных шариков и спичечных коробков, благодаря относительно небольшому размеру игрового пространства, а также различным симметриям.

После изучения такого классного способа научить компьютер играть, нам, возможно, не так уж интересно возвращаться к MinMax применительно к крестикам-ноликам.В конце концов MinMax - это относительно простой способ обрезки дерева решений, что вряд ли необходимо при небольшом игровом пространстве tic-tac-toe.Но, если мы должны ;-) [вернитесь к MinMax]...

Мы можем заглянуть в "спичечный коробок", связанный со следующей игрой (т.е.совсем не углубляясь), и используйте процентное содержание бусин, связанных с каждым квадратом, в качестве дополнительного фактора.Затем мы можем оценить традиционное дерево, но только на глубину, скажем, 2 или 3 хода (небольшая перспективная глубина, которая обычно заканчивается проигрышем или ничьей) и оценивать каждый следующий ход на основе простого рейтинга -1 (проигрыш), 0 (ничья / неизвестно), + 1 (победа).Затем, комбинируя процентное соотношение бусин и простой рейтинг (скажем, путем сложения, конечно, не путем умножения), мы можем эффективно использовать MinMax способом, который больше похож на то, как он используется в случаях, когда невозможно оценить игровое дерево до конца.

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