最小极大算法不适用于深度>1

Question

我正在 python 上做一个棋盘游戏，我需要在其中实现算法最小值。当我尝试增加搜索深度时，我的程序停止工作。我也尝试实施 alpha beta 削减，但它似乎无法正常工作。当我尝试其他深度值时，它开始进行无效播放，并且还出现此错误：

r = len(Matrix)

TypeError: object of type 'NoneType' has no len()

以下是我的代码:

def AIPlayerMove(board: Board, depth, MaxPlayer: bool, PlayerIndex: int):
if depth == 0:
    # value = board.BoardValue()
    return board.BoardMatrix

if MaxPlayer == True:
    # print("Search Max\n")
    BoardNodes = FecthChildNodes(board, PlayerIndex)
    results = []
    BestMatrix = None
    for BN in range(len(BoardNodes)):    
        results.append(AIPlayerMove(BoardNodes[BN], depth-1, False, PlayerIndex*-1))
    for r in range(len(results)):
        if r == 0:
            m = results[r]
            BestMatrix = m
        else:
            m = results[r]
            v1 = CountElementsOfMatrix(m)
            v2 = CountElementsOfMatrix(BestMatrix)
            if v1 > v2:
                BestMatrix = m
    #print(BestMatrix)
    return BestMatrix
else:
    # print("Search Min\n")
    BoardNodes = FecthChildNodes(board, PlayerIndex)
    results = []
    WorstMatrix = None
    for BN in range(len(BoardNodes)):
        results.append(AIPlayerMove(BoardNodes[BN], depth-1, True, PlayerIndex*-1))
        #WorstMatrix = results[0]
    for r in range(len(results)):
        if r == 0:
            m = results[r]
            WorstMatrix = m
        else:
            m = results[r]
            v1 = CountElementsOfMatrix(m)
            v2 = CountElementsOfMatrix(WorstMatrix)
            if v1 < v2:
                    WorstMatrix = m
    print(WorstMatrix)
    return WorstMatrix

阿尔法测试版修剪：

def AIPlayerMoveAlphaBeta(board: Board, depth, MaxPlayer: bool, PlayerIndex: int, Alpha, Beta):
if depth == 0:
    # value = board.BoardValue()
    return board.BoardMatrix

if MaxPlayer == True:
    BoardNodes = FecthChildNodes(board, PlayerIndex)
    results = []
    BestMatrix = None
    for BN in range(len(BoardNodes)):
        results.append(AIPlayerMoveAlphaBeta(BoardNodes[BN], depth-1, False, PlayerIndex*-1, Alpha, Beta))
    for r in range(len(results)):
        if r == 0:
            m = results[r]
            BestMatrix = m
        else:
            v2 = CountElementsOfMatrix(BestMatrix)
            alpha = max(Alpha, v2)
            if Beta <= alpha:
                print("Break Max")
                break
            # check alpha beta for best scenario of player Beta <= Alpha
            m = results[r]
            v1 = CountElementsOfMatrix(m)
            if v1 > v2:
                BestMatrix = m
    return BestMatrix
else:
    BoardNodes = FecthChildNodes(board, PlayerIndex)
    results = []
    WorstMatrix = None
    for BN in range(len(BoardNodes)):
        results.append(AIPlayerMoveAlphaBeta(BoardNodes[BN], depth-1, True, PlayerIndex*-1, Alpha, Beta))
    #print(results)
    for r in range(len(results)):
        if r == 0:
            m = results[r]
            WorstMatrix = m
        else:
            v2 = CountElementsOfMatrix(WorstMatrix)
            beta = min(Beta, v2)
            if beta <= Alpha:
                print("Break Min")
                break
            # check alpha beta for Worst scenario of player Beta > Alpha
            m = results[r]
            v1 = CountElementsOfMatrix(m)
            if v1 < v2:
                WorstMatrix = m
    return WorstMatrix

辅助功能：

def FecthChildNodes(board: Board, PlayerIndex: int):
TestBoards = []
for row in range(board.row_count):
    for column in range(board.column_count):
        # Check if player is according to index
        if board.BoardMatrix[row][column] == PlayerIndex:
            # Check for Tangent Movements
            TangentPositions = board.GetAvailableTangentPositions((row, column))
            for p in range(len(TangentPositions)):
                tempBoard: Board = Board(board.row_count, board.column_count)
                tempBoard.ChangeMatrixValuesWithMatrix(board.BoardMatrix)
                tempBoard.MakeNewPieceAt(TangentPositions[p], PlayerIndex)
                tempBoard.CatchPiece(TangentPositions[p], PlayerIndex)
                TestBoards.append(tempBoard)
                # tempBoard.DrawBoardTerminal()
            # Check for Long Movements
            LongPositions = board.GetAvailableTagentPositionsMovement((row, column))
            for p in range(len(LongPositions)):
                tempBoard: Board = Board(board.row_count, board.column_count)
                tempBoard.ChangeMatrixValuesWithMatrix(board.BoardMatrix)
                tempBoard.MovePieceTo((row, column), LongPositions[p], PlayerIndex)
                tempBoard.CatchPiece(LongPositions[p], PlayerIndex)
                TestBoards.append(tempBoard)
                # tempBoard.DrawBoardTerminal()
return TestBoards

启发式功能：

def CountElementsOfMatrix(Matrix):
    r = len(Matrix)
    c = len(Matrix[0])
    counter = 0
    for row in range(r):
        for col in range(c):
            counter += Matrix[row][col]
    return counter

Answer 1

当您到达无法移动的状态时（也许游戏只是结束了？），然后FetchChildNodes返回一个空列表，这会导致AIPlayer移动返回无，这会导致错误。