22. Бесконечная вероятность

В этой главе

• Проблема бесконечности.

• Матрицы.

• Машины состояний.

• Преобразование машины состояний в матрицу.

• Практические примеры.

Задача бесконечности

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

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

Вот простой пример такой задачи.

Волшебная резиновая лента Морденкайнена

Заклинание первого уровня. Выберите цель. Она получает 1 очко урона. Затем бросьте 1d10. При выпадении цифры 1 или 2 действие заклинания завершается. В противном случае цель получает еще 1 очко урона и вы бросаете кубик еще раз. Кубик нужно бросать таким образом до тех пор, пока не выпадет цифра 1 или 2.

Какой урон в среднем будет наносить это заклинание?

• С вероятностью 20 % это заклинание сразу прекратит действовать и, таким образом, нанесет только 1 очко урона.

• С вероятностью 16 % (80 % × 20 %) это заклинание нанесет +1 очко урона один раз и после этого прекратит действовать, что в целом даст 2 очка урона.

• С вероятностью 12,8 % (80 % × 80 % × 20 %) это заклинание нанесет +1 очко урона два раза и после этого прекратит действовать, что в целом даст 3 очка урона, и т.д.

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

Матрицы

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

.

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

.

Умножение матрицы на вектор-столбец дает в результате еще один вектор-столбец. Для получения каждого элемента результирующего вектора-столбца нужно умножить элементы соответствующей строки матрицы, взятые в направлении слева направо, на элементы вектора-столбца, взятые в направлении сверху вниз, и сложить то, что получилось. В данном случае для получения верхнего элемента результирующего вектора-столбца нужно взять верхнюю строку матрицы (4 5 2) и умножить каждый ее элемент на соответствующий элемент вектора-столбца (x y z). Сложив результаты, получим 4x + 5y + 2z. Для получения других элементов результирующего вектора-столбца нужно сделать то же самое, используя другие строки матрицы:

.

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

.

Это сокращенный способ записи следующей системы уравнений:

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

Машины состояний

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

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

Вот как выглядит диаграмма бесконечной машины состояний в случае волшебной резиновой ленты Морденкайнена (рис. 22.1).

Рис. 22.1

Цифра в круге каждого состояния указывает, какой урон наносит заклинание при достижении этой точки. После обретения конечного состояния нанесенный заклинанием урон равен урону, указанному для того состояния, из которого был выполнен последний переход. Начав с 1 очка урона, мы далее в каждом состоянии имеем 80%-ную вероятность перехода в следующее более высокое состояние и 20%-ную вероятность перехода в конечное состояние. Так продолжается бесконечно (хотя с практической точки зрения вероятности становятся ничтожно малыми через несколько сотен состояний).

Условие перехода между состояниями может определяться не только степенью вероятности. Допустим, вы имеете дело с видеоигрой жанра «стелс». В ней игрок должен передвигаться крадучись, чтобы его не заметили охранники, которые обычно патрулируют, двигаясь по строго заданной траектории. Если охранник замечает что-то необычное (например, слышит шум), он переходит в состояние повышенной бдительности и начинает искать источник шума или других подозрительных явлений. Если в любой момент — в состоянии патрулирования или поиска — игрок попадает в зону прямой видимости охранника, тот переходит в боевой режим и открывает огонь. Если игрок исчезает из поля зрения и достаточно долго остается скрытым, охранник снова переходит к поиску. Если поиск не дает никаких результатов, он вновь переходит в режим патрулирования. Вот как выглядит машина состояний этого охранника (обратите внимание, что здесь нет конечных состояний) (рис. 22.2).

Рис. 22.2

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

Преобразование машины состояний в матрицу

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

Здесь мы начинаем движение из начального состояния 1. На каждом из ходов, выполняемых из состояния 1, происходит переход в состояние 2. Из состояния 2 вы с 50%-ной вероятностью можете перейти либо в состояние 1, либо в состояние 3. Из состояния 3 с вероятностью 1/3 можете перейти в любое из трех состояний, включая само состояние 3. Таким образом, машина продолжает выполнять переходы между этими тремя состояниями до бесконечности.

Рис. 22.3

Эту ситуацию можно смоделировать с помощью матрицы возможных вариантов, каждый столбец которой представляет текущее состояние машины, а каждая строка — состояние, в которое она может перейти при следующей смене состояния. Каждый элемент этой матрицы представляет собой вероятность перехода из текущего состоя­ния (соответствующего номеру столбца) в новое (соответствующее номеру строки):

.

В левом столбце (где текущим является состояние 1) существует нулевая вероятность перехода в состояние 1 или 3 и 100%-ная вероятность перехода в состояние 2 (потому что из состояния 1 машина всегда переходит в состояние 2). В центральном столбце (текущее состояние 2) существует 50%-ная вероятность перехода в состояние 1 или 3 и нулевая вероятность остаться в состоянии 2. В третьем столбце (текущее состояние 3) вы с вероятностью 1/3 можете перейти в любое из трех состояний.

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

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

Чтобы вычислить это, мы должны начать с вектора-столбца, отражающего начальное состояние. В данном случае начальным является состояние 1, то есть мы со 100%-ной вероятностью можем изначально оказаться в состоянии 1 и с нулевой вероятностью — в состоянии 2 или 3 (если бы нам нужно было, чтобы движение начиналось из случайно выбранного состояния, мы могли бы просто использовать исходный вектор-столбец с вероятностями [1/3 1/3 1/3]):

.

Что же мы получим, умножив матрицу на этот вектор-столбец? Матрица указывает, с какой вероятностью можно перейти из каждого состояния в другое состояние. Вектор-столбец указывает, с какой вероятностью мы можем оказаться в том или ином состоянии в данный момент. Соответственно, в результате умножения получим вектор-столбец, элементы которого будут указывать, с какой вероятностью мы можем перейти в то или иное состояние на следующем шаге:

.

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

А каким образом можно определить, что произойдет после второго перехода? Для этого нужно умножить матрицу переходов на вектор-столбец [0 1 0], который мы получили после первого перехода:

.

Здесь опять же нет ничего удивительного. Если известно, что машина находится в состоянии 2, то после этого перехода она с равной долей вероятности может оказаться в состоянии 1 или 3. Но теперь, после двух переходов, мы находимся в неопределенном состоянии — мы больше не можем с уверенностью сказать, в каком состоянии окажется машина. Как же определить, что произойдет после третьего перехода? Вот так:

.

По сути, мы производим взвешивание, умножая вероятность перехода из состояния 1 или 3 на 1/2 (вероятность попадания в эти состояния), и складываем вместе остальные неперекрывающиеся вероятности. То есть здесь нужно сложить половину вероятности перехода из состояния 3 в любое другое состояние, которая равна 1/3 (что составляет 1/6), и половину 100%-ной вероятности перехода из состояния 1 в состояние 2.

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

