Решены ли шашки математически? Как 18 лет вычислений доказали ничью и что это меняет для игроков

На протяжении многих столетий мастера, исследователи и завсегдатаи клубов задавались фундаментальным вопросом: предопределён ли исход шашечной партии с самого первого хода? Если два соперника садятся за доску из шестидесяти четырёх полей и не допускают ни малейшей неточности, получает ли первый игрок гарантированное преимущество? Обречён ли второй номер на неизбежную защиту? Или же при идеальной игре обеих сторон на доске царит абсолютное математическое равновесие?

Летом 2007 года авторитетный научный журнал Science опубликовал исследование, положившее конец многолетним спорам^[1]. Группа исследователей Альбертского университета под руководством профессора Джонатана Шеффера официально объявила: классические английские шашки (известные в англоязычных странах как чекерс или draughts) математически решены. После масштабного вычислительного проекта, продолжавшегося 18 лет и стартовавшего в 1989 году, программа Chinook доказала: безупречная игра с обеих сторон неумолимо приводит к ничьей.

Эта историческая победа компьютерных наук вовсе не обесценила древнюю игру. Чтобы осознать, почему классические шашки продолжают восхищать игроков в клубах и в сети, необходимо разобраться, что именно вкладывает теория игр в понятие точного решения.

Три уровня решения игр в теории вычислений

В повседневной речи мы называем задачу решённой, как только находим остроумный ответ. В дискретной математике и искусственном интеллекте этот термин имеет строгое научное определение, сформулированное нидерландским учёным Виктором Аллисом в 1994 году^[2]. Аллис выделил 3 формальных уровня решения игр с полной информацией:

1. Ультра-слабое решение. Математическое доказательство строго устанавливает теоретический исход начальной позиции (победа белых, победа чёрных или ничья), однако не предоставляет конкретного алгоритма ходов или практического дерева решений. Ярким примером служит игра гекс: теория игр доказала, что первый игрок имеет форсированный выигрыш благодаря принципу кражи стратегии, однако перечислить сами выигрышные ходы на больших досках невозможно.
2. Слабое решение. Конкретный алгоритм или проверенное дерево доказательства задаёт полноценную стратегию, гарантирующую как минимум ничью или победу из стартовой расстановки против любых возможных ходов оппонента. Программа может не знать исхода экзотических положений, возникающих после череды грубых ошибок, но с начальной позиции её невозможно победить. Именно к этой категории принадлежат шашки^[1].
3. Сильное решение. Алгоритм в реальном времени определяет точную теоретическую оценку и оптимальный ход для абсолютно любой допустимой позиции на доске, независимо от предшествующих ошибок. Игра Connect Four была сильно решена в 1988 году: первый игрок при верных ходах форсированно побеждает из любого достижимого положения^[2].

Шашки были решены именно на слабом уровне, поскольку хранение оценки для каждой иррациональной конфигурации потребовало бы нереалистичных объёмов памяти. Команда Шеффера сосредоточила усилия на расчёте пути от официальной начальной расстановки. На старте 12 тёмных шашек противостоят 12 светлым на 32 тёмных полях, что даёт в сумме 24 шашки на доске^[3].

Восемнадцать лет расчётов: как Chinook исследовал шашки

Математическое пространство шашек колоссально и многократно превосходит представления любителей. На доске 8×8 насчитывается около 5 × 10^20 возможных легальных позиций^[1]. Это число соответствует примерно полутриллиону миллиардов положений. Если бы обычный компьютер проверял эти варианты последовательно, вычисления затянулись бы на многие тысячелетия.

Чтобы одолеть эту астрономическую величину, учёные разделили задачу на два встречных направления: обратный расчёт из окончаний и прямой поиск из начальной позиции.

Ретроградный анализ и 39 триллионов позиций в памяти

Краеугольным камнем доказательства стали эндшпильные базы данных. Вместо того чтобы наугад двигаться вперёд от первого хода, исследователи начали с самого финала, когда на доске остаётся лишь несколько шашек. Позиция с одной тёмной дамкой против одной светлой тривиальна — это немедленная ничья. Две дамки против одной одинокой шашки в углу дают форсированный выигрыш.

Используя метод ретроградного анализа, Chinook шаг за шагом просчитывал ценность всех допустимых конфигураций. Если ход ведёт в уже доказанную выигрышную позицию, исходное положение также признаётся победным. Если все ответы ведут к поражению, позиция помечается как проигранная. Если точная игра удерживает равновесие, фиксируется ничья.

К 2007 году программа полностью рассчитала все возможные расстановки с числом шашек 10 и менее^[1]. Эта база данных включает 39 триллионов уникальных позиций. Как только в партии остаётся 10 шашек, Chinook больше не вычисляет варианты — он мгновенно считывает абсолютную истину прямо из базы.

Мост из дебюта в эндшпильные таблицы

