Python实现无敌井字棋：MiniMax算法评估值异常问题

Let's walk through the issues in your Tic-Tac-Toe Minimax code and fix them so your evaluation values work correctly:

Key Problems in Your Original Code #

1. Evaluation Function Returns None
   Your evaluation function only handles three cases (human wins, robot wins, tie) but doesn’t return anything when the game is still ongoing (there are empty spots left). Python defaults to returning None for functions with no explicit return, which breaks the Minimax recursion—since you’re trying to compare None with numeric values, the whole chain ends up returning None.

2. Misused & Uninitialized empty_spots

   • You never initialized the empty_spots list before appending to it in empty_spots_func, which would throw an error on first run.
   • You called minimax before populating empty_spots, so the function started with an empty list—meaning no recursive loops ran, and you got incorrect results.
   • Using a global empty_spots variable is risky here: when you make/undo moves in recursion, the global list won’t update to reflect the current board state, leading to invalid moves.

3. Incorrect Minimax Termination Logic
   You checked for depth <=0 first, but you should prioritize checking if the game is already over (win/tie) regardless of depth. If the game ends, recursion should stop immediately—no need to keep going even if depth is still positive.

4. Redundant Parameter
   The first spot parameter in your minimax function is unused (you loop through all empty spots anyway), so it’s just cluttering the code.

Fixed Code #

board = ["O", 1, "X", "X", 4, "X", 6, "O", "O"]
human = "O"
robot = "X"

# Check if a player has won
def winning(board, player):
    # Horizontal, diagonal, vertical win conditions
    return (
        # Horizontal
        (board[0] == player and board[1] == player and board[2] == player) or
        (board[3] == player and board[4] == player and board[5] == player) or
        (board[6] == player and board[7] == player and board[8] == player) or
        # Diagonal
        (board[0] == player and board[4] == player and board[8] == player) or
        (board[2] == player and board[4] == player and board[6] == player) or
        # Vertical
        (board[0] == player and board[3] == player and board[6] == player) or
        (board[1] == player and board[4] == player and board[7] == player) or
        (board[2] == player and board[5] == player and board[8] == player)
    )

# Get list of empty spots (returns indices where value is an integer)
def get_empty_spots(board):
    return [i for i in range(len(board)) if isinstance(board[i], int)]

def minimax(board, depth, maximizing_player):
    # First check terminal states (game over)
    if winning(board, human):
        return +10  # Human wins, bad for robot
    if winning(board, robot):
        return -10  # Robot wins, good for robot
    if len(get_empty_spots(board)) == 0:
        return 0  # Tie

    # Stop recursion if depth is exhausted
    if depth <= 0:
        return 0  # For tic-tac-toe, no heuristic needed here

    if maximizing_player:
        max_eval = -float('inf')
        for spot in get_empty_spots(board):
            # Make the move
            board[spot] = robot
            # Recurse to evaluate this move
            eval = minimax(board, depth - 1, False)
            # Undo the move (backtrack)
            board[spot] = spot
            # Update the best evaluation
            max_eval = max(max_eval, eval)
        return max_eval
    else:
        min_eval = float('inf')
        for spot in get_empty_spots(board):
            # Make human's move
            board[spot] = human
            # Recurse
            eval = minimax(board, depth - 1, True)
            # Undo move
            board[spot] = spot
            # Update worst-case evaluation
            min_eval = min(min_eval, eval)
        return min_eval

# Test the function correctly
empty_spots = get_empty_spots(board)
test_eval = minimax(board, len(empty_spots), True)
print(f'The best move evaluation is: {test_eval}')

What Changed & Why #

• No More None Returns: The Minimax function now only returns numeric values for all terminal states and depth-limited stops. We removed the separate evaluation function and integrated terminal state checks directly into Minimax for clarity.
• Dynamic Empty Spots: get_empty_spots returns a fresh list of empty indices every time it’s called, based on the current board state—no more global variable bugs.
• Correct Termination: We check for game over first, so recursion stops as soon as someone wins or ties, regardless of depth.
• Cleaner Parameters: Removed the unused spot parameter and stopped passing empty_spots around, since we calculate it on the fly.

Now when you run the code, you’ll get a valid numeric evaluation instead of None, and the Minimax logic will properly simulate optimal play from both sides.

内容的提问来源于stack exchange，提问作者Hasanat Jahan