Программа Чинук не проигрывает человеку в английские шашки (чекерс)

Английские шашки хакнули. Или, как еще говорят, крякнули. Но на самом деле их просто перебрали. Все ходы не только записаны, но и заранее просчитаны. Поэтому сражения с компьютером больше не интересны: «железка» теперь знает, как действовать без проигрыша. Поэтому с ней сыграть можно только вничью (если очень постараться), либо проиграть ей. А третьего не дано.

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

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

Доктор Джонатан Шеффер. Если посмотреть на картинки на его мониторе, можно подумать, что у него горит зуб на шахматы. Впрочем, это не так – ученого нынче беспокоит не эта игра, а покер.

Ранее окончания и «живой» и «программной» шашечной партии можно было спрогнозировать лишь с определенной степенью вероятности. Приятным исключением на протяжении многих лет считался американский чемпион мира по шашкам Марион Тинсли (Marion Tinsley). С тех пор как он получил статус чемпиона мира в этой игре в 1954 году, Тинсли на официальных соревнованиях проиграл всего девять раз.

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

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

Ученые университета Альберты начали работу над «взломом» шашек еще в 1989 году.

Окончательной целью проекта было, естественно, создание программы, которая могла бы отвечать на ход соперника только оптимальными действиями, которые могут приводить только к выигрышу. Эту программу под названием Chinook сделали довольно скоро и постоянно ее совершенствовали.

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

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

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

Возможно, большой шашистов одолел бы компьютер, но проблемы со здоровьем не дали ему возможности продолжить соревнования. В результате в 1994 году Chinook получил «звание» чемпиона мира по шашкам.

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

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

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

И вот недавно Шеффер в статье в журнале Science заявил, что проблемы шашек больше не существует. Это означает, что его «Чинук» теперь стал беспроигрышной программой, и теперь она знает все правильные ходы для любой ситуации.

Главный редактор «Журнала Международной ассоциации компьютерных игр» (International Computer Games Association Journal), профессор математики, Яап ван ден Херик (H. Jaap van den Herik), который взялся прокомментировать работу Шеффера (непосредственного участия в ней он не участвовал), признал ее «поистине знаменательным успехом в области искусственного интеллекта».

Сделаем небольшое уточнение. Создание Chinook – это действительно прорыв в области искусственного интеллекта. Однако сама программа как окончательный продукт к какому-либо интеллекту, пожалуй, имеет мало отношения. Chinook не «думает» – вместо этого он выбирает из базы данных оптимальный ход, который соответствует данному расположению шашек на доске.

Мэрион Тинсли на турнире 1992 года, во время которого он боролся с «Чинук». «Chinook запрограммирован Джонатаном, а я запрограммирован Богом», – говорил Тинсли, который, кстати, был не только выдающимся шашистом, а доктором математики, а также служил пресвитером в баптистской церкви (фото с сайта cs.ualberta.ca).

Ван ден Херик поделился заодно своими размышлениями по поводу судьбы других игр.

Что касается, например, крестиков-ноликов, то их «проблема», как известно, решается тривиально. Уровень сложности этой игры минимален и написать «софтину», которая будет всегда или выигрывать, или сводить партию к ничьей, может практически любой программист.

С шашками вышло сложнее – «хакать» их пришлось без малого двадцать лет, однако, как видите, это дело оказалось совсем не безнадежным. В то, что окончательная победа все-таки произошла, не очень верится, но если хотите, можете проверить – Шеффер любезно предоставляет «Чинук» в онлайн-варианте.

Решая проблему беспроигрышных шашек, американские военные предложили понимать слово «ходить» в буквальном смысле. Не помогло (фото с сайта diggerhistory3.info).

И если то, что он выложил – действительно «Чинук», то обыграть его у вас не получится – максимум удастся довести партию до ничьей. Так что тема шашек закрыта. «К сожалению» или «на счастье»? Кому как …

Пока так и не удалось «раскусить» шахматы, но, если верить ван ден Херику, то это только вопрос времени. По его оценкам, сделать это получится «если во время нашей жизни, то при наших детей – где-то между 2060 и 2070 годы». Напомним, что когда-то это пытались сделать усилиями собственного мышления Крамник и Каспаров. Зачастую это удавалось, но секрет всего лишь в слабости техники.

Для игры го перспективы более далекие, хотя и светлые. Если общее количество расстановок фигур в шахматах составляет около 1046, то для го это число примерно равно 10100, и чтобы сделать новую беспроигрышную «го-программу», потребуется еще лет сто.

Бывают, кстати, еще и русские и стоклеточные шашки, но математики одолели пока только те, которыми играют преимущественно в Англии и США – английскими шашками, или, как их иначе называют – чекерсом.

Впрочем, Шеффер сомневается, что это возможно сделать с теми средствами, которые у нас сейчас. «Такие игры, как шахматы и го, невозможно разгадать с теми технологиями, которые имеем мы в наше время», – сетует математик. Не исключено, впрочем, что это произойдет вскоре после того, как закон Мура окончательно выйдет в третье измерение.

Вот такое большое событие произошло в мире настольных игр. Что же касается домино, то по планам «хака» этой игры Шеффер пока не говорил ничего. Ну, это даже хорошо – по крайней мере, нам интереснее играть в «невзломанное» домино. Ведь если его сломают, то все станет предсказуемым, и тогда непонятно, как вообще нам тогда быть и чем заниматься.

Стоп, ждите … «Рыба»!

Опубликовано: Апрель 23, 2012