Битва роботов, вероятности

[Belsagor]

Здравствуйте. Помогите разобраться.

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

Решение.
Почитал в интернете как можно решать подобную задачу, нашел подходящий, по моему, вариант, Цепями Маркова. Обозначим роботов индексами $_{a}$ и $_{b}$. Предположим, первый робот имеет параметры: 4, 0.5, 1. Второй: 5, 0.4, 1. Считаем для первого робота. Составляем матрицу переходов:

$$\[P_{a} = \left( {\begin{array}{*{20}{c}} {0.5} & {0.5} & 0 & 0 & 0 \\ 0 & {0.5} & {0.5} & 0 & 0 \\ 0 & 0 & {0.5} & {0.5} & 0 \\ 0 & 0 & 0 & {0.5} & {0.5} \\ 0 & 0 & 0 & 0 & {1} \\ \end{array}} \right)\]$$

Матрица начального состояния: $p_{a0}=(1\ 0\ 0\ 0\ 0)$
Считаем для каждого раунда:
$p_{a1}=p_{a0} P_{a}=(0.5\ 0.5\ 0\ 0\ 0)$
$p_{a2}=p_{a1} P_{a}=(0.25\ 0.5\ 0.25\ 0\ 0)$
И т.д., но отсюда нас интересует только последний столбик, а именно вероятность победы в этом раунде. Далее записал эти значения в массив для 16 раундов:
$p_{av}=(0.000\ 0.000\ 0.000\ 0.063\ 0.188\ 0.344\ 0.5\ 0.637\ 0.746\ 0.828\ 0.887\ 0.927\ 0.954\ 0.971\ 0.982\ 0.989)$
Аналогично считаем для второго робота:

$$\[P_{b} = \left( {\begin{array}{*{20}{c}} {0.6} & {0.4} & 0 & 0 \\ 0 & {0.6} & {0.4} & 0 \\ 0 & 0 & {0.6} & {0.4} \\ 0 & 0 & 0 & 1 \\ \end{array}} \right)\]$$

$p_{b0}=(1\ 0\ 0\ 0)$
$p_{bv}=(0.000\ 0.000\ 0.064\ 0.179\ 0.137\ 0.456\ 0.580\ 0.685\ 0.768\ 0.833\ 0.881\ 0.917\ 0.942\ 0.960\ 0.973\ 0.982)$

Вопрос 1. Это правильно?
Вопрос 2. Может быть есть проще способ рассчитать эти вероятности?

Далее считаем вероятности ничьей в каждом раунде, поэлементно умножая вероятности:
$p_{aw}=p_{bw}=(0.000\ 0.000\ 0.000\ 0.011\ 0.026\ 0.157\ 0.290\ 0.436\ 0.573\ 0.690\ 0.781\ 0.850\ 0.899\ 0.932\ 0.955\ 0.971)$

Пересчитываем вероятности победы только одного робота, для каждого раунда, вычитая вероятность ничьей:
$p_{av}=(0.000\ 0.000\ 0.000\ 0.052\ 0.162\ 0.187\ 0.210\ 0.201\ 0.173\ 0.138\ 0.106\ 0.077\ 0.055\ 0.039\ 0.027\ 0.018)$
$p_{bv}=(0.000\ 0.000\ 0.064\ 0.168\ 0.111\ 0.299\ 0.290\ 0.249\ 0.195\ 0.143\ 0.100\ 0.067\ 0.043\ 0.028\ 0.018\ 0.011)$

Считаем вероятность, что бой продолжается:
$p_{au}=p_{bu}==(1.000\ 1.000\ 0.936\ 0.769\ 0.701\ 0.357\ 0.210\ 0.114\ 0.059\ 0.029\ 0.013\ 0.006\ 0.003\ 0.001\ 0.000\ 0.000)$

Вопрос 3. Это правильно?
Вопрос 4. Теперь, как получить вероятность победы каждого робота в бою, в целом?
Вопрос 5. Есть ли формула или алгоритм сразу получить массивы вероятностей, для произвольных параметров роботов?

[DmitriyMB]

Перемножь вышеуказанные параметры и будет тебе счастье

[Belsagor]

DmitriyMB в сообщении #325347 писал(а):

Перемножь вышеуказанные параметры и будет тебе счастье

Если перемножить параметры роботов получится 2 и 2, т. е. шансы каждого победить 50% и ничья невозможна, но это не правильно. Или нужно перемножать что-то другое?

[gris]

Задача интересная, хотя и упрощённая. В реальности наносимый урон и вероятность попадания зависят от здоровья, причём обоих роботов. Тогда есть смысл строить матрицу переходов сразу для двух роботов. То есть матрицу $30\times 30$, $\big((5+1)\cdot (4+1)\big)^2$.

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

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

[Belsagor]

gris спасибо за ответ.

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

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

Да, задачу, для начала существенно упростил. В реальной ситуации, всё сложнее. Здоровье роботов может быть трехзначным числом. Другие параметры от него не зависят, это условный показатель. Возможно, со временем введу зависимость попадания и урона от здоровья, если игроки не будут против, но сейчас этого нет. Вероятность попадания константа на время боя. Наносимый урон, это случайная, в определенных пределах, величина, например (8-20). Кроме того, может быть битва не только один на один.

Вариант построить общую матрицу, интересен. Не могу понять как её заполнять. Ведь получается две цепи. Или нужно построить отдельно, а потом перемножить?

И еще вопрос, правильно ли я в первом сообщении рассчитал вероятности для каждого раунда? И нет ли алгоритма или формулы попроще?

[gris]

Я имел в виду построение пространства состояний в виде матрицы $M=(k;l), 0\leqslant k\leqslant m;0\leqslant l\leqslant n$, где $(k;l)$ - текущее здоровье каждого робота. Для каждой точки этого пространства существует матрица $P(m+1;n+1)$ перехода в другие точки. В Вашем случае она почти вся состоит из нулей, так как вероятность убить противника со здоровьем, большим 1 сразу, у Вас равна 0. И вероятности не меняются от точки к точке.

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

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