为什么我的递归永远不会在我的tic tac toe minimax算法中结束（在Python3中？）>

Question

首先，我只想说非常感谢

花时间阅读本文。我使用python 3中的图形制作了井字游戏。要激活AI，必须单击设置，然后单击玩家按钮。然后，一旦我开始使用ai，程序就会错误地指出<>我不知道为什么我的AI_Turn函数从不停止递归。如果有人可以为我的项目提供帮助，我将不胜感激，因为我对minimax算法的工作原理非常好奇，我想进一步了解AI领域，但是如果我不明白这一点，我将无能为力。我使用minimax算法的功能称为AI_Turn。我需要帮助调试的唯一函数是AI_Turn函数。我是编码的初学者，所以如果我的某些代码看起来很原始，这就是为什么。无论如何，非常感谢您抽出宝贵的时间阅读本文。

import turtle, copy

def get_o_win(board):
    if (
           board[0][0] == board[0][1] == board[0][2] == "o"
        or board[1][0] == board[1][1] == board[1][2] == "o"
        or board[2][0] == board[2][1] == board[2][2] == "o"
        or board[0][0] == board[1][0] == board[2][0] == "o"
        or board[0][1] == board[1][1] == board[2][1] == "o"
        or board[0][2] == board[1][2] == board[2][2] == "o"
        or board[0][0] == board[1][1] == board[2][2] == "o"
        or board[2][0] == board[1][1] == board[0][2] == "o"
        ):
        return True
    else:
        return False

def get_X_win(board):
    if (
           board[0][0] == board[0][1] == board[0][2] == "x"
        or board[1][0] == board[1][1] == board[1][2] == "x"
        or board[2][0] == board[2][1] == board[2][2] == "x"
        or board[0][0] == board[1][0] == board[2][0] == "x"
        or board[0][1] == board[1][1] == board[2][1] == "x"
        or board[0][2] == board[1][2] == board[2][2] == "x"
        or board[0][0] == board[1][1] == board[2][2] == "x"
        or board[2][0] == board[1][1] == board[0][2] == "x"
        ):
        return True
    else:
        return False

def get_Win(board):
    if (
           board[0][0] == board[0][1] == board[0][2] != "n"
        or board[1][0] == board[1][1] == board[1][2] != "n"
        or board[2][0] == board[2][1] == board[2][2] != "n"
        or board[0][0] == board[1][0] == board[2][0] != "n"
        or board[0][1] == board[1][1] == board[2][1] != "n"
        or board[0][2] == board[1][2] == board[2][2] != "n"
        or board[0][0] == board[1][1] == board[2][2] != "n"
        or board[2][0] == board[1][1] == board[0][2] != "n"
        ):
        return True
    else:
        return False

def AI_Turn(board, turn):
    board_copy = copy.deepcopy(board) 
    turn = 0

    for _ in board:
        for __ in _:
            if __ != "n":
                turn +=1


    o_win = get_o_win(board_copy)
    x_win = get_o_win(board_copy)

    if o_win: # PLAYER WINS
        return (-1, None)

    elif x_win: # AI WINS
        return (1, None)

    elif turn == 9: #TIE
        return (0, None)

    else:
        if turn%2==0: # Player's Turn
            board_copy = copy.deepcopy(board)
            best = (0, None)

            for x in range(3):
                for y in range(3):
                    if board_copy[x][y] == "n":
                        board_copy[x][y] = "o"
                        turn += 1

                        temporary_score_tuple = AI_Turn(board, turn)
                        best_score = best[0]
                        temporary_score = temporary_score_tuple[0]
                        if temporary_score > best_score:
                            best = (temporary_score,[x,y])

            return best

        else: # AI's Turn
            board_copy = copy.deepcopy(board)
            best = (0, None)

            for x in range(3):
                for y in range(3) :
                    if board_copy[x][y] == "n":
                        board_copy[x][y] = "x"
                        turn += 1

                        temporary_score_tuple = AI_Turn(board, turn)
                        best_score = best[0]
                        temporary_score = temporary_score_tuple[0] 
                        if temporary_score > best_score:
                            best = (temporary_score,[x,y])

            return best[1]



