У любителей шашек появился непобедимый соперник

Марион Тинсли (Marion Tinsly), долгое время являвшийся чемпионом мира по шашкам и постоянно выигрывавший у всех соперников, проиграл всего лишь 9 игр за 40 лет после получения своей короны в 1954 г.

Он лишился звания чемпиона мира, передав его компьютерной программе в 1994 году, а теперь та же программа стала непобедимой. Ее создатели доказали, что даже если идеально сыграть против нее, то игра завершится в ничью.

Джонатан Шеффер (Jonatan Shaeffer) и его команда из университета Альберты в Канаде работают над программой Chinook с 1989 года, сообщает Nature. Она выполняется одновременно на 200-х компьютерах. Шеффер сообщил, что с её помощью удалось решить задачу игры в американские (английские) шашки или чекерс, которая разыгрывается на доске 8 на 8.

Программе Chinook не придется разыгрывать каждый из 5х10²⁰ возможных ходов - нет необходимости анализировать все неправильные шаги. На каждом этапе нужно лишь обдумать единственный выигрышный ход. В конечном счете, рассчитывается только 1/5 000 000 часть возможных ходов. Программе Chinook, рассчитавшей все варианты игры, нет необходимости тратить виртуальное время на обдумывание хорошего хода.

На сайте Chinookдоступны материалы, описывающие работу программы, и статья, направленная в журнал Science. Джап ван ден Эрик (Jaap van den Herik), редактор журнала International Computer Games Journal, назвал достижение очень существенным в области искусственного интеллекта.

Разрешимость игры на доске обычно зависит от двух факторов: числа возможных позиций (сложности пространства состояний), и сложности принятия наилучшего решения для хода. Крестики-нолики достаточно просты по обоим параметрам, шашки гораздо сложнее, не говоря уже о шахматах. Пространство состояний шахмат имеет размерность 10 ⁴⁶. Сложность решений затруднительно охарактеризовать числом, но очевидна их сложность в шахматах.

Ван ден Эрик считает, что шахматы будут решены следующим поколением, возможно, где-то между 2060 и 2070 годами. “20 лет назад бы думали, что шахматы имеют бесконечное пространство решений. Но доказательство Шеффера - это ещё один шаг к их решению.”

Однако для этого понадобятся новые средства. "Шахматы и игра Го не могут быть решены современными средствами”, - считает Шеффер. Игра Го на доске 19х19 часто считается самой сложной из популярных игр, с точки зрения возможности ее полного решения. В ней порядка 10 ¹⁰⁰ возможных позиций.

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

Скорее всего, любители шашек высоко оценят работу Шеффера. Люди по-прежнему остаются “правообладателями” игры в шашки. Создатель готических шахмат и эксперт по шашкам Эд Трайс (Ed Trice) (выигрывавший даже у некоторых чемпионов), говорит, что участники турниров не будут раздосадованы сообщением о создании непобедимой программы. В конце концов, "люди занимаются спортом даже после изобретения автомобиля".