我的Python井字游戏的极小极大算法正在显示最大递归次数

Question

我正试着自己为python中的tic-tac-toe编写minimax算法的代码，我已经编写了代码，但是每当调用这个函数时，它就会显示一个“比较中的最大递归深度”错误。我被困在这一部分。当我试着调试它的时候，它也没有帮助。你知道吗

import sys

marked=['','','','','','','','','']
markingSignal=[False,False,False,False,False,False,False,False,False]


def printTable():
    print("\t%s|\t%s|\t%s\n------------------------\n\t%s|\t%s|\t%s\n------------------------\n\t%s|\t%s|\t%s\n"%(marked[0],marked[1],marked[2],marked[3],marked[4],marked[5],marked[6],marked[7],marked[8]))

def winning(m,player):
    i=0
    x=0
    while x<3:
        if m[i]==player and m[i+1]==player and m[i+2]==player:
            return True
        x=x+1
        i=i+3    
    x=0
    i=0
    while x<3:
        if m[2]==player and m[4]==player and m[6]==player:
            return True
        x=x+1
        i=i+3  
    x=0
    i=0
    if m[0]==player and m[4]==player and m[8]==player:
        return True
    if m[2]==player and m[4]==player and m[6]==player:
        return True
    return False         


def minimax(table,marktab,points,pos=0):
    copyTab=table
    copymark=marktab
    remaining=0
    for x in table:
        if x==False:
            remaining=remaining+1
    if remaining==0:
        return points,pos
    scores=[None]*remaining
    positions=[None]*remaining
    z=0
    maximum=0
    bestpos=0
    previous=88
    x=0
    while x<9:
        if table[x]==False:
            if points%2==0:
                copyTab[x]==True
                copymark[x]=='O'
                result=winning(copymark,'O')
                previous=x
                if result:
                    return points ,x
            else:
                copyTab[x]==True
                copymark[x]=='X'    
            scores[z],positions[z]=minimax(copyTab,copymark,points+1,previous)
            z=z+1
            copyTab[x]==False
            copymark[x]==''
        x=x+1
    for x in range(0,len(scores)):
        if x==0:
            maximum=scores[x]
            bestpos=positions[x]
        if scores[x]<maximum:
            maximum=scores[x]
            bestpos=positions[x]
    return maximum, bestpos        



def takeInput(player):
    filled=False
    while filled==False:
        print("Enter Your Choice 1-9")
        x=int(input())
        if x>9:
            print("Invalid Choice")
            continue
        if markingSignal[x-1]:
            print("This slot is already filled")
            continue
        filled=True    
    marked[x-1]=player
    markingSignal[x-1]=True


def main():

    sys.setrecursionlimit(5000)
    print(sys.getrecursionlimit())
    printTable()
    count=0
    player='X'
    while count<9:

        if count%2==0:
            player='X'
            takeInput(player)
        else:
            player='O'  
            p,choice=minimax(markingSignal,marked,0)  
            marked[choice]=player
            markingSignal[choice]=True         
        printTable()
        result=winning(marked,player)
        if result:
            print("\n%s WON !!!\n"%(player))
            break
        count=count+1


main()  

在这段代码中，用户输入部分工作正常，但计算机输入或minimax算法部分不工作，并显示递归错误

Answer 1

所以，在你的代码里

scores[z],positions[z]=minimax(copyTab,copymark,points+1,previous)

这是一个永无止境的循环。它一次又一次地破碎。。。上一个值始终介于88和0之间。递归函数必须在某个点返回（只有在调用递归函数之前才有一个返回，因为递归函数是一个胜利的位置。在第一次移动之后，你不可能有一个胜利的位置，因此递归永远不会结束）。你知道吗

考虑到这一点，在minimax函数中，您不是复制值，而是通过引用传递：

copyTab=table.copy()
copymark=marktab.copy()

另外，您没有增加X值，因为在递归函数中，电路板没有更新和测试。你知道吗

因此，您需要指定值： copyTab[x]=真 copymark[x]=“O” 不使用只返回布尔值的双等于==。你知道吗

因此，该功能正在按预期工作：

def minimax(table,marktab,points,pos=0):
    copyTab=table.copy()
    copymark=marktab.copy()
    remaining=0
    for x in table:
        if x==False:
            remaining=remaining+1
    if remaining==0:
        return points,pos
    scores=[None]*remaining
    positions=[None]*remaining
    z=0
    maximum=0
    bestpos=0
    previous=88
    x=0
    while x<9:
        if table[x]==False:
            if points%2==0:
                copyTab[x]=True
                copymark[x]='O'
                result=winning(copymark,'O')
                previous=x
                if result:
                    return points ,x
            else:
                copyTab[x]=True
                copymark[x]='X' 
            scores[z],positions[z]=minimax(copyTab,copymark,points+1,previous)
            z=z+1
            copyTab[x]=False
            copymark[x]=''
        x=x+1
    for x in range(0,len(scores)):
        if x==0:
            maximum=scores[x]
            bestpos=positions[x]
        if scores[x]<maximum:
            maximum=scores[x]
            bestpos=positions[x]
    return maximum, bestpos

