python - 我的 Python 中 Tic Tac Toe 的极小极大算法显示了最大递归误差

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()  

在此代码中，用户输入部分工作正常，但计算机输入或极小极大算法部分无法工作，并显示递归错误

Answer 1

所以，在你的代码中

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

这正在进入一个永无止境的循环。它一遍又一遍地打破......之前的值总是在88和0之间。该递归函数必须在某个点返回(在调用递归函数之前只有一个返回，其中是获胜位置。在第一次移动之后，你无法获得获胜位置，因此递归永远不会结束)。

在 minimax 函数中考虑到这一点，您不会复制值，仅通过引用传递:

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

此外，您不会增加 X 值，因为在递归函数中，板未更新且未测试。

所以你需要分配这些值: copyTab[x]=True 复制标记[x]='O' 并且不使用 double equals == ，它只会返回一个 bool 值。

因此该函数现在可以按预期工作:

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