AI·XI Горизонты Глава 62 из 65
Турнир ботов
Последняя часть книги начинается с игры. Вы напишете бота для крестиков-ноликов, который никогда не проигрывает, потом для «Четырёх в ряд» — и выпустите их на турнир. По дороге — дерево игры и минимакс, альфа-бета отсечение, которое выбрасывает заведомо ненужные ветки, оценочные функции для игр, где до конца не досчитать, поиск Монте-Карло, приведший к победе над чемпионом в го, и решённые до конца шашки.
Горизонты
- 62 Игры вы здесь
- 63 Обучение
- 64 Кванты
- 65 Белые пятна
Опирается на: 17 · Сад деревьев поиска 09 · Задача внутри задачи 26 · Подбросим монетку
Что вы унесёте из главы
- строить дерево игры и выбирать ход минимаксом, считая, что соперник играет лучшим образом
- ускорять перебор альфа-бета отсечением и знать, что при удачном порядке ходов оно сокращает число узлов примерно до квадратного корня
- оценивать позицию, когда до конца игры не досчитать, и знать, когда помогает поиск Монте-Карло
Всю книгу мы писали для машины точные рецепты, а она их исполняла — быстро и не задумываясь. Даже в прошлой главе каждое правило защиты записали мы сами: здесь проверь границу, здесь экранируй, сюда не пускай. Сама машина не решила ничего. Может ли она выбирать без нашего пошагового рецепта? Проверим на игре: научим машину играть. Заранее записанная комбинация тут не поможет: по другую сторону доски сидит противник, который тоже думает, и думает против вас.
Этим игра и отличается от задач из прошлых глав: ответ зависит не только от вас. Массив при сортировке не сопротивляется, а в игре на каждый ваш ход приходит ответный, рассчитанный вам во вред. Хорош тот ход, который остаётся хорошим и после самого злого ответа соперника. Глава устроена как турнир. Сначала вы напишете бота для крестиков-ноликов, который никогда не проигрывает, потом — для «Четырёх в ряд», где до конца уже не досчитать, и выпустите обоих в турнирную таблицу.
Арена: крестики-нолики
Бот — это функция: ей дают позицию на доске и чей ход, она возвращает ход. Всё остальное — как эта функция решает. Начнём с самой маленькой арены, крестиков-ноликов на поле три на три. Доску запишем списком из девяти клеток ('X', 'O' или '.'), клетки пронумерованы от 0 до 8 слева направо и сверху вниз. Вот судья: он сводит двух ботов и доигрывает партию до конца.
Два бота, которые ходят наугад, разыгрывают ничью примерно в каждой восьмой партии, а в остальных побеждает чаще первый — у него лишний ход. Случайный бот — слабак: он не замечает ни своей победы в один ход, ни чужой угрозы. Чтобы играть всерьёз, нужно смотреть вперёд, то есть перебирать: что будет, если я так, а он эдак, а я тогда так. Получается дерево.
Стокгольм, 1974: первый чемпион мира
За машинами от «Каиссы» до Deep Blue стоит одна идея, и крестиков-ноликов хватает, чтобы понять её до конца: представить игру деревом и выбрать в нём ход, считая, что соперник отвечает наилучшим образом.
Дерево игры
Возьмём позицию и нарисуем все её продолжения. Корень — текущая доска. От него ветки — все возможные ходы; из каждой получившейся позиции — снова все ответы соперника, и так до конца партии, где кто-то выиграл или вышла ничья. Это дерево игры. Листья — законченные партии, про каждую сразу ясно, чем она кончилась. Уровни чередуются: на одном ходит один игрок, на следующем — другой. Один такой уровень, ход одного игрока, называют полуходом.
Насколько велико это дерево? На пустой доске первый игрок выбирает одну из 9 клеток, второй — одну из 8, и так далее. Сверху число партий ограничено $9!$, но многие ветки обрываются раньше: партия кончается, едва кто-то собрал линию. Точное число листьев даст полный обход.
Листьев получается 255 168 — меньше, чем $9! = 362\,880$, потому что партии, где линия собралась раньше девятого хода, дальше не ветвятся. Четверть миллиона листьев компьютер обходит за долю секунды, так что крестики-нолики можно досчитать до самого конца и для любой позиции узнать, чем она кончится при правильной игре. Осталось понять, как выбрать по дереву ход, если соперник нам не союзник.
Минимакс: считать на худшее
Припишем листьям числа с нашей точки зрения: наш выигрыш — $+1$, проигрыш — $-1$, ничья — $0$. Мы хотим наибольшее число, соперник — наименьшее (наш проигрыш — его выигрыш). Значит, спускаясь по дереву, на своих уровнях мы выберем ветку с наибольшим значением, а на уровнях соперника обязаны считать, что он выберет наименьшее. Получается правило: значение узла, где ходим мы, — максимум значений детей; где ходит соперник — минимум. Это минимакс. Он отвечает на вопрос «какой исход гарантирован, если соперник играет идеально».
Свёртка «максимум — минимум» старше компьютеров. В 1928 году математик Джон фон Нейман доказал теорему о минимаксе для игр двух лиц с нулевой суммой, а в 1950-м Клод Шеннон в статье «Программирование компьютера для игры в шахматы» перенёс идею на машину. Тогда же Алан Тьюринг с Дэвидом Чамперноуном придумали шахматную программу, которую Тьюринг в 1952 году разыгрывал вручную, на бумаге: запустить её было не на чем. С этих работ и началось компьютерное изучение игр. Запишем минимакс для крестиков-ноликов. Удобно считать в одной системе: значение всегда с точки зрения того, кто сейчас ходит, а значение ребёнка берём со знаком минус (что хорошо ему, плохо нам). Такую запись называют негамаксом.
Начальная позиция стоит ноль: при точной игре крестики-нолики всегда кончаются ничьей. Поэтому бот на best_move никогда не проигрывает: он выбирает ход, после которого даже лучшая игра соперника не приносит тому победы. Угрозы он тоже видит. Заметив два нолика в ряд, крестик закрывает третью клетку: любой другой ход ведёт к проигрышу, а проигрыш для value хуже ничьей. В задаче minimax-ttt вы напишете такого бота, и проверка попробует обыграть его во всех возможных партиях — безуспешно. В виджете ниже попробуйте поймать соперника на «вилку», две угрозы сразу: «близорукий» на ней попадается, а «идеальный» построить её не даст.
Альфа-бета: не смотреть лишнее
Минимакс обходит всё дерево. Но часто целые ветки можно не смотреть, потому что они уже не повлияют на ответ. Представьте, что вы выбираете из двух ходов. Первый вы просчитали: он гарантирует ничью, ноль. Начинаете считать второй и в первом же ответе соперника видите, что тот может вас обыграть — минус один. Соперник выберет именно этот ответ (он играет на минимум), значит, второй ход не лучше минус единицы и уже проигрывает найденной ничьей. Остальные ответы соперника на второй ход можно не смотреть: что бы там ни было, этот ход мы и так отвергли. Ветка отсечена.
Так работает альфа-бета отсечение. В переборе мы несём с собой два числа: α — сколько уже гарантировано тому, кто играет на максимум, и β — сколько гарантировано сопернику. Как только в каком-то узле становится ясно, что он выходит за эти границы, перебор его детей обрывают. Ответ получается в точности тот же, что у минимакса, — отбрасываются только заведомо ненужные ветки. Посчитаем на дереве крестиков-ноликов, сколько узлов обходит чистый минимакс и сколько — с отсечением.
Отсечение сокращает перебор в десятки раз — здесь примерно в тридцать, — и ответ при этом не меняется ни в одной позиции. Чем глубже дерево, тем больше выигрыш. Если ходы перебирать в удачном порядке — сначала самые сильные, — альфа-бета в лучшем случае обходит около $\sqrt{b^d}$ узлов вместо $b^d$, где $b$ — число ходов в позиции, $d$ — глубина. Извлечь корень — значит вдвое уменьшить показатель степени, поэтому за то же время можно заглянуть вдвое глубже и видеть на восемь ходов вместо четырёх. Идею независимо находили многие: она носилась в воздухе с середины 1950-х (похожее предлагал Маккарти ещё в 1956 году), в 1963-м её опубликовал советский математик Александр Брудно, а строгий анализ дали Дональд Кнут и Рональд Мур в 1975 году. В задаче alphabeta вы напишете отсечение сами, и проверка потребует уложиться в порог по числу просмотренных листьев.
Альфа-бета ничего не упрощает в самой игре: тот же минимакс и тот же точный ответ, только без времени, потраченного на ветки, которые уже не могут изменить решение. Это общий приём — «ветви и границы»: держать текущий лучший результат и обрывать всё, что заведомо его не побьёт. Мы уже встречали этот приём у судьи коммивояжёров в главе 58: там отбрасывали ветви, где нижняя граница уже хуже найденного тура.
Когда до конца не досчитать
Крестики-нолики кончаются за девять ходов, их дерево — четверть миллиона листьев. С шахматами так не выйдет. Ещё Шеннон в 1950-м прикинул, что разных партий в шахматах порядка $10^{120}$. Это число теперь зовут числом Шеннона, и оно больше числа атомов во Вселенной: такое дерево не обойти ни с каким отсечением. «Четыре в ряд» на поле 7×6 скромнее, но и там свыше $4{,}5 \cdot 10^{12}$ позиций — за время одного хода до конца не досчитать.
Выход предложил тот же Шеннон: остановиться на отмеренной глубине, не доходя до листьев, и оценить незаконченную позицию числом. Такое число даёт оценочная функция. В шахматах она считает материал и расположение фигур; в «Четырёх в ряд» — чьих троек и двоек, готовых стать четвёркой, больше. Поиск идёт минимаксом с отсечением на несколько полуходов вперёд, а вместо недостижимых листьев берёт оценку. Чем глубже заглядываешь, тем сильнее игра, — и тут снова выручает альфа-бета, удваивая доступную глубину.
Соберём бота для «Четырёх в ряд». Доску запишем списком из семи столбцов, в каждом фишки снизу вверх. Оценка нехитрая: перебираем все четвёрки клеток, где линию ещё можно собрать. Своя тройка с местом под четвёртую фишку даёт много очков, двойка — поменьше, такие же у соперника идут со знаком минус. Отдельно награждать центр не нужно: через центральные клетки проходит больше линий, и очков они набирают больше сами собой. А ходы бот перебирает от центра к краям — так отсечение срабатывает раньше.
Бот, заглядывающий на четыре полухода вперёд, обыгрывает случайного всухую. До конца игры он не считает: останавливается на четвёртом полуходе и доверяет оценке, кто ближе к четвёрке. В задаче connect4-bot вы напишете такого бота, и он сразится на турнире против эталонных ботов — простака, который всегда ходит в левый столбец, и тактика, который берёт победу и закрывает угрозы. Уложиться нужно в отведённое время: глубже — сильнее, но и дольше.
Когда ветвей слишком много: Монте-Карло
Оценочная функция работает, когда понятно, что в позиции ценно. В шахматах это известно веками: материал, центр, безопасность короля. А для го, игры на доске 19×19, работающую оценку долго не могли придумать: позиция, которая выглядит проигрышной, через двадцать ходов оказывается выигранной, и ни одна простая формула этого не ловит. Вдобавок из каждой позиции сотни ходов, и дерево ветвится так, что тонет даже альфа-бета.
Выход нашёлся в случайности из главы 26. Чтобы оценить позицию, можно обойтись без формулы: доиграть из неё до конца много партий случайными ходами и посмотреть, как часто мы выигрываем. Доля побед и станет оценкой. А чтобы не тратить случайные партии поровну на все ходы, их раздают с умом: больше — тем ветвям, что пока выглядят лучше, но и остальным понемногу, на случай, если мы в них ошиблись. Этот способ называют поиском по дереву Монте-Карло. Его собрали в 2006 году: Реми Кулом описал, как вести поиск по дереву случайными партиями, и дал приёму имя, а Левенте Кочиш и Чаба Сепешвари — формулу, как делить пробы между «использовать лучшее» и «разведать остальное».
Именно на этом выросла AlphaGo, обыгравшая Ли Седоля в 2016-м: поиск Монте-Карло, в котором выбор ветвей подсказывала нейросеть, обученная на партиях людей, а позицию, кроме случайных доигрываний, оценивала вторая сеть (о том, как учатся сети, — следующая глава). Обещанный 37-й ход второй партии — редкий «плечевой удар», какой, по словам комментаторов, большинство профессионалов не стали бы и рассматривать. Программа сыграла его вопреки собственной сети, выученной на партиях людей: та как раз и подсказывала, что человек так почти никогда не ходит. Решили поиск и оценка позиции, выросшая из миллионов партий программы с самой собой, а не человеческая формула.
Решённые игры
Если дерево игры удаётся обойти до конца, пусть даже за годы счёта, можно узнать, чем кончается игра, когда обе стороны не ошибаются. Такие игры называют решёнными. Крестики-нолики — ничья, это мы уже видели. «Четыре в ряд» в 1988 году независимо решили Джеймс Аллен и Виктор Аллис: при идеальной игре первый побеждает, если первым ходом занимает центральный столбец. А шашки держались дольше всех: в 2007 году группа Джонатана Шеффера из Альбертского университета после восемнадцати лет счёта доказала, что при безошибочной игре обеих сторон шашки кончаются вничью. Статья в журнале Science так и называлась: «Шашки решены». Позиций в шашках около $5 \cdot 10^{20}$, и без хитростей, сводивших дерево к обозримому, их не обошли бы и за всю историю человечества.
Играть в решённую игру по-прежнему интересно: человек ошибается, и партия остаётся живой. «Решена» значит лишь, что идеальная линия известна вся. В играх, слишком больших, чтобы пройти их до конца, перебор с оценкой и отсечением к такой линии только приближается.
Турнир: задачи
Три бота — от непобедимого на маленькой доске до бойца для большой. Проверка не читает ваш код: она запускает его и судит по делу — по сыгранным партиям, по числу просмотренных листьев, по времени.
Напишите best_move(board, player) — ход бота в крестики-нолики, который не проигрывает никогда. Доска — список из девяти клеток со значениями 'X', 'O' или '.', клетки пронумерованы от 0 до 8 по строкам. player — 'X' или 'O', чей ход. Верните номер свободной клетки. Проверка сыграет вашим ботом все возможные партии — и первым, и вторым — и убедится, что соперник не может его обыграть ни в одной; отдельно проверит, что бот берёт победу в один ход, когда она есть, и закрывает угрозу соперника.
Оцените каждый свободный ход минимаксом: после своего хода спросите, что получит соперник при идеальной игре, и возьмите ход, где сопернику достаётся меньше всего. Значение закончившейся партии: кто собрал линию — тому +1, сопернику -1, нет ходов — 0.
Удобнее считать «с точки зрения того, кто ходит»: функция value(board, turn) возвращает лучшее для turn, а значение хода — это -value(доска после хода, соперник). Если на доске уже есть победитель, ходящему это проигрыш: return -1. Это та же рекурсия, что в главе 9, только ветвится по ходам.
Дерево крестиков-ноликов — четверть миллиона листьев, поэтому полный минимакс для каждого хода считается мгновенно, и бот играет идеально: при точной игре обеих сторон выходит ничья, а стоит сопернику ошибиться — бот наказывает. Проверка «все партии сразу» перебирает за соперника каждый ответ, а за бота берёт ваш best_move, и нигде не находит проигрыша. В больших играх так в лоб не досчитать — там нужны оценка и отсечение из соседних задач.
Игру задали деревом: лист — целое число (оценка позиции для нас), внутренний узел — список поддеревьев. Корень — наш ход (максимум), уровни чередуются (соперник — минимум). Напишите solve(tree), которая вернёт пару (значение, сколько листьев просмотрено): значение по минимаксу и число листьев, в которые пришлось заглянуть, если применять альфа-бета отсечение. Лист считается просмотренным в тот момент, когда берут его значение. Отсекайте ветку, как только она уже не может улучшить результат (значение дошло до β на максимуме или до α на минимуме). Проверка сверит значение с минимаксом и потребует, чтобы просмотренных листьев было не больше, чем при правильном отсечении, — а это заметно меньше, чем всего листьев в дереве.
Пронесите через рекурсию два числа — alpha и beta. На максимуме после каждого ребёнка обновляйте alpha = max(alpha, best); как только best >= beta, выходите из цикла — остальные дети уже не нужны. На минимуме симметрично: beta = min(beta, best) и выход при best <= alpha.
Листья складывайте по ходу: seen += s на каждом ребёнке. Когда ветку обрываете break-ом, непросмотренные дети в seen не попадают — в этом вся экономия. Начальные границы в корне — alpha = -∞, beta = +∞.
Значение совпадает с минимаксом всегда: отсекаются только ветки, которые заведомо не влияют на ответ. А число просмотренных листьев падает — тем сильнее, чем удачнее порядок ходов. В пределе, при идеальном порядке, альфа-бета обходит около корня из числа листьев минимакса — отсюда и правило «вдвое глубже за то же время».
Напишите choose(board, me) — ход в игре «Четыре в ряд» на поле 7×6. Доска — список из семи столбцов; каждый столбец — список уже брошенных в него фишек снизу вверх ('X' или 'O'), пустой столбец — []. me — ваш цвет. Верните номер столбца от 0 до 6, который ещё не полон. Цель — собрать четыре свои фишки в ряд (по вертикали, горизонтали или диагонали) раньше соперника. Проверка устроит турнир: ваш бот должен обыграть простака, который всегда ходит в левый столбец (и первым, и вторым), и не проиграть тактику, который берёт победу в один ход и закрывает ваши угрозы. На всё — ограниченное время, так что перебор без отсечения и без ограничения глубины не пройдёт.
Нужны три кирпича: drop(board, c, p) — копия доски с брошенной фишкой; winner(board) — кто собрал четыре в ряд (проверьте все четвёрки по четырём направлениям); evaluate(board, me) — оценка незаконченной позиции (посчитайте окна из четырёх клеток: своя тройка с местом — много очков, двойка — меньше, у соперника — со знаком минус).
Дальше — минимакс с альфа-бета отсечением на фиксированную глубину (хватит 4–5 полуходов). В листьях рекурсии: если кто-то выиграл — большое ± число (чем быстрее победа, тем лучше); если глубина кончилась — evaluate. Перебирайте столбцы от центра к краям — так отсечение работает лучше, а центр и сам сильнее.
Чтобы точно брать победу и закрывать угрозы, глубины достаточно: на глубине 1 бот сам находит выигрышный ход, на глубине 2 — видит и закрывает угрозу соперника. Если упираетесь во время — уменьшите глубину или перебирайте только незаполненные столбцы, от центра к краям.
Весь бот — минимакс с оценкой и альфа-бета отсечением из этой главы, перенесённый с крестиков-ноликов на поле побольше. Нового в нём две вещи: оценочная функция вместо досчёта до конца и фиксированная глубина. Перебор от центра к краям и отсечение дают заглянуть на пять полуходов в отведённое время; этого хватает, чтобы не упускать побед и угроз. Хотите сильнее — углубляйтесь, но следите за временем: каждый лишний полуход умножает работу в несколько раз (без отсечения — в семь, по числу столбцов).
Куда дальше
Машина у нас теперь играет: идеально там, где дерево удаётся обойти, и очень сильно там, где нет. Deep Blue обыграл чемпиона мира тем же набором — быстрый перебор, альфа-бета отсечение и оценочная функция. Но присмотритесь, где в этой машине ум. Перебор и отсечение — чистая механика, в ней всё можно доказать. А что считать хорошей позицией, то есть оценку, для Deep Blue писали люди: программисты вместе с гроссмейстером-консультантом годами настраивали, сколько стоит проходная пешка и открытая вертикаль.
Для шахмат такую оценку кое-как собрали вручную, для го не смогли: никто не умел записать формулой, какая позиция на большой доске лучше. А если человек оценку написать не может? Способна ли машина вывести её сама, из примеров и сыгранных партий, как в итоге и сделала AlphaGo? С этого вопроса начинается следующая глава, а с ним и всё, что сегодня называют машинным обучением.