Задавайте вопросы

Задавайте вопросы и получайте ответы от нашего сообщества

Отвечайте

Отвечайте на вопросы и станьте экспертом по своей теме

Свяжитесь с администрацией

Наши специалисты готовы ответить на ваши вопросы

Инфо Знакомство с правилом «минимакс»

Информация о теме

О теме Здравствуйте, вы читаете тему Знакомство с правилом «минимакс» созданную в в разделе Алгоритмы пользователем Deimos#. Эта тема была просмотрена 752 раз(а), получила 0 комментариев и 0 очки реакции...
Название категории Алгоритмы
Название темы Знакомство с правилом «минимакс»
Автор темы Deimos#
Дата начала
Ответы
Просмотры
Количество реакций
Последнее сообщение Deimos#

Deimos#

Модератор #2
Регистрация
17.02.2016
Сообщения
116
Реакции
41
Баллы
35
Лучшие ответы
0
  • Автор темы
  • Модератор
  • #1
Как написать бота, которого будет нельзя обыграть в «крестики-нолики»,
или Знакомство с правилом «минимакс»


Как и профессиональный шахматист, этот алгоритм просчитывает действия соперника на несколько ходов вперёд
до тех пор, пока не достигнет конца партии, будь то победа, поражение или ничья. Попав в это конечное состояние,
ИИ начислит себе положительное количество очков (в нашем случае +10) за победу, отрицательное (-10) — за поражение, и нейтральное (0) — за ничью.

В то же время алгоритм проводит аналогичные расчёты для ходов игрока.
Он будет выбирать ход с наиболее высоким баллом, если ходит ИИ, и ход с наименьшим, если ходит игрок.
Используя такую стратегию, минимакс избегает поражения.
Попробуйте сыграть с компьютером который использует минимакс
Пожалуйста, Вход или Регистрация для просмотра содержимого URL-адресов!


Алгоритм «минимакс» проще всего описать в виде рекурсивной функции, которая:
  1. Возвращает значение, если найдено конечное состояние (+10, 0, -10),
  2. Проходит по всем пустым клеткам на поле,
  3. Вызывает минимакс-функцию для каждой из них (рекурсия),
  4. Оценивает полученные значения
  5. И возвращает наилучшее из них.

Реализация минимакса
Мы рассмотрим ситуацию, когда игра подходит к концу (смотрите картинку ниже).
Поскольку минимакс проходит по всем возможным состояниям игры (а их сотни тысяч),
имеет смысл рассматривать эндшпиль — так нам придётся отслеживать меньшее количество
рекурсивных вызовов функции (всего 9).
Пусть ИИ играет крестиками, человек — ноликами.

Чтобы упростить работу с полем, объявим его как массив из 9 элементов со значениями,
равными содержимому клеток. Заполним его крестиками и ноликами, как на картинке выше, и назовём origBoard
Код:
Пожалуйста, Вход или Регистрация для просмотра содержания кодов!
Затем объявим переменные aiPlayer и huPlayer и присвоим им значения "X" и "O" соответственно.

Кроме того, нам потребуется функция, которая ищет победные комбинации и возвращает
истинное значение в случае успешного поиска, и функция, которая хранит индексы доступных клеток.
Код:
Пожалуйста, Вход или Регистрация для просмотра содержания кодов!
Итак, давайте определим минимакс-функцию с двумя аргументами: newBoard (новое поле) и player (игрок).
Затем найдём индексы свободных клеток на поле и передадим их в переменную availSpots.
Код:
Пожалуйста, Вход или Регистрация для просмотра содержания кодов!
Кроме того, нам нужно отслеживать конечные состояния и возвращать соответствующие значения.
Если побеждает «нолик», нужно вернуть -10, если «крестик» — +10. Если размер массива availSpots
равен нулю, значит, свободных клеток нет, игра закончится ничьёй, и нужно вернуть ноль.
Код:
Пожалуйста, Вход или Регистрация для просмотра содержания кодов!
После этого нужно собрать очки с каждой из пустых клеток.
Для этого создадим массив ходов moves и пройдём в цикле по всем пустым клеткам, помещая индексы и очки каждого хода в объект move.

Затем зададим индекс пустой клетки, который хранился в виде числа в origBoard, равным свойству-индексу объекта move.
Потом сходим за текущего игрока на пустую клетку нового поля newBoard и вызовем функцию minimax от другого игрока
и получившегося поля newBoard. После этого нужно поместить свойство score объекта, возвращённого функцией minimax,
в свойство score объекта move.

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

И наконец, функция сбрасывает изменения newBoard и помещает объект move в массив moves.

Код:
Пожалуйста, Вход или Регистрация для просмотра содержания кодов!
Затем минимаксу нужно выбрать наилучший ход move из массива moves.
Ему нужен move с наибольшим счётом, если ходит ИИ, и с наименьшим, если это ход человека.
Таким образом, если значение player равно aiPlayer, алгоритм инициализирует переменную bestScore
очень маленьким числом и идёт циклом по массиву moves: если ход move приносит больше очков score, чем bestScore,
алгоритм запоминает этот move. В случае ходов с одинаковыми очками алгоритм запоминает первый из них.

