Идеальная ставка

Минимизировать сожаления – значит спрашивать себя: «Что было бы, если бы я поступил по-другому?» Оказывается, способность ответить на этот вопрос чрезвычайно важна в азартных играх. В 2000 году ученые из Университета Айовы опубликовали результаты исследований, которые показали: люди с повреждением участка головного мозга, ответственного за чувство сожаления, – орбитофронтальной коры – за игровым столом ведут себя иначе, чем люди без такого повреждения. И не потому, что они хуже запоминают предыдущие ошибочные решения. Во многих случаях пациенты с повреждениями орбитофронтальной коры сохраняют достаточно хорошую рабочую память и не испытывают особых трудностей, если их просят разложить картинки по порядку или совместить изображения. Проблемы начинаются, когда пациенты сталкиваются с неопределенностью и необходимостью использовать прошлый опыт, чтобы оценить степень риска. Ученые обнаружили: если в процессе принятия решения не участвует чувство сожаления, пациент склоняется к большему риску. Выходит, с надеждой смотреть вперед, стараясь получить максимальную прибыль, недостаточно – иногда нужно оглянуться назад, оценить события в ретроспективе и уже с этих позиций пересмотреть стратегию. Такой подход идет вразрез с экономической теорией, в рамках которой акцент часто ставится на ожидаемую выгоду и стремление максимально увеличить будущий доход.

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

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

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

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

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

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