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

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

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

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

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

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

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

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

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

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

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

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

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

Разумеется, никакая обезьяна не может жить вечно, да еще безвылазно сидя за пишущей машинкой. Так что лучше рассматривать ее как метафору случайного генератора, выдающего произвольную последовательность знаков. Так как буквы расположены хаотично, существует вероятность – хотя и очень маленькая, – что обезьяна сразу же напечатает: «Кто здесь?» – реплику, с которой начинается «Гамлет». А потом у нее случится полоса везения, и она будет нажимать на нужные буквы, пока не наберет все шекспировские пьесы. Это крайне маловероятно, но возможно. Или же обезьяна будет печатать бессмыслицу, пока ей не удастся попасть пальцем в правильные клавиши в правильном порядке. Возможно, перед этим ей придется выдавать абракадабру в течение нескольких миллиардов лет.