Оказывается, если выполнять это умножение довольно долго, то после примерно 13 итераций вы получите вектор-столбец [0,3 0,4 0,3], умножение которого на матрицу переходов дает точно такой же результат:

.

Дальнейшее умножение этого вектора-столбца на матрицу переходов не ведет к каким-либо изменениям вероятностей, то есть в итоге получено так называемое установившееся состояние: в долгосрочной перспективе мы в среднем проводим по 30 % времени в состояниях 1 и 3 и 40 % — в состоянии 2. Это весьма интересный результат, к которому вряд ли можно прийти интуитивно, без описанных вычислений. И если эти вероятности будут указывать, сколько времени в среднем проводит в каждом из своих состояний охранник в игре жанра «стелс», то мы сможем скорректировать свои действия для достижения желаемой комбинации состояний.

Важные практические примеры: игра Chutes & Ladders («Спуски и лестницы»)

Хотя только что рассмотренная нами машина состояний представляет собой прекрасный вводный пример такой проблемы, этот случай все же слишком простой и надуманный. Теперь давайте возьмем в качестве примера реальную игру Chutes & Ladders («Спуски и лестницы»). В ней используется игровое поле с клетками, пронумерованными от 1 до 100. Игроки начинают движение из-за пределов игрового поля, перемещаясь на каждом ходе на количество клеток, определяемое броском 1d6. При попадании в клетку, в которой расположен нижний конец лестницы, игрок поднимается по ней вверх. При попадании в клетку, в которой расположен верхний конец спуска, игрок спускается по нему вниз. При попадании в клетку, в которой расположен верхний конец лестницы или нижний конец спуска, ничего не происходит. Игроки делают ходы по очереди. Победителем становится тот, кому удается первым добраться до клетки с номером 100. Попадание в нее должно быть точным: если, к примеру, у игрока, находящегося в клетке 97, выпадет число 4, он останется на том же месте, потратив свой ход впустую. Обычно игровое поле содержит девять лестниц, которые связывают друг с другом клетки 1 и 38, 4 и 14, 9 и 31, 21 и 42, 28 и 84, 36 и 44, 51 и 67, 71 и 91, 80 и 100. Также имеется десять спусков, которые связывают друг с другом клетки 16 и 6, 47 и 26, 49 и 11, 56 и 53, 62 и 19, 64 и 60, 87 и 24, 93 и 73, 95 и 75, 98 и 78.

Если вам приходилось играть в эту игру, то вы, возможно, задавались вопросом: сколько времени должно пройти и сколько ходов должны сделать игроки до достижения победы кем-либо из них? Ведь если каждый игрок будет снова и снова возвращаться по спускам назад, эта игра теоретически может длиться бесконечно. Однако на практике вероятность того, что игра останется незавершенной, становится ничтожно малой после определенного количества ходов. Мы можем проанализировать эту игру, рассматривая ее как конечный автомат, имеющий по одному состоянию на каждую клетку игрового поля и одно стартовое состояние, соответствующее «клетке 0», расположенной за пределами игрового поля.

Сколько состояний имеет наша матрица переходов? Игровое поле состоит из 100 клеток, и к нему нужно добавить одну стартовую клетку, расположенную за пределами игрового поля. Однако следует учесть, что клетки, содержащие нижний конец лестницы или верхний конец спуска, в действительности не представляют собой какого-либо состояния, поскольку игрок не может в них остановиться (он всегда перемещается из такой клетки к другому концу спуска или лестницы). Исключив десять верхних концов спусков и девять нижних концов лестниц, получим 100 + 1 – 10 – 9 = 82 состояния.

Как выглядит наша матрица переходов? Это большая матрица размером 82 × 82. Также это очень разреженная матрица: из любого заданного состояния можно перейти не более чем в шесть других состояний (поскольку игрок бросает 1d6) с вероятностью каждого перехода, равной 1/6. В некоторых случаях существует меньше возможных вариантов: так, в клетке 99 (которой в матрице соответствует состояние 81) вы с вероятностью 5/6 можете остаться на месте и с вероятностью 1/6 перейти в последнюю клетку 100 (состояние 82). После перехода в конечное состояние игрок со 100%-ной вероятностью в нем остается. Все остальные позиции каждого столбца заполнены нулями. В исходном векторе-столбце существует 100%-ная вероятность начать движение из исходного состояния (состояния 1 или клетки 0) и нулевая вероятность — начать движение с любого другого места. Далее мы можем умножить этот исходный вектор на матрицу переходов, чтобы получить вероятности попадания в то или иное состояние после первого хода… а затем умножить этот результат на матрицу переходов, чтобы получить вероятности попадания в то или иное состояние после второго хода… и продолжить этот процесс для довольно большого количества ходов. После этого можем проанализировать полученные векторы-столбцы в совокупности (рис. 22.4).

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

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

Следующим важным моментом является то, на каком ходе вероятность попадания в конечное состояние впервые становится больше чем 0,5, — половина всех игр состоит из меньшего, а половина — из большего количества ходов. Это медианная продолжительность игры. В данном случае медиана составляет 32 хода.

Рис. 22.4

Но что, если мы захотим определить среднюю продолжительность игры? Для этого нужно вероятность завершения игры на каждом конкретном ходе умножить на номер хода и сложить все полученные результаты. Любой отдельный вектор-столбец для того или иного заданного хода не указывает вероятность попадания в то или иное состояние на этом ходе, поскольку вероятности следует рассматривать в совокупности (игрок может попасть в конечное состояние и на этом, и на предыдущем ходе, и десять ходов назад). Однако мы можем определить вероятность перехода в заданное состояние на конкретном ходе, вычтя значение, указанное в векторе-столбце предыдущего хода, из значения, указанного в векторе-столбце этого хода. Если вероятность попадания в конечное состояние на этом ходе составляет 0,476 34, а на предыдущем — 0,463 01, то, отняв одно от другого, можно определить, что вероятность перехода игрока в конечное состояние именно на данном ходе составляет 0,013 33. Поэтому мы должны умножить вероятность перехода на каждом отдельном ходе на номер хода и сложить результаты. Поскольку эта игра теоретически может продолжаться бесконечно, на практике можно просто вычислить результаты для первых нескольких сотен ходов и прекратить добавление новых слагаемых после того, как величина изменения, вносимого ими в конечный результат, станет сравнимой с величиной ошибки округления. В данном случае средняя продолжительность составляет около 35 ходов.

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

Рис. 22.5

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

