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

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

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

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

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

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

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

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

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

Сама их не выучит?

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

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

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

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