我正在用Python为2048游戏编写一个AI。比我预想的要慢得多。我把深度限制设置为5,但还是花了几秒钟才得到答案。一开始我以为我所有函数的实现都是垃圾,但我找到了真正的原因。搜索树上的叶子比应该有的还要多。在
下面是一个典型的结果(我计算了树叶、树枝和展开的数量):
111640 leaves, 543296 branches, 120936 expansions
Branching factor: 4.49242574585
Expected max leaves = 4.49242574585^5 = 1829.80385192 leaves
另一方面,为了更好的衡量:
^{pr2}$正如你所看到的,搜索树上的叶子比使用naiveminimax会有更多的叶子。这是怎么回事?我的算法如下:
# Generate constants
import sys
posInfinity = sys.float_info.max
negInfinity = -sys.float_info.max
# Returns the direction of the best move given current state and depth limit
def bestMove(grid, depthLimit):
global limit
limit = depthLimit
moveValues = {}
# Match each move to its minimax value
for move in Utils2048.validMoves(grid):
gridCopy = [row[:] for row in grid]
Utils2048.slide(gridCopy, move)
moveValues[move] = minValue(grid, negInfinity, posInfinity, 1)
# Return move that have maximum value
return max(moveValues, key = moveValues.get)
# Returns the maximum utility when the player moves
def maxValue(grid, a, b, depth):
successors = Utils2048.maxSuccessors(grid)
if len(successors) == 0 or limit < depth:
return Evaluator.evaluate(grid)
value = negInfinity
for successor in successors:
value = max(value, minValue(successor, a, b, depth + 1))
if value >= b:
return value
a = max(a, value)
return value
# Returns the minimum utility when the computer moves
def minValue(grid, a, b, depth):
successors = Utils2048.minSuccessors(grid)
if len(successors) == 0 or limit < depth:
return Evaluator.evaluate(grid)
value = posInfinity
for successor in successors:
value = min(value, maxValue(successor, a, b, depth + 1))
if value <= a:
return value
b = min(b, value)
return value
有人请帮帮我。我把这个代码看了好几遍,都弄不清是什么地方出了问题。在
显然,您是在比较}(beta)和{}(alpha)。代码中的比较如下:
value
和{以及
^{pr2}$然而,alpha-beta剪枝的条件是每当alpha的增长超过beta,即alpha>;beta,我们不需要遍历搜索树。在
因此,它应该是:
以及
这是您丢失的边缘大小写,因为}(beta)不一定总是等于
a
(alpha)和{value
。在相关问题 更多 >
编程相关推荐