小编Occ*_*ade的帖子

我正在使用Python为2048游戏编写AI.它比我预期的要慢很多.我将深度限制设置为5,仍然需要几秒钟才能得到答案.起初我认为我所有函数的实现都是垃圾,但我找出了真正的原因.搜索树上的叶子数量甚至超过了甚至可能的数量.

这是一个典型的结果(我计算了叶子,分支和扩展数量):

111640 leaves, 543296 branches, 120936 expansions
Branching factor: 4.49242574585
Expected max leaves = 4.49242574585^5 = 1829.80385192 leaves

和另一个,好的措施:

99072 leaves, 488876 branches, 107292 expansions
Branching factor: 4.55650001864
Expected max leaves = 4.55650001864^5 = 1964.06963743 leaves

正如您所看到的,搜索树上的叶子数量多于使用天真极小极大时的叶子数量.这里发生了什么？我的算法发布如下:

# 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 …