Категории каталога
Каталог / Наука / Новые технологии, изобретения / Роботы и искусственный интеллект / Чинук-программа побеждает человека в шашках

Чинук-программа побеждает человека в шашках

Джонатан Шеффер (Jonathan Schaeffer), профессор университета Альберты (University of Alberta), заведующий тамошней кафедрой вычислительной техники объявил, что шашки больше не представляют для человечества никакой загадки.

Нельзя сказать, что и до этого-то шашки были для людей средоточием чего-то мистического. Но всё же, итог игры никогда не был полностью предсказуемым. Именно поэтому, между прочим, одни люди по сей день садятся играть в шашки друг с другом, а другие пишут "компьютерные шашки" — потому что интересно.

Доктор Джонатан Шеффер. Если посмотреть на картинки на его мониторе, можно подумать, что у него горит зуб на шахматы. Впрочем, это не так — учёного нынче заботит не эта игра, а покер (фото с сайта expressnews.ualberta.ca).

Доктор Джонатан Шеффер. Если посмотреть на картинки на его мониторе, можно подумать, что у него горит зуб на шахматы. Впрочем, это не так — учёного нынче заботит не эта игра, а покер (фото с сайта expressnews.ualberta.ca).
Раньше окончание и "живой", и "программной" шашечной партии можно было спрогнозировать лишь с определённой степенью вероятности. Приятным исключением на протяжении многих лет считался американский чемпион мира по шашкам Мэрион Тинсли (Marion Tinsley). С тех пор как он получил статус чемпиона мира в этой игре в 1954 году, Тинсли на официальных соревнованиях проиграл всего девять раз.

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

Чтобы смоделировать усилия такой настойчивой пары, потребовалось бы проанализировать 51020 (это число можно записать и просто как пятёрку с двадцатью нулями) позиций шашек на поле. Было бы занятно прикинуть, сколько миллиардов лет решал бы эту задачу самый опытный гроссмейстер, но Шеффер не стал этим забивать свою голову. Он просто решил просчитать все эти ситуации с помощью нескольких десятков компьютеров.

Учёные университета Альберты начали работу над "взломом" шашек ещё в 1989 году (фото Mitch Diamond).

Учёные университета Альберты начали работу над "взломом" шашек ещё в 1989 году (фото Mitch Diamond).
Окончательной целью проекта было, естественно, создание программы, которая могла бы отвечать на ход соперника только оптимальными действиями, которые могут приводить только к выигрышу. Эту программу под названием Chinook сделали довольно скоро и постоянно её совершенствовали.

После того как стартовал этот процесс, и компьютеры всё больше пополняли базу данных изученных позиций, эффективность "Чинука" периодически проверяли. Одним из самых лучших испытателей был, конечно, Тинсли.

Компьютеры, а также программисты и математики из команды Шеффера старались изо всех сил, наращивая мощь "Чинука". Однако битва "Chinook против Тинсли", как правило, заканчивалась ничейным результатом. Победы бывали крайне редко — да и то в осоновном со стороны Тинсли.

Картина маслом. "Игра в шашки" (Game of Draughts), написана художником Алоизусом О'Келли (Aloysius O'Kelly) в 1889 году. Тогда вычислительной техникой для шашек особенно не пользовались. Однако компьютеры, которые использовала <a href="http://webdocs.cs.ualberta.ca/~games/" target="_blank" title="Откроется в новом окне">GAMES</a> — исследовательская группа Шеффера — работали с 1989-го почти непрерывно. Как сообщается, максимальное количество рабочих станций, которое применялось для "взлома" шашек достигло двухсот (иллюстрация с сайта fortunecity.com).

Картина маслом. "Игра в шашки" (Game of Draughts), написана художником Алоизусом О'Келли (Aloysius O'Kelly) в 1889 году. Тогда вычислительной техникой для шашек особенно не пользовались. Однако компьютеры, которые использовала GAMES — исследовательская группа Шеффера — работали с 1989-го почти непрерывно. Как сообщается, максимальное количество рабочих станций, которое применялось для "взлома" шашек достигло двухсот (иллюстрация с сайта fortunecity.com).
Возможно, великий шашист одолел бы компьютер, но проблемы со здоровьем не дали ему возможности продолжить соревнования. В результате в 1994 году Chinook получил "звание" чемпиона мира по шашкам.

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

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

Окно компьютерной программы, показывающей возможные варианты ходов. Все эти версии компьютеры просчитывали на протяжении 18 лет. Кстати, чинук — это название племени индейцев. Также чинук — это тёплый зимний ветер на побережье Канады. Чинук — это ещё много чего, но всё это к шашкам раньше не имело отношения. А теперь чинук — это ещё и программа. Ну и дела! (иллюстрация University of Alberta)

Окно компьютерной программы, показывающей возможные варианты ходов. Все эти версии компьютеры просчитывали на протяжении 18 лет. Кстати, чинук — это название племени индейцев. Также чинук — это тёплый зимний ветер на побережье Канады. Чинук — это ещё много чего, но всё это к шашкам раньше не имело отношения. А теперь чинук — это ещё и программа. Ну и дела! (иллюстрация University of Alberta)
И вот недавно Шеффер в статье в журнале Science заявил, что проблемы шашек больше не существует. Это значит, что его "Чинук" теперь стал беспроигрышной программой, и теперь она знает все правильные ходы для любой ситуации.

Материал предоставлен: Membrana.RU - Люди. Идеи. Технологии.

Реклама:
Где заказать рерайтинг текстов узнай на сайте eTXT.ru