Привет, Хабр!

Сейчас, когда вы слышите про ИИ в шахматах, наверняка первое, что приходит в голову – это AlphaZero, который "научился" играть в шахматы, превзойдя чемпионов мира, не имея никакого предварительного знания об игре. Но позвольте, это же только верхушка айсберга!

Не будем тратить время на объяснение того, как двигаются фигуры – это вы и так знаете. В сегодняшней статьи мы разберем алогоритм Minimax.

Немного истории

Было время, когда математик Эрнест Зермело разрабатывал теорию игр, а Джон фон Нейман, который позже станет отцом современной компьютерной архитектуры, представил концепцию Minimax.

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

В 50-х годах Клод Шеннон предложил концепцию программирования шахматных алгоритмов. Он описал базовую стратегию для шахматных программ, использующих Minimax, и ввел понятие "функции оценки" для анализа позиций. Это был настоящий прорыв, ведь теперь компьютеры могли "думать" несколько ходов вперед, оценивая каждый из них.

В 60-е годы появились первые шахматные программы, использующие Minimax. Программы вроде IBM's Deep Thought и другие начинали демонстрировать впечатляющие результаты, хотя до уровня гроссмейстера им было еще далеко. Эти программы использовали Minimax для анализа тысяч позиций, но ограниченная вычислительная мощность того времени ставила свои рамки.

В 90-х IBM представила Deep Blue. В 1997 году эта программа победила гроссмейстера Гарри Каспарова. Deep Blue использовала усовершенствованный Minimax с альфа-бета обрезкой и могла анализировать до 200 миллионов позиций в секунду.

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

Minimax

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

Дерево решений

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

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

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

Корневой узел – это текущее состояние игры, откуда начинается анализ.

Листовые узлы – это конечные точки дерева, где игра заканчивается (шахматы – это мат, пат или ничья) или где анализ прекращается на определенной глубине.

Оценка позиций

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

Простейшая форма оценки – это подсчет общего значения фигур на доске. Например, пешка может оцениваться в 1 очко, конь и слон – в 3, ладья – в 5, ферзь – в 9. Таким образом, если один игрок имеет материальное преимущество, его позиция оценивается выше.

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

Простая материальная оценка: Представим, что у белых на доске ферзь, ладья и пять пешек (общая оценка 19 очков), а у черных – только ферзь и шесть пешек (общая оценка 15 очков). Эвристическая функция может оценить эту позицию как +4 в пользу белых.

Позиционная оценка: Допустим, у белых есть пешки на c4 и d4, контролирующие центр, в то время как черные пешки находятся на a7 и b7. Хотя материально ситуация равная, позиционно белые стоят лучше из-за контроля центра и более активных пешек.

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

Min и Max уровни

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

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

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

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

В Minimax алгоритм чередует уровни Min и Max, представляя ходы обоих игроков. Он начинается с Max уровня (ход игрока), затем переходит к Min уровню (ход противника), и так далее. Это чередование продолжается до достижения заданной глубины анализа или до конца игры.

Backtracking и выбор хода

Backtracking – это процесс возвращения от листовых узлов дерева решений к корню, с целью выбора наилучшего хода. После того как алгоритм достигает определенной глубины или конца игры (листового узла), он начинает "отступать" назад, оценивая и сравнивая полученные результаты.

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

Оценки позиций на нижних уровнях дерева "поднимаются" вверх. На каждом уровне Min и Max алгоритм выбирает соответствующий ход: Max выбирает ход с максимальной оценкой, Min – с минимальной.

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

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

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

Предположим, первый ход белых приводит к оценке +3 (после лучшего ответа черных), а второй ход – к оценке +5. Выбирая между этими двумя ходами, алгоритм выберет второй, так как он приводит к более выгодной позиции.

Alpha-Beta Pruning

Alpha-Beta Pruning – это метод оптимизации для алгоритма Minimax, который позволяет уменьшить количество узлов, которые нужно оценивать в дереве игры. Основная идея заключается в том, чтобы "обрезать" ветви дерева, которые не нужно исследовать, потому что они не приведут к лучшему выбору.

В алгоритме используются две переменные: Alpha и Beta. Alpha – это наилучшая уже найденная оценка на пути к корню для игрока Max, а Beta – для игрока Min. Изначально Alpha равна минус бесконечности, а Beta – плюс бесконечности.

Если в какой-то момент оказывается, что Beta меньше или равна Alpha (Beta ≤ Alpha), это означает, что текущий узел не может улучшить уже найденный предыдущий ход, и поэтому дальнейшее исследование этой ветви бессмысленно.

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

Теперь вы рассматриваете второй ход. Предположим, первый ответ черных на этот ход дает оценку +1 для белых. Так как +1 меньше текущего значения Alpha (+2), дальнейшее исследование этой ветви не имеет смысла, так как черные могут выбрать ход, который уже хуже для белых, чем найденный ранее.

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

Alpha-Beta Pruning существенно уменьшает количество узлов, которые нужно оценить, что делает Minimax намного быстрее и эффективнее. В шахматах это сокращает время анализа с нескольких часов до нескольких секунд.

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

Также я большой любитель поиграть в шахматы. Если есть желающие сыграть партейку, отпишите мне в сообщения.

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