Minimax: An AI That Never LosesMinimax: یاریزانێکی ژیر کە هەرگیز نادۆڕێت

# The score of a FINISHED game. Save next to tic_tac_toe.py.
from tic_tac_toe import player_won


def evaluate_board(board):
    if player_won(board, 'x'):
        return 1                        # x (the AI) has won
    if player_won(board, 'o'):
        return -1                       # o (the human) has won
    return 0                            # a draw


x_wins = [['x', 'x', 'x'],
          ['o', 'o', ' '],
          [' ', ' ', ' ']]
o_wins = [['x', 'x', 'o'],
          [' ', 'o', ' '],
          ['o', 'x', ' ']]
a_draw = [['x', 'o', 'x'],
          ['x', 'o', 'o'],
          ['o', 'x', 'x']]
print(evaluate_board(x_wins), evaluate_board(o_wins), evaluate_board(a_draw))

# First version, as in the course: every win scores +1 (improved later).
# The AI plays 'x' (the MAX player), the human plays 'o' (the MIN player).
# Save this file in the same folder as tic_tac_toe.py (previous lesson).
from tic_tac_toe import print_board, can_insert, player_won, draw, read_move


def evaluate_board(board):
    if player_won(board, 'x'):
        return 1                        # x (the AI) has won
    if player_won(board, 'o'):
        return -1                       # o (the human) has won
    return 0                            # a draw


count = [0]                             # how many positions minimax visited


def minimax(board, is_maximizing_player):
    count[0] += 1
    if player_won(board, 'x') or player_won(board, 'o') or draw(board):
        return evaluate_board(board)    # the game is over: give its score

    if is_maximizing_player:            # x's turn: take the HIGHEST score
        best_score = -float('inf')
        for row in range(3):
            for col in range(3):
                if board[row][col] == ' ':
                    board[row][col] = 'x'               # try the move
                    score = minimax(board, False)       # o answers
                    board[row][col] = ' '               # undo the move
                    best_score = max(best_score, score)
        return best_score
    else:                               # o's turn: take the LOWEST score
        best_score = float('inf')
        for row in range(3):
            for col in range(3):
                if board[row][col] == ' ':
                    board[row][col] = 'o'
                    score = minimax(board, True)        # x answers
                    board[row][col] = ' '
                    best_score = min(best_score, score)
        return best_score


def find_best_move(board):
    best_move = None
    best_score = -float('inf')
    for row in range(3):
        for col in range(3):
            if board[row][col] == ' ':
                board[row][col] = 'x'
                score = minimax(board, False)
                board[row][col] = ' '
                if score > best_score:  # keeps the FIRST of equal scores
                    best_score = score
                    best_move = (row, col)
    return best_move


def main():
    board = [[' ', ' ', ' '] for _ in range(3)]
    player = 'x'                        # the AI starts
    while True:
        print_board(board)
        if player == 'x':
            count[0] = 0
            row, col = find_best_move(board)
            can_insert(board, row, col, 'x')
            print(f"AI plays {row} {col} (positions examined: {count[0]})")
        else:
            row, col = read_move(player)
            if not can_insert(board, row, col, player):
                print("Invalid move. Try again.")
                continue
        if player_won(board, player):
            print_board(board)
            print(f"Player {player} wins!")
            break
        if draw(board):
            print_board(board)
            print("It's a draw!")
            break
        player = 'o' if player == 'x' else 'x'


if __name__ == "__main__":
    main()

# Does the AI take a win that is available RIGHT NOW?
# Save next to tic_tac_toe.py and minimax_ai.py.
from tic_tac_toe import player_won, draw
from minimax_ai import minimax          # the old version: +1 / 0 / -1


def minimax_depth(board, depth, is_maximizing_player):
    """Like minimax, but a FASTER win scores higher."""
    if player_won(board, 'x'):
        return 10 - depth               # win at depth 1 -> 9, at depth 3 -> 7
    if player_won(board, 'o'):
        return depth - 10               # a later loss is less bad
    if draw(board):
        return 0
    scores = []
    for row in range(3):
        for col in range(3):
            if board[row][col] == ' ':
                board[row][col] = 'x' if is_maximizing_player else 'o'
                scores.append(minimax_depth(board, depth + 1,
                                            not is_maximizing_player))
                board[row][col] = ' '
    return max(scores) if is_maximizing_player else min(scores)


def find_best_move_depth(board):
    best_move, best_score = None, -float('inf')
    for row in range(3):
        for col in range(3):
            if board[row][col] == ' ':
                board[row][col] = 'x'
                score = minimax_depth(board, 1, False)  # x's move = depth 1
                board[row][col] = ' '
                if score > best_score:
                    best_move, best_score = (row, col), score
    return best_move