Что означают полученные нами цифры? Среднее значение здесь намного больше, чем мода и медиана. Это говорит о том, что иногда игра длится очень долго, что обеспечивает высокую среднюю продолжительность, но это случается настолько редко, что не сказывается на моде и медиане.

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

Хотите узнать, что произойдет, если мы добавим, изменим или удалим несколько спусков или лестниц? Просто внесите соответствующие изменения в матрицу переходов. Обычно добавление спусков увеличивает, а добавление лестниц — сокращает длительность игрового процесса, однако так происходит не всегда. Например, добавив спуск, помещающий игрока перед большой лестницей, вы не увеличите, а сократите среднюю продолжительность игры. Можете также для каждого вектора отдельно рассчитать вероятность попадания на тот или иной спуск или лестницу на соответствующем ходе, чтобы определить, какие спуски и лестницы используются наиболее часто, насколько часто и с какой вероятностью они будут задействоваться в любой заданной игре. (Такой анализ особенно полезен в таких играх, как «Монополия», где игрок делает выбор, исходя из того, с какой вероятностью его соперники могут попасть в определенные клетки игрового поля.)

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

Каким же образом можно определить среднее, медианное и модальное количество ходов в многопользовательской игре? Здесь существует два подхода.

Первый подход сводится к тому, чтобы значительно расширить матрицу переходов, отразив в ней все возможные игровые состояния. Если каждый игрок может оказаться в любой из 82 клеток, то в игре с четырьмя участниками это в целом дает 824 состояния. В любой момент времени ход может делать один из четырех игроков, что тоже можно считать состоянием, и, таким образом, реальный размер пространства возможностей игрового поля составляет 4 × 824, или около 180 млн вариантов. Эту цифру можно немного уменьшить, исключив ряд невозможных игровых состояний — попадание в клетку 100 сразу двух игроков, попадание одного из игроков в клетку с большим номером при нахождении остальных игроков в клетке 0 и т.д., но даже после этого она будет оставаться довольно большой. Размер матрицы переходов при этом составит (4 × 824)2, поскольку она представляет собой квадрат, содержащий по одной строке и одному столбцу на каждое состояние. Соответственно, уже только в одной матрице, без учета векторов-столбцов, вам потребуется разместить примерно 32 квадриллиона чисел. Поскольку на данный момент это выходит за рамки возможностей стандартного компьютера, мы должны поискать другой способ.

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

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

«Покер на костях»

В отличие от игры «Спуски и лестницы» такая разновидность игры в кости, как Yahtzee («Покер на костях»), позволяет игрокам принимать решения. В ней игрок бросает пять кубиков d6, после чего может отложить в сторону часть кубиков, цифры на которых его устраивают (или даже все), либо не откладывать ни один из них и перебросить. Затем при желании перебросить кубики можно во второй раз, но после этого полученная комбинация уже не меняется. Игроку могут начисляться очки за множество разных комбинаций, каждую из которых игрок может использовать только один раз. Наибольшее количество очков приносит комбинация «покер» (пять одинаковых цифр), которая является и самой труднодостижимой. Хотя обсуждение того, какая стратегия будет оптимальной в этой игре, выходит за рамки данной главы, давайте рассмотрим одну небольшую вероятностную задачу, представляющую собой подмножество более широкого класса задач. Допустим, что игрок бросает кубики с целью получить пять одинаковых цифр (покер). То есть он игнорирует все другие комбинации, просто стремясь к тому, чтобы после первого броска и двух повторных у него было пять одинаковых цифр. Это означает, что он всегда должен откладывать в сторону те кубики, которые дают в совокупности наибольшее количество одинаковых цифр, и перебрасывать остальные. То есть решение здесь всегда принимается автоматически, исходя из игрового состояния.

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

Комбинация	Вероятность получения этой комбинации после первого броска
A A A A A (покер, пять одинаковых)	6/7776
A A A A B (четыре одинаковых)	150/7776
A A A B B (фулл-хаус)	300/7776
A A A B C (три одинаковых)	1200/7776
A A B B C (две пары)	1800/7776
A A B C D (пара)	3600/7776
A B C D E (без выигрышной комбинации)	720/7776

Как были получены эти числа? Мы подсчитали количество способов получения каждой комбинации и разделили это число на общее количество возможных комбинаций.

• Общее количество возможных комбинаций составляет 65, поскольку здесь независимым образом бросают пять кубиков с шестью сторонами. Каждый кубик выдает один из шести возможных результатов, поэтому всего может быть 6 × 6 × 6 × 6 × 6 = 7776 различных комбинаций. Именно поэтому во всех случаях в знаменателе стоит это число.

• Существуют только шесть способов получения покера. Для этого на всех кубиках должны выпасть одинаковые цифры — 1, 2, 3, 4, 5 или 6.

• В случае комбинации из четырех одинаковых цифр существует шесть различных способов получения этих четырех цифр плюс пять различных способов получения пятой цифры, отличающейся от остальных (6 × 5 = 30). Кроме того, есть пять способов выбора одного из пяти кубиков в качестве отличающегося от остальных, а значит, существует 30 × 5 = 150 способов получения данной комбинации.

• В случае фулл-хауса, как и в случае четырех одинаковых цифр, имеется 30 способов получения цифр A и B, но только 10 способов выбора двух кубиков из пяти в качестве пары (число сочетаний из 5 по 2 = 5! / (2! × 3!) = 10). Это дает нам 30 × 10 = 300 способов получения данной комбинации.

• В случае комбинации из трех одинаковых цифр существует три способа получения этих цифр, пять способов выбора одного из двух оставшихся кубиков и четыре способа выбора последнего кубика, который должен отличаться и от трех одинаковых, и от четвертого кубика, 6 × 5 × 4 = 120. Теперь давайте подсчитаем количество возможных вариантов расположения. Мы имеем здесь пять различных способов выбора кубика с цифрой B и четыре способа выбора последнего кубика с цифрой C (остальные три позиции должны занимать кубики с цифрой A). Это в целом дает 5 × 4 = 20 различных вариантов расположения кубиков. Однако тут следует проявлять осторожность, чтобы не посчитать что-либо дважды. Например, комбинация 3–4–5–3–3, в которой цифра 4 выступает в качестве цифры B, а цифра 5 — в качестве цифры C, и комбинация 3–4–5–3–3, в которой цифра 4 выступает в качестве цифры C, а цифра 5 — в качестве цифры B, на самом деле представляют собой одну и ту же комбинацию, и то же самое верно в отношении других возможных вариантов выбора. Поэтому на самом деле количество возможных комбинаций здесь в два раза меньше, чем кажется на первый взгляд. В итоге имеем 120 × 20 / 2 = 1200 различных способов получения комбинации из трех одинаковых цифр. (К этому результату можно прийти и по-другому. Допустим, цифра B всегда будет больше, чем цифра С, таким образом всегда обеспечивая уникальную конфигурацию. В этом случае имеем (число сочетаний из 5 по 2) = 10 различных способов выбора двух кубиков с разными цифрами, отличающимися от цифры на трех остальных кубиках, где бóльшая из двух цифр — это B.)

