gpt4 book ai didi

python - 为什么我的 Minimax 不能正确展开和移动?

转载 作者:太空狗 更新时间:2023-10-30 00:19:17 25 4
gpt4 key购买 nike

我正在 Python 2.7.11 中的 Pacman 基本游戏中实现 minimax。 Pacman 是最大化代理,一个或多个幽灵(取决于测试布局)是最小化代理。

我必须实现 minimax 以便可能存在多个 最小化代理,并且它可以创建一棵 n 层(深度)。例如,第 1 层是每个幽灵轮流将其可能移动的最终状态效用最小化,以及吃 bean 人轮流最大化幽灵已经最小化的东西。从图形上看,第 1 层看起来像这样:

Ply 1 depth of minimax

如果我们将以下任意实用程序分配给绿色终端状态(从左到右):

-10, 5, 8, 4, -4, 20, -7, 17

Pacman 应该返回 -4 然后朝那个方向移动,根据那个决定创建一个全新的 minimax 树。首先,我的实现需要一个变量和函数列表:

# 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()

这是我的实现:

""" 
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/人工智能专家可以识别我的问题。提前致谢。

更新:通过将我的 self.myDepth 值实例化为 0 而不是 1,我已经消除了异常抛出问题。但是,我的实现总体上仍然存在错误。

最佳答案

我终于找到了解决问题的方法。主要问题是我没有正确引用 depth 来跟踪层。与其在 maxValue 方法中递增深度,不如将其作为参数传递给每个函数,并且仅在传递到 maxValue 时递增。还有其他一些逻辑错误,例如没有正确引用 numAgents,还有我的 miniMax 方法没有返回操作。这是我的解决方案,结果证明有效:

def getAction(self, gameState):

self.numAgents = gameState.getNumAgents()
self.myDepth = 0
self.action = Direction.STOP # Imported from a class that defines 5 directions

def miniMax(gameState, index, depth, action):
maxU = float('-inf')
legalMoves = gameState.getLegalActions(index)
for move in legalMoves:
tempU = maxU
successor = gameState.generateSuccessor(index, move)
maxU = minValue(successor, index + 1, depth)
if maxU > tempU:
action = move
return action

def maxValue(gameState, index, depth):
if gameState.isWin() or gameState.isLose() or depth == self.depth:
return self.evaluationFunction(gameState)

index %= (self.numAgents - 1)
maxU = float('-inf')
legalMoves = gameState.getLegalActions(index)
for move in legalMoves:
successor = gameState.generateSuccessor(index, move)
maxU = max(maxU, minValue(successor, index + 1, depth)
return maxU

def minValue(gameState, index, depth):
if gameState.isWin() or gameState.isLose() or depth == self.depth:
return self.evaluationFunction(gameState)

minU = float('inf')
legalMoves = gameState.getLegalActions(index)
if index + 1 == self.numAgents:
for move in legalMoves:
successor = gameState.generateSuccessor(index, move)
# Where depth is increased
minU = min(minU, maxValue(successor, index, depth + 1)
else:
for move in legalMoves:
successor = gameState.generateSuccessor(index, move)
minU = min(minU, minValue(successor, index + 1, depth)
return minU

return miniMax(gameState, self.index, self.myDepth, self.action)

很快!我们最终的工作多智能体 minimax 实现。

关于python - 为什么我的 Minimax 不能正确展开和移动?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36022941/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com