Игры против ИИ: минимакс и перебор ходов¶

Коротко

Чтобы обыграть человека в шахматах, компьютеру не нужна интуиция — ему достаточно просчитать ходы вперёд и выбрать самый выгодный. В этом уроке разберём дерево игры, алгоритм минимакс (когда вы тянете результат вверх, а соперник — вниз) и оценочную функцию, которая измеряет «силу» позиции. Поймём, почему настольные игры так удобны для машины, а реальная жизнь — нет, и проследим путь от грубого перебора Deep Blue к самообучению AlphaGo.

Игра как дерево вариантов¶

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

Корень дерева — текущая позиция на доске. Листья (самые дальние узлы) — это завершённые партии: выигрыш, проигрыш или ничья. Задача ИИ проста на словах: пройти по этому дереву и выбрать тот ход, который ведёт к наилучшему для него исходу — при условии, что соперник тоже играет как можно лучше.

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

Минимакс: я тяну вверх, соперник тянет вниз¶

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

Договоримся измерять исход числом с вашей точки зрения: +1 — вы выиграли, −1 — проиграли, 0 — ничья. Тогда логика такая:

На вашем ходу вы выбираете вариант с максимальным числом — тянете результат вверх.
На ходу соперника он выбирает вариант с минимальным числом — тянет результат вниз.

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

Важно

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

Оценочная функция: как измерить недосчитанную позицию¶

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

Но тогда возникает вопрос: как оценить позицию, которая ещё не закончилась? Для этого нужна оценочная функция — формула, которая по виду доски выдаёт число: насколько позиция выгодна. Чем больше число, тем лучше для вас. В шахматах она учитывает понятные вещи: материал (ферзь ценнее пешки), безопасность короля, контроль центра, активность фигур. Это как опытный тренер, который бросает взгляд на доску и говорит «у белых лучше», не доигрывая партию.

Получается рабочая схема: минимакс перебирает варианты на ограниченную глубину, а на границе перебора оценочная функция подставляет приблизительную «стоимость» позиции вместо точного результата. Чем глубже считает движок и чем точнее его оценочная функция, тем сильнее он играет. Здесь же кроется и слабое место: если оценка позиции грубая, далёкая угроза может остаться незамеченной за горизонтом расчёта.

Пример: Каспаров против Deep Blue

Самый известный матч человека и машины — поединки Гарри Каспарова (он родился в СССР, в Баку) с суперкомпьютером IBM Deep Blue. В 1997 году машина выиграла матч у действующего чемпиона мира. Deep Blue не «понимал» шахматы и не учился на партиях — он брал грубой силой: просматривал колоссальное число позиций в секунду, считал глубоко по дереву и оценивал их функцией, которую вручную настраивали инженеры и приглашённые гроссмейстеры. По сути, это был минимакс с очень мощным перебором и тщательно выверенной оценкой позиции.

Почему игры удобны для ИИ, а жизнь — нет¶

Настольные игры — почти идеальная среда для алгоритмов, и вот почему:

Чёткие правила. Известно, какие ходы разрешены и что считается победой. Никакой двусмысленности.
Полная информация. Вся доска перед глазами, ничего не спрятано (в отличие, скажем, от покера).
Ход по очереди. Игроки ходят строго поочерёдно, нет одновременных действий.
Понятная цель. Есть однозначный критерий успеха — выиграть.

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

От перебора к обучению: Deep Blue и AlphaGo¶

Шахматный подход — перебор по дереву плюс оценочная функция от человека — упирается в стену там, где вариантов слишком много. Классический пример — го: на доске 19 на 19 после первых же ходов число позиций несравнимо больше, чем в шахматах, и его не возьмёшь грубым перебором. К тому же хорошую позицию в го невероятно трудно описать формулой — её скорее «чувствуют».

