Адам Кучарски - Идеальная ставка

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

Теория игр лучше всего работает в простых ситуациях, когда вся информация известна. Отличный пример – крестики-нолики: после нескольких партий почти каждый игрок способен прийти к равновесию Нэша. Все дело в том, что в крестиках-ноликах не так уж много вариантов развития событий: игра заканчивается, когда кто-то ставит три крестика или три нолика в ряд, ходы игроки делают по очереди, а расположение игрового поля никак не влияет на ход игры. И хотя существует 19 683 способа расположить крестики и нолики на игровом поле размером три на три клетки, лишь около 100 из них действительно релевантны.

Найти идеальную стратегию реагирования на действия противника в крестиках-ноликах легче легкого. Как только идеальную стратегию выработают оба игрока, все последующие партии сведутся к ничьей. Шашки куда сложнее. Даже лучшие игроки так и не отыскали для них идеальную стратегию. Но если и есть человек, сумевший ее нащупать, то это Марион Тинсли.

Тинсли преподавал математику в Университете Флориды и имел репутацию непобедимого игрока в шашки. Свой первый турнир он выиграл в 1955 году, удерживал звание чемпиона на протяжении четырех лет, после чего бросил играть, сославшись на отсутствие достойных противников. В 1975 году он снова сел за доску и немедленно вернул себе чемпионский титул, разгромив всех соперников. Однако 14 лет спустя интерес Тинсли к шашкам опять стал угасать. Тогда-то он и узнал о программе, которую разрабатывали в Канаде, в Университете Альберты.

В настоящее время Джонатан Шеффер занимает в этом учебном заведении должность декана, но в далеком 1989 году он был молодым преподавателем факультета информатики. Изучая программы для игры в шахматы, Шеффер заинтересовался и шашками. Так же как в шахматах, в шашки играют на поле восемь на восемь клеток. Фигуры двигаются вперед по диагонали и «съедают» фигуры противника, перепрыгивая через них. Достигнув противоположного края доски, шашка становится дамкой и может двигаться как вперед, так и назад. Простота шашек привлекала теоретиков легкостью анализа и прогноза последствий каждого хода. Но можно ли научить компьютер выигрывать в шашки?

Шеффер назвал свою программу для игры в шашки Chinook – в честь юго-западного теплого ветра чинук, который дует на канадские прерии со Скалистых гор. Тут не обошлось без игры слов, поскольку британское название шашек – draughts – означает также «воздушный поток». При поддержке коллег-программистов и шашечных энтузиастов Шеффер приступил к решению первой проблемы: как справиться со сложностью игры? В шашках существует около 10 20различных позиций. Это десятка с 20 нулями: если вы соберете песок со всех пляжей мира, в вашем распоряжении окажется приблизительно такое же количество песчинок.

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

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

Chinook пришла в большой спорт в 1990 году, заняв второе место на Национальном чемпионате США по шашкам. Это означало, что программа получала доступ к участию в мировом первенстве, однако Американская федерация шашек и Английская ассоциация шашек были против того, чтобы компьютер соревновался с людьми. К счастью, Тинсли не разделял их взглядов. После нескольких проведенных в 1990 году неофициальных игр он понял, что ему импонирует агрессивный стиль Chinook . Соперники-люди пытались добиться от Тинсли ничьей, но программа не боялась рисковать и стремилась к победе. Тинсли так хотелось сразиться с ней на официальных соревнованиях, что он отказался от чемпионского титула, и организаторам пришлось скрепя сердце допустить компьютер до участия в турнире. В 1992 году Chinook сыграл против Тинсли в мировом чемпионате «Человек против машины». Из 39 игр Тинсли выиграл четыре, программа – две, остальные партии окончились ничьей.

Несмотря на достойное сопротивление, которое Chinook оказала Тинсли, Шеффер и его команда не собирались останавливаться на достигнутом. Они мечтали сделать Chinook непобедимой. Эффективность программы зависела от детального прогнозирования, что делало ее игроком сильным, но по-прежнему уязвимым перед лицом случайности. Сумев убрать из программы элемент удачи, разработчики получили бы идеального шашиста.

Может показаться странным, что в шашках требуется удача. Если в каждой партии делать одни и те же ходы, она будет заканчиваться одним и тем же результатом. Говоря математическим языком, это детерминированная игра, и, в отличие от покера, фактор случайности не имеет в ней значения. Тем не менее результат матча зависел только от действий Chinook , а это означало, что программу можно обыграть. Теоретически ее мог победить даже неопытный противник.

Чтобы понять почему, снова обратимся к исследованиям Эмиля Бореля. Помимо теории игр, он изучал крайне маловероятные события. Чтобы показать, что даже почти невозможные события обязательно произойдут, если подождать достаточно долго, он сформулировал теорему о бесконечных обезьянах. Основывалась она на простом предположении: допустим, обезьяна случайным образом ударяет по клавишам пишущей машинки (но не ломая ее, как это случилось в Университете Плимута в 2003 году, когда команда ученых решила проверить теорему на практике), и занимается этим бесконечно долгое время. Рано или поздно она напечатает собрание сочинений Шекспира. Согласно теореме, в какой-то момент волей чистого случая последовательность букв, возникающих на бумаге благодаря стараниям обезьяны, сложится в 37 пьес великого английского драматурга.