大约一个月以来，我一直致力于制作游戏求解器，尝试了各种策略，但大多数都以蛮力为导向。这适用于更简单的游戏情况，但不适用于更复杂的情况（更高的游戏树深度）。这是游戏的抽象表述：
1）有一组可能的动作要做，A。
2) 将动作应用于状态会产生可能状态的概率分布。应用(A, s) = [[s1, p1], [s2, p2], [s3, p3]]
3) 当达到目标状态时，游戏结束。
4) 每个状态都有一个与之相关的分数。
3) 有两种类型的目标状态，“成功”状态的得分是其前一状态的得分，“失败”状态的得分为 0。
5) 目标是制定一种策略，使游戏结束时的平均得分最大化。
6) 没有循环。所有路径的长度都是有限的。
我尽可能以最抽象的方式制定游戏，因为我认为这是人们最熟悉的游戏。我目前的策略是一个简单的深度优先搜索，它缓存独特的状态以防止工作重复。这一直有效到大约 2 亿个唯一状态，这是我内存不足的时候。在我开始分解较低级别的细节以找到优化之前，我想知道是否有任何巧妙的算法适用于游戏的一般情况。如果有人对如何生成状态转换的细节感兴趣，我可以提供。以下是我将问题减少为已知问题的一些方法。
1) 随机马尔可夫决策过程，其中状态奖励函数对于任何非目标状态为 0，否则为目标状态的得分。我知道 MDP 的通用算法不是很有效，但是某些类型的 MDP 有有效的解决方案。这个问题是否适合这些特定类别之一？
2) 具有负边权的有向无环图中的随机最长路径问题。