def show_scores(board):
    for row in range(3):
        for col in range(3):
            if board[row][col] == ' ':
                board[row][col] = 'x'
                old = minimax(board, False)
                new = minimax_depth(board, 1, False)
                board[row][col] = ' '
                print(f"  x at {row} {col}: old score {old:2}, new score {new:2}")
    print("  the new AI plays", find_best_move_depth(board))


if __name__ == "__main__":
    for rows in (["  x", "oxo", "ox "], ["   ", "  x", "oox"]):
        board = [list(r) for r in rows]
        print("board rows:", rows)
        show_scores(board)

# Three difficulty levels. Save next to tic_tac_toe.py.
import random
from tic_tac_toe import print_board, can_insert, player_won, draw, read_move

LINES = ([[(r, 0), (r, 1), (r, 2)] for r in range(3)] +          # rows
         [[(0, c), (1, c), (2, c)] for c in range(3)] +          # columns
         [[(0, 0), (1, 1), (2, 2)], [(0, 2), (1, 1), (2, 0)]])   # diagonals


def estimate(board):
    """Evaluation function: lines x can still complete minus lines o can."""
    x_open = sum(1 for line in LINES if all(board[r][c] != 'o' for r, c in line))
    o_open = sum(1 for line in LINES if all(board[r][c] != 'x' for r, c in line))
    return (x_open - o_open) / 10       # always between -1 and 1


def minimax(board, depth, is_maximizing, max_depth):
    if player_won(board, 'x'):
        return 10 - depth
    if player_won(board, 'o'):
        return depth - 10
    if draw(board):
        return 0
    if depth >= max_depth:              # not finished, but we stop looking
        return estimate(board)
    scores = []
    for row in range(3):
        for col in range(3):
            if board[row][col] == ' ':
                board[row][col] = 'x' if is_maximizing else 'o'
                scores.append(minimax(board, depth + 1, not is_maximizing,
                                      max_depth))
                board[row][col] = ' '
    return max(scores) if is_maximizing else min(scores)


def find_best_move(board, level):
    empty = [(r, c) for r in range(3) for c in range(3) if board[r][c] == ' ']
    if level == 'easy':
        return random.choice(empty)               # any free cell
    max_depth = 2 if level == 'medium' else 9     # medium: 2 moves ahead
    best_move, best_score = None, -float('inf')
    for row, col in empty:
        board[row][col] = 'x'
        score = minimax(board, 1, False, max_depth)
        board[row][col] = ' '
        if score > best_score:
            best_move, best_score = (row, col), score
    return best_move


def ask_level():
    while True:
        level = input("Choose difficulty (easy, medium, hard): ").strip().lower()
        if level in ('easy', 'medium', 'hard'):
            return level
        print("Please type easy, medium or hard.")


def main():
    level = ask_level()
    board = [[' ', ' ', ' '] for _ in range(3)]
    player = 'x'
    while True:
        print_board(board)
        if player == 'x':
            row, col = find_best_move(board, level)
            can_insert(board, row, col, 'x')
            print(f"AI ({level}) plays {row} {col}")
        else:
            row, col = read_move(player)
            if not can_insert(board, row, col, player):
                print("Invalid move. Try again.")
                continue
        if player_won(board, player):
            print_board(board)
            print(f"Player {player} wins!")
            break
        if draw(board):
            print_board(board)
            print("It's a draw!")
            break
        player = 'o' if player == 'x' else 'x'


if __name__ == "__main__":
    main()

# Can a human beat the "medium" AI? Try EVERY possible human reply.
# Save next to difficulty.py.
import difficulty


def count_results(board, results):
    """The AI (x) moves, then we try each possible reply of o."""
    row, col = difficulty.find_best_move(board, 'medium')
    board[row][col] = 'x'
    if difficulty.player_won(board, 'x'):
        results['AI wins'] += 1
    elif difficulty.draw(board):
        results['draw'] += 1
    else:
        for r in range(3):
            for c in range(3):
                if board[r][c] == ' ':
                    board[r][c] = 'o'
                    if difficulty.player_won(board, 'o'):
                        results['human wins'] += 1
                    elif difficulty.draw(board):
                        results['draw'] += 1
                    else:
                        count_results(board, results)
                    board[r][c] = ' '
    board[row][col] = ' '


for label, estimate in [("medium WITHOUT evaluation", lambda board: 0),
                        ("medium WITH evaluation", difficulty.estimate)]:
    difficulty.estimate = estimate      # swap the evaluation function
    results = {'AI wins': 0, 'draw': 0, 'human wins': 0}
    count_results([[' ', ' ', ' '] for _ in range(3)], results)
    print(label, results)