我在Pacman的基本游戏中在Python 2.7.11中实现了minimax . Pacman是最大化剂,并且一个或多个鬼(取决于测试布局)是最小化剂 .
我必须实现minimax,以便可能有最小化代理,以便它可以创建 n plies (深度)的树 . 例如,Ply 1将是每个幽灵轮流最小化其可能移动的终端状态效用,以及pacman轮流最大化鬼魂已经最小化的内容 . 从图形上看,ply 1看起来像这样:
如果我们将以下任意实用程序分配给绿色终端状态(从左到右):
-10, 5, 8, 4, -4, 20, -7, 17
吃 beans 子应该返回 -4
然后向那个方向移动,根据该决定创建一个全新的极小极大树 . 首先,我的实现所需的变量和函数列表是有意义的:
# Stores everything about the current state of the game
gameState
# A globally defined depth that varies depending on the test cases.
# It could be as little as 1 or arbitrarily large
self.depth
# A locally defined depth that keeps track of how many plies deep I've gone in the tree
self.myDepth
# A function that assigns a numeric value as a utility for the current state
# How this is calculated is moot
self.evaluationFunction(gameState)
# Returns a list of legal actions for an agent
# agentIndex = 0 means Pacman, ghosts are >= 1
gameState.getLegalActions(agentIndex)
# Returns the successor game state after an agent takes an action
gameState.generateSuccessor(agentIndex, action)
# Returns the total number of agents in the game
gameState.getNumAgents()
# Returns whether or not the game state is a winning (terminal) state
gameState.isWin()
# Returns whether or not the game state is a losing (terminal) state
gameState.isLose()
This is my implementation:
"""
getAction takes a gameState and returns the optimal move for pacman,
assuming that the ghosts are optimal at minimizing his possibilities
"""
def getAction(self, gameState):
self.myDepth = 0
def miniMax(gameState):
if gameState.isWin() or gameState.isLose() or self.myDepth == self.depth:
return self.evaluationFunction(gameState)
numAgents = gameState.getNumAgents()
for i in range(0, numAgents, 1):
legalMoves = gameState.getLegalActions(i)
successors = [gameState.generateSuccessor(j, legalMoves[j]) for j, move
in enumerate(legalMoves)]
for successor in successors:
if i == 0:
return maxValue(successor, i)
else:
return minValue(successor, i)
def minValue(gameState, agentIndex):
minUtility = float('inf')
legalMoves = gameState.getLegalActions(agentIndex)
succesors = [gameState.generateSuccessor(i, legalMoves[i]) for i, move
in enumerate(legalMoves)]
for successor in successors:
minUtility = min(minUtility, miniMax(successor))
return minUtility
def maxValue(gameState, agentIndex)
self.myDepth += 1
maxUtility = float('-inf')
legalMoves = gameState.getLegalActions(agentIndex)
successors = [gameState.generateSuccessor(i, legalMoves[i]) for i, move
in enumerate(legalMoves)]
for successor in successors:
maxUtility = max(maxUtility, miniMax(successor))
return maxUtility
return miniMax(gameState)
有没有人有任何想法为什么我的代码这样做?我希望有一些Minimax /人工智能专家可以识别我的问题 . 提前致谢 .
UPDATE: 通过将我的 self.myDepth
值实例化为 0
而不是 1
,我已经照射了异常抛出问题 . 但是,我的实现的整体不正确性仍然存在 .
1 回答
我终于找到了解决问题的方法 . 主要问题是我没有正确引用
depth
以跟踪层 . 它应该作为参数传递给每个函数,而不是在maxValue
方法中递增深度,而只是在传递给maxValue
时递增 . 还有其他一些逻辑错误,例如未正确引用numAgents
,以及我的miniMax
方法未返回操作的事实 . 这是我的解决方案,结果证明是有效的:并且presto!我们的最终工作多代理minimax实现 .