我有两个玩家，我想模拟他们之间的游戏。两者都有一些属性(力量、智力……)和不同的 Action 。一些行动的结果是基于属性值和一些运气因素。
算法:
- 为双方玩家构建一个包含所有可能 Action 的博弈树
- 博弈树的深度可能有限
- 每一关都属于不同的玩家
- 在叶节点处使用一些启发式方法来找出必须采取行动的玩家获胜的概率
- 向上传播概率(就像极小极大算法一样)
- 选择概率最高的一步
- 从这个算法的开始继续
所以，基本上这是极小极大算法。不过我有几个问题:
- 如何考虑运气因素？
- 当我迈出一步时，是否必须重新运行整个算法？ (构建+1深度的树和新的根节点，计算新的概率...)
- 还有其他模拟战斗的想法吗？
谢谢。
最佳答案
您应该研究一下 Monte Carlo Tree Search，它听起来很适合您的问题。
它没有使用启发式算法，而是在扩展树之前在每个分支使用随机玩家运行完整的游戏。这样做的好处是，您实际上是在构建一棵概率树，并且您不必将树扩展到末尾或使用像 MinMax 这样的启发式方法进行截断。
MCTS也是目前GO游戏中最好的方法，目前最擅长玩未知规则的游戏。为了获得额外的效果，您可以使用一些有限状态机代理而不是随机玩家来使概率更准确。您还可以通过使用跳过某些分支的决策器，使用机器学习派生的启发式来减少分支因子。 (但这是你最后做的事情，以提高技术的速度)
如果你能做 MinMax，那么你就可以毫不费力地做 MCTS :) 而且 MCTS 可以玩比 MinMax 复杂得多的游戏，因为相比之下它的复杂性大大降低了。 (如果你打算不断扩展游戏规则，那就太好了)
感兴趣的可以看这里:
http://www.aaai.org/Papers/AIIDE/2008/AIIDE08-036.pdf
是的，您必须对每位玩家的每一步都执行此操作。所以 MinMax 和 MCTS 都会很慢；所有基于游戏树的技术都很慢。
使用 MinMax，您可以保留一些树；移动到你的新状态的分支，并删除它的父级和连接到它的子树。然后在剩下的子树中进一步扩展一个深度。但这是猜测；我以前从来没有时间这样做过:)(但是你会在概率计算中保留错误)
这些技术的好处在于，当您构建它们时，它们就会起作用。机器学习技术运行得更快，但在使用前需要数小时甚至数天的培训；)
关于algorithm - 如何模拟两个玩家之间的战斗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/5445060/