实现蒙特卡罗树搜索-游戏状态节点与可能移动节点



我正试图在一个相当复杂的游戏中实现蒙特卡罗搜索树方法,但我对此有些不了解(也许这适用于其他搜索算法,我不确定)。对不起,如果我的英语不够清晰。

我的问题是:树节点代表什么——可能的游戏状态或玩家可以做出的可能动作?我会尽力解释为什么两者对我来说都没有意义。

如果节点是游戏状态,为什么选择可能导致最佳状态的移动是有意义的?很有可能我的对手会选择不同的打法,这将导致我的比赛状态非常糟糕

如果节点是可能的移动,同样的逻辑也适用,只需降低一级-选择每个移动的最佳子移动是没有意义的,因为没有保证我的对手会以让我玩该移动的方式玩。相反,更随意地看孩子是有道理的,但这与这种方法的工作方式相矛盾。

所以我想常见的实现是两者之间的某种混合?我确实做了一些研究,我知道有时搜索算法会使用一个具有简单策略的确定性对手,并将其用于搜索。这似乎对我不起作用,因为我正在实施的游戏没有直观的策略(这就是我选择蒙特卡罗方法的原因——不需要评估函数)。感觉我缺少了一些非常简单的东西。

我希望我的问题足够清楚,如果有任何帮助,我将不胜感激。

游戏树中的节点表示状态-边是从一个状态到另一个状态的移动。

在我熟悉的传统MiniMax游戏搜索中,从特定位置出发的最佳移动是剥夺对手在下一级别进行最佳潜在移动的机会,以此类推,直到搜索深度耗尽。

例如,在两层搜索(向前看一个完整的移动)中,如果当初始玩家玩移动X1时,玩家二具有潜在的响应移动Y1、Y2和Y3,其各自的得分(从她的角度来看)为1、2和3,则X1从第一玩家的角度来看的得分变为-3。如果玩家1的X2移动的得分为-4,那么X1是更好的初始移动(它剥夺了玩家2获得4分的机会),但如果X2得出的得分为-2,那么X1仍然是树顶部的最佳移动。

按照我的理解,蒙特卡洛树搜索意味着将被检查的游戏节点的数量限制在某个随机子集。使用蒙特卡罗,你不必一直到终止节点(对于总是可以到达的游戏),尽管你可以,但如果需要,它也可以与评估函数一起使用。

最新更新