Рассчитать вероятность справедливого броска костей (в неэкспоненциальном времени) - PullRequest
Новая
       33

Рассчитать вероятность справедливого броска костей (в неэкспоненциальном времени)

0 голосов
/ 05 июня 2018

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

Простая задача: Рассчитать шансы на бросок n на кубике с осью XY.

Простое решение: Создайте n-арное декартово произведение рулона, суммируйте каждое произведение, подсчитайте, сколько раз сумма является целью, сделайте небольшое деление и вуаля.

Пример простого решения в Go: https://play.golang.org/p/KNUS4YBQC0g

Простое решение отлично работает.Я расширил его, чтобы учесть случаи, такие как отбрасывание высших / низших n граней, и результаты применимы к выборочному тестированию.

Но рассмотрим {Count: 20,Sides: 20,DropHighest: 0,DropLowest:0, Target: 200}.

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

Существует ли более эффективный способ вычисления вероятности для большого количества игральных костей со многими сторонами?Если да, то может ли он объяснить более сложный выбор условий «успеха», таких как сброс некоторых кубиков?

Я уверен, что это возможно благодаря существованию этого прекрасного веб-сайта: https://anydice.com/program/969

РЕДАКТИРОВАТЬ:

Решение, которое работало лучше всего для меня, был ответ Дэвида Эйзенстата, который я перенес: https://play.golang.org/p/cpD51opQf5h

Ответы [ 2 ]

0 голосов
/ 05 июня 2018

Вот некоторый код, который обрабатывает отбрасывание низких и высоких бросков.Извините, что переключился на Python, но мне нужны были легкие бигнумы и библиотека заметок, чтобы сохранить здравомыслие.Я думаю, что сложность что-то вроде O(count^3 sides^2 drop_highest).

Способ работы этого кода состоит в том, чтобы разделить пространство возможностей для броска count кубиков, каждая из которых имеет sides сторон, на то, сколько кубиков показывают максимальное число.(count_showing_max).Есть binomial(count, count_showing_max) способов добиться такого броска на кубиках с уникальной маркировкой, следовательно, multiplier.Учитывая count_showing_max, мы можем выяснить, сколько максимальных костей выпало за то, что они высокие, и сколько выпало за то, что они низкие (так бывает), и добавить эту сумму к результатам для оставшихся костей. 

#!/usr/bin/env python3
import collections
import functools
import math


@functools.lru_cache(maxsize=None)
def binomial(n, k):
    return math.factorial(n) // (math.factorial(k) * math.factorial(n - k))


@functools.lru_cache(maxsize=None)
def outcomes(count, sides, drop_highest, drop_lowest):
    d = collections.Counter()
    if count == 0:
        d[0] = 1
    elif sides == 0:
        pass
    else:
        for count_showing_max in range(count + 1):  # 0..count
            d1 = outcomes(count - count_showing_max, sides - 1,
                          max(drop_highest - count_showing_max, 0),
                          drop_lowest)
            count_showing_max_not_dropped = max(
                min(count_showing_max - drop_highest,
                    count - drop_highest - drop_lowest), 0)
            sum_showing_max = count_showing_max_not_dropped * sides
            multiplier = binomial(count, count_showing_max)
            for k, v in d1.items():
                d[sum_showing_max + k] += multiplier * v
    return d


def main(*args):
    d = outcomes(*args)
    denominator = sum(d.values()) / 100
    for k, v in sorted(d.items()):
        print(k, v / denominator)


if __name__ == '__main__':
    main(5, 6, 2, 2)
0 голосов
/ 05 июня 2018

Вы можете вычислить распределение сумм игральных костей x y, умножив следующий многочлен в переменной Z: 

(Z + Z^2 + ... + Z^x)^y / x^y.

Например, для двух шестигранных костей: 

(Z + Z^2 + ... + Z^6)^2 / 6^2
  = (Z + Z^2 + ... + Z^6) * (Z + Z^2 + ... + Z^6) / 36
  = (Z^2 + 2Z^3 + 3Z^4 + 4Z^5 + 5Z^6 + 6Z^7 + 5Z^8 + 4Z^9 + 3Z^10 + 2Z^11 + Z^12) / 36,

, поэтому вы можете считать вероятность получения суммы 6 как коэффициент Z^6 (5/36).

Для трех "двусторонних" костей: 

(Z + Z^2)^3 / 2^3 = (Z + Z^2) * (Z + Z^2) * (Z + Z^2) / 8
                  = (Z^2 + 2Z^3 + Z^4) (Z + Z^2) / 8
                  = (Z^3 + 3Z^4 + 3Z^5 + Z^6) / 8,

, поэтому вероятность получения суммы 4 равна коэффициенту Z^4 (3/8).

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

package main

import "fmt"

func dieRolls(x, y int) map[int]float64 {
    d := map[int]float64{0: 1.0}
    for i := 0; i < x; i++ {
        d1 := make(map[int]float64)
        for j := 1; j <= y; j++ {
            for k, v := range d {
                d1[k+j] += v / float64(y)
            }
        }
        d = d1
    }
    return d
}

func main() {
    for k, v := range dieRolls(2, 6) {
        fmt.Printf("%d %g\n", k, v)
    }
    fmt.Printf("\n")
    for k, v := range dieRolls(3, 2) {
        fmt.Printf("%d %g\n", k, v)
    }
}

Выполнить код: https://play.golang.org/p/O9fsWy6RZKL

...