Блэкджек на кубиках, или «Многогранное очко»

Общие правила всех рассмотренных вариантов игры:

• •    В игре участвуют два игрока.

• •    Игрокам необходимо, бросая кубики, набрать сумму очков больше, чем у соперника, но не превышающую 21.

• •    Первый ход каждого игрока обязательно совершается броском 2-х кубиков.

• •    В базовой версии игры каждый последующий ход может быть либо броском ещё одного кубика, не использованного ранее, либо остановкой игры с фиксацией набранной суммы.

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

• •    После окончания игры победителем считается тот, кто набрал большее число очков по сравнению с соперником, но не превышающее 21. Игрок, набравший более 21 очка, считается проигравшим; если игроки набрали одинаковое количество очков или оба игрока набрали больше 21 очка, то засчитывается ничья.

2.    Первый вариант игры — последовательный (с пропуском хода либо без такового)

На основе этих правил мы строим три вариации игры и разбираем их с точки зрения теории игр, чтобы найти равновесия, выигрышные стратегии и средний выигрыш обоих игроков. Значимость работы заключается в том, что на простом и популярном примере показаны все основные базовые концепции теории игр. Кроме того, данная игра, насколько нам известно, никогда до сих пор не рассматривалась и не рассчитывалась до конца в научной литературе, хотя сам блэкджек уже анализировался в других работах (см., например, подсчет среднего выигрыша оптимального игрока [3]).

Игра начинается с того, что первый игрок ходит любыми двумя кубиками из своих пяти «Платоновых тел». Далее аналогично поступает его соперник.

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

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

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

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

Опишем основные выводы вычислений:

• •    Первый игрок на первом ходу должен использовать кубики 4 (тетраэдр) и 20 (икосаэдр). Таким образом он обеспечивает себе наибольший средний выигрыш, приблизительно равный -0.0116. Этот ход позволяет избавиться от наибольшего по значению кубика с минимальной вероятностью перебора.

• •    Второй игрок использует ту или иную пару кубиков в зависимости от результатов хода первого игрока: от пары выбранных им кубиков и от количества выпавших очков.

Если считать, что первый игрок ходит оптимально, то есть кидает кубики 4 и 20, то зависимость ходов второго игрока от хода первого такова: бросаются кубики б и 20 в случае, если первый игрок набрал 9, 12, 13, 15, 18, 19, 20 или 21. В противном случае бросаются кубики 4 и 20. Впрочем, разница в средних выигрышах между этими двумя ходами составляет около двух сотых. Если у первого игрока сразу случился перебор, то надо бросить кубики 4 и 6.

• •    Далее каждый ход определяется текущим состоянием игры: количеством очков у активного игрока и его соперника, наборами неиспользованных кубиков в арсеналах игроков, фактом пропуска хода соперником при его последнем действии.

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

• •    Игра выгодна второму игроку: при идеальной игре он выигрывает в среднем 0.0116 при ставке в 1 (выигрыш его складывается из вероятности победы ~ 0.4108 , ничьей « 0.1898 л пропгрыша. « 0.3992).

• •    Если рассматривать вариант игры без пропуска хода (только полная остановка, без возможности продолжить броски далее), то игра станет ещё более нечестной, и при использовании оптимальных стратегий второй игрок выиграет ~ 0.0366.

• •    Общее число уникальных состояний, для которых необходимо выбирать ход, превышает 374 000 для игры с пропусками и 127 000 для игры без пропуска хода.

• •    В первый ход (если у первого игрока не случился перебор) всегда имеет смысл избавиться от икосаэдра (кубика 20), в последующие - почти всегда надо бросать наибольший по значению куб, если вероятность перебора достаточно низкая.

Таблица!

Средний выигрыш первого игрока при идеальной игре с пропусками в зависимости от первого хода

Ход	Средний выигрыш
{4, 20}	-0.0116
{6, 20}	-0.0211
{8, 20}	-0.0608
{8, 12}	-0.0680
{6, 12}	-0.0809
{4, 12}	-0.1063
{4, 8}	-0.1352
{6, 8}	-0.1363
{12, 20}	-0.1557
{4, 6}	-0.1682

В табл. 1 представлены средние выигрыши первого игрока, округлённые до десятитысячных. В расчетах мы исходили из предположения, что после соответствующего хода оба игрока действуют оптимально.

