algorithm - 将 if-then-else 映射到概率

Question

我需要一种算法来将游戏规则(p&p 角色扮演)转换为概率，特别是从 if-then-else 构建的条件结构，条件由 bool 值(not、and、or)和关系运算符(==、> =,<=,<,>) 和掷骰子以及 bool 值。

例子:

var a = diceRoll(d8,d10,d12) // a shaker full of dices
                             // a 8 sides, a 10 sided and a 12 sided dice
                             // values added together
var w = true
var result = (
  if (a>=20) then 10.3994
  else if (a>=14 and w) then 8.23
  else if (a>=8 and diceRoll(d6)>3) then 5.22
  else 0
)

应该以编程方式转换为预期平均结果的公式，例如

var result = diceProbabilityGreaterThan(a,20)*10.3994 
+(diceProbabilityGreaterThan(a,14)-diceProbabilityGreaterThan(a,20))*8.23 
+ ..

我知道如何将单个 diceRoll 上的单个关系运算符映射到概率 (diceProbabilityGreaterThan)，并且我知道如何手动转换这个特定的简单示例，但我无法找到任何给定的通用转换方案规则。对我来说，这个问题的难点在于相关概率(比如 a>20 ... a>10)。

更多背景:

• 我知道我可以使用蒙特卡洛方法，但我试过了，结果是对于我的用例来说太慢了。
• 规则是现成的数据结构，所以不需要解析。
• 骰子可能会爆炸，意思是 6落在 6 上的单面骰子将再次滚动并相加，因此最大振动器结果不受有限数限制。
• 规则不包含 while 或 for 之类的循环控制结构，它们只是形成一个可能嵌套的 if-then-else-tree。
• 中的 bool 值和数值条件是常数。
• 解决方案可以仅限于一个依赖概率变量(如示例中的 a)，但我是也对任何数字的通用解决方案的存在感兴趣因变量。

这个问题是 https://math.stackexchange.com/questions/842458/map-if-then-else-to-probability 的克隆问题因为它在那里被标记为离题。

Answer 1

您想要的是计算函数的期望值。这可以递归完成。

我假设您拥有树状数据结构中的规则。然后初始调用将只是 root.CalculateExpectedValue()。

节点分为三种:

1. 叶节点(指定实际值)。 CalculateExpectedValue() 应该为叶节点返回这个值。
2. 变量定义。这些节点有一个子节点并返回 child.CalculateExpectedValue()。但是，他们必须引入变量声明及其概率质量函数。所有事件变量的概率质量函数必须作为参数传递给 CalculateExpectedValue()。有关以下概率质量函数的更多信息。
3. 决定。这些节点有两个 child 。给定主动变量的概率质量函数，可以计算这两种情况的概率。那么这些节点应该返回 p * trueChild.CalculateExpectedValue() + (1 - p) * falseChild.CalculateExpectedValue()。此外，他们必须调整所涉及变量的概率质量函数。

变量的概率质量函数定义了该变量成为某个值的可能性有多大。对于一个简单的六面骰子，这将是 1 -> 1/6, 2 -> 1/6, 3 -> 1/6 ...。将此函数存储为字典或映射可能是最简单的。

对于具有多个骰子的 diceRoll 函数，我们必须能够添加两个概率质量函数(例如 d8 的 pmf + d10 的 pmf，以及后来的 d12)。为此，我们创建了一个新的空 pmf。对于两个输入分布的每对元素，我们计算结果总和 (element1.Value + element2.Value) 及其概率 (element1.probability * element2.probability) .

现在我们可以为变量声明节点创建和修改 PMF。我们仍然需要决策节点的行为。

首先是计算决策的概率。这很容易。选择相应变量的 PMF，迭代所有条目，如果条件对元素成立，则对概率求和。

对于 true 子项，我们必须修改 PMF，以删除所有条件为假的条目。对于 false 子项，我们必须删除其他条目。之后我们必须重新归一化 PMF(即除以剩余概率之和)。请务必创建新的 PMF。您不希望这些修改干扰树的其他部分。

您还可以将累积概率传播到叶节点。但是，这不是计算预期值所必需的。