• В случае двух пар требуются столь же сложные расчеты и внимательность во избежание двойного подсчета. Допустим, что цифра А первой пары больше цифры В второй пары. Мы выбираем две разные цифры от 1 до 6 в качестве цифр A и B (число сочетаний из 6 по 2 = 6! / (2! × 4!) = 15), после чего у нас остается четыре возможных способа выбора отличающейся от них цифры C, 15 × 4 = 60. Что касается вариантов расположения кубиков с цифрами А, B и C, то сначала мы можем выбрать любой из кубиков в качестве кубика с цифрой C (пять возможных вариантов). Затем из четырех оставшихся нужно выбрать два кубика с цифрой А (число сочетаний из 4 по 2 = 4! / (2! × 2!) = 6), после чего останутся только два кубика с цифрой B, 5 × 6 = 30. Умножив первый результат на второй, будем иметь 60 × 30 = 1800 различных способов получения двух пар.

• В случае одной пары давайте вновь во избежание двойного подсчета допустим, что цифры B, C и D расположены в порядке убывания. В таком случае количество способов получения трех разных цифр B, C и D (B — наибольшая, а D — наименьшая) составляет: число сочетаний из 6 по 3 = 6! / (3! × 3!) = 20, после чего у нас остается три возможных способа получения пары кубиков с цифрой А. В итоге имеем 20 × 3 = 60 различных способов выбора выпадающих на кубиках цифр. Теперь определим количество возможных вариантов расположения этих цифр. Любой из пяти кубиков может быть кубиком с цифрой B, любой из четырех оставшихся — кубиком с цифрой C, и любой из трех оставшихся после этого — кубиком с цифрой D. В результате у нас без каких-либо вариантов останутся два кубика с цифрой А. Итак, 5 × 4 × 3 = 60. Умножив первый результат на второй, получим 60 × 60 = 3600 различных способов получения одной пары.

• Если не выпало ни одной из комбинаций, мы должны выбрать из шести цифр пять разных цифр A, B, C, D и E, где A — наибольшая, а E — наименьшая. Имеем число сочетаний из 6 по 5 = 6! / (5! × 1!) = 6. Теперь подсчитаем количество возможных вариантов расположения. Любой из пяти кубиков может быть кубиком с цифрой A, любой из четырех оставшихся — кубиком с цифрой B, любой из трех оставшихся после этого — кубиком с цифрой C, и любой из двух оставшихся после этого — кубиком с цифрой D. В результате у нас без каких-либо вариантов останется кубик с цифрой Е. Итак, 5 × 4 × 3 × 2 = 120. Умножив первый результат на второй, имеем 6 × 120 = 720 способов бросания кубиков без получения выигрышной комбинации.

• В качестве проверки можно сложить количество вариантов, полученное в каждом случае: 6 (покер) + 150 (четыре одинаковых) + 300 (фулл-хаус) + 1200 (три одинаковых) + 1800 (две пары) + 3600 (пара) + 720 (ни одна из комбинаций) = 7776, то есть в совокупности это действительно равно общему количеству возможных комбинаций. Если бы полученная сумма была больше чем 7776, это означало бы, что в одном или нескольких случаях мы произвели двойной подсчет. Если бы полученная сумма была меньше чем 7776, нам, наоборот, нужно было бы посмотреть, где мы упустили из виду часть возможных вариантов.

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

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

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

.

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

Здесь можно легко определить некоторые другие значения. Так, при переходе из пятого состояния (от комбинации «покер») игрок со 100%-ной вероятностью останется в том же состоянии. Прежде всего это объясняется тем, что, как вы помните, в машине состояний элементы каждого столбца должны в сумме давать 1 (при выполнении каждого перехода существует 100%-ная вероятность перехода в одно и только одно новое состояние — таков принцип работы машины состояний). В пятом столбце все известные элементы равны 0, поэтому оставшийся неизвестный элемент должен быть равен 1. Это имеет и логическое объяснение: если игрок уже получил комбинацию «покер», то он не будет перебрасывать какие-либо кубики и останется с тем, что имеет.

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

Не вызывает больших трудностей и заполнение третьего столбца, который соответствует комбинации из трех одинаковых цифр. Здесь игрок перебрасывает два кубика d6 и, соответственно, может получить 36 разных результатов. При этом только один результат (с вероятностью 1/36) позволяет получить пять одинаковых цифр и таким образом перейти в пятое состояние. В десяти случаях (с вероятностью 10/36) игрок получит одну совпадающую и одну несовпадающую цифры (например, если нужно получить цифру 1, то ее будут содержать следующие десять комбинаций: 1–2, 1–3, 1–4, 1–5, 1–6, 2–1, 3–1, 4–1, 5–1 и 6–1). Вероятность сохранения текущего третьего состояния при этом составит 25/36. Теперь матрица переходов выглядит так:

.

В случае одной пары игрок перебрасывает три кубика d6, а значит, мы должны произвести такие же, но чуть более сложные расчеты.

Определить вероятность совпадения всех трех цифр довольно просто: каждая цифра может оказаться совпадающей с вероятностью 1/6, а значит, вероятность совпадения всех трех цифр равна (1/6)3 = 1/216.

Переход из состояния 2 в состояние 4 может произойти только в том случае, если на двух из трех переброшенных кубиков выпадет такая же цифра, как на первой паре, а на третьем кубике — другая цифра. Соответственно, вероятность получения такой комбинации равна 1/6 × 1/6 × 5/6. Здесь мы имеем три такие комбинации (три способа выбора из трех кубиков одного кубика с несовпадающей цифрой), а значит, итоговая вероятность равна 3 × 1/6 × 1/6 × 5/6 = 15/216.

Переход из состояния 2 в состояние 3 может произойти в двух случаях. Первым случаем является выпадение такой же цифры, как на первой паре, на одном из трех переброшенных кубиков. Вероятность получения этой комбинации равна 1/6 × 5/6 × 5/6, и мы снова должны выполнить умножение на 3, поскольку существует три способа выбора из трех кубиков одного кубика с совпадающей цифрой (или двух кубиков с несовпадающей цифрой), что дает нам вероятность 75/216. Также существует вероятность того, что на всех трех переброшенных кубиках выпадет одинаковая цифра, которая не будет совпадать с цифрой первой пары. Поскольку с цифрой первой пары могут не совпадать пять цифр, вероятность этого составляет 5/216. Сложив обе вероятности, получим: общая вероятность перехода из состояния 2 в состояние 3 составляет 80/216.

