递归太长，无法生成Tic-Tac T的博弈树

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 for\n",S,p,node
        return
    elif move_was_winning_move(S, p*-1):
        print "It is a winning move for\n",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

当我从一个状态启动代码时：

^{pr2}$

它跑得太长了。我发现，最多应该有9个！节点数，应该不会太长。在

有人能告诉我密码有没有错？或者有什么方法可以优化递归呢？在

Answer 1

你可以总是多线程的程序，尽管这种方法可能会有点过头。程序运行的默认方式是多核，而不是多线程。这确实加快了程序的运行速度，但我不能说是多少。Python文档解释了如何进行多线程处理，因此我将首先在那里查找关于如何多线程的说明。在

Answer 2

一些评论：

在检查是否位于树中某个分支的末尾后，不需要重新检查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函数在每次迭代中至少被调用一次，它们可能对运行时有很大贡献，但您没有向我们展示这些代码，因此我们无法帮助您优化它。在

您真正需要做的是查看^{} module并找出代码中的瓶颈是什么。在