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