Вероятность того, что игрок останется в состоянии 2, можно вычислить напрямую (подсчитав, в каком количестве случаев цифры на переброшенных кубиках не будут совпадать друг с другом и с цифрой исходной пары и в каком количестве случаев две цифры из трех будут составлять новую пару при несовпадении всех трех цифр с цифрой исходной пары), но легче просто вычесть из единицы вероятности всех других переходов: 1 – 1/216 – 15/216 – 80/216 = = 120/216. Таким образом, заполненная матрица переходов будет выглядеть следующим образом:

.

Как при этом будет выглядеть исходный вектор-столбец? С одной стороны, мы можем со 100%-ной вероятностью начать движение из состояния 1 и с нулевой вероятностью — из любого другого места (это можно считать состоянием до первого броска). С другой стороны, можем начать движение из состояния 1 с вероятностью 720/7776, из состояния 2 — с вероятностью 5400/7776, из состояния 3 — с вероятностью 1500/7776, из состояния 4 — с вероятностью 150/7776 и из состояния 5 — с вероятностью 6/7776 (это можно считать состоянием после первого броска).

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

Рис. 22.6

Как оказывается, итоговая вероятность составляет около 4,6 %. Это говорит о том, что, даже если игрок будет стараться получить покер, пренебрегая всеми другими комбинациями, он довольно редко будет достигать этого результата. Вместе с тем он будет довольно часто (примерно в каждом четвертом случае) получать комбинацию из четырех одинаковых цифр и почти в половине случаев — комбинацию из трех одинаковых цифр.

Вы можете продолжить анализ и определить вероятность получения других выигрышных комбинаций, например фулл-хауса или стрита. Также можно перемножить вектор-столбец на матрицу переходов еще несколько раз, чтобы посмотреть, какой эффект мы получим, если разрешим перебрасывать кубики еще несколько раз. Если игрок будет перебрасывать кубики лишь на один раз больше (выполняя в целом четыре броска), вероятность получения покера вырастет более чем вдвое, превысив 10 %. Если будут выполняться 10 бросков, вероятность получения покера впервые превысит 50 %, а значит, 10 — медианное количество бросков, необходимых для получения пяти одинаковых цифр при бросании пяти кубиков d6.

Игра Risk («Риск»)

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

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

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

Сделав это, вы должны получить следующие результаты.

Количество бросков	2d6 (обороняющийся игрок)	1d6 (обороняющийся игрок)
3d6 (атакующий игрок)	Обороняющийся игрок проигрывает оба раза: 2890/7776. Оба игрока проигрывают по одному разу: 2611/7776. Атакующий игрок проигрывает оба раза: 2275/7776	Обороняющийся игрок проигрывает: 855/1296. Атакующий игрок проигрывает: 441/1296
2d6 (атакующий игрок)	Обороняющийся игрок проигрывает оба раза: 295/1296. Оба игрока проигрывают по одному разу: 420/1296. Атакующий игрок проигрывает оба раза: 581/1296	Обороняющийся игрок проигрывает: 125/216. Атакующий игрок проигрывает: 91/216
1d6 (атакующий игрок)	Обороняющийся игрок проигрывает: 55/216. Атакующий игрок проигрывает: 161/216	Обороняющийся игрок проигрывает: 15/36. Атакующий игрок проигрывает: 21/36

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

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

Давайте вспомним, что вычислить вероятность того, что одновременно произойдут два независимых события, можно, перемножив соответствующие вероятности, а вычислить вероятность того, что произойдет хотя бы одно из двух независимых и непересекающихся событий, можно, сложив соответствующие вероятности. Например, чтобы вычислить вероятность того, что атакующий игрок победит, выставив две армии против одной армии обороняющегося, нужно к вероятности того, что победа будет одержана сразу (125/216), добавить вероятность того, что изначально будет потеряна одна армия (91/216), умножив ее на вероятность победы после того, как с каждой стороны останется только по одной армии (15/36). В целом это составляет 125/216 + (91/216)(15/36) = ~0,754.

А какой будет вероятность победы атакующего игрока, если он кинет в бой не две, а три армии против одной армии обороняющегося? Здесь атакующий может победить сразу с вероятностью 855/1296, в противном случае вероятность победы будет равна вероятности победы при выставлении двух армий против одной, которую мы только что вычислили. При выставлении четырех армий против одной с вероятностью 855/1296 может сразу победить атакующий игрок и с вероятностью 441/1296 игра может быть сведена к поединку с тремя армиями против одной (вероятность победы в котором нам еще нужно вычислить).

А что можно сказать о поединке двух армий против двух? Здесь с вероятностью 295/1296 может сразу победить атакующий игрок, с вероятностью 581/1296 — обороняющийся игрок и с вероятностью 420/1296 игра может быть сведена к поединку одной армии против одной (вероятность победы в нем мы уже знаем и можем умно­жить на 420/1296, чтобы получить вероятность победы или поражения в этом случае). Перемножив составляющие каждой цепи событий и сложив полученные результаты, получим, что вероятность победы атакующего игрока в данном случае составляет 295/1296 + (420/1296 × 15/36) = ~0,36. В случае бóльших вероятностей мы должны на каждом этапе определять вероятность победы и сводить игру к более простому случаю, продолжая действовать так до тех пор, пока не будет достигнут случай с известными значениями (например, поединок двух армий против одной или одной против одной). Если вы в какой-то степени знакомы с теорией вычислительных машин, то, вероятно, поняли, что здесь мы имеем дело с рекурсией (многократным повторением некоторого процесса с передачей результата одной итерации на вход следующей). Например, какой будет вероятность победы атакующего игрока, если он выставит семь армий против пяти армий обороняющегося? Здесь с вероятностью 2890/7776 обороняющийся игрок может потерять две армии (что сведет игру к поединку семи атакующих армий с тремя обороняющимися), с вероятностью 2611/7776 оба игрока могут потерять по одной армии (что сведет игру к поединку шести армий против четырех) и с вероятностью 2275/7776 две армии может потерять атакующий игрок (что сведет игру к поединку пяти армий против пяти). Далее мы можем выразить каждую из этих вероятностей в вероятностях менее сложных случаев, вплоть до базового, вероятность которого нам уже известна (рис. 22.7). (Следует заметить: поскольку при каждом броске кубиков игроки теряют две армии, они просто не могут оказаться в некоторых ситуациях, таких, например, как поединок семи армий против четырех.)

