Как машина научилась играть

Игра с конечным числом позиций, без случайности и без скрытой информации разрешима в принципе. Эрнст Цермело показал это в 1913 году на примере шахмат: либо у одной из сторон есть выигрывающая стратегия, либо обе способны добиться ничьей, и третьего не дано. Доказательство не говорит, как играть, — оно говорит, что ответ уже лежит в дереве. Дальше техника: раскрыть дерево до листьев, где партия кончилась, и подняться обратно с точным результатом. В крестиках-ноликах доска заполняется 9! = 362 880 способами — меньше, чем процессор перебирает за миллисекунду. Оценки здесь нет вовсе: выигрыш, проигрыш и ничья посчитаны, а не угаданы.

Дерево растёт не в длину, а в степень: при b продолжениях на позицию и партии в d полуходов узлов порядка b^d, и каждая добавленная пара ходов работу умножает. Шеннон в 1950 году оценил число шахматных партий примерно в 10¹²⁰. Оно не уменьшается ни от нового процессора, ни от тысячи сразу: расстояние между шашками (10²⁰ позиций) и шахматами (10⁴⁴) — см. Решённые игры — железом не закрывается. Полный перебор не медленный. Он невозможный.

По дереву нельзя пройти, не решив, что происходит в чужих узлах. Минимакс отвечает раз и навсегда: в своих узлах берём максимум, в чужих — минимум, то есть считаем, что соперник выберет худшее для нас из доступного ему. Теорему для игр с нулевой суммой доказал Джон фон Нейман в 1928 году; к 1950-му Шеннон расписал, как это программируется для шахмат, а Алан Тьюринг в начале пятидесятых проигрывал свой Turochamp на бумаге, считая позиции вручную за неимением машины. Безошибочный соперник — не пессимизм, а единственный способ получить гарантию: оценка минимакса есть то, что вы получите при худшем поведении соперника, и хуже не будет.

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

Альфа-бета — не ускорение перебора, а отказ от перебора на большей части дерева. Если в ветке уже нашёлся ответ соперника, делающий её хуже, чем найденное в другом месте, ветку можно бросить целиком: что бы в ней ни лежало дальше, выбор она не изменит. Существенно, что ответ получается тот же, что при полном переборе, — это не приближение, а доказательство ненужности. Приём независимо переоткрывали несколько раз в конце пятидесятых: он есть уже в шахматной программе Ньюэлла, Шоу и Саймона 1958 года, название закрепилось за Джоном Маккарти, полный разбор дали Дональд Кнут и Рональд Мур в 1975-м. Результат количественный: при идеальном порядке ходов альфа-бета смотрит порядка b^d/2 узлов вместо b^d. Корень. За то же время — вдвое большая глубина.

Всё держится на порядке ходов. Хороший первый кандидат обрубает соседние ветки сразу; плохой не обрубает ничего, и в худшем случае альфа-бета честно просматривает всё дерево, не выиграв ни узла. Отсюда сортировка перед перебором — в наших шашках сначала взятия, потом проходы в дамки, потом остальное, — которая на ответ не влияет вовсе, а на объём работы влияет решающе. И есть предел, о котором приятно забыть: корень из невозможного — по-прежнему невозможное. 10¹²⁰ превращается в 10⁶⁰, и это не меняет ничего.

До листьев дойти нельзя, поэтому счёт обрывают на заданной глубине, объявляют получившуюся позицию концом партии и приписывают ей число. Первую такую формулу опубликовал Шеннон в 1950 году: ферзь — девять, ладья — пять, слон и конь — по три, пешка — одна, плюс десятая доля за каждый лишний доступный ход, минус половина за каждую сдвоенную, изолированную или отсталую пешку. Всё, что программа «понимает» в игре, живёт в этой строке. Как эти цифры выглядят у нас: в реверси углы дороже всего, соседние с углами клетки идут со штрафом (через них углы и отдают), края ценнее центра, а подвижность в середине партии весит больше разницы фишек. В шашках у Артура Самуэля это материал плюс продвижение: сколько шашек и насколько близко к дамкам.

Числа берутся не из игры. Их назначает человек — по опыту, по аналогии, иногда просто чтобы сходился масштаб, — и любая позиция, где смысл расходится с цифрой, разыгрывается неверно и с полной уверенностью. Самая известная форма этой ошибки — горизонт: беду на полуход дальше границы перебора программа не видит, зато оттягивает её серией бессмысленных разменов, потому что за горизонтом беды нет. Термин ввёл Ханс Берлинер в 1974-м. Лечат это доигрыванием боёв до тишины — так делают наши шашки, — и лечат частично: горизонт отодвигается, а не исчезает. Deep Blue в 1997 году нёс около восьми тысяч признаков и всё равно понимал позицию как взвешенную сумму. Отсюда все «нечеловеческие» ошибки — не сбой, а место, где восемь тысяч чисел не сложились в смысл.

Два разных отказа считать вперёд. Первый — считать назад. Берут все позиции, где на доске не больше N фигур, размечают те, где партия кончена, и распространяют результат в обратную сторону, пока размечено не будет всё. Получается таблица, из которой ответ читают, а не выводят. Кен Томпсон построил такие таблицы для четырёх- и пятифигурных шахматных окончаний в 1980-х; к 2012 году досчитали все семифигурные, и там обнаружились выигрыши длиной в сотни ходов. Chinook к 2007 году держал базу всех позиций с десятью и менее шашками — тридцать девять триллионов, — и английские шашки объявили ничьей: восемнадцать лет счёта, где перебор шёл сверху, база снизу, и они встретились. Второй отказ радикальнее. В го оценивать позицию числом никто не умел: материала нет, любая формула врёт. Монте-Карло убирает оценку вообще — доиграть отсюда наугад много раз и посчитать победы. Идею предложил Бернд Брюгманн в 1993-м, в дерево её встроили Реми Кулом и, независимо, Левенте Кочиш с Чабой Сепешвари в 2006-м. Позиция перестаёт оцениваться и начинает измеряться.

База знает только свой хвост. Десять шашек — да, двадцать четыре — нет, и таблица для полной игры не поместится ни на каком носителе: та же степень, только упирается уже не во время, а в место. У Монте-Карло беда другая: случайное доигрывание меряет не позицию, а среднее по глупостям, и там, где выигрыш держится на единственной точной последовательности, среднее не видит ничего. Слепые пятна к тому же устойчивы. В 2023 году исследователи нашли у сильнейших программ го стратегию, которую те не понимают, — обход большой группы по краю, — и любитель Келлин Пелрин выиграл по ней четырнадцать партий из пятнадцати, без компьютера во время игры.

Если веса оценки — самое слабое место, их можно не назначать вручную. Первым это сделал Артур Самуэль: его шашечная программа на IBM 701 подправляла собственные коэффициенты по сыгранным партиям и в 1956 году обыграла автора. Настоящий результат пришёл в 1992-м, за двадцать четыре года до AlphaGo. TD-Gammon Джеральда Тезауро — сеть, которой сообщили только правила нард; она сыграла триста тысяч партий сама с собой, обучаясь методом временных разностей Ричарда Саттона, и вышла на уровень сильнейших людей. Важнее уровня другое: часть её дебютных предпочтений расходилась с человеческой теорией и была признана лучше — люди пересмотрели розыгрыш нескольких начальных бросков. Дальше известное: AlphaGo Zero в 2017 году обучилась го без единой человеческой партии и обыграла предшественницу 100:0, а AlphaZero тем же способом взяла шахматы и сёги.

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