Answer 2

另一个答案是想帮助你，但实际上你不需要这些副本。你正在应用的是一个do-undo模式，所以你做了一个步骤，检查结果并撤销这个步骤。这可以在不复制表的情况下完成，但也必须在从循环内部返回之前完成。当然，还需要解决===错误

def minimax(table,marktab,points,pos=0):
    #copyTab=table                             # copyTab eliminated
    #copymark=marktab                          # copymark eliminated
    remaining=0
    for x in table:                            # note that this...
        if x==False:
            remaining=remaining+1
    if remaining==0:
        return points,pos
    scores=[None]*remaining
    positions=[None]*remaining
    z=0
    maximum=0
    bestpos=0
    previous=88
    x=0
    while x<9:
        if table[x]==False:                    # ... and this line were referring to table anyway
            if points%2==0:
                table[x]=True                  # now it is table and =
                marktab[x]='O'                 # marktab and =
                result=winning(marktab,'O')
                previous=x
                if result:
                    table[x]=False             # this ...
                    marktab[x]=''              # ... and this undo steps were missing
                    return points ,x
            else:
                table[x]=True                  # table and =
                marktab[x]='X'                 # marktab and =
            scores[z],positions[z]=minimax(table,marktab,points+1,previous) # table and marktab
            z=z+1
            table[x]=False                     # table and =
            marktab[x]=''                      # marktab and =
        x=x+1
    for x in range(0,len(scores)):
        if x==0:
            maximum=scores[x]
            bestpos=positions[x]
        if scores[x]<maximum:
            maximum=scores[x]
            bestpos=positions[x]
    return maximum, bestpos        

然后对手高兴地输了，就像另一个一样。你知道吗

旁白

• marked和markingSignal可以使用复制，所以marked = ['']*9和markingSignal = [False]*9
• %格式要求在右边有一个元组，因此您可以简单地编写% tuple(marked)而不是长的% (marked[0],...)内容
• 在去掉copyTab和copymark之后，table和marktab实际上不需要作为参数传递
• ^实际上并不需要{}，检查table[x]==''可以判断字段是空闲还是已占用

这解决了递归问题，但对算法没有帮助。查看Wikipedia上的伪代码的外观：

function minimax(node, depth, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
        return value
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
        return value

在您的代码中只有一个最大查找，我们称之为max(scores)。你还需要一个min(scores)的地方，这取决于现在考虑的是哪一个播放器，或者你可以应用min(scores)经常使用的“技巧”作为寻找max(-scores)，但是这种“翻转”在代码中也不存在。你知道吗

正如您所说的您想自己修复它，我只提供了包含建议的简化的简短版本，但在其他方面是完整的（因此它会毫不犹豫地丢失）：

import sys

marked=[''] * 9

def printTable():
    print("\t%s|\t%s|\t%s\n            \n\t%s|\t%s|\t%s\n            \n\t%s|\t%s|\t%s\n"%tuple(marked))

def winning(player):
    i=0
    x=0
    while x<3:
        if marked[i]==player and marked[i+1]==player and marked[i+2]==player:
            return True
        x=x+1
        i=i+3    
    x=0
    i=0
    while x<3:
        if marked[2]==player and marked[4]==player and marked[6]==player:
            return True
        x=x+1
        i=i+3  
    x=0
    i=0
    if marked[0]==player and marked[4]==player and marked[8]==player:
        return True
    if marked[2]==player and marked[4]==player and marked[6]==player:
        return True
    return False         

def minimax(points,pos=0):
    remaining=0
    for x in marked:
        if x=='':
            remaining=remaining+1
    if remaining==0:
        return points,pos
    scores=[None]*remaining
    positions=[None]*remaining
    z=0
    maximum=0
    bestpos=0
    previous=88
    x=0
    while x<9:
        if marked[x]=='':
            if points%2==0:
                marked[x]='O'
                result=winning('O')
                previous=x
                if result:
                    marked[x]=''
                    return points ,x
            else:
                marked[x]='X'    
            scores[z],positions[z]=minimax(points+1,previous)
            z=z+1
            marked[x]=''
        x=x+1
    for x in range(0,len(scores)):
        if x==0:
            maximum=scores[x]
            bestpos=positions[x]
        if scores[x]<maximum:
            maximum=scores[x]
            bestpos=positions[x]
    return maximum, bestpos        

def takeInput(player):
    filled=False
    while filled==False:
        print("Enter Your Choice 1-9")
        x=int(input())
        if x>9:
            print("Invalid Choice")
            continue
        if marked[x-1]!='':
            print("This slot is already filled")
            continue
        filled=True    
    marked[x-1]=player

def main():
    printTable()
    count=0
    player='X'
    while count<9:
        if count%2==0:
            player='X'
            takeInput(player)
        else:
            player='O'  
            p,choice=minimax(0)  
            marked[choice]=player
        printTable()
        result=winning(player)
        if result:
            print("\n%s WON !!!\n"%(player))
            break
        count=count+1

main()