def draw_box(x1,y1,x2,y2,fillcolor,outline,text):
    pointer.pensize(15) 
    pointer.color(outline)
    pointer.goto(x1,y1)
    pointer.begin_fill()
    pointer.fillcolor(fillcolor)
    pointer.down()
    pointer.goto(x2,y1)
    pointer.goto(x2,y2)
    pointer.goto(x1,y2)
    pointer.goto(x1,y1)
    pointer.end_fill() 
    pointer.up()
    pointer.goto(x1+(x2-x1)/2,(y1-0.15)+(y2-y1)/2)
    style = ("Courier", 50, "bold")
    pointer.color("white")
    pointer.write(text, font=style, align="center")
    pointer.pensize(27)

def draw_o(x,y):
    pointer.goto(x,y)
    pointer.shape("circle")
    pointer.color("tomato")
    pointer.shapesize(7,7)
    pointer.stamp()
    pointer.color("Cornflower Blue")
    pointer.shapesize(4.2,4.2)
    pointer.stamp()

def draw_X(x,y):
    pointer.color("navy blue")
    draw_line(x+0.17,y+0.17,x-0.17,y-0.17)
    draw_line(x-0.17,y+0.17,x+0.17,y-0.17)


def load():
    global board, sign, turn, start
    start_ttt()
    with open ("board.txt", "r") as f:
        BOARD = f.readlines()
        b1 = (((BOARD[0].replace("'","")).replace("\n","")).replace(" ","")).split(",")
        b2 = (((BOARD[1].replace("'","")).replace("\n","")).replace(" ","")).split(",")
        b3 = (((BOARD[2].replace("'","")).replace("\n","")).replace(" ","")).split(",")
        board = [b1,b2,b3]

    for x in range(3):
        for y in range(3):
            if board[x][y] == "x":
                draw_X(x + 0.5, y + 0.5)
                turn += 1

            elif board[x][y] == "o":
                draw_o(x + 0.5, y + 0.5)
                turn +=1

def save():
    global board
    with open ("board.txt","w") as f:
        f.write((str(board[0]).strip("[")).strip("]") +"\n")
        f.write((str(board[1]).strip("[")).strip("]") + "\n")
        f.write((str(board[2]).strip("[")).strip("]") + "\n")


def draw_line(x1,y1,x2,y2):
    pointer.up()
    pointer.goto(x1,y1)
    pointer.down()
    pointer.goto(x2,y2)
    pointer.up()

def reset():
    global win, start, control_menu, turn, statistics_menu,settings_menu,player
    pointer.clear()
    pointer.goto(1.45,2.4)
    pointer.color("Black")
    style = ("Courier", 70, "bold")
    pointer.write("TIC TAC TOE", font=style, align="center")
    draw_box(0.5, 2.2, 2.5, 1.8, "blue", "medium blue","Start")
    draw_box(0.5, 1.7, 2.5, 1.3, "Gold", "Goldenrod", "Controls")
    draw_box(0.5,1.2,2.5,0.8,"Green", "Dark Green", "Statistics")
    draw_box(1.8,0.1,2.8,0.6,"Red","Dark Red","Quit")
    draw_box(0.25, 0.1,1.4 , 0.6, "hot pink","deep pink" , "Settings")
    board = [["n","n","n"],["n","n","n"],["n","n","n"]]
    win = False
    start = False
    control_menu = False
    statistics_menu = False
    settings_menu = False
    turn = 0

def start_ttt():
    global turn, win, board
    pointer.clear()
    pointer.color("black")
    draw_line(0,2,3,2)
    draw_line(0,1,3,1)
    draw_line(1,3,1,0)
    draw_line(2,3,2,0)
    turn = 0
    win = False
    board = [["n","n","n"],["n","n","n"],["n","n","n"]]


