1

我有两个玩家，我想模拟他们之间的游戏。两者都有一些属性（力量，智力......）和不同的行动。一些动作的结果是基于属性值和一些运气因素。

算法：

  • 为双方玩家构建所有可能移动的游戏树
    • 博弈树的深度可能有限
    • 每个级别都属于不同的玩家
  • 在叶节点上使用一些启发式方法来找出必须采取行动的玩家获胜的概率
  • 向上传播概率（就像极小极大算法一样）
  • 选择概率最高的走法
  • 在这个算法的开始处继续

所以，基本上这是极小极大算法。我有几个问题：

  1. 如何考虑运气因素？
  2. 当我迈出一步时，我是否必须再次运行整个算法？（构建具有+1深度和新根节点的树，计算新概率......）
  3. 还有其他模拟战斗的想法吗？

谢谢。

4

3 回答 3

3

您应该研究蒙特卡洛树搜索，听起来好像很适合您的问题。

它没有使用启发式算法，而是在扩展树之前在每个分支使用随机玩家运行完整游戏。这样做的好处是，您实际上是在构建一个概率树，并且您不必将树扩展到末尾或使用 MinMax 之类的启发式进行一些截止。

MCTS也是目前GO游戏中最好的方法，目前最擅长玩未知规则的游戏。为了获得额外的效果，您可以使用一些有限状态机代理来代替随机播放器，以使概率更准确。您还可以通过使用跳过某些分支的决策器，使用机器学习派生的启发式方法来减少分支因子。（但这是你为了提高技术速度而最后要做的事情）

如果你能做 MinMax，你就可以轻松地做 MCTS :) 而且 MCTS 可以玩比 MinMax 更复杂的游戏，因为相比之下它的复杂性大大降低。（如果您打算不断扩展游戏规则，那很好）

如果您有兴趣，请看这里：

http://www.aaai.org/Papers/AIIDE/2008/AIIDE08-036.pdf

是的，你必须在每一个球员的每一步都这样做。所以 MinMax 和 MCTS 都会很慢；所有基于游戏树的技术都很慢。

但是，使用 MinMax，您可以保留一些树；移动到你的新状态的分支，并删除它的父树和连接到它的子树。然后在剩余的子树中进一步扩展一个深度。但这是猜测；我以前从来没有时间这样做:)（但是，您会在概率计算中保留错误）

这些技术的好处在于，当您构建它们时，它们就会起作用。机器学习技术运行得更快，但在使用前需要数小时甚至数天的培训；）

于 2011-03-27T09:54:21.497 回答
2

虽然通常您的算法是有意义的，但我们无法保证该算法是最好的算法。例如让我们想象两个游戏：

  1. 在第一场比赛中，每个玩家有 2 个动作：用枪射击和用剑攻击。在这个游戏中，每个步骤都不会影响其他步骤，因此构建移动树在这里没有任何意义。每个玩家只需要选择武器并继续射击/打击和大喊'用盾牌或盾牌！'直到死亡或胜利。
  2. 第二局还有第三个动作——偷对方的盾。在这种情况下，移动树会更有意义，因为很明显，如果你已经决定偷走敌人的盾牌，那么在用剑攻击之前偷走它会更有意义。

所以你是否需要这个移动树很大程度上取决于你的游戏规则。

正如我所看到的，关于运气因素的主要选择是是否将其影响包含在移动树中。这取决于运气因素是否以相同的方式影响每个动作。如果为真，那么在计算移动树时可以忽略运气因素，然后在计算所选动作的结果时应用。否则，如果运气因素以不同的方式影响不同的动作（例如，即使完全失败的人也可以用枪射击敌人，但用勺子技能杀死需要运气），那么在计算移动树中的概率时应该考虑运气因素。

是否需要在每个节点之后重新计算整个树取决于您是否可以 100% 预测所选操作的结果。例如，在国际象棋中，您可以预测如果您决定移动一个棋子，那么该棋子肯定会移动到您决定的位置。这允许您在每一步中选择移动树中的分支，并为其中的每个场景再计算一次移动，而不是从零开始重新计算整个树。但是如果玩家可以决定用枪射击但由于他不走运的一天他会用一条腿射击自己，则这不适用。

于 2011-03-26T21:11:37.247 回答
1

您所要求的内容非常“庞大”......但许多开发人员已经完成了。

我建议你开始阅读这样一本关于游戏设计的书：http: //www.amazon.com/Game-Design-Practice-Wordware-Developers/dp/1556229127/ref=cm_cr_pr_product_top

...并在www.CodeProject.com和www.codeplex.com中搜索游戏实现示例。

祝你好运，

于 2011-03-26T20:32:02.117 回答