Завершив расчёт окончаний для 10 шашек, учёные приступили к наведению неразрывного моста от исходных 24 шашек к этой базе^[1].

Для этого исследователи применили алгоритмы поиска по доказательственным числам (proof-number search) в сочетании с классической процедурой альфа-бета отсечения. Программа систематически исследовала критические варианты, выискивая форсированные размены и упрощения, ведущие в известные таблицы, и безжалостно отсекая тупиковые или заведомо невыгодные ветви.

Параллельные расчёты велись годами на сотнях серверов. Были отсеяны миллиарды ненужных разветвлений и выстроено проверенное дерево доказательства из десятков миллионов ключевых узлов. Каждый магистральный путь из дебюта либо вёл в неприступную ничейную крепость, либо напрямую стыковался с ничейной позицией из базы 39 триллионов состояний. В 2007 году работа увенчалась успехом: шашки математически гарантируют ничью^[1].

Мэрион Тинсли: человек против машинного разума

Задолго до того как кремниевые процессоры просчитали игру до конца, один человек приблизился к абсолютной гармонии благодаря выдающейся интуиции. Доктор Мэрион Тинсли, профессор математики из Флориды, признан величайшим шашистом в истории человечества.

Турнирные показатели Тинсли граничат с фантастикой. За свою 45-летнюю карьеру в турнирах высшего уровня Тинсли проиграл всего 9 партий из многих тысяч сыгранных встреч^[1]. Он носил титул чемпиона мира на протяжении десятилетий, уступая корону лишь тогда, когда добровольно брал паузу в соревнованиях. Чтобы проверить Chinook в противостоянии с абсолютной вершиной человеческого мастерства, Джонатан Шеффер организовал в 1992 году официальный матч за мировую корону.

Матч 1992 года вошёл в летопись как эпохальная битва интуиции и точного счёта. На дистанции в 39 напряжённых партий Тинсли продемонстрировал непревзойдённую позиционную зоркость и одержал победу над Chinook со счётом 4 победы при 2 поражениях и 33 ничьих^[1]. Это был первый случай в истории, когда программа играла официальный матч за титул против действующего чемпиона мира среди людей в классической настольной дисциплине.

В 1994 году состоялся матч-реванш. Сыграв 6 ничьих подряд, Тинсли был вынужден прервать поединок из-за тяжёлого онкологического заболевания и ушёл из жизни в 1995 году^[1]. Титул чемпиона мира среди машин и людей перешёл к Chinook. Позднейший анализ партий Тинсли показал поразительный факт: его ходы в сложнейших позициях практически безупречно совпадали с вердиктами идеальных баз окончаний.

Лестница комбинаторной сложности: от Connect Four до шахмат

Чтобы верно оценить масштаб шашечного прорыва, полезно сопоставить шашки с другими интеллектуальными играми.

Ещё в 1950 году основоположник теории информации Клод Шеннон исследовал математическую структуру шахмат^[4]. По оценке Шеннона, шахматы насчитывают порядка 10^44 допустимых позиций, а число возможных партий составляет не менее 10^120 — эта величина сегодня известна как число Шеннона^[4].

Сопоставим эти масштабы между собой:

• Connect Four: Сильно решена в 1988 году^[2]. Игра насчитывает триллионы состояний и полностью просчитывается на обычном ноутбуке за считанные секунды.
• Английские шашки 8×8: Слабо решены в 2007 году при пространстве около 5 × 10^20 позиций^[1]. Потребовалось 18 лет распределённых вычислений и база на 39 триллионов эндшпилей.
• Шахматы: Полностью не решены. При 10^44 позициях и 10^120 ветвях^[4] шахматы неизмеримо превосходят современные мощности полного перебора. Сегодня шахматные таблицы окончаний рассчитаны лишь до 7 фигур включительно. Создание таблиц для 8 фигур потребует петабайтов памяти, а решение полной игры с 32 фигурами недостижимо для классических компьютеров.
• Международные шашки 10×10: Не решены. Доска из 100 клеток и по 20 шашек у соперников создают пространство ориентировочно в 10^30 позиций. Летающие дамки и правило обязательного большинства порождают дерево вариантов колоссального размаха.

Почему математическое решение сохраняет интерес к игре

Когда в 2007 году весть о решении облетела мировые издания, скептики поспешили заявить, будто шашки исчерпали себя. Зачем садиться за доску, если науке известно, что финалом станет ничья?

Такие рассуждения в корне неверны по отношению к реальной борьбе. Математическое решение описывает взаимодействие двух непогрешимых разумов на протяжении пятидесяти идеальных ходов. Однако люди — не компьютеры. Ни один гроссмейстер не способен удержать в памяти 39 триллионов окончаний или мгновенно просчитать миллионы разветвлений.

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

В реальной турнирной практике судьбу встречи определяют три фактора:

