Chinook

Chinook (с англ. — «Чинук») — компьютерная программа, которая играет в шашки. Разработана в 1989 году в Альбертском университете группой программистов во главе с Джонатаном Шеффером с участием Роба Лейка, Поля Лу, Мартина Брайанта и Нормана Трелоара. В июле 2007 года разработчики Chinook сообщили, что программа была усовершенствована до такой степени, что не может проиграть.

Чемпионат: человек против машины

Chinook является первой компьютерной программой, которая смогла выиграть титул чемпиона мира в соревновании против людей.

В 1990 году она завоевала право играть на чемпионате мира среди людей, став второй после Мариона Тинсли в чемпионате США. Сначала Американская федерация шашек (ACF) и Английская Ассоциация по игре в шашки (EDA) были против участия компьютера в человеческом чемпионате. Когда Тинсли ушёл в отставку в знак протеста, ACF и EDA создали новую категорию: «Мировой чемпионат человека против машины», и соревнования продолжились. Тинсли выиграл у Chinook с четырьмя победами (также было 33 ничьих).

В 1994 году, в матче-реванше против Тинсли, после шести ничьих и отставки Тинсли из-за плохого самочувствия Chinook была объявлена чемпионом мира по шашкам в категории «человек-машина». Так, несмотря на то, что Chinook стала чемпионом мира, она не победила лучшего игрока всех времён — Тинсли^[1].

В 1995 году Chinook защитила свой титул чемпиона мира в игре против Дона Лафферти^[2]. Матч из 32 игр закончился со счётом 1:0.

Алгоритм

Алгоритм программы включает в себя открытые библиотеки ходов, которые делали гроссмейстеры в своих играх, алгоритм поиска в глубину, функцию оценки хода. В конце игры программа имеет варианты выигрыша для любой позиции, заглядывая на 8 ходов вперёд.

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

Хронология

Джонатан Шеффер написал книгу о Chinook «Один скачок вперёд: борьба с преимуществом человека в шашках» (англ. One Jump Ahead: Challenging Human Supremacy in Checkers) в 1997 году^[3]. Обновлённая версия книги была опубликована в ноябре 2008 года.

24 мая 2003 Chinook завершила создание своей 10-й базы данных^[4].

2 августа 2004 команда Chinook объявила, что открытый турнир по шашкам в Англии (10-14 22-18 12-16) (называемый «Белый Доктор») закончился ничьей^[5].

18 января 2006 команда Chinook объявила, что открытый чемпионат (09-13 21-17 05-09) был сыгран вничью.

19 июля 2007 журнал Science опубликовал статью команды Шеффера «Checkers Is Solved», представив доказательства того, что лучший игрок в игре против Chinook может достичь максимум ничьей^[6].