Введение
Чинук — это компьютерная программа, играющая в шашки (также известные как дротки). Она была разработана в период с 1989 по 2007 год в Университете Альберты командой под руководством Джонатана Шеффера, в которую входили Роб Лейк, Пол Лу, Мартин Брайант и Норман Трелоар. Алгоритмы программы включают в себя дебютный справочник, представляющий собой библиотеку дебютных ходов из партий, сыгранных гроссмейстерами по шашкам; алгоритм глубокого поиска; функцию оценки качества хода; и базу данных эндшпиля для всех позиций с восемью или менее фигурами. Все знания, которыми обладает Чинук, были запрограммированы его создателями, а не получены с помощью системы искусственного интеллекта.
Chinook is a computer program that plays checkers (also known as draughts). It was developed between the years 1989 to 2007 at the University of Alberta, by a team led by Jonathan Schaeffer and consisting of Rob Lake, Paul Lu, Martin Bryant, and Norman Treloar. The program's algorithms include an opening book which is a library of opening moves from games played by checkers grandmasters; a deep search algorithm; a good move evaluation function; and an end game database for all positions with eight pieces or fewer. All of Chinook's knowledge was programmed by its creators, rather than learned using an artificial intelligence system.
Чемпион мира "Человек против машины"
Чинук – первая компьютерная программа, завоевавшая титул чемпиона мира в соревновании с людьми. В 1990 году она получила право участвовать в чемпионате мира среди людей, заняв второе место после Мариона Тинсли на национальном чемпионате США. Первоначально Американская федерация шашек и Английская ассоциация игры в шашки выступали против участия компьютера в человеческом чемпионате. Когда Тинсли отказался от своего титула в знак протеста, ACF и EDA учредили новый титул – Чемпионат мира «Человек против машины», и соревнования продолжились. Тинсли выиграл со счетом 4:2, при 33 ничьих. В матче-реванше в 1994 году Чинук был объявлен чемпионом мира по шашкам в матче против Мариона Тинсли после шести ничьих и отказа Тинсли от дальнейшей борьбы из-за рака поджелудочной железы. Хотя Чинук стал чемпионом мира, он так и не смог победить лучшего игрока в шашки за всю историю, Тинсли, который значительно превосходил даже своего ближайшего конкурента. В 1995 году Чинук защитил свой титул в матче из 32 партий против Дона Лафферти. Итоговый счет был 1:0 в пользу Чинука при 31 ничьей. После матча Джонатан Шеффер решил больше не допускать Чинук к соревнованиям, а вместо этого попытаться решить задачу шашек. На тот момент его рейтинг составлял 2814 Elo. Решение было найдено, и результаты были опубликованы в 2007 году.
Алгоритм
Алгоритм программы Chinook включает в себя дебютную книгу, библиотеку дебютных ходов из партий, сыгранных гроссмейстерами; алгоритм глубокого поиска; функцию оценки позиции; и базу данных эндшпилей для всех позиций с восемью или менее фигурами. Линейная, разработанная вручную функция оценки учитывает несколько характеристик игровой доски, включая количество фигур, количество королей, положение королей в ловушке, очередь хода, шашки, имеющие прямой путь к коронованию, и другие незначительные факторы. Все знания Chinook были запрограммированы его создателями, а не получены с использованием искусственного интеллекта.
Хронология
1997 Джонатан Шеффер пишет книгу о Чинуке под названием «Один прыжок вперед: бросая вызов человеческому превосходству в шашках». Обновленная версия книги была опубликована в ноябре 2008 года. 24 мая 2003 года Чинук завершает создание своей базы данных из 10 элементов, с 5 фигурами на каждой стороне. 2 августа 2004 года команда Чинука объявляет, что дебют турнира в шашках, известный как «Белый Доктор» (10–14 22–18 12–16), доказан как ничья. 18 января 2006 года команда Чинука объявляет, что дебют 09–13 21–17 05–09 доказан как ничья. 18 апреля 2006 года команда Чинука объявляет, что дебют 09–13 22–17 13–22 доказан как ничья. 10 марта 2007 года Джонатан Шеффер объявил (на конференции ACM SIGCSE 2007), что окончательное решение проблемы шашек ожидается в течение 3–5 месяцев. 19 июля 2007 года журнал Science публикует статью команды Шеффера «Checkers Is Solved», представляющую их доказательство того, что наилучший результат, которого может достичь игрок, играя против соперника с полной информацией, – это ничья.