在项目背景下，参考UC伯克利Pacman AI项目（第二部分），我想在足够小的布局中实现极小极大算法，不使用alpha-beta剪枝，用于对抗性代理，递归不会成为问题。
将问题定义为2玩家（我们假设只有1个鬼魂）、轮流、零和、完美信息的游戏，应用递归将非常简单。然而，由于许多不同的策略可能最终导致相同的游戏状态（定义为Pacman的位置、鬼魂的位置、食物的位置以及当前玩家），我想找到一种方法来避免重新计算所有这些状态。
我搜索并阅读了一些关于转置表的内容。然而，我不太确定如何使用这种方法，我认为我应该实现的是：每次扩展一个未访问过的状态时，将其添加到“已访问”集合中。如果状态已经被扩展过，那么如果是最大玩家（Pacman）的回合，返回+inf值（通常不会被最小玩家选择），如果是最小玩家的回合，则相应地返回-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 #问题在这里！ else return evalFnc(currentState) end MaxPlayerdef 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 #问题也在这里！ else return evalFnc(currentState) end MinPlayer请注意，第一个玩家是最大玩家，我选择得分最高的动作。无论是否考虑无穷值，游戏中仍然存在代理失败或无限循环的情况。
回答：
我遇到的问题最终与'游戏状态'的定义以及如何处理'重复状态'有关。
事实上，考虑游戏状态树和特定游戏状态x，它由以下内容标识：
- Pacman的位置。
- 网格上食物的数量和位置。
- 鬼魂的位置和方向（考虑方向是因为鬼魂被认为无法进行半转）。
现在假设你开始沿着树的某个分支向下走，在某个点你访问了节点x。假设它之前没有被访问过，并且不是游戏的终止状态，这个节点应该被添加到已访问节点集合中。
现在假设你完成这个特定分支后，开始探索另一个分支。在经过一定数量的步骤后，你再次到达一个被标识为x的节点。这就是问题所在，问题中的代码存在问题。
事实上，虽然游戏状态定义完全相同，但到达这个状态的路径不同（因为我们目前在与原始分支不同的新分支上）。显然，将状态视为已访问或使用最后一个分支计算的效用是错误的。这会产生意想不到的结果。
解决这个问题的方法很简单，就是为树的每个分支设置一个单独的已访问节点集合。这样就可以避免上述情况。从那时起，可以考虑两种策略：
- 第一种策略是将循环通过已访问状态视为Pacman的最坏情况和鬼魂的最佳策略（这显然不完全正确）。考虑到这一点，同一树分支中的重复状态被视为一种“终止”状态，返回
-inf作为效用值。 - 第二种方法是使用转置表。然而，这并不容易实现：如果节点不在字典中，将其初始化为无穷大，以表明它当前正在计算，如果稍后访问，不应重新计算。到达终止状态时，在所有节点上递归时，将当前节点与相应终止状态之间的游戏得分差异存储在字典中。如果在遍历分支时访问到字典中已有的节点，返回当前游戏得分（这取决于你到达此节点的路径，并且可能因分支而异）加上字典中的值（这是从此节点到终止状态的得分增益（或损失），并且始终相同）。
在实际操作中，第一种方法非常简单，只需每次将集合作为参数传递给下一个玩家时复制它（这样不同分支的值就不会相互影响）。这会使算法显著变慢，即使对于非常小、简单的迷宫（1个食物颗粒和可能7×7的迷宫）也应该应用alpha-beta剪枝。在其他情况下，Python要么会抱怨递归，要么解决问题的时间太长（超过几分钟）。然而，它是正确的。
第二种方法更复杂。我没有正式的正确性证明，尽管直觉上它似乎有效。它显著更快，并且也与alpha-beta剪枝兼容。
相应的伪代码很容易从解释中推导出来。
