1. Исторический прорыв: Слабое решение шашек
В июле 2007 года в журнале Science была опубликована статья исследовательской группы Альбертского университета под руководством профессора Джонатана Шеффера (Jonathan Schaeffer) «Checkers Is Solved». Это стало кульминацией 18-летней исследовательской программы, доказавшей, что при безошибочной игре обеих сторон партия в английские шашки (чеккерс 8×8) гарантированно завершается ничьей.
Масштаб задачи потребовал колоссальных вычислительных мощностей для того времени:
- Полное пространство допустимых состояний: приблизительно 5 × 10²⁰ позиций.
- Объем сжатых релевантных поддеревьев поиска: около 10¹⁴ позиций.
- Полные базы эндшпиля для всех конфигураций с числом фигур до 10 включительно (39 триллионов позиций).
2. Компактное представление: 32-битные битборды
Поскольку в шашках игра ведется исключительно по 32 темным полям доски, все состояние игры можно компактно упаковать в 32-битные целые числа без потерь:
uint32_t white_men— простые белые шашки;uint32_t white_kings— белые дамки;uint32_t black_men— простые черные шашки;uint32_t black_kings— черные дамки.
Оптимизация обязательного взятия
Правило обязательного взятия (mandatory capture) в шашках является ключевым фактором, радикально снижающим фактор ветвления дерева поиска. Проверка наличия доступных взятий реализуется с помощью быстрых побитовых сдвигов (<< 4, << 5, >> 4, >> 5) и логического умножения с маской полей противника.
Если маска взятий не равна нулю, движок мгновенно отсекает все ветви простых тихих ходов, сокращая средний коэффициент ветвления с 6–7 до 1.2–1.5 в тактически напряженных позициях.
3. Ретроспективный анализ и базы эндшпилей (Endgame Databases)
Основой доказательства Шеффера стали базы данных окончаний, вычисленные методом ретроспективного анализа (retrograde analysis):
- Терминальные состояния: Определяются все позиции, в которых одна из сторон не имеет ходов или фигур (прямое поражение/победа).
- Обратная итерация: Значения позиций итеративно распространяются назад. Если из позиции существует ход в позицию победы, текущая позиция помечается выигрышной с шагом конверсии
d = d_next + 1. - Стационарные ничьи: Все позиции, из которых любой возможный ход ведет лишь к ничьей или поражению соперника, квалифицируются как теоретически ничейные.
Сжатие баз данных до объемов оперативной памяти было достигнуто за счет исключения пространственных симметрий (горизонтальное отражение доски) и канонической лексикографической нумерации комбинаций шашек.
4. Алгоритм Proof-Number Search
Чтобы соединить начальную расстановку с таблицами окончаний, классического Minimax с фиксированной глубиной было недостаточно из-за огромной длины отдельных форсированных вариантов. Шеффер применил Proof-Number Search (PNS):
- Каждому узлу сопоставляются два числа: proof number (минимальное число листьев, требующих доказательства для победы узла) и disproof number (для опровержения).
- Алгоритм всегда раскрывает самый «уязвимый» узел, требующий минимального числа проверок для изменения истинностного значения корня.
5. Шашечные движки и браузерные технологии сегодня
Благодаря алгоритмам Chinook и современным возможностям веб-интерфейсов, классические шашки получили второе дыхание. Модели со сжатыми таблицами окончаний и высокоточными эвристиками легко компилируются под веб и исполняются прямо на клиентском устройстве игрока.
Для всех, кто хочет изучить основы тактики шашек, попрактиковаться против точного компьютерного соперника или сыграть с реальными соперниками со всего мира, веб-платформа Boardgammon Checkers — интерактивный движок шашек 8x8 с серверным анализом в браузере предлагает мгновенный запуск, строгие соревновательные правила и адаптивную сложность искусственного интеллекта без необходимости установки дополнительных приложений.
6. Итоги
Решение шашек доказало научному сообществу, что комбинация эвристического направленного поиска и масштабного ретроспективного расчета способна справляться с пространствами состояний астрономических масштабов. Опыт разработки Chinook сегодня используется в автоматическом доказательстве теорем и синтезе верифицированных алгоритмов.