В случае, когда player равен huPlayer, всё аналогично — только теперь bestScore инициализируется
большим числом, а минимакс ищет ход move с наименьшим количеством очков.
В итоге минимакс возвращает объект, хранящийся в bestMove.

Код:
Пожалуйста, Вход или Регистрация для просмотра содержания кодов!
Вот и вся минимакс-функция. Исходный код реализации алгоритма вы можете найти на
Пожалуйста, Вход или Регистрация для просмотра содержимого URL-адресов!


Минимакс в действии
ользуясь схемой ниже, разберем пошаговую модель алгоритма.


1.Алгоритму подаются origBoard и aiPlayer. Он составляет список из трёх найденных пустых клеток,
проверяет конечность состояния, и проходит циклом по всем пустым клеткам. Затем алгоритм меняет newBoard,
помещая aiPlayer в первую пустую клетку. После этого он вызывает сам себя от newBoard и huPlayer и ждёт, пока второй вызов вернёт значение.

2.Пока первый вызов функции всё ещё работает, запускается второй, создавая список из двух пустых клеток,
проверяя конечность состояния и проходя циклом по всем пустым клеткам. Затем второй вызов изменяет newBoard,
помещая huPlayer в первую пустую клетку. После этого он вызывает сам себя от newBoard и aiPlayer и ждёт, пока третий вызов вернёт значение.

3.Алгоритм составляет список пустых клеток и фиксирует победу игрока после проверки конечности состояния.
Поэтому он возвращает объект с полем счёта, равным (-10).

4.Алгоритм составляет список пустых клеток и фиксирует победу игрока после проверки конечности состояния.
Поэтому он возвращает объект с полем счёта, равным (-10).
Во втором вызове функции алгоритм получает значения, возвращённые с нижнего уровня третьим и четвёртым вызовами функции.
Поскольку ход huPlayer принёс эти два результата, алгоритм выбирает наименьший из них.
Так как они одинаковы, алгоритм выбирает первый и передаёт его первому вызову функции.
На этот момент первый вызов функции получил оценку хода aiPlayer в первую пустую клетку.
Затем он изменяет newBoard, помещая aiPlayer во вторую пустую клетку. После этого он вызывает сам себя от newBoard и huPlayer.

5.В пятом вызове функции алгоритм составляет список пустых клеток и фиксирует победу ИИ после проверки конечности состояния.
Поэтому он возвращает объект с полем счёта, равным +10. После этого первый вызов изменяет newBoard, помещая aiPlayer в третью пустую клетку.
Затем он вызывает сам себя от newBoard и huPlayer.

6.Шестой вызов составляет список из двух пустых клеток, проверяет конечность состояния и идёт циклом по всем пустым клеткам.
Затем он изменяет newBoard, помещая huPlayer в первую пустую клетку. Потом он вызывает сам себя от newBoard и aiPlayer и ждёт,
пока седьмой вызов вернёт значение.

7.Новый вызов составляет список из одной пустой клетки, проверяет конечность состояния и изменяет newBoard,
помещая aiPlayer в пустую клетку. После этого он вызывает сам себя от newBoard и huPlayer и ждёт, пока этот вызов вернёт значение.

8.Восьмой вызов составляет пустой список пустых клеток и фиксирует победу aiPlayer после проверки конечности состояния.
Поэтому он возвращает объект с полем счёта, равным (+10), на уровень выше, седьмому вызову. Седьмой вызов получил лишь одно,
положительное значение от нижних уровней. Поскольку это значение было получено в ход aiPlayer, алгоритм возвращает наибольшее
из полученных значений. Поэтому он возвращает положительное значение (+10) на уровень выше, шестому вызову.
Поскольку шестой вызов обнаружил две пустых клетки, минимакс изменяет newBoard, помещая huPlayer во вторую пустую клетку.
Затем он вызывает сам себя от newBoard и aiPlayer.

9.После этого алгоритм составляет список пустых клеток и фиксирует победу aiPlayer после проверки конечности состояния.
Поэтому он возвращает объект с полем счёта, равным (+10), на уровень выше. На этом этапе шестой вызов должен выбрать между счётом (+10),
который вернул седьмой вызов, и счётом (-10), который вернул девятый вызов. Поскольку ход huPlayer принёс эти два результата,
алгоритм выбирает наименьший из них и возвращает его на уровень выше в виде объекта с полями счёта и индекса.
Наконец, все три ветви первого вызова оцениваются (-10, +10, -10). Поскольку ход aiPlayer принёс эти три результата,
алгоритм выбирает объект, содержащий наибольшее количество очков (+10) и его индекс (4).

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


источник:
Пожалуйста, Вход или Регистрация для просмотра содержимого URL-адресов!
 
Последнее редактирование:

Больше тем этой же категории

Верх Низ