Чинук (компьютерная программа)

Компьютерная программа для игры в шашки

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

Чемпион мира «Человек против машины»

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

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

В 1995 году «Чинук» защитил свой титул «человек-машина» против Дона Лафферти в матче из 32 игр. Окончательный счет был 1–0 при 31 ничьей в пользу «Чинука» над Лафферти. ^[2] После матча Джонатан Шеффер решил больше не позволять «Чинуку» участвовать в соревнованиях, а вместо этого попытаться решить шашки. На тот момент его рейтинг составлял 2814 Эло . Решение было достигнуто, и результат опубликован в 2007 году. ^{[3] [4]}

Алгоритм

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

График

• 1997 — Джонатан Шеффер пишет книгу о «Чинуке» под названием « Один прыжок вперед: вызов человеческому превосходству в шашках ». ^[5] Обновленная версия книги была опубликована в ноябре 2008 года.
• 24 мая 2003 г. — Chinook завершает работу над базой данных из 10 частей, по 5 частей на каждой стороне. ^[6]
• 2 августа 2004 г. - Команда «Чинук» сообщает, что открытие турнира по шашкам под названием «Белый доктор» (10–14 22–18 12–16) завершилось вничью. ^[7]
• 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 публикует статью команды Шеффера «Шашки решены», в которой представлено их доказательство того, что лучшее, чего игрок может достичь, играя против игрока с идеальной информацией, - это ничья. ^[3]

Рекомендации

1. "Матч по шашкам Чинук-Тинсли 1994 года" . Архивировано из оригинала 29 августа 2006 г.
2. «Подробности чемпионата мира «Человек против машины» 1995 года» .
3. Шеффер, Дж.; Берч, Н.; Ю. Бьернссон; Кишимото, А.; Мюллер, М.; Лейк, Р.; Лу, П.; Сатфен, С. (2007). «Шашки решены» (PDF) . Наука . 317 (5844): 1518–22. Бибкод : 2007Sci...317.1518S. дои : 10.1126/science.1144079. PMID  17641166. S2CID  10274228.
4. Шеффер, Дж.; Бьернссон, Ю.; Берч, Н.; Кишимото, А.; Мюллер, М.; Лейк, Р.; Лу, П.; Сатфен, С. «Решение шашек» (PDF) . Материалы Международной совместной конференции по организации искусственного интеллекта 2005 г.
5. Шеффер, Джонатан (1997). На один прыжок вперед: вызов человеческому превосходству в шашках . Спрингер. ISBN 978-0-387-94930-7.
6. "Домашняя страница Чинука" . 24 июня 2003 г. Архивировано из оригинала 24 июня 2003 г.
7. "Домашняя страница Чинука" . 30 сентября 2004 г. Архивировано из оригинала 30 сентября 2004 г.

Внешние ссылки

• Официальный сайт Университета Альберты