def box_clicker(x,y):
    global turn, win, start, control_menu, o_placed, x_placed, statistics_menu, settings_menu, player
    if start:
        if not win:
            if turn % 2 == 0: 
                sign = "o"
            else:
                sign = "x" 

            if 0 < x < 0.9:
                if 0.1 < y < 0.9 and board[0][0] == "n":
                    if sign == "x":
                        draw_X(0.5,0.5)
                        x_placed += 1
                    else:
                        draw_o(0.5,0.5)
                        o_placed += 1
                    board[0][0] = sign
                    turn += 1
                elif 1.1 < y < 1.9 and board[0][1] == "n":
                    if sign == "x":
                        draw_X(0.5,1.5)
                        x_placed += 1
                    else:
                        draw_o(0.5,1.5)
                        o_placed += 1
                    board[0][1] = sign
                    turn += 1
                elif 2.1 < y < 2.9 and board[0][2] == "n":
                    if sign == "x":
                        draw_X(0.5,2.5)
                        x_placed += 1
                    else:
                        draw_o(0.5,2.5)
                        o_placed += 1
                    board[0][2] = sign
                    turn += 1

            elif 1.1 < x <1.9:
                if 0 < y < 0.9 and board[1][0] == "n":
                    if sign == "x":
                        draw_X(1.5,0.5)
                        x_placed += 1
                    else:
                        draw_o(1.5,0.5)
                        o_placed += 1
                    board[1][0] = sign
                    turn += 1    
                elif 1.1 < y < 1.9 and board[1][1] == "n":
                    if sign == "x":
                        draw_X(1.5,1.5)
                        x_placed += 1
                    else:
                        draw_o(1.5,1.5)
                        o_placed += 1
                    board[1][1] = sign
                    turn += 1
                elif 2.1 < y < 2.9 and board[1][2] == "n":
                    if sign == "x":
                        draw_X(1.5,2.5)
                        x_placed += 1
                    else:
                        draw_o(1.5,2.5)
                        o_placed += 1
                    board[1][2] = sign
                    turn += 1

            elif 2.1 < x < 2.9:
                if 0 < y < 0.9 and board[2][0] == "n":
                    if sign == "x":
                        draw_X(2.5,0.5)
                        x_placed += 1
                    else:
                        draw_o(2.5,0.5)
                        o_placed += 1
                    board[2][0] = sign
                    turn += 1
                elif 1.1 < y < 1.9 and board[2][1] == "n":
                    if sign == "x":
                        draw_X(2.5,1.5)
                        x_placed += 1
                    else:
                        draw_o(2.5,1.5)
                        o_placed += 1
                    board[2][1] = sign
                    turn += 1
                elif 2.1 < y < 2.9 and board[2][2] == "n":
                    if sign == "x":
                        draw_X(2.5,2.5)
                        x_placed += 1
                    else:
                        draw_o(2.5,2.5)
                        o_placed += 1
                    board[2][2] = sign
                    turn += 1

            if player == 1:     
                if turn%2 == 1:           
                    AImove = AI_Turn(board,turn)
                    print(AImove)
                    board[AImove[0]][AImove[1]] = "x"
                    draw_X(AImove[0] + 0.5, AImove[1] + 0.5)
                    x_placed += 1
                    turn += 1
                    sign = "x"
                    print(board)

            win = get_Win(board)
            if win == True:
                pointer.color("deep pink")
                style = ("Courier", 100, "bold")
                pointer.goto(1.55,1.5)
                pointer.write((sign) + " WINS!", font=style, align="center")
                win = True
                pointer.color("Black")
                if sign == "x":
                    x_wins += 1
                else:
                    o_wins += 1

                with open("Statistics.txt", "r+") as f:
                    stats = f.readlines()
                    oo = int(stats[0])
                    xx = int(stats[1])
                    o_placed += oo
                    x_placed += xx
                    f.write(str(o_placed) + "\n" + str(x_placed))

            elif turn == 9:
                pointer.color("grey")
                pointer.goto(1.55,1.5)
                style = ("Courier", 70, "bold")
                pointer.write("It's a draw...", font=style, align="center")
                pointer.color("Black")

            with open("Statistics.txt", "r+") as f:
                stats = f.readlines()
                oo = int(stats[0])
                xx = int(stats[1])
                o_placed += oo
                x_placed += xx
                f.write(str(o_placed) + "\n" + str(x_placed) + "\n")

    elif start == False and control_menu == False and statistics_menu == False and settings_menu == False:
        if 0.5<x<2.5 and 1.8<y<2.2:
            start = True
            start_ttt()
        elif 1.8<x<2.8 and 0.1<y<0.6:
            turtle.bye()

        elif 0.5<x<2.5 and 1.3<y<1.7: # Controls Button
            pointer.clear()
            draw_box(1.8, 0.6, 2.8, 0.2, "Gold", "Goldenrod", "Back")
            pointer.color("Black")
            pointer.goto(1.5,2.5)
            style = ("Courier", 35, "bold")
            pointer.write("CONTROLS", font = style, align="center")
            pointer.goto(0.3,2.2)
            style = ("Courier", 25, "bold")
            pointer.write("Press s To Save The Current Board", font=style, align="left")
            pointer.goto(0.3,1.9)
            pointer.write("Press l To Load A Previously Saved Board", font=style, align="left")
            pointer.goto(0.3,1.6)
            pointer.write("Press r To Reset The Game", font=style, align="left")

            control_menu = True

        elif 0.5<x<2.5 and 0.8<y<1.2: # Statistics Button
            statistics_menu = True
            pointer.clear()
            draw_box(1.8, 0.6, 2.8, 0.2, "Green", "Dark Green", "Back")
            pointer.color("black")
            pointer.goto(1.5,2.5)
            style = ("Courier", 35, "bold")
            pointer.write("STATISTICS", font = style, align="center")
            pointer.goto(0.3,2.2)
            style = ("Courier", 25, "bold")
            pointer.write("O Placed: " + str(o_placed), font=style, align="left")
            pointer.goto(0.3,1.9)
            pointer.write("X Placed: " + str(x_placed), font=style, align="left")

        elif 0.25<x<1.4 and 0.1<y<0.6: # Settings Button
            settings_menu = True
            pointer.clear()
            pointer.color("black")
            pointer.goto(1.5,2.5)
            style = ("Courier", 35, "bold")
            pointer.write("SETTINGS", font = style, align="center")
            draw_box(2.8, 0.6, 1.8, 0.2, "Hot Pink", "Deep Pink", "Back")
            draw_box(0.45, 1.8 ,0.6, 1.9, "hot pink", "deep pink", "")
            style = ("Courier", 20, "bold")
            pointer.color("Black")            
            pointer.goto(0.54,1.95)
            pointer.write("Players", font=style, align="center")
            if player == 2:
                pointer.goto(0.65,1.79)
                pointer.write("Two Players", font=style, align="left")
            else:
                pointer.goto(-0.1,1.79)
                pointer.write("One Player", font=style, align="left")



    elif control_menu == True and start == False  and statistics_menu == False and settings_menu == False:
        if 1.8<x<2.8 and 0.2<y<0.6:
            reset()

    elif control_menu == False and start == False  and statistics_menu == True and settings_menu == False:
        if 1.8<x<2.8 and 0.2<y<0.6:
            reset()

    elif control_menu == False and start == False  and statistics_menu == False and settings_menu == True:
        if 1.8<x<2.8 and 0.2<y<0.6:
            reset()

        elif 0.45<x<0.6 and 1.8<y<1.9:
            if player == 2:
                draw_box(0.65, 1.77, 1.2, 1.88, "cornflower blue", "cornflower blue", "")
                pointer.goto(-0.1,1.79)
                pointer.color("Black")
                style = ("Courier", 20, "bold") 
                pointer.write("One Player", font=style, align="left")
                player = 1
            else:
                draw_box(-1.1 ,1.77,0.4 ,1.88 , "cornflower blue", "cornflower blue", "")
                pointer.goto(0.65,1.79)
                pointer.color("black")
                style = ("Courier", 20, "bold") 
                pointer.write("Two Players", font=style, align="left")
                player = 2

screen = turtle.Screen()
screen.screensize(100,100)
screen.setworldcoordinates(0,0,3,3)
turtle.bgcolor("Cornflower Blue")
pointer = turtle.Turtle()
pointer.hideturtle()
pointer.up()
pointer.speed(0)
pointer.pensize(27)

reset()
o_placed = 0
x_placed = 0
x_wins = 0
o_wins= 0
player = 2


screen.onclick(box_clicker)

def bye():
    turtle.bye()

screen.onkey(reset,"r")
screen.onkey(save,"s")
screen.onkey(load,"l")
screen.onkey(bye,"q")

screen.listen()
screen.mainloop()

首先，我想说非常感谢您抽出宝贵的时间阅读本文。我使用python 3中的图形制作了井字游戏。要激活AI，必须单击设置，然后单击[...

Answer 1

看来您在AI_Turn中有一些逻辑问题。无限递归问题是由于：

[temporary_score_tuple = AI_Turn(board, turn)我想您是要通过board_copy而不是board（因为board尚未更改，因此您的例程将一直检查棋盘，而没有任何移动）。