生成井字游戏树的递归时间太长

Question

我正在尝试生成完整的井字游戏树。我假设参与人1是1，参与人2是-1。我使用了以下代码:

nodeDict = {}
nodescore = {}
succDict = {}
def buildTree(S, p, node):
    succ = []
    succScore = []  
    if move_was_winning_move(S, p):
        print "It is a winning move forn",S,p,node
        return
    elif move_was_winning_move(S, p*-1):
        print "It is a winning move forn",S,p*-1,node
        return
    elif not move_still_possible(S):
        return
    # if S is not terminal: switch player & compute successors
    if not move_was_winning_move(S, p):
        rs, cs = np.where(S==0)
    for j in range(rs.size):
        Ssucc = np.copy(S)
        Ssucc[rs[j],cs[j]] = p
        newnode = max(nodeDict.keys())+1
        nodeDict[newnode] = Ssucc
        succ.append(newnode)
    succDict[node] = succ
   nextPlayer = p * (-1)
   for s in succ:
        buildTree(nodeDict[s], nextPlayer, s)
   return

当我从一个状态开始代码时:

0  0  0
0  0  0
0  0  0

它运行太长。我发现，最多应该有9个!节点的数目，它不应该太长运行。

谁能告诉我，如果我在代码上错了吗?或者有什么方法可以优化递归?

Answer 1

几点注释:

当你检查你是否在树的分支的末尾时，你不需要重新检查S是否为终端:

# if S is not terminal: switch player & compute successors
    ##if not move_was_winning_move(S, p):   THIS LINE IS NOT NECESSARY
    rs, cs = np.where(S==0)

此外，在我看来，由于您的move_was_winning_move和move_still_possible函数每次迭代至少调用一次，它们可能对运行时间做出重大贡献，但您没有向我们展示该代码，因此我们无法帮助您优化它。

你真正需要做的是查看cProfile模块并找出代码中的瓶颈是什么

Answer 2

您总是可以多线程程序，尽管这种方法可能有些多余。多线程是一种使用多个内核来运行程序的方式，而不仅仅是一个，这是python程序运行的默认方式。这确实加快了程序的运行速度，尽管我不能说加快了多少。Python文档比我更好地解释了如何使用多线程，所以我想先看看如何使用多线程的说明。