计算公平掷骰子的概率(在非指数时间内)
Calculate probability of a fair dice roll (in non-exponential time)
这个问题的变体是很常见的问题,但我所有的 google-fu 都让我感到困惑。我想计算一次公平掷骰的几率,但我想高效。有很多关于如何执行此操作的示例,但我发现的所有算法在计算上都过于昂贵(指数时间),无法处理大量多面骰子。
简单问题: 计算在 x y 面骰子上掷 n 的几率。
简单的解决方案:创建roll的n元笛卡尔积,对每个积求和,计算和为目标的次数,做一点除法和瞧。
Go 中的简单解决方案示例: https://play.golang.org/p/KNUS4YBQC0g
简单的解决方案非常有效。我扩展了它以允许像删除 highest/lowest n 个面这样的情况,结果经得起现场测试。
但考虑 {Count: 20,Sides: 20,DropHighest: 0,DropLowest:0, Target: 200}
.
如果我用之前的解决方案对其进行评估,我的 "table" 将有 104 个奇怪的 septillion 单元格,并且很容易将 CPU 最大化。
有没有更有效的方法来计算大量多面骰子的概率?如果是这样,它能否解释更复杂的 "success" 条件选择,例如掷一些骰子?
由于这个美丽的网站的存在,我相信这是可能的:https://anydice.com/program/969
编辑:
最适合我的解决方案是 David Eisenstat 的回答,我将其移植到:https://play.golang.org/p/cpD51opQf5h
您可以通过在变量 Z
中乘以以下多项式来计算 x
y
面骰子总和的分布:
(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
) 的系数。
三个 "two-sided" 骰子:
(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)
}
}
这里有一些代码可以处理掉落的低赌注和高赌注。抱歉切换到 Python,但我需要简单的 bignums 和记忆库来保持理智。我认为复杂度类似于 O(count^3 sides^2 drop_highest)
.
此代码的工作方式是将每个具有 sides
面的 count
骰子的 space 可能性除以显示最大数字的骰子数量(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)
这个问题的变体是很常见的问题,但我所有的 google-fu 都让我感到困惑。我想计算一次公平掷骰的几率,但我想高效。有很多关于如何执行此操作的示例,但我发现的所有算法在计算上都过于昂贵(指数时间),无法处理大量多面骰子。
简单问题: 计算在 x y 面骰子上掷 n 的几率。
简单的解决方案:创建roll的n元笛卡尔积,对每个积求和,计算和为目标的次数,做一点除法和瞧。
Go 中的简单解决方案示例: https://play.golang.org/p/KNUS4YBQC0g
简单的解决方案非常有效。我扩展了它以允许像删除 highest/lowest n 个面这样的情况,结果经得起现场测试。
但考虑 {Count: 20,Sides: 20,DropHighest: 0,DropLowest:0, Target: 200}
.
如果我用之前的解决方案对其进行评估,我的 "table" 将有 104 个奇怪的 septillion 单元格,并且很容易将 CPU 最大化。
有没有更有效的方法来计算大量多面骰子的概率?如果是这样,它能否解释更复杂的 "success" 条件选择,例如掷一些骰子?
由于这个美丽的网站的存在,我相信这是可能的:https://anydice.com/program/969
编辑:
最适合我的解决方案是 David Eisenstat 的回答,我将其移植到:https://play.golang.org/p/cpD51opQf5h
您可以通过在变量 Z
中乘以以下多项式来计算 x
y
面骰子总和的分布:
(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
) 的系数。
三个 "two-sided" 骰子:
(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)
}
}
这里有一些代码可以处理掉落的低赌注和高赌注。抱歉切换到 Python,但我需要简单的 bignums 和记忆库来保持理智。我认为复杂度类似于 O(count^3 sides^2 drop_highest)
.
此代码的工作方式是将每个具有 sides
面的 count
骰子的 space 可能性除以显示最大数字的骰子数量(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)