Pacman AI - Minimax 应用 - 避免重复的游戏树状态

Question

在项目的上下文中，继 UC Berkley pacman ai 项目（其第二部分）之后，我想在布局足够小以至于递归不是问题。

将问题定义为 2 人游戏（我们假设只有 1 个幽灵）、回合制、具有完美信息的零和游戏，应用递归将非常简单。然而，由于许多不同的策略最终可能会处于相同的游戏状态（定义为吃豆人的位置、幽灵的位置、食物的位置和当前玩的玩家的元组），我想找到一种方法来避免重新计算所有这些状态。

我搜索并阅读了一些关于换位表的内容。然而，我不太确定如何使用这种方法，我认为我应该实施的是以下内容：每次展开一个尚未访问的状态时，将其添加到 'visited' 集合中。如果状态已经展开，那么如果轮到最大玩家（pacman）return +inf 值（通常不会被最小玩家选择），如果轮到最小玩家return - inf相应地。

这个想法的问题，我认为，以及为什么它适用于某些布局而不适用于其他布局的原因是，当我点击一个节点时，它的所有子节点都已经展开，我拥有的唯一值可供选择的是 +/- 无穷大。这导致无限值向上传播并被选中，而实际上这种游戏状态有可能导致失败。我想，我已经理解了这个问题，但我似乎找不到解决它的方法。

有没有其他方法可以避免计算重复的游戏状态？有没有我不知道的标准方法？

这是一些伪代码：

 def maxPLayer(currentState, visitedSet):
     if not isTerminalState
         for nextState, action in currentState.generateMaxSuccessors()
             if nextState not in visitedSet
                mark nextState as visited
                scores = scores + [minPlayer(nextState, visitedSet)]
         if scores is not empty
            return bestScore = max(scores)
         else
            return +inf              #The problem is HERE!
     else
         return evalFnc(currentState)
 end MaxPlayer

def minPlayer(currenstState, visitedSet):
    if not isTerminal
        for nextState, action in generateMinSuccessors()
            if nextState not in visitedSet 
                mark nextState as visited
                scores = scores + [maxPLayer(nextState, visitedSet)]
        if scores is not empty
            return bestScore = min(scores)
        else
            return -inf            #The problem is also HERE!
    else
        return evalFnc(currentState)
   end MinPlayer

请注意，第一个玩的玩家是最大的，我选择得分最高的动作。无论我是否考虑无限值，都没有任何变化，仍然存在代理输掉或无限循环的游戏实例。

Answer 1

我认为你的方法的主要缺点是你认为已经访问过的状态是对手移动到的不受欢迎的目标。您应该检索首次访问该状态时计算的值，而不是返回无穷大值。

实际上这意味着您应该使用（状态-> 值）映射而不是（状态）集合。

仅在第一次访问的值尚未计算的情况下（因为递归调用导致访问 ancestor 状态），您需要使用保留价值。但是让那个值为undefined/null/None，这样就不会把它当作其他数值结果，而是会被排除在可能的路径之外，即使在回溯的时候。

作为旁注，我将在函数的 start 执行状态的查找和标记——在当前状态——而不是在循环内邻国。

下面是两个函数之一的外观：

def maxPLayer(currentState, evaluatedMap):
    if currentState in evaluatedMap
        return evaluatedMap.get(currentState)

    evaluatedMap.set(currentState, undefined)

    if not isTerminalState
        bestScore = undefined
        for nextState in currentState.generateMaxSuccessors()
            value = minPlayer(nextState, evaluatedMap)
            if value != undefined
                scores.append(value)
        if scores is not empty
            bestScore = max(scores)
    else
        bestScore = evalFnc(currentState)

    evaluatedMap.set(currentState, bestScore)
    return bestScore
end MaxPlayer

值 undefined 将在访问状态期间使用，但其值尚未确定（因为挂起的递归调用）。如果一个状态是当前玩家没有有效移动（是 "stuck"），那么该状态将永久获得值 undefined，在其他情况下，值 undefined 最终将获得替换为真实分数。

Answer 2

我遇到的问题最终与 'game state' 的定义以及必须如何处理 'repeated states' 有关。

事实上，考虑一个游戏状态树和一个特定的游戏状态 x，它由以下标识：

pacman的位置。
食物颗粒在网格上的数量和位置。
鬼的位置和方向（考虑方向是因为鬼被认为不能转半圈。

现在假设您开始沿着树的某个分支向下移动，并在某个时候访问了节点 x。假设它以前没有被访问过并且它不是游戏的最终状态，这个节点应该添加到访问节点集中。

现在假设一旦你完成了树的这个特定分支，你就开始探索另一个不同的分支。经过一定数量的不确定步骤后，您将再次到达标识为 x 的节点。这就是题中代码的问题所在。

事实上，虽然定义的游戏状态完全相同，但到达此状态所遵循的路径却不同（因为我们目前处于与原始分支不同的新分支上）。显然，将状态视为已访问或使用最后一个分支计算的效用是错误的。它会产生意想不到的结果。

这个问题的解决方案很简单，就是为树的每个分支设置一组单独的已访问节点。这样就避免了上述情况。从那以后，可以考虑两种策略：

第一个包括将循环遍历已访问的状态作为 pacman 的最坏情况和 ghost 的最佳策略（这显然不是严格意义上的）。考虑到这一点，树的同一分支中的重复状态被视为一种 'terminal' 状态 return -inf 作为实用程序。
第二种方法包括使用换位 table。然而，这实现起来并不容易：如果一个节点不在字典中，则将其初始化为无穷大以表明它当前正在计算并且如果以后访问则不应重新计算。当达到终止状态时，在所有节点上递归时，将当前节点与相应终止状态之间的游戏分数差异存储在字典中。如果在遍历一个分支时您访问了一个已经在字典中的节点 return 当前游戏分数（这取决于您到达该节点所采用的路径并且可以从一个分支更改为另一个分支）加上值在字典中（这是从该节点到最终状态的分数形式的增益（或损失）并且始终相同）。

更实际地说，第一种方法实现起来非常简单，每次将它作为参数传递给下一个玩家时复制集合就足够了（这样不同分支中的值就不会相互影响） ).这将使算法显着变慢，并且即使对于非常小的简单迷宫（1 个食物颗粒和可能 7x7 的迷宫）也应该应用 alpha beta。在任何其他情况下，python 都会抱怨递归或者只是花太长时间来解决（超过几分钟）。然而这是正确的。

第二种方法比较复杂。我没有正式的正确性证明，尽管直觉上它似乎有效。它明显更快并且与 alpha beta 修剪兼容。

根据解释很容易推导出相应的伪代码

Pacman AI - Minimax 应用 - 避免重复的游戏树状态

Pacman AI - Minimax Application - Avoiding repeated game tree states

algorithm

artificial-intelligence

memoization

minimax

pacman