我的tic tac toe游戏告诉我，当它是平局时，我就赢了。

Question

从理论上讲，我的极大极小算法应该工作得很好。我找不到任何明显的问题。但是..。每当我把它作为'O‘运行时，我的算法就会说玩家会赢。然而，井字游戏是一场平局。我很困惑！

import time
positionsChecked = 0
maxDepthChecked = 0
drawn = 0
wonForAI = 0
wonForPlayer = 0

def areMovesLeft(board):
    for i in board:
        for j in i:
            if j == '-':
                return True
    return False


def evaluate(board, humanSprite, AISprite):
    movesLeft = areMovesLeft(board)
    if not movesLeft:
        return 0
    for i in range(3):
        if board[i][0] == board[i][1] and board[i][1] == board[i][2]:
            if board[i][0] == humanSprite:
                return -10
            elif board[i][0] == AISprite:
                return 10
        if board[0][i] == board[1][i] and board[1][i] == board[2][i]:
            if board[0][i] == humanSprite:
                return -10
            elif board[0][i] == AISprite:
                return 10
    if board[0][0] == board[1][1] and board[1][1] == board[2][2]:
        if board[0][0] == humanSprite:
            return -10
        elif board[0][0] == AISprite:
            return 10
    if board[0][2] == board[1][1] and board[1][1] == board[2][0]:
        if board[0][2] == humanSprite:
            return -10
        elif board[0][2] == AISprite:
            return 10
    return 0


def minimax(board, isMaxPlayer, depth, humanSprite, AISprite, alpha, beta):
    global positionsChecked, maxDepthChecked, drawn, wonForAI, wonForPlayer
    best = 0
    if depth > maxDepthChecked:
        maxDepthChecked = depth
    movesLeft = areMovesLeft(board)
    if not movesLeft:
        positionsChecked += 1
        return 0
    score = evaluate(board, humanSprite, AISprite)

    if score == 10:
        return score - depth
        positionsChecked += 1
    if score == -10:
        positionsChecked +=1
        return score + depth
    for i in range(3):
        for j in range(3):
            if board[i][j] == '-':
                movesLeft = True
    if isMaxPlayer:
        best = -1000
        for i in range(3):
            for j in range(3):
                if board[i][j] == '-':
                    board[i][j] = AISprite
                    var2 = minimax(board, not isMaxPlayer, depth + 1, humanSprite, AISprite, alpha, beta)
                    best = max(best, var2)
                    board[i][j] = '-'
                    alpha = max(alpha, best)
                    if alpha <= beta:
                        break
                        break


        return best
    else:
        best = 1000
        for i in range(3):
            for j in range(3):
                if board[i][j] == '-':
                    board[i][j] = humanSprite
                    var2 = minimax(board, not isMaxPlayer, depth + 1, humanSprite, AISprite, alpha, beta)
                    best = min(best, var2)
                    board[i][j] = '-'
                    beta = min(beta, best)
                    if beta <= alpha:
                        break
                        break

        print(best)
        if best > 0:
            wonForAI += 1
        elif best == 0:
            drawn +=1
        elif best < 0:
            wonForPlayer += 1
        return best


def calcBestMove(board, humanSprite, AISprite):
    global positionsChecked
    global maxDepthChecked
    maxDepthChecked = 0
    positionsChecked = 0
    print("Best move being calculated...")
    timeBeforeMove = time.time()  # I am using this to calculate how long the program takes to find the best move
    bestValue = -1000
    for i in range(3):
        for j in range(3):
            if board[i][j] == '-':
                board[i][j] = AISprite
                moveValue = minimax(board, False, 1, humanSprite, AISprite, -1000, 1000)
                board[i][j] = '-'
                if moveValue > bestValue:
                    bestValue = moveValue
                    bestRow = i
                    bestCol = j
    print(f"\nThe value of the best move is {bestValue}. The best move is ({bestRow + 1}, {bestCol + 1})")
    timeAfterMove = time.time()
    timeTaken = timeAfterMove - timeBeforeMove
    print(f"The time it took the AI to find the best move is {timeTaken} seconds.")
    print(f"The AI searched {positionsChecked} positions.")
    print(f"Deepest search is {maxDepthChecked}")
    print(f"Drawn is {drawn} and won for player is {wonForPlayer} and wonfor ai is {wonForAI}")
    board[bestRow][bestCol] = AISprite


def printBoard(board):  # this prints the board
    print("         |         |         ")
    print(f"    {board[0][0]}    |    {board[0][1]}    |    {board[0][2]}    ")
    print("         |         |         ")
    print("---------|---------|---------")
    print("         |         |         ")
    print(f"    {board[1][0]}    |    {board[1][1]}    |    {board[1][2]}    ")
    print("         |         |         ")
    print("---------|---------|---------")
    print("         |         |         ")
    print(f"    {board[2][0]}    |    {board[2][1]}    |    {board[2][2]}    ")
    print("         |         |         ")