Рис. 22.7

Выполнить эти расчеты проще всего в электронной таблице. Мы знаем, что в самом простом случае (одна армия против одной) вероятность победы составляет 15/36. Чтобы получить любую другую вероятность, нужно умножить вероятность выпадения того или иного результата на ячейку, содержащую этот результат. Так, если ячейка A1 будет представлять случай с одной армией против одной, а ячейка B1 — случай с одной атакующей армией против двух обороняющихся, то вероятность победы во втором случае составит 55/216 × A1. Если ячейка A2 будет представлять случай с двумя атакующими армиями против одной обороняющейся, то вероятность победы атакующего игрока составит 125/216 + (91/216 × A1). Если ячейка B2 будет представлять случай с двумя атакующими армиями против двух обороняющихся, то вероятность победы атакующего игрока составит 295/1296 + (420/1296 × A1). Если ячейка E7 будет представлять случай с семью атакующими армиями против пяти обороняющихся, то вероятность победы составит (2890/7776 × C7) + (2611/7776 × D6) + (2275/7776 × E5) и т.д. После заполнения первых нескольких строк и столбцов можно заполнить остальную часть таблицы с помощью функции автозаполнения, продублировав вниз и вправо универсальную формулу из ячейки B3 (отражающую случай с тремя атакующими армиями против трех обороняющихся).

Данная таблица показывает вероятность победы вплоть до случая с десятью армиями против десяти, при этом выделены ячейки, в которых вероятность победы атакующего игрока составляет не менее 50 %. Из этих данных можно сделать ряд интересных выводов. При равном количестве атакующих и обороняющихся армий обороняющийся игрок имеет преимущество вплоть до случая с четырьмя армиями против четырех, так как он получает преимущество при ничейном результате. Но, начиная со случая с пятью армиями против пяти, преимуществом обладает уже атакующий игрок, поскольку он получает небольшое преимущество при бросании трех кубиков против двух и оно становится преобладающим, если кубики бросают много раз. На самом деле, расширив эти данные до случая с 20 армиями против 20, мы можем увидеть, что начиная с определенного момента атакующий игрок будет иметь преимущество даже при небольшом численном превосходстве противника (например, в случае с 17 атакующими армиями против 19 обороняющихся)! В целом можно сказать, что чем больше будет армий на игровом поле, тем больше шансов на успех у атакующего игрока.

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

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

Как геймдизайнеры, мы также можем заметить, как используемая в игре «Риск» механика боев сказывается на игровом процессе. В небольших сражениях шансов на успех, как правило, больше у обороняющегося игрока, а в боях с большим количеством армий — у атакующего. Это означает, что в начале игры, когда у каждого из геймеров еще сравнительно немного армий, доминирующей стратегией является оборона, что побуждает их к тому, чтобы захватить небольшую область (многие стараются захватить Южную Америку или Австралию, поскольку это позволяет оборонять сравнительно небольшое количество границ) и постараться удержаться на ней с расчетом на то, что бонусы за удержание континента позволят получить преимущество на более поздних этапах игры. Однако по мере того, как игроки получают большое количество дополнительных армий в качестве бонуса за континенты и карты, преимущество переходит к атакующему — эта положительная петля обратной связи позволяет привести игру к завершению даже в том случае, когда каждый игрок использует оптимальную стратегию.

Вопросы для обсуждения

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

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

3. К матрице переходов, созданной в качестве ответа на предыдущий вопрос, примените цепь Маркова и определите, с какой вероятностью игрок может оказаться в том или ином состоянии с течением времени. Особое внимание обратите на такие вопросы: достигает ли ваш конечный автомат установившегося состояния, и если да, то когда; в какой момент вероятность достижения конечного состояния впервые превышает 50 %?

4. Рассмотрите игру, в которой вы делаете ставку 1 доллар и подбрасываете «честную» монету. При выпадении орла вы теряете ставку. При выпадении решки ставка увеличивается в три раза, вы можете либо выйти из игры (сохранив свою ставку), либо подбросить монету еще раз. Монету можно подбрасывать как один, так и бесконечное количество раз. Смоделируйте это с помощью бесконечной машины состояний.

5. Примените цепь Маркова к игре из предыдущего вопроса и определите, на какой выигрыш в ней можно рассчитывать. Что происходит по мере увеличения количества попыток подбрасывания монеты?

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

7. Подумайте о том, в какой из игр, в которые вам приходилось играть, присутствует хотя бы одна система или один механизм, которые можно проанализировать с помощью описанных в этой главе методов. Что это за игра?

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

9. Смоделируйте задачу из предыдущего вопроса с помощью машины состояний или матрицы переходов.

10. Решите задачу и найдите ответ, используя инструменты из предыдущего вопроса.

Побочные квесты

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

Побочный квест 22.1. Игра «Гроза»

«Гроза» — это традиционная немецкая детская игра с кубиками. В своей исходной версии она представляет собой следующее.

• Количество игроков: два или больше, верхнего предела нет.

• Цель: оказаться последним оставшимся в игре участником.

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

• На первом ходе игрок бросает все шесть кубиков d6 (на последующих ходах можно бросать меньшее количество). После этого:

• если как минимум на одном из брошенных кубиков выпадает цифра 1, то все кубики с цифрой 1 откладываются в сторону, а остальные передаются следующему игроку;

• если цифра 1 выпадает на всех кубиках, то следующему игроку передаются все брошенные кубики и все кубики, которые были отложены в сторону ранее. Следующий игрок бросает все шесть кубиков;

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

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

Возможно, вас интересует, сколько может длиться одна такая игра?

Допустим, что речь идет об однопользовательской версии игры. Продолжайте играть, пока не получите шесть страйков. Итоговым результатом игрока при этом будет общее количество бросков, сделанных им до выхода из игры. Применяя цепь Маркова, определите среднее, медианное и модальное значения результата для одного игрока. Это можно смоделировать в виде машины состояний, в которой каждое состояние является уникальной комбинацией количества полученных игроком страйков (от 0 до 5) и количества бросаемых кубиков (от 1 до 6), а также имеется одно конечное состояние (где уже получены шесть страйков и количество кубиков не имеет значения, потому что игра завершена).

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

Теперь давайте сделаем упрощающее допущение о том, что в многопользовательской версии игры страйк с равной вероятностью могут получить все игроки (на самом деле это не так, поскольку первый игрок бросает 6d6 на первом ходе, что делает получение страйка менее вероятным, чем для игроков, совершающих свой ход после него). Каждый из игроков накапливает страйки вплоть до выхода из игры, поэтому общее количество страйков в случае, когда в игре участвуют N игроков, будет находиться в диапазоне от 6 × (N – 1) до 6 × (N – 1) + 5, потому что все вышедшие из игры игроки получат по шесть страйков, а единственный победитель — от нуля до пяти страйков. Исходя из этого диапазона, определите, в каком диапазоне будет находиться среднее количество выполняемых бросков.