В табл. 2 представлены данные, аналогичные табл. 1, но для случая игры без возможности пропустить ход.

Разберём первую вариацию игры без пропусков на примере. У активного игрока 16 очков и 8-гранник в запасе, а у его соперника 14 очков и тетраэдр.

У активного игрока в данном случае две стратегии: остановиться либо бросить оставшийся 8-гранник. Рассмотрим обе.

Т а б л и ц а 2

Средний выигрыш первого игрока при идеальной игре без пропусков в зависимости от первого хода

Ход	Средний выигрыш
{4, 20}	—0.0366
{6, 20}	—0.0403
{8, 20}	—0.0790
{8, 12}	—0.0791
{6, 12}	—0.0870
{4, 12}	—0.1089
{4, 8}	—0.1322
{6, 8}	—0.1341
{4, 6}	—0.1646
{12, 20}	—0.1724

• •    Если активный игрок остановится, то соперник бросит тетраэдр и в одном из 4-х случаев проиграет, ещё в одном случае игра закончится ничьёй, а в 2-х из оставшихся случаев соперник выиграет. Итого средний выигрыш первого игрока от данного хода составит: - - +  = —

44  4

• •    Если бросить 8-гранник, то с шансом - получаем перебор, с шансом - получаем 88

3.    Второй вариант игры — одновременный (с пропуском хода либо без такового)

значение от 19 до 21, что гарантирует победу. В оставшихся двух случаях имеем 17

или 18 очков. Соперник же, имея 14 очков, бросит тетраэдр и будет надеяться на ничью. Итоговый средний выигрыш будет равен:---1---1— х (---1—) +— х - = -

*

888 44 848

Таким образом, для данного состояния игры выгоднее бросать 8-гранник, хотя такой ход и включает в себя немалый шанс перебора.

Данный вариант игры отличается от последовательного очередностью ходов: в одновременной игре игроки принимают решения одновременно и независимо друг от друга.

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

Рассмотрим сначала расширенный вариант игры, с правом пропустить ход и последующей (если игра не закончится) возможностью вернуться в игру. Во время своих ходов, начиная со второго, каждый из игроков, видя результаты предыдущего хода, выбирает, бросить ещё один из своих кубиков или же пропустить ход.

Игра завершается либо когда хотя бы один из игроков перебрал, либо при одновременном пропуске/невозможности совершить ход (например, один пропускает ход, а другой уже не имеет возможности бросить кубик). Таким образом, игрок, имеющий меньше очков и пропускающий ход, сильно рискует: если его соперник тоже пропустит ход, то это будет означать автоматический проигрыш для отстающего игрока!

Заметим, что в этой игре уже возможна ситуация одновременного перебора, — в таком случае в игре фиксируется ничья; в остальных случаях правила определения победителя не меняются.

Данная игра, в отличие от предыдущей, является симметричной, так как началвное состояние и стратегические возможности у обоих игроков совпадают; следовательно, при идеальной (при «правильной») игре средний выигрыш обоих игроков равен нулю.

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

Ниже мы рассмотрим результаты вычислений, проведённых для данного варианта игры. Надо понимать, какое именно равновесие мы ищем, поскольку это достаточно сложная концепция равновесия, совершенного на подыграх (см. например, [4], а также [5]).

Суть этой концепции решения состоит в том, что после любой пары начальных ходов мы далее выстраиваем игру, как если бы она началась не «с начала», а с ситуации, когда каждый из игроков имеет сразу полученное на первом ходу количество очков и некоторые три кубика из пяти: для выбора из них либо пропуска хода. Но и это ещё не всё, ибо вслед за этим вновь разыгрывается ещё более «урезанная» игра. Глубина такого прощупывания ограничена 8-ю этажами, но это при решении с конца означает перебор астрономического количества вариантов! К счастью, современные компьютеры позволяют этот перебор осуществить благодаря составленной программе.

Т а б л и ц а 3

Средний выигрыш игрока при оптимальной игре в зависимости от первого хода (вариант с пропусками хода)