1. Точность дебютной подготовки. Хотя магистральные пути ведут к уравнению, по сторонам скрыто множество коварных ловушек. Неверный шаг на первых ходах нередко приводит к поражению за пару темпов.
2. Позиционное маневрирование. Борьба за ключевой центр, укрепление дамочных полей и связывание флангов требуют глубокого понимания. Игроки, освоившие основы стратегии шашек, стабильно переигрывают тех, кто полагается лишь на сиюминутный расчёт.
3. Филигранная техника окончаний. При равном количестве шашек решающую роль играет позиционная оппозиция. Малейший просчёт лишает заслуженной победы или позволяет сопернику ускользнуть в неприступную крепость, как показано в нашем руководстве по эндшпилю в шашках.

В спортивных состязаниях давно применяется жеребьёвка начальных ходов, уводящая соперников от заученных схем в неисследованные дебри. Шашки не умерли; математический анализ лишь подтвердил гармонию и стройность их внутренней механики.

Психологическая глубина практической игры

Практическая привлекательность шашек кроется в том, что абстрактное равенство позиций совершенно не гарантирует спокойной ничьей на практике. В условиях ограниченного времени каждый ход требует исключительной концентрации. Шашист должен непрерывно оценивать динамику диагоналей, следить за разменами и предвидеть скрытые маневры соперника.

Турнирный опыт показывает: побеждает тот, кто лучше понимает тонкие позиционные слабости и умеет создавать неочевидные проблемы. Математическое решение задало абсолютный ориентир совершенства, однако само искусство борьбы за доской расцветает именно там, где сталкиваются человеческие характеры, творческие замыслы и спортивная воля. Даже глубокая теоретическая оценка позиции не спасает игрока от цейтнота, когда стрелка часов неумолимо приближается к падению флажка. В такие моменты хладнокровие, интуитивное чувство гармонии позиции и способность быстро находить скрытые ловушки оказываются куда важнее механического перебора вариантов.

Красота шашечной партии раскрывается в постоянном диалоге замыслов. Когда соперники разыгрывают сложные построения в центре доски, теоретическая ничья отступает на второй план, уступая место чистому расчёту и поиску парадоксальных решений. Именно поэтому за доской продолжают собираться новые поколения мастеров, находя в старинной игре свежие идеи и неисчерпаемое вдохновение.

Изучаете ли вы классические правила шашек, знакомитесь ли с богатым семейством вариантов шашек или хотите играть в шашки онлайн с любителями со всего мира — шашечная доска остаётся неисчерпаемым полем для творчества. Компьютеры нанесли на карту конечный пункт, но сама дорога всегда принадлежит живым игрокам.

Часто задаваемые вопросы

Решены ли шашки для абсолютно любых нелепых ходов?

Нет, шашки решены слабо, а не сильно. Доказательство гарантирует безупречную ничейную стратегию из стандартной начальной позиции с 24 шашками на 32 тёмных клетках^[1]. Кроме того, все позиции с 10 шашками и менее исчерпывающе просчитаны базой на 39 триллионов состояний. Однако хаотичные позиции с дюжиной шашек после обоюдных грубых ошибок не каталогизированы полностью.

Может ли живой игрок одолеть Chinook сегодня?

Против полной версии Chinook с подключённой дебютной книгой и 10-фигурной базой выиграть невозможно. Поскольку ничья доказана математически, идеальная программа не уступит ни при каких обстоятельствах. При безукоризненных ходах человека встреча завершится вничью; при малейшей позиционной оплошности машина беспощадно перехватит инициативу и форсирует выигрыш.

Имеют ли чёрные преимущество начального хода в английских шашках?

В английских шашках право первого хода принадлежит тёмным. Начальная инициатива позволяет бороться за центральные поля, однако исследование Шеффера доказало, что этого преимущества недостаточно для победы при грамотной защите^[1]. При идеальной игре инициатива первого хода постепенно нивелируется, и партия неизменно заканчивается ничьей.

Источники

1. Schaeffer, J., Burch, N., Björnsson, Y., Kishimoto, A., Müller, M., Lake, R., Lu, P., & Sutphen, S. (2007). Checkers Is Solved. Science, 317(5844), 1518–1522.
2. Allis, L. V. (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. thesis, University of Limburg, Maastricht.
3. Boardgammon. “Checkers Rules: How to Play, Movement, and Captures.”
4. Shannon, C. E. (1950). Programming a Computer for Playing Chess. Philosophical Magazine, Ser. 7, 41(314), 256–275.
5. Boardgammon. “Checkers Crown: Play Online Checkers and Regional Draughts Variants.”
6. Boardgammon. “Play Checkers Online: Free Browser and Mobile Draughts.”
7. Boardgammon. “Checkers Variants: The Kinds of Draughts Played Around the World.”

Нашли ошибку или неловкую фразу? Напишите нам