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

«Чинук» — компьютерная программа для игры в шашки (также известные как шашки). Он был разработан в период с 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]

Ссылки

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

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

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

[1] «Матч по шашкам Чинук-Тинсли 1994 года» . Архивировано из оригинала 29 августа 2006 г.

[2] «Подробности чемпионата мира «Человек против машины» 1995 года» .

[auto-3] Jump up to: ^а ^б Шеффер, Дж.; Берч, Н.; Ю. Бьернссон; Кишимото, А.; Мюллер, М.; Лейк, Р.; Лу, П.; Сатфен, С. (2007). «Шашки решены» (PDF) . Наука . 317 (5844): 1518–22. Бибкод : 2007Sci...317.1518S . дои : 10.1126/science.1144079 . ПМИД 17641166 . S2CID 10274228 .

[4] Шеффер, Дж.; Бьернссон, Ю.; Берч, Н.; Кишимото, А.; Мюллер, М.; Лейк, Р.; Лу, П.; Сатфен, С. «Решение шашек» (PDF) . Материалы Международной совместной конференции по организации искусственного интеллекта 2005 г.

[5] Шеффер, Джонатан (1997). На один прыжок вперед:: Оспаривание человеческого превосходства в шашках . Спрингер. ISBN 978-0-387-94930-7 .

[6] «Домашняя страница Чинука» . 24 июня 2003 г. Архивировано из оригинала 24 июня 2003 г.

[7] «Домашняя страница Чинука» . 30 сентября 2004 г. Архивировано из оригинала 30 сентября 2004 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]