Постоянные читатели знают и, надеюсь, любят эту колонку в том числе и за темы, имеющие ненулевой потенциал. Пророком для этого быть не нужно: достаточно обходить стороной то, что уже примелькалось, превратилось в попсу. Однако такая политика приводит порой к странным результатам — заставляя игнорировать и вроде бы взрывные события. Подобные случившемуся на прошлой неделе, когда канадско-финский коллектив компьютерщиков сорвал бурю аплодисментов в научной и популярной прессе, объявив, что сумел просчитать оптимальную стратегию игры в покер.
В одной из своих любимейших игр человек более не в состоянии состязаться с машиной (ну или так по крайней мере это подали СМИ)! Что ж, событие и правда замечательное, да только ничего принципиально нового в нём нет и придавать ему особое значение будет ошибкой. Позвольте проиллюстрировать это с помощью настольного эксперимента. И будьте готовы: вам придётся не только читать, но и вспомнить навыки программирования 😉
Так вот забудьте пока о покере. Давайте начнём с игры, к которой компьютеры ещё не применялись — игры, лежащей в основе кинофильма «Тринадцать». Если вы когда-нибудь его смотрели, то, конечно, помните о чём речь, если нет — посмотрите, хотя бы чтобы проникнуться замечательно-чёрной циничной атмосферой кровавого азарта.
Суть, в общем, в том, что герой принуждён участвовать в своеобразной версии русской рулетки. Полтора десятка человек выстраиваются кругом, каждому вручается револьвер с одним патроном, барабаны прокручиваются случайное число раз и — по команде ведущего — участники делают выстрел в голову соседа. Тела уносят, круг сужается, патронов выдаётся на один больше и всё повторяется. Естественно, вокруг ринга толпятся зрители, делающие ставки с множеством нулей. Выживший тоже получает щедрый утешительный приз и отправляется лечить нервы.
Если попал в подобное место, побороться стоит — но вот вопрос: существует ли в такой игре выигрышная стратегия? Участники верят в удачу, однако, сами понимаете, удача хороша для кино, но не выдерживает математической критики. Можно ли в самом деле придумать алгоритм, следуя которому один из участников увеличит свои шансы остаться в живых?
Вопрос сложный, потому что даже при семнадцати игроках (столько в фильме) существуют больше ста тысяч равновероятных исходов: патроны занимают случайные места, курки спускаются не одновременно, судьба каждого следующего игрока зависит от действий нескольких предыдущих (первый убивает второго, тогда остаётся жив третий и с большей вероятностью гибнет четвёртый; первый не убивает второго и тогда третий с большей вероятностью гибнет, и т.д. и т.п.). Но компьютер позволяет ответить на него запросто. Давайте прямо сейчас напишем программу, которая просчитает эту игру во всех её ипостасях.
В качестве инструмента я выбрал BASIC-256 — один из свободных диалектов самого простого языка программирования (есть версии для всех популярных десктопных ОС). Бейсик хорош тем, что писать на нём можно не задумываясь о собственно программировании, но в данном случае есть и другая причина, определившая мой выбор — о ней позже. Не ругайте сильно получившийся код: я не стал оптимизировать задачу, а решил её в лоб, по-быстрому, промоделировав сто тысяч первых раундов с участием тринадцати человек и высчитав средний шанс для каждого игрока. Итак, вот программа:
dim PLAYER(14)
dim FIRE(14)
dim SUCCESS(14) REM Количество раундов, которые пережил каждый игрок
PLAYERS=13 REM Количество игроков
for ROUND=1 to 100000 REM Проведём хоть миллион раундов
for i=1 to PLAYERS : PLAYER[i]=1 : FIRE[i]=1+floor(rand()*6) : next i REM Все игроки живы, патроны в барабанах
num=0 REM Пока попытались стрелять ноль человек
START:
P=1+floor(rand()*PLAYERS*1) REM Определяем случайно, кто стреляет сейчас - чтобы дать первому игроку преимущество, поменяйте множитель 1 на большее число
if P>PLAYERS then P=1 REM Лишний шанс нашему игроку начать стрелять первым
end if
if PLAYER[P]=1 then GOSUB TRY_TO_KILL
end if
if FIRE[P]>0 then num=num+1 : FIRE[P]=0 REM Игрок сделал ход
end if
if num<PLAYERS then goto START
for i=1 to PLAYERS
if PLAYER[i]>0 then SUCCESS[i]=SUCCESS[i]+1 REM Игрок пережил ещё один раунд
end if
next i
next ROUND
print "Шансы выжить:"
for i=1 to PLAYERS : print i+": "+100*SUCCESS[i]/ROUND+"%"
next i
TRY_TO_KILL:
P1=P+1
if P1=PLAYERS+1 then P1=1
end if
if FIRE[P]=1 then PLAYER[P1]=0 REM Если был выстрел, следующий убит
REM if FIRE[P]=1 AND P<>1 then PLAYER[P1]=0 REM Раскомментируйте, чтобы заставить игрока 1 пропустить выстрел
end if
PLAYER[P]=2 REM Выстрел сделан, либо патрона не было
RETURN
Понятно, что реализованный здесь сценарий упрощён по сравнению с кино (всегда то же число участников и один патрон). Понятно, что в действительности, даже зная оптимальную стратегию, участвовать в такой игре — сумасшествие. Но для нас важна математика. Что же получилось? Минутный эксперимент показывает, что если курки спускаются случайно, шансы выжить у всех равные: примерно 84%. А что если заставить нашего игрока (номер один) стрелять раньше других? Увы, вопреки кажущейся возможности повлиять таким образом на исход, при большом числе соперников никакого заметного преимущества это ему не даст. Лишь при условии, что на ринге окажутся всего 4 человека, поторопившись с выстрелом, первый игрок увеличит свой шанс выжить на десятую долю процента. Мало? Биржевики и профессиональные карточные игроки, думаю, поспорят 🙂
Но к чему вообще этот эксперимент, почему для него выбран BASIC, да ещё такого странного вида? Всё просто. Мы с вами только что решили задачу нахождения оптимальной стратегии игры тем же способом, что и канадцы, «просчитавшие» покер: грубым перебором.
Метод этот используется чуть ли не с рождения электронной вычислительной техники — и тем же периодом датируется самый громкий успех его применения: в начале 60-х годов американский математик Эдвард Торп, задействовав вычислительную машину IBM 704 (лампы, 12 тысяч операций в секунду, FORTRAN; её, впрочем, даже компьютером не называли: калькулятор!), просчитал блэкджек и описал стратегию, придерживаясь которой можно — в статистической перспективе — выигрывать чаще среднего игрока (пятьдесят лет назад его книга была бестселлером, нынче он больше известен публике по к/ф «Двадцать одно»).
Сегодня любая персоналка в миллионы раз производительней тех древних машин. Вы только что убедились в этом сами — применив для моделирования вполне реальной ситуации инструмент, предназначенный для детей (BASIC-256 придуман для обучения программированию, отсюда его примитивность; уж простите мне этот маленький розыгрыш ;-). А собрав кластер из нескольких тысяч компьютеров и оплатив пару месяцев машинного времени, можно замахнуться на игры, где количество ситуаций исчисляется триллионами. Что и проделали канадцы с покером: они выбрали один из наиболее простых для обсчёта вариантов этой карточной игры (известный у нас как разновидность холдема) и перебрали все комбинации ходов.
Справедливости ради следует отметить, что попутно они предложили новый алгоритм перебора — на порядок более эффективный, нежели ранее применявшиеся. И надеются, что он поможет строить автоматические системы, принимающие решения в условиях неопределённости (не все, кстати, согласны, что неопределённость на игровом столе можно сравнивать с неопределённостью в настоящей жизни). Однако в основе их работы — тот же древний метод перебора.
Нет новизны и нет доблести в том, чтобы ломать игры числодробительным тараном в XXI веке. Это делают уже пятьдесят лет. И, кстати, Торп проверял свои вычисления не в лаборатории, а за карточным столом в настоящих казино, заняв у бандитов…
Конечно, покер отличается от блэкджека и уж тем паче от русской рулетки — большим количеством неизвестных. Так что свести оптимальную стратегию даже для ограниченного варианта холдема к простому набору правил не удалось: каждый ход требует анализа десятков терабайт информации, на чём заметно притормаживает и суперкомпьютер (бот Cepheus выведен в Сеть: к нему можно обратиться за советом и даже с ним сыграть). И всё-таки — ничего нового.
Куда интересней было бы, если б кто-то просчитал стратегию для одной из игр, где число вариантов заведомо слишком велико. Пусть и для обыкновенного покера (10^160), а лучше — для древней го, которая, при своей кажущейся простоте, количеством комбинаций превосходит любые другие игры (10^761).
Увы, тут вычислительная машина пасует. Одного умения считать мало!
P.S. В статье использованы иллюстрации Florencia&Pe, Ale Ale, кадры из к/ф «Тринадцать».