Прорыв случился в 2016 году, когда программа AlphaGo от DeepMind обыграла одного из сильнейших профессионалов мира. Ключевое отличие от Deep Blue: AlphaGo не полагалась на оценочную функцию, написанную людьми. Она училась сама — сначала на партиях мастеров, затем играя миллионы партий против собственных версий и запоминая, какие позиции чаще ведут к победе. Иначе говоря, оценку позиции она выработала сама, через нейросети и опыт, а не получила готовой от инженеров.

Это важный сдвиг в самой философии: Deep Blue воплощал идею «просчитать всё, что успеем», а AlphaGo — идею «научиться чувствовать, что хорошо». Современные сильнейшие движки совмещают оба подхода — быстрый перебор и обученную оценку позиции. О том, как именно машины учатся на опыте без подсказок, мы поговорим в главе про виды машинного обучения, а механику этого мы начнём разбирать уже в следующем уроке про неопределённость.

Упражнение: примените минимакс к крошечному дереву

Сейчас ваш ход (вы — крестики). У вас есть два варианта: ход A и ход B. После каждого вашего хода соперник (нолики) выбирает свой ответ. Партия маленькая, поэтому варианты сразу доходят до результата. Числа даны с вашей точки зрения: +1 — вы выиграли, 0 — ничья, −1 — вы проиграли.

Ход A → у соперника два ответа, ведущие к результатам 0 и −1.
Ход B → у соперника два ответа, ведущие к результатам +1 и 0.

Какой ход выбрать?

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

После хода A соперник выбирает между 0 и −1. Он возьмёт −1 (худшее для вас). Значит, ход A на самом деле «стоит» −1.
После хода B соперник выбирает между +1 и 0. Он возьмёт 0. Значит, ход B «стоит» 0.

Теперь наш выбор — мы тянем результат вверх, берём максимум из оценок ходов: max(−1, 0) = 0.

Ответ: выбираем ход B. Он гарантирует как минимум ничью, тогда как ход A при правильной игре соперника ведёт к проигрышу. Обратите внимание: заманчивый «+1» в ветке B нам не достаётся — соперник не пойдёт туда, где вы выигрываете. Именно так и работает минимакс: оценивайте ход по тому, что соперник выберет худшее для вас, а не по лучшему мечтаемому исходу.

Проверьте себя¶

Короткий тест по уроку: выберите ответ и нажмите «Проверить» — увидите счёт и разбор.

Частые вопросы¶

Чем минимакс отличается от обычного поиска пути?

В поиске пути (например, маршрута в Навигаторе) среда не сопротивляется — дорога не «ходит» против вас. В играх же есть соперник с противоположной целью, поэтому минимакс на каждом этаже дерева чередует максимизацию (ваш ход) и минимизацию (ход соперника). Про поиск как таковой — в уроке Поиск и планирование.

Почему нельзя просто просчитать шахматы до конца?

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

Зачем нужна оценочная функция, если есть минимакс?

Минимакс умеет тянуть числа от концов дерева к корню, но в больших играх до концов не добраться. Оценочная функция подставляет приблизительную «стоимость» позиции там, где расчёт остановился. Без неё минимакс на ограниченной глубине просто не знал бы, какая из недоигранных позиций лучше.

AlphaGo — это тоже минимакс?

Отчасти. AlphaGo использует перебор вариантов, но её ключевое отличие от Deep Blue в том, что оценку позиции она выработала сама через обучение на множестве партий, а не получила готовой формулой от инженеров. Это шаг от чистого перебора к обучению, и о нём подробнее — в главе про машинное обучение.

В курсе: ← Назад: Поиск и планирование: как ИИ находит решение · Дальше: Неопределённость и шансы: как ИИ принимает решения →

Авторы курса: Герман Коваленко (основатель ENGRAM) и Сергей Добров.

Попробуйте ENGRAM на своих данных

Нейросеть на ваших встречах, документах и переписке: отвечает со ссылкой на источник. Это ваша вторая память на базе ИИ. Данные хранятся в России, старт бесплатный.

Зарегистрироваться бесплатно