Более объемная задача. Немного усложните описанную ранее дополнительную задачу: используя любой метод, определите ожидаемое количество страйков для того случая, когда в игре участвуют N игроков. Умножьте это количество на вероятность получения страйка в установившемся состоянии, чтобы найти ожидаемое количество ходов в игре, выраженное относительно количества игроков N.

Задача-максимум. Определите, насколько более или менее выгодным является положение первого игрока в игре с двумя игроками. Здесь потребуется рассмотреть не только получаемое в итоге установившееся состояние, но и броски, выполняемые до перехода в него. В цепи Маркова рассчитайте вероятность получения страйка для всех четных и нечетных ходов, отслеживая ожидаемое количество страйков, накопленных каждым игроком. Кто из игроков первым превысит порог 50%-ной вероятности проигрыша? Проанализируйте таким же образом версии игры с тремя, четырьмя, пятью и бóльшим количеством игроков. Нет ли закономерности в том, какая позиция игрока в очередности выполнения ходов наиболее или наименее выгодна?

Побочный квест 22.2. Игра Hi Ho! Chery-O («Вишни»)

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

• Игроки: два или более.

• Цель: стать первым игроком, набравшим 10 или более очков.

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

• Игровой процесс: при выполнении хода каждый игрок вращает спиннер, выдающий один из семи равновероятных результатов (что равносильно бросанию одного кубика d7). Результаты включают в себя следующее: получение 1, 2, 3 или 4 очков; потеря 1 или 2 очков; сброс набранных очков до 0.

Сначала рассмотрим случай с одним игроком. Такую игру можно смоделировать в виде машины состояний с 11 состояниями (состояния с количеством очков от 0 до 9 плюс конечное состояние, где игрок может иметь 10 или больше очков). С помощью цепи Маркова вычислите среднюю, медианную и модальную продолжительность игры, выраженную в количестве ходов. Постройте кривую вероятностей, откладывая по оси Y вероятность завершения игры, а по оси X — соответствующее количество ходов вплоть до 100.

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

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

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

Какой из этих двух методов оказался более простым? Что было для вас сложнее — настраивать вероятности или изменять саму механику?

Побочный квест 22.3. Волшебная резиновая лента Морденкайнена

Рассмотрите волшебное заклинание, о котором мы говорили в начале этой главы: оно наносит 1 очко урона с 80%-ной вероятностью нанесения + 1 очка урона (что может повторяться до тех пор, пока игрок не бросит кубик неудачно). Вычислите ожидаемый урон, наносимый этим заклинанием, используя цепь Маркова. Поскольку здесь вы имеете дело с бесконечной машиной состояний, рассмотрите только первую пару сотен состояний (после этого величина вносимых изменений становится сравнимой с величиной ошибки округления).

Чтобы убедиться в правильности полученного ответа, проведите те же расчеты еще раз с помощью симуляции Монте-Карло.

Дополнительная задача. Здесь можно использовать и алгебраический подход. Данный случай можно смоделировать как последовательность вероятностей, где количество урона Dn = 1 + 0,8Dn + 1. Поскольку в данном конкретном случае это верно для каждого состояния (каждое состояние является таким же, как все остальные), Dn = Dn + 1, мы можем привести уравнение к следующему виду: D = 1 + 0,8D. Определите количество урона, решив это простое уравнение, и убедитесь, что оно дает тот же результат, что и два других упомянутых ранее метода.

Побочный квест 22.4. Игра Kill the Elf («Убить эльфа») в виде машины состояний

В главе 17 мы уже говорили об игре с названием «Убить эльфа». Это игра для двух участников. Один игрок (воин) наносит 1 очко урона за один ход, а другой (волшебник) бросает 1d6 и с вероятностью 1/6 наносит 6 очков урона за один ход или с вероятностью 5/6 не наносит никакого урона. Хотя в долгосрочной перспективе оба персонажа в среднем наносят одинаковый урон за ход, как показывает практика, в краткосрочной перспективе при игре до 6 очков урона гораздо чаще побеждает волшебник. В задаче 17.2 вас просили определить вероятность победы в случае, когда для победы нужно нанести 4 или 10 очков урона. Но что, если мы захотим узнать, какой урон обеспечивает воину и волшебнику максимально равные шансы на успех среди любых значений из диапазона от 1 до 1000? Если для ответа на этот вопрос использовать только стандартные инструменты для работы с вероятностью, то решение очень быстро станет слишком громоздким.

Однако мы можем смоделировать его в виде машины состояний, каждое состоя­ние которой представляет некоторое количество побед волшебника (рис. 22.8).

Рис. 22.8

Это дает нам довольно простую матрицу переходов. Постройте ее и используйте начальный вектор-столбец, в котором вероятность нахождения игрока в состоянии 0 равна 1. Затем, применяя цепь Маркова, можно определить вероятность нахождения игрока в том или ином состоянии для любого количества ходов (а умножив на 6, также можно получить текущее количество нанесенного урона). Для любого заданного хода можно определить вероятность нанесения того или иного урона (исходя из того, что на ходе n воин успевает нанести ровно n очков урона).

Какие тенденции наблюдаются по мере увеличения необходимого урона? Какое значение из диапазона от 1 до 1000 обеспечивает воину и волшебнику максимально равные шансы на успех (то есть при каком значении ожидаемая вероятность победы волшебника будет наиболее близка к 50 %)?

Побочный квест 22.5. «Конные скачки», точное решение

В главе 17 мы также говорили об игре «Конные скачки», в которой два игрока пытаются опередить друг друга, бросая 50d6. В задаче 17.3 требовалось рассчитать вероятность победы каждого из игроков для случая, когда на первом броске у одного игрока выпадает цифра 1, а у второго — 6. В этой задаче предлагалось приблизительно определить вероятность с помощью симуляции Монте-Карло, поскольку, как было упомянуто, найти точное решение с помощью расчетов довольно сложно.

