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

Примечание. Эти жемчужины мудрости, которые вы можете здесь прояснить, являются продуктом реализации функции минимакса в JavaScript.

Рекурсия

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

Поведение минимаксных функций отражает поведение абстрактного типа данных, известного как древовидная структура. Минимаксная функция должна иметь следующие три вещи:

· Терминальное условие - условие, которое выполняется для выхода из рекурсии. В нашем случае, когда либо достигается выигрышное игровое состояние, либо больше не нужно делать ходов.

· Рекурсивный шаг - более крупная и сложная проблема разбивается на серию более простых, самовыполняющихся шагов, которые вместе составляют решение. В нашем случае это когда минимакс вызывается, когда конкретное состояние игры не соответствует требованиям терминального условия.

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

Визуализировать это - непростая задача. Вот где мне показалось полезным мышление в терминах узлов. Узлы - это участки, на которых пересекаются пути, что в нашем случае является более абстрактным способом сказать, что конкретное игровое состояние имеет ряд доступных ему ходов. Нас интересуют три типа узлов:

· Корневой узел - у него нет родительского узла, но он может вести к дочерним узлам. Это первый вызов функции максимина.

· Внутренний узел - узел с потомками. В нашем случае это состояние игры, в котором есть доступные ходы.

· Конечный узел - узел без детей. В нашем случае это когда состояние игры не имеет доступных ходов; либо из-за того, что были сделаны все ходы, либо из-за того, что было получено состояние выигрыша в игре.

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

Функция maximin в основном выполняет две функции:

· Создает все пути между родительскими узлами и дочерними узлами

· Постройте путь от корневого узла к конечному узлу, который приведет к не победе оппозиции.

Поэтому, если вы столкнулись с ошибкой, т.е. если функция maximin не возвращает значение или возвращает неправильное значение, она попадет в одну из трех категорий ошибок:

· Определенный путь между родительским и дочерним узлами должен быть, но его нет, т.е. перемещение, которое должно быть доступно, недоступно. Возвращаемое значение, хотя и является субоптимальным, является условно правильным в той мере, в какой ему доступны доступные пути. Изучите функции, связанные с конечным условием и рекурсивным шагом.

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

· Ожидаемый доступный ход для данного состояния игры отсутствует, и, учитывая неполный диапазон доступных ходов, возвращаемое значение также не такое, как ожидалось. Поскольку построение оптимального пути зависит от наличия полного диапазона ходов, отдавайте приоритет функциям фиксации, связанным с конечным условием и рекурсивным шагом.

Отладка

Если вы знаете, что должно происходить в любой момент времени, это должно иметь большую цель для ваших усилий по отладке. Эту деятельность можно дополнительно поддержать, выполнив следующие действия:

· Я разложил свою минимаксную функцию на составные части и протестировал каждую часть. Это требует времени, но меньше времени, чем поиск источников неопределенного значения в сложной мега-функции.

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

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

· Если вы воспользуетесь приведенным выше советом, помните о разнице между мелкой копией и глубокой копией объекта. Если вы сделаете неглубокую копию корневого узла в процессе генерации дочерних узлов, свойство дочернего узла, массив, содержащий состояние игры, на самом деле является ссылкой на игровое состояние корневого узла. Любые изменения, внесенные в этот массив на уровне дочернего узла, т. Е. Совершение нового хода, фактически отражаются на уровне корневого узла. Это вызывает хаос. Не забудьте глубокое клонирование.

· Представляйте свободные ходы с нулевыми значениями. Это упрощает тестирование различных сценариев с помощью «фиктивных ходов», то есть при тестировании различных сценариев выигрыша в игре несоответствующие ходы могут быть представлены персонажем, не являющимся X / O. Таким образом, он сужает диапазон доступных ходов, не мешая функции проверки состояния выигрыша в игре.

· Свободное использование операторов console.log - это хорошо. Операторы Console.log в сочетании с инструментами разработчика Chrome лучше. Используйте оператор отладчик.

Минимаксный возврат неоптимального хода

Итак, ваша минимаксная функция вроде работает. Если вы хотите, чтобы он работал должным образом, чтобы он делал оптимальный ход в любых обстоятельствах:

· В зависимости от того, как вы рассчитываете «оптимальный путь», иногда возвращенный ход приводит к неоптимальной победе, то есть к выбору комбинации ходов, которая приводит к победе за несколько ходов, а не сразу. Другой пример ... компьютер никогда не должен находиться в проигрышном положении. Однако, если ваше приложение может включать компьютерный режим «Игрок стихи» на полпути в игре, и компьютер берет на себя роль игрока, которая в конечном итоге приведет к поражению, иногда компьютер бросается на свой собственный меч вместо того, чтобы играть на руку. Горький конец. Этого можно избежать, если учесть «временную скидку» в баллах, начисленных за состояние-победитель. Я использовал номер поворота, чтобы уменьшить количество начисленных очков. Это будет благоприятствовать действиям, которые приведут к более раннему выигрышному сценарию.

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

· Неопределенные значения проникают в функции map () и reduce (), которые отвечают за идентификацию и создание новых игровых состояний.

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

Источники неопределенных значений

· Рекурсивным функциям требуется хотя бы одно конечное условие для выхода из рекурсии. Минимакс имеет два, когда достигнуто состояние выигрыша игры И когда больше нет ходов. Обязательно включите оба.

· Если вы приняли к сведению предыдущий совет для функции минимакс, чтобы возвращать объекты, а не примитивные значения, убедитесь, что когда вы ссылаетесь на свойства объекта, вы пишете их правильно!

Резюме

Привлечение «теории деревьев» не всем придется по вкусу, я нашел это полезным способом сосредоточиться на состоянии игры и на том, что должно происходить, и не затрагивать детали реализации рекурсивной функции. Это послужило моим компасом, когда я начал копаться в деталях реализации и пошагово выполнять вызовы функций с помощью инструментов разработчика Chrome.

Я нашел реализацию функции минимакса сложной задачей, но чувствую, что был щедро вознагражден за свои усилия. Есть и другие способы реализовать режим «игрок стихает пригородный» в игре «Крестики-нолики», однако я настоятельно рекомендую всем, кто любит сложные задачи, попробовать.

Если вы нашли эту статью полезной, подумайте о том, чтобы дать ей аплодисменты.