Две части: поиск и оценка
Шахматный движок — это две программы, работающие вместе. Поиск смотрит вперёд: «если я сыграю так, соперник ответит так, тогда я сыграю так…». Оценка смотрит на одну позицию, ничего не передвигая, и даёт ей одно число: у кого лучше и насколько.
Они нужны друг другу. Чем глубже поиск, тем меньше значит слабая оценка; чем лучше оценка, тем меньшая глубина нужна. Оценка запускается в конце каждого варианта — сотни тысяч раз в секунду, — поэтому она должна быть и хорошей, и очень быстрой.
Поиск
Движок думает каждый раз на один уровень глубже (итеративное углубление), поэтому у него всегда есть готовый ход, когда заканчивается время. Рассмотреть каждый ход на любую глубину было бы бесконечно долго, поэтому большая часть работы — в том, чтобы не рассматривать ходы, которые ничего не решают:
- Альфа-бета. Как только один ответ опровергает ход, движок перестаёт его рассматривать. При хорошем упорядочивании ходов это отсекает большую часть дерева, не меняя результата.
- Лучшие ходы — первыми. Сначала пробуются ход, который был лучшим, когда эта позиция встречалась в прошлый раз, взятия ценных фигур и тихие ходы, сработавшие в похожих позициях (ходы-убийцы и таблица истории).
- Память. Таблица транспозиций запоминает уже просмотренные позиции, потому что одна и та же позиция часто возникает при разном порядке ходов.
- Обоснованные сокращения. Малоперспективные поздние ходы просматриваются менее глубоко (late move reductions); позицию настолько хорошую, что преимущество сохраняется даже при пропуске хода, отсекают досрочно (null move pruning); шахи просматриваются на ход глубже.
- Только спокойные позиции. Поиск никогда не останавливается посреди размена: в конце каждого варианта он продолжает перебирать взятия, пока позиция не успокоится (quiescence search), так что оценка никогда не видит ферзя, которого вот-вот заберут в ответ.
- Несколько ядер. Движок может искать несколькими потоками одновременно, и все они используют общую таблицу транспозиций (Lazy SMP).
Доска
Внутри движка доска — это набор 64-битных чисел, по биту на поле (битборды): одно число для белых коней, одно для чёрных ладей и так далее. Ходы и атаки сводятся к нескольким битовым операциям, а дальнобойные фигуры берут свои атаки из заранее вычисленных таблиц (магические битборды). Составные фигуры варианта — Махараджа, Архиепископ и Канцлер — ходят как объединение своих составляющих, поэтому используют те же таблицы.
Оценка позиции вручную
Исходная оценка движка — это список эмпирических шахматных правил, у каждого свой вес: материал, где стоит каждая фигура, сколько полей она контролирует, проходные и изолированные пешки, пара слонов, ладьи на открытых линиях, пешечное прикрытие короля. Веса постепенно меняются от дебюта к эндшпилю.
Она работает, и именно она сейчас играет в приложении, но знает лишь то, что кто-то догадался записать. Всё остальное для неё невидимо.
Нейросеть
Нейросеть заменяет только оценку. Поиск остаётся точно таким же — сеть не выбирает ходы, она много раз в секунду отвечает на один вопрос: насколько хороша эта позиция?
- Вход — это сама доска. Есть 18 видов фигур — пешка, конь, слон, ладья, ферзь, король и три составные фигуры, двух цветов, — и 64 поля: 18 × 64 = 1152 вопроса с ответом да или нет, например «стоит ли белый конь на f3?». В обычной позиции примерно на 32 из них ответ «да». Составные фигуры — отдельные входы, а не смесь других фигур, поэтому сеть сама учится, чего стоит Махараджа.
- Обе точки зрения. Доска подаётся дважды: так, как её видит сторона, которая ходит, и зеркально, как её видит соперник. Сети не нужно учить шахматы дважды, отдельно за белых и за чёрных.
- Нейроны никто не программирует. Никто не говорит нейрону, что искать. Во время обучения они сами превращаются в детекторы — чего-то вроде «король без пешечного прикрытия» или «ладья, прорвавшаяся на седьмую горизонталь».
Почему это быстро
Название сети, NNUE, означает Efficiently Updatable Neural Network — эффективно обновляемая нейросеть. Первый слой — это таблица с одним столбцом чисел на каждый вход, а нейроны — просто сумма столбцов тех входов, на которые ответ «да». Ход меняет лишь от двух до четырёх входов, поэтому сумму никогда не пересчитывают заново — её обновляют:
Всё считается в небольших целых числах, помногу сразу, с помощью векторных инструкций процессора. По нашим замерам движок с сетью достигает той же глубины поиска примерно вдвое быстрее, чем с ручной оценкой (0,95 против 2,0 секунды на наших тестовых позициях, одно ядро нашей тестовой машины).
Как она учится
Каждый обучающий пример — это позиция с двумя метками: оценка, которую ей дал поиск на несколько ходов вглубь, и то, чем в итоге закончилась партия. Сеть учится угадывать обе с первого взгляда. В этом весь фокус: когда поиск спрашивает сеть о позиции, ответ уже содержит то, что нашёл бы более глубокий взгляд, — как будто поиск бесплатно заглянул дальше.
Движок учится только на собственных партиях, включая составные фигуры и свои армии, — анализ никакого другого движка в него не попадает. Новую сеть оставляют, только если она побеждает предыдущую в матче из сотен партий. Пока каждый раунд был заметно сильнее предыдущего:
| Сеть | Обучающих позиций | Результат в игре с собой |
|---|---|---|
| Первая | 3 миллиона | +44 Эло к ручной оценке |
| Вторая | 10 миллионов | +168 Эло к первой |
| Третья | 30 миллионов | +157 Эло ко второй |
| Четвёртая | 68 миллионов | +102 Эло к третьей |
Эти цифры получены в партиях из классических дебютов между версиями нашего собственного движка, по 600 партий в матче. Игра с самим собой обычно преувеличивает прирост; измерение против стороннего движка — на странице о силе движка.
Где мы сейчас
- Четвёртая сеть уже встроена в движок. Против Fairy-Stockfish с силой 2500 она набирает 55%, то есть около 2535 по этой шкале; ручная оценка в том же тесте достигает около 2210.
- Сеть знает вариант хуже, чем классические шахматы. Каждую свою армию, на которой она училась, создал наш генератор, а не игрок, поэтому эти начальные позиции немного искусственные. Какие армии расставляли бы настоящие игроки, мы пока не знаем. К тому же вариант просто сложнее: больше видов фигур и новая расстановка почти в каждой партии.
- Партии игроков пока не собираются. По замыслу сервер должен сохранять партии, в которых игрок выбрал 5-й уровень и победил движок своей армией. Пока такой возможности нет. Сети нужны десятки миллионов позиций для обучения — четвёртая училась на 68 миллионах, — а партий с вариантом игроки сыграли ещё далеко не столько, чтобы их дать.