我在 Boardgame StackExchange 上问过这个问题，关于哪个角色更有可能赢得一场 Button Men 的比赛。这让我想到了在合理的时间内回答问题的具体方法。游戏规则相当简单。
在游戏开始时，每个玩家都掷出他们的多面体骰子。
拥有最低骰子的玩家首先进入（平局使用下一个最低的骰子）。
玩家可以通过两种可能的方式捕获对手死亡。
1）强力攻击：使用大于或等于值的单个骰子（然后重新滚动该骰子）。
2）技能攻击：用多个骰子完全等于一个对手死亡（重新掷骰子在捕获中使用的所有骰子）。
3）如果一个玩家不能抓住一个对手死亡，他们必须通过。
当玩家没有剩余骰子时，游戏结束。每个玩家从对手手中夺取的每个 dX 得分 X 分，剩余的每个骰子得分 0.5dX。（即如果您捕获了对手 d4, d4, d10, d12, d20，并且仍然拥有自己的 d20，则您的得分为 (4+4+10+12+20+0.5*20)=60 分。）
蛮力 Avis 角色掷出 d4、d4、d10、d12 和 dX（其中 dX 是 d4、d6、d8、d10、d12 或 d20）。这意味着他们在初始滚动后最多有 (4*4*10*12*20) 38,400 个状态。Iago 角色最多有 4d20（如果他们使用 d20 作为他们的 'dX' 摇摆骰子），给他们 160,000 种可能的起始状态。总之，这会导致 61.44 亿个可能的起始状态，而且事情会从这里变得更糟。如果没有任何试图找出最佳动作的智慧，就必须尝试所有可能的动作。在最坏的情况下，玩家可能会在技能攻击中重新掷出所有骰子。由于在游戏结束之前必须进行多达 8 次捕获，因此即使在每一方的强力攻击中重新滚动一个 d20 也会加起来（20^8 = 256 亿）。蛮力方法可能会导致评估 157+ Quintillion 或更多可能的状态。这是不可行的，但有更好的方法。蛮力方法多次重新评估相同的游戏状态。
马尔可夫链 如果我们观察游戏中一系列最终转换到最终游戏的可能状态，我们可以评估从游戏中的一个状态移动到另一个状态的几率，并最终得出每个角色获胜的几率游戏的开始。游戏仅以几种可能的状态结束（相对而言）。一个玩家没有骰子，而另一个玩家有一些自己的骰子组合（在下面的示例中，dX 摇摆骰子被选为 d20。这只是一个概念证明，所以不要担心这个骰子因游戏而异）。
安飞士：d4 | d10 | d12 | d20
安飞士：d4,d4 | d4,d10 | d4,d12 | d4,d20
安飞士：d4,d4,d10 | d4,d4,d12 | d4,d4,d20 | d4,d10,d12 | d4,d10,d20 | d4,d12,d20 | d10,d12,d20
安飞士：d4,d4,d10,d12 | d4,d4,d10,d20 | d4,d10,d12,d20
安飞士：d4,d4,d10,d12,d20
伊阿古：d20
伊阿古：d20,d20
伊阿古：d20,d20,d20
伊阿古：d20,d20,d20,d20
一旦为每个玩家对这些结束游戏状态进行评分，并确定该状态对于每个角色是赢还是输，就可以检查“倒数第二个”游戏状态。以类似的方式，可以确定每个“倒数第二个”游戏状态将导致我们的最终游戏状态之一的可能性。一些简单的电子表格计算得出大约 99 亿个游戏状态的结果（因为我只需要存储游戏状态的输赢性质，我应该能够将这些信息打包成一个位，对吧？）。这似乎不是一个不可逾越的游戏状态来存储/评估。
是否有可能在合理的时间和相当便宜的硬件上使用马尔可夫链回答哪个角色更好？
有没有更好的方法来解决这类问题？