Ходы	{4,6}	{4,8}	{4,12}	{4,20}	{6,8}	{6,12}	{6,20}	{8,12}	{8,20}	{12,20}
{4, 6}	0	-0.034	-0.072	-0.170	-0.034	-0.099	-0.149	-0.113	-0.099	0.015
{4, 8}	0.034	0	-0.037	-0.136	-0	-0.062	-0.116	-0.076	-0.067	0.043
{4, 12}	0.072	0.037	0	-0.105	0.038	-0.027	-0.089	-0.04.3	-0.042	0.064
{4, 20}	0.170	0.136	0.105	0	0.135	0.077	0.003	0.062	0.040	0.127
{6, 8}	0.034	+0	-0.038	-0.135	0	-0.062	-0.113	-0.076	-0.063	0.046
{6, 12}	0.099	0.062	0.027	-0.077	0.062	0	-0.062	-0.016	-0.017	0.086
{6, 20}	0.149	0.116	0.089	-0.003	0.113	0.062	0	0.048	0.034	0.116
{8, 12}	0.113	0.076	0.043	-0.062	0.076	0.016	-0.048	0	-0.004	0.098
{8, 20}	0.099	0.067	0.042	-0.040	0.063	0.017	-0.034	0.004	0	0.082
{12, 20}	-0.015	-0.043	-0.064	-0.127	-0.046	-0.086	-0.116	-0.098	-0.082	0

Каждый элемент в табл. 3 представляет собой средний выигрыш игрока при использовании им стратегии из строки, в то время как его соперник использует стратегию из столбца. Значения округлены до тысячных долей, обозначения +0 и —0 отображают околонулевые значения с соответствующим знаком.

Данные в табл. 4 аналогичны данным в табл. 3, но для варианта игры без возможности пропустить ход. Примечательно, что числа немного отличаются, однако выводы остаются теми же:

• •    Как можем заметить из таблиц, игроку в начальном состоянии выгодно совершить такой же первый ход, как и в случае одновременной игры: бросить 4 и 20, так как все числа в соответствующей строке неотрицательные.

• •    Оптимальный ход также является доминирующей стратегией в начальном состоянии: независимо от выбора соперника, максимальный средний выигрыш достигается именно этим ходом.

• •    В более общих случаях на втором и третьем ходу строго доминирующей стратегии может не быть, и игрокам придётся пользоваться смешанными стратегиями, разыгрывая перед ходом некоторое выбранное самим игроком вероятностное распределение (по поводу смешанных стратегий см. [6]).

Т а б л и ц а 4

Средний выигрыш игрока при оптимальной игре в зависимости от первого хода (вариант без пропусков хода)

Ходы	{4,6}	{4,8}	{4,12}	{4,20}	{6,8}	{6,12}	{6,20}	{8,12}	{8,20}	{12,20}
{4, 6}	0	-0.029	-0.059	-0.128	-0.018	-0.072	-0.114	-0.082	-0.067	0.041
{4, 8}	0.029	0	-0.028	-0.095	0.011	-0.041	-0.082	-0.050	-0.037	0.068
{4, 12}	0.059	0.028	0	-0.073	0.037	-0.015	-0.062	-0.024	-0.018	0.084
{4, 20}	0.128	0.095	0.073	0	0.095	0.050	0.001	0.04.3	0.038	0.128
{6, 8}	0.018	-0.011	-0.037	-0.095	0	-0.048	-0.081	-0.056	-0.036	0.070
{6, 12}	0.072	0.041	0.015	-0.050	0.048	0	-0.041	-0.008	0.002	0.103
{6, 20}	0.114	0.082	0.062	-0.001	0.081	0.041	0	0.034	0.035	0.120
{8, 12}	0.082	0.050	0.024	-0.043	0.056	0.008	-0.034	0	0.009	0.110
{8, 20}	0.067	0.037	0.018	-0.038	0.036	-0.002	-0.035	-0.009	0	0.084
{12, 20}	-0.041	-0.068	-0.084	-0.128	-0.070	-0.103	-0.120	-0.110	-0.084	0

• •    Общее количество уникальных состояний, в которых как минимум один игрок совершает ход, превышает 190 000 для игры с пропусками ходов и 40 000 для игры без пропусков.

Рассмотрим для примера состояние в игре без пропусков, где у первого игрока 18 очков, а в арсенале остались тетраэдр и куб (4 и 6), а у второго игрока 14 очков с тетраэдром и икосаэдром (4 и 20). Просчитав все возможные исходы со средними выигрышами для каждой пары стратегий игроков, получим следующую матрицу выигрышей (строки — стратегии первого игрока, стобцы — второго):

Т а б л и ц а 5

Матрица выигрышей первого игрока для приведенного состояния игры