def switchTurns(humanSprite, AISprite, isHumanTurn, board):  # controls the flow of the game
    printBoard(board)

    if isHumanTurn:
        while True:
            row = input("Enter row: ")
            column = input("Enter column: ")
            if (row == '1' or row == '2' or row == '3') and (column == '1' or column == '2' or column == '3'):
                row = int(row)-1
                column = int(column)-1
                if 0 <= row <= 2 and 0 <= column <= 2 and board[row][column] == '-':
                    board[row][column] = humanSprite
                    break
                else:
                    if not (0 <= row <= 2 and 0 <= column <= 2):
                        print("Out of range!")
                    else:
                        print("Box already filled")
            else:
                print("Not valid values!")
    else:
        calcBestMove(board, humanSprite, AISprite)
    gameStatus = evaluate(board, humanSprite, AISprite)

    if gameStatus == 0:
        movesLeft = False
        for i in range(3):
            for j in range(3):
                if board[i][j] == '-':
                    movesLeft = True
        if not movesLeft:
            print("It's a tie!")
        else:
            switchTurns(humanSprite, AISprite, not isHumanTurn, board)
    else:
        printBoard(board)
        if gameStatus == -10:
            print("Human wins!")
        elif gameStatus == 10:
            print("AI wins!")
        return


def chooseFirstOrSecond():
    playerGoesFirst = input("DO you want to be first or second? (f/s) ")
    if playerGoesFirst == 'f' or playerGoesFirst == 's':
        if playerGoesFirst == 'f':
            switchTurns('X', 'O', True, [['-', '-', '-'], ['-', '-', '-'], ['-', '-', '-']])
        if playerGoesFirst == 's':
            switchTurns('O', 'X', False, [['-', '-', '-'], ['-', '-', '-'], ['-', '-', '-']])
    else:
        print("Invalid!")
        chooseFirstOrSecond()


chooseFirstOrSecond()

让我给你举一个我玩的游戏的例子：

DO you want to be first or second? (f/s) s
         |         |         
    -    |    -    |    -    
         |         |         
---------|---------|---------
         |         |         
    -    |    -    |    -    
         |         |         
---------|---------|---------
         |         |         
    -    |    -    |    -    
         |         |         
Best move being calculated...

The value of the best move is -4. The best move is (1, 1)
The time it took the AI to find the best move is 1.8505730628967285 seconds.
The AI searched 59492 positions.
Deepest search is 9
Drawn is 17158 and won for player is 20451 and wonfor ai is 2820
         |         |         
    X    |    -    |    -    
         |         |         
---------|---------|---------
         |         |         
    -    |    -    |    -    
         |         |         
---------|---------|---------
         |         |         
    -    |    -    |    -    
         |         |         
Enter row: 1
Enter column: 3
         |         |         
    X    |    -    |    O    
         |         |         
---------|---------|---------
         |         |         
    -    |    -    |    -    
         |         |         
---------|---------|---------
         |         |         
    -    |    -    |    -    
         |         |         
Best move being calculated...

The value of the best move is -4. The best move is (2, 1)
The time it took the AI to find the best move is 0.04171943664550781 seconds.
The AI searched 1322 positions.
Deepest search is 7
Drawn is 17529 and won for player is 20903 and wonfor ai is 2862
         |         |         
    X    |    -    |    O    
         |         |         
---------|---------|---------
         |         |         
    X    |    -    |    -    
         |         |         
---------|---------|---------
         |         |         
    -    |    -    |    -    
         |         |         
Enter row: 3
Enter column: 1
         |         |         
    X    |    -    |    O    
         |         |         
---------|---------|---------
         |         |         
    X    |    -    |    -    
         |         |         
---------|---------|---------
         |         |         
    O    |    -    |    -    
         |         |         
Best move being calculated...

The value of the best move is -6. The best move is (2, 2)
The time it took the AI to find the best move is 0.0019884109497070312 seconds.
The AI searched 66 positions.
Deepest search is 5
Drawn is 17531 and won for player is 20939 and wonfor ai is 2862
         |         |         
    X    |    -    |    O    
         |         |         
---------|---------|---------
         |         |         
    X    |    X    |    -    
         |         |         
---------|---------|---------
         |         |         
    O    |    -    |    -    
         |         |         
Enter row: 2
Enter column: 3
         |         |         
    X    |    -    |    O    
         |         |         
---------|---------|---------
         |         |         
    X    |    X    |    O    
         |         |         
---------|---------|---------
         |         |         
    O    |    -    |    -    
         |         |         
Best move being calculated...

The value of the best move is 9. The best move is (3, 3)
The time it took the AI to find the best move is 0.0 seconds.
The AI searched 4 positions.
Deepest search is 3
Drawn is 17531 and won for player is 20941 and wonfor ai is 2862
         |         |         
    X    |    -    |    O    
         |         |         
---------|---------|---------
         |         |         
    X    |    X    |    O    
         |         |         
---------|---------|---------
         |         |         
    O    |    -    |    X    
         |         |         
AI wins!

(高于0是AI的胜利，低于0是玩家的胜利。)你可以清楚地看到，它说我一直赢到最后一个回合……我不知道为什么..。

Answer 1

我想你在alpha-beta修剪中翻转了一个比较运算符。具体来说，在if isMaxPlayer:分支中，

if alpha <= beta:
    break

应该是

if alpha >= beta:
    break