python - 无限递归调用极小极大算法

Question

我最近实现了使用极小极大算法的4X4 tic tac toe 游戏的代码。然而，我的 minimax 函数正在递归地调用自身无限否。次。

初始棋盘 (4X4) 井字游戏 ->

board = np.array([['_','_','_', '_'],['_','_','_', '_'],['_','_','_', '_'],['_','_','_', '_']])

计算机轮流代码 ->

import math
from utility import *

def minimax(board, spotsLeft, maximizing):
    bestIdx = (0,0)
    p1 = 'X'
    p2 = 'O'
    res, stat = checkGameOver(board, spotsLeft)
    if res==True:
        if stat == 'X': return 17-spotsLeft, bestIdx
        elif stat == 'O': return -17+spotsLeft, bestIdx
        else: return 0, bestIdx
    
    if maximizing:
        # return max score
        bestMove = -math.inf
        for i in range(4):
            for j in range(4):
                if board[i][j] == '_':
                    board[i][j] = p1
                    score, idx = minimax(board, spotsLeft-1, False)
                    print(score, idx)
                    board[i][j] = '_'
                    if bestMove<score:
                        bestMove = score
                        bestIdx = (i,j)
        return bestMove, bestIdx
    else:
        # return min score
        bestMove = math.inf
        for i in range(4):
            for j in range(4):
                if board[i][j] == '_':
                    board[i][j] = p2
                    score, idx = minimax(board, spotsLeft-1, True)
                    print(score, idx)
                    board[i][j] = '_'
                    if bestMove>score:
                        bestMove = score
                        bestIdx = (i,j)
        return bestMove, bestIdx
    

def ai(board):
    spotsLeft = 16
    p1 = 'X'    # Computer
    p2 = 'O'    # Player
    turn = p1
    while True:
        res, stat = checkGameOver(board, spotsLeft)
        if res==False:
            if turn == p1:
                # AI
                boardCopy = board[:]
                score, idx = minimax(boardCopy, spotsLeft, True)
                board[idx[0]][idx[1]] = turn
                turn = p2
                spotsLeft-=1
            else:
                # Human
                inp = int(input(f"Your turn: "))
                i, j = spotToIdx(inp)
                if board[i][j]=='_':
                    board[i][j] = turn
                    turn = p1
                    spotsLeft-=1
        else: return stat
        printBoard(board)

在上面的代码中spotsLeft 是船上的空位，checkGameOver 返回“X”(如果玩家 X 获胜)，返回“O”(如果玩家 O 获胜)并返回“T”(如果比赛平局)

checkGameOver 函数 ->

def checkWin(board):
    # Check Row
    for i in board:
        if len(set(i)) == 1 and i[0]!='_':
            return i[0]
        
    # Check Column
    for i in range(4):
        if (board[0][i] == board[1][i] == board[2][i] == board[3][i]) and board[0][i]!='_':
            return board[0][i]
    
    # Check Diagonals
    if (board[0][0]==board[1][1]==board[2][2]==board[3][3]) and board[0][0]!='_':
            return board[0][0]
    if (board[0][3]==board[1][2]==board[2][1]==board[3][0]) and board[0][3]!='_':
        return board[0][3]
    
    # No One Won Yet
    return -1
    

def checkGameOver(board, spotsLeft):
    # t -> Game Tied
    # x -> Player X won
    # o -> Player O won
    
    # if tied - all spots filled
    if spotsLeft == 0:
        return True, 'T'
    
    # if any player won the game
    result = checkWin(board)
    if result!=-1:
        return True, result
    
    return False, -1

Answer 1

我认为你的代码很好，并且可以做你想做的事情。该问题很可能是由于问题的复杂性造成的，对于较低维度的井字游戏，它会工作得很好。

让我们首先简化并查看 2x2 的情况。对于第一轮，您从 ai 函数调用 minimax，该函数将在第一级调用自身 4 次。在下一级别，这些调用中的每一个也将调用 minimax，但比上一级别少一次。将其作为列表:

• 级别 0(ai 函数):1 次调用 minimax
• 级别 1:4 次调用
• 第 2 级:4x3 调用(上述 4 个调用中的每一个调用都会进行 3 个新调用)
• 第 3 级:4x3x2 调用
• 第 4 级:4x3x2x1 调用

现在使用 n 阶乘表示法作为 n!，我们可以将调用总数计算为:

4!/4! + 4!/(4-1)! + 4!/(4-2)! + 4!/(4-3)! + 4!/(4-4!)

这是 0 和 n 之间 k 的 n!/(n-k)! 之和(包括)，n以板上的单元数开始。这里的结果是 2x2 板对 minimax 的调用 65 次。

放入Python代码:

def factorial(n):
    if n > 1: return n*factorial(n-1)
    else: return 1

def tictactoeComplexity(gridsize):
    return sum([factorial(gridsize)/factorial(gridsize-k) for k in range(gridsize+1)])

print(tictactoeComplexity(2*2)) # result is 65

现在让我们检查一下 3*3 板:

print(tictactoeComplexity(3*3)) # result is 986,410

仅仅从 2x2 到 3x3，我们就从大约 100 增加到大约 1,000,000。您可以猜测 4x4 棋盘的结果:

print(tictactoeComplexity(4*4)) # result is 56,874,039,553,217

所以你的程序做了你要求它做的事情，但你要求的太多了。