Алгоритм для решения сложных задач в теории – минимакс

Минимакс – метод, способствующий определению оптимального выбора в невыгодной ситуации.

Сегодня вас ждет алгоритм решения сложных задач в теории игр – от теории к практике.

В ходе исследования теории игр в нашей прошлой статье было выяснено:

• Теория игр – ключевой фундамент, без которого дальнейшие шаги усложняются.
• Теория игры – арсенал инструментов для принятия рациональных, обдуманных и точных решений, а также для понимания данных.
• В игре, которую мы анализируем, обязательно участвуют по меньшей мере два участника. У каждого из них есть собственные интересы и варианты действий.
• Решение принимается из информации о действиях других участников.
• Есть общепринятые правила, доступные всем.

Большинство обыденных ситуаций можно рассматривать с точки зрения теории игр. Даже обычные разговоры о зарплате или месте для отпуска подвергаются влиянию теории игр.

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

Минимакс: стратегия

В теории игр задача каждого игрока состоит в поиске стратегии, максимизирующей его выгоду.

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

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

Правило минимакса

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

1. В некоторых играх поражение выражается числом, например денежной потерей после игры. В других случаях поражение просто указывает, кто победил и кто проиграл.
2. Каждый другой игрок делает решения, которые могут увеличить вашу максимальную потерю. Например, из-за его действия вы можете потерять 10 или 500 очков. Максимальная возможная потеря в этом случае – 500 очков.
3. Цель состоит в том, чтобы на каждом шагу принимать решения, уменьшающие эту потерю. Иными словами, даже если потеря происходит, то не 500, а 10 – минимальная из возможных вариантов.

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

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

Алгоритм в действии

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

1. Первый игрок размещает крестик в любой клетке поля. Всего 9 клеток, одна занята, осталось 8.
2. Мы последовательно рассматриваем все возможные клетки, где можно разместить нолик, и оцениваем ситуацию – побеждаем ли мы или проигрываем. Если неясно, переходим на новую ситуацию и выполняем такой же алгоритм.
3. Этот процесс продолжается, пока все клетки не заполнятся – получим множество возможных вариантов и разветвлений.
4. Для успешных вариантов мы добавляем определенное количество баллов за каждый наш ход в конкретную клетку, а для проигрышных – вычитаем такое же количество.
5. После таких расчетов мы получаем оценку для каждой из 8 свободных клеток.
6. Наконец, выбираем клетку с высокими баллами для следующего хода и размещаем нолик там.

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

Для желающих создать собственную игру – приглашаем на курсы программирования от IT школы GoMother. В зависимости от возраста ребенка и желаемого конечного результата мы подберем оптимальный язык программирования.

Минимакс: как работает этот принцип в реальной жизни

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

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

Если продавец имеет данные о продаже, релевантных показателях и цифрах, он может рассчитать несколько вариантов развития событий с определенной глубиной, например, на 2-4 хода вперед с учетом конкурентов. Затем он анализирует наиболее распространенные решения и выбирает те, которые приносят наибольший результат. Это оптимальный шаг в борьбе за клиентов.

Эта стратегия называется максиминным алгоритмом. Суть состоит в том, чтобы максимизировать минимально возможный выигрыш.

Применение в области информационных технологий

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

В следующем разделе мы проверим работу правила минимакса на практике – создадим игру «крестики-нолики» и научим компьютер выбирать оптимальные ходы. Следите за обновлениями на нашем сайте и подписывайтесь на наш Instagram!