递归太长，无法生成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

一些评论：

在检查是否位于树中某个分支的末尾后，不需要重新检查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并找出代码中的瓶颈是什么。在