Компьютеры просчитали игру в английские шашки

Канадские ученые сумели найти окончательное решение одной из древнейших настольных игр — английских шашек (checkers). На построение математического доказательства того, что при оптимальной игре обеих сторон результатом партии станет ничья, понадобилось почти 20 лет.

В 1989 году команда исследователей из Университета провинции Альберта под руководством Джонатана Шеффера (Jonathan Shaeffer) начала работу над программой Chinook. Разработчики поставили амбициозную цель: не просто научить компьютер играть в английские шашки, но добиться победы над чемпионом мира.

Уже в 1990 году Chinook заняла второе место на отборочном турнире в США, получив формальное право на поединок с Марионом Тинсли (Marion Tinsley) — непревзойденным гроссмейстером игры, за свою 40-летнюю (на тот момент) карьеру проигравшим только семь официальных партий.

Из-за протеста федераций шашистов США и Великобритании первый титульный матч между человеком и компьютером состоялся лишь в августе 1992 года — во многом благодаря инициативе самого Тинсли. Программа смогла выиграть только 2 партии, проиграв 4 («зависнув» в одной из них), ничейный исход был зафиксирован 33 раза.

Уже через два года началось повторное сражение за звание сильнейшего, однако из-за проблем со здоровьем Мариона Тинсли уже после шести партий (закончившихся вничью) матч был прерван. Болезнь Тинсли оказалась смертельной: в апреле 1995 он ушел из жизни непобежденным чемпионом, не проиграв ни одного титульного поединка ни человеку, ни компьютеру.

Заменить Тинсли было предложено Дону Лафферти (Don Lafferty), второму по силе шашисту мира. Начало возобновленного матча сложилось для него удачно — в восьмой партии матча Chinook вынуждена была сложить оружие, попав в известное теоретически проигрышное положение в самом дебюте. Это было первое поражение программы в 149 официальных играх.

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

В 1996 году команда разработчиков Chinook объявила о решении уйти из профессионального спорта, сосредоточившись на еще более грандиозном, чем достижение первенства, компьютерном проекте: поиске полного решения английских шашек.

Опираясь на собранную базу конечных положений игры (с менее чем 10 шашками), ученые существенно облегчили свою задачу: вместо теоретических 500 квинтиллионов (10 в 18-й степени) Chinook предстояло проанализировать только 100 триллионов позиций. Но и для этого понадобилась внушительная вычислительная мощность: на пике проекта в расчетах одновременно принимало участие более 200 компьютеров.

В период с 2004 по 2006 годы Chinook доказала ничейность ряда популярных дебютов английских шашек, а в 2007 году завершила анализ всех возможных начальных ходов. Все пользователи могут просмотреть базу данных на сайте проекта, а при желании (и должной степени упрямства) — попробовать опровергнуть доказательство ничейности английских шашек в игре с Chinook.