Ходы	4	20	HOLD
4	31 80	227 480	1 2
6	3 - 40	13 64	0
HOLD	39 80	7 16	1

Если рассмотреть данное состояние как статистическую игру (как это и делается при нахождении равновесия, совершенного на подыграх!), то получится, что первый игрок сме-2441

шивает бросок тетраэдра и остановку с шансами — и — соответственно. На что опти-6565

мальной стратегией второго игрока будет смешивание броска тетраэдра и 20-гранника с 1748

шансами — и — соответственно. Читателям предлагается проверить это утверждение са-6565

мостоятельно, воспользовавшись принципами нахождения равновесий Нэша и < выигрышами всех пар стратегий из табл. 5.

Однако такие состояния, в которых приходится обращаться к смешанным । ям, достаточно редки: почти для всех игровых ситуаций равновесие находится стратегиях. Но даже в них равновесные ходы бывают достаточно неинтуитивны.

средними

стратеги-в чистых

4.    Третий вариант игры — скрытый

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

Броски совершаются в таком же порядке - каждый первый бросок осуществляется с помощью двух кубиков, а каждый последующий - с одним. Пропуск хода здесь смысла не имеет, так как информация скрытая.

В данной игре также возможен одновременный перебор, и она, как и предыдущая, является симметричной, так как стратегические возможности для обоих игроков совпадают (при этом пространство стратегического выбора имеет достаточно сложную структуру).

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

Почему игра «в тёмную» оказывается такой сложной? Можно подумать, что она сводится к оптимизации своей стратегии поведения, однако на самом деле в розыгрыше присутствуют содержательные теоретико-игровые аспекты.

Представим себе, что мы играем против «болвана», который не останавливается, пока не получит 21 очко (или не переберёт). Можно посчитать, что такой игрок будет перебирать примерно в 38% случаев. Интуитивно наиболее выгодной стратегией против него будет стратегия, гарантирующая с большей долей вероятности попадание в диапазон 17 — 21 и при этом минимизирующая шанс на перебор.

А если, наоборот, вы играете с «трусом», настолько глупым, что он кидает куб и тетраэдр, после чего всегда останавливается? Тогда стратегия будет немного отличаться от предыдущей: для победы будет достаточно набрать лишь 11 очков, так как соперник физически не наберёт больше 10. Поэтому даже стратегия с нулевым риском перебора будет давать средний выигрыш около 0.98.

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

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

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

Игра сводится к поиску такой стратегии, наилучшим ответом на которую будет она сама - в таком случае, очевидно, средний выигрыш равен 0, и стратегия входит в симметричное равновесие (говоря коротко, является равновесной симметричной стратегией). Запрограммировав поиск стратегии, максимизирующей выигрыш против любой заданной стратегии, мы строим последовательность оптимальных стратегий, которая сойдётся к нашей искомой равновесной.

Основные выводы на базе проведенных вычислений:

• •    В симметричном равновесии первый ход осуществляется броском б и 20, что отличается от рассмотренных ранее последовательных и одновременных вариантов розыгрыша.

• •    Бросок 4 и 20 является вторым по оптимальности и приносит средний выигрыш « —0.014.

• •    Всегда имеет смысл останавливаться при 19 очках и выше.

5.    Заключение

Т а б л и ц а б

Вероятности набрать то или иное значение при игре по оптимальной равновесной стратегии

	F *	F * об. дроби
2	0	0
3	0	0
4	0	0
5	≈0	1 46080
6	й 0,0001	1 9216
7	й 0,0003	1 3072
8	й 0,0008	7 9216
9	й 0,0015	23 15360
10	й 0,0026	121 46080
11	й 0,0042	97 23040
12	й 0,0063	29 4608
13	й 0,0089	409 46080
14	й 0,0119	61 5120
15	й 0,0153	707 46080
16	й 0,0191	293 15360
17	й 0,0293	337 11520
18	й 0,0796	917 11520
19	й 0,2233	343 1536
20	й 0,2095	1609 7680
21	й 0,1619	7459 46080
Перебор	й 0,2254	10387 46080

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

В рамках статьи мы рассмотрели три вариации игры, были написаны программы, сравнивающие средние выигрыши при идеальной игре в зависимости от хода для каждого возможного состояния. Результаты, что ожидаемо, достаточно громоздки для предоставления их в человекочитаемом формате, гораздо проще представлять их через интерфейс для введённого пользователем состояния.

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