Теперь мы можем смоделировать «Конные скачки» в виде конечного автомата, где состояние представляет собой разность между количеством очков, набранным первым и вторым игроками (возможны состояния с отрицательным значением!). Исходным является состояние со значением 5 (потому что на первом броске один игрок набирает 6 очков, а другой — 1 очко). В зависимости от получаемого результата на каждом последующем броске изменение состояния может составить от –5 до +5 (поскольку на каждом ходе может выпасть только 36 различных комбинаций, здесь довольно просто рассчитать вероятность каждого из возможных переходов между состояниями). В любой момент положительное состояние озна­чает, что выигрывает игрок, выбросивший 6 на первом броске, отрицательное состояние означает, что выигрывает игрок, выбросивший 1 на первом броске, а состояние с нулевым значением говорит о том, что на текущий момент получен ничейный результат.

Поскольку мы имеем здесь 50 ходов (согласно условию задачи первый ход переводит нас в состояние со значением 5), состояние после того, как все они будут сделаны, может находиться в диапазоне от –240 до 250, что в общей сложности составляет 491 состояние. Хотя мы, в принципе, можем выполнить соответствующие расчеты в электронной таблице, это потребует слишком больших усилий. Вместо этого рассмотрим более простой случай — игру с десятью ходами, в которой состояния варьируются от –40 до 50, что в целом составляет 91 состояние. Используя цепь Маркова, определите, с какой вероятностью после каждого хода будет выигрывать игрок, выбросивший 6 на первом броске (то есть будет получено состояние с положительным значением). Постройте соответствующий график, откладывая по оси Y вероятность победы, а по оси X — количество ходов от 1 до 10 (при этом вероятность победы после первого хода будет равна 1, поскольку мы имеем здесь жестко заданный результат — состояние со значением 5).

Какую закономерность вы смогли заметить на графике? Как, на ваш взгляд, изменится характер этой зависимости, если игроки будут выполнять по 50, 100 или 500 ходов?

Побочный квест 22.6. Две карты подряд

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

Хотя здесь можно использовать метод грубой силы (то есть метод перебора), если бы мы имели дело с большим количеством карт (например, если бы речь шла о пяти картах подряд в полной колоде из 26 черных и 26 красных карт), то расчеты очень быстро стали бы слишком громоздкими — поначалу кажется, что это легко, но после того, как вы попробуете решить эту задачу обычными методами, начинает казаться, что это невозможно. К счастью, ее можно смоделировать и в виде машины состояний!

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

В качестве первой карты мы можем вытянуть либо черную карту (с вероят­ностью 3/6) с переходом в состояние (2, 3, 1), либо красную карту (с веро­ятностью 3/6) с переходом в состояние (3, 2, 0). В состоянии (2, 3, 1) можно с вероятностью 2/5 вытянуть вторую черную карту и перейти в состояние (1, 3, 2), которое является конечным, потому что вне зависимости от того, какие карты будут вытянуты в дальнейшем, мы уже имеем две идущие подряд черные карты. С вероятностью 3/5 здесь также можно вытянуть красную карту после первой черной и перейти в состояние (2, 2, 0). Таким образом, часть диаграммы состояний будет выглядеть следующим образом (рис. 22.9).

Рис. 22.9

Вы можете расширить эту диаграмму состояний, включив в нее все возможные варианты. Затем определите вероятность достижения каждого конечного состояния как минимум с двумя идущими подряд черными картами, перемножив вероятности всех ведущих в это состояние событий (например, в данном случае вероятность достижения состояния (1, 3, 2) составляет 3/6 × 2/5 = 1/5). Сложив вероятности всех таких конечных состояний, вы получите общую вероятность вытягивания как минимум двух идущих подряд черных карт.

А как это можно смоделировать в электронной таблице? Поскольку первое число может находиться в диапазоне от 0 до 3, второе число — в диапазоне от 0 до 3 и третье число — в диапазоне от 0 до 2, здесь не более чем 4 × 4 × 3 = 192 состояния. Мы можем просто присвоить каждому из них трехзначный номер (исходному состоянию будет присвоен номер 330).

Для большей эффективности можно трем числам (a, b, c) поставить в соответствие номер состояния, вычисляемый по формуле 12a + 3b + c, который будет уникальным для любой допустимой комбинации чисел. (Мы могли бы добиться еще большей эффективности, приняв во внимание тот факт, что такие состояния, как (3, 3, 3), недостижимы, но, поскольку в итоге получаем довольно небольшое число, это пока можно не учитывать.) Как и в приведенном в этой главе практическом примере с игрой «Риск», каждое состояние (a, b, 2) для любых чисел a и b считается положительным конечным состоянием, и мы можем вычислить вероятность его достижения, вернувшись в предыдущее состояние (a + 1, b, 1). Любое состояние (m, n, 1) может быть достигнуто из состояния (m + 1, n, 0). Любое состояние (x, y, 0) может быть достигнуто из состояния (x, y + 1, 0) или (x, y + 1, 1). Двигаясь рекурсивно, вы в итоге вернетесь в состояние (3, 3, 0), пройдя по всем переходам. Умножая вероятность каждого состояния на вероятность перехода в него из предыдущего состояния — вероятность вытягивания черной карты в состоянии (черные, красные, серия), которая равна черные/(черные + красные), или вероятность вытягивания красной карты, которая равна красные/(черные + красные), — вы можете определить вероятность перехода из любой точки в любое заданное состояние. Сложив вероятности достижения всех конечных состояний, в которых серия = 2, вы получите искомую вероятность.

Задача-максимум (требует навыков программирования). Игрок садится за стол для блек-джека, где карты раздаются из «шуза», включающего в себя восемь колод, то есть из набора карт, содержащего 32 туза, 128 десятиочковых карт (десяток, валетов, дам и королей) и 256 мелких карт (номерных карт от 2 до 9). Допустим, что тасование производится честным и абсолютно случайным образом и при раздаче используются все карты «шуза». Какова вероятность того, что в определенный момент из колоды будут вытянуты десять десятиочковых карт подряд?

(Поскольку здесь важно лишь то, является ли карта десятиочковой, данной задаче равносильна следующая: допустим, что у вас есть строка из 416 компьютерных битов — единиц или нулей, 128 из которых являются единицами, а оставшиеся 288 — нулями. Биты расположены в случайном порядке. Какова вероятность того, что в этой строке имеется хотя бы один участок с 10 или бóльшим количеством идущих подряд единиц?)

От предыдущей задачи данная отличается лишь тем, что здесь вместо состояния (3, 3, 0) исходным является состояние (128, 256, 0), а конечными — состояния с непрерывной серией из десяти, а не двух элементов. В данном случае имеем около 400 000 возможных состояний — слишком много для того, чтобы их можно было пронумеровать с помощью нарисованной вручную диаграммы состояний. Заполнение электронной таблицы тоже потребует больших усилий, если только вам не удастся найти способ, позволяющий заполнять ячейки автоматически. В то же время данная задача вполне решаема, если использовать для этого программный код с рекурсивными вызовами функций.

---