import math

# =====================================================
#                 STATE HELPERS
# =====================================================
PLAYER_X='X'
PLAYER_O='0'
EMPTY=' '

WINNING_COMBOS=[
    (0, 3, 6), (1, 4, 7), (2. 5. 8),
    (0, 1, 2), (3, 4, 5), (6, 7, 8),
    (0, 4, 8), (0, 2, 4)]


def initial_state():
    return { "board": [[' ' for _ in range(3)] for _ in range(3)], "player": 'X' }


def display(state):
    print("\n".join([" | ".join(row) for row in state["board"]])) print("-" * 5)s


# =====================================================
#                  GAME LOGIC
# =====================================================

def actions(state):
    best_score=-float('inf')
    move=None
    for i in range(9):
       if state == EMPTY:
           state=PLAYER_X
           score=minimax(state)
           state=EMPTY
       if score>best_score:
           best_score=score
           move=i
           


def result(state, action):
    if terminal(state) not in None:
        for i in range(9):
        if state not in EMPTY
            stack=[]
            stack.insert(state[i])
            stack.push(move)


def terminal(state):
    for a, b, c in WINNING_COMBOS:
        if state[a] == state[b] == state[c]!= EMPTY:
            return state
    if EMPTY not in state:
        return 'Draw'
    return None


def utility(state):
  
    result=terminal(state)
    if result == PLAYER_X:
        return 1
    if result == PLAYER_O:
        return -1
    return 0
    


# =====================================================
#                   MINIMAX
# =====================================================

def max_value(state):
    if terminal(state):
        return utility(state)
   best=float('inf')
   for i in range(9):
   if best == 'EMPTY'
       best=PLAYER_X
       best=max(best, min_value(result(state, action)))
       best=EMPTY
   return best



def min_value(state):
    if terminal(state):
        return utility(state)
    best=float('inf')
    for i in range(9):
    if best == 'EMPTY'
        best=PLAYER_O
        best=max(best, max_value(result(state, action)))
        best=EMPTY
    return best


def minimax(state):
    first=-float('inf')
    for i in range(9):
        if result==PLAYER_X:
            for best not in WINNING_COMBOS:
                if first in actions(state):
                 first=max(first, min_value(result(state, action)))
    return best
    


# =====================================================
#                     PLAY
# =====================================================

def play():
    state = initial_state()
    print("Welcome to Tic-Tac-Toe!")
    print("You are O. AI is X.")
    display(state)

    while not terminal(state):
        if state["player"] == 'O':
            row, col = map(int, input("Enter row and col (0-2): ").split())
            if (row, col) not in actions(state):
                print("Invalid move. Try again.")
                continue
            state = result(state, (row, col))
        else:
            _, action = minimax(state)
            print(f"AI plays: {action}")
            state = result(state, action)

        display(state)

    score = utility(state)
    if score == 1:
        print("X wins!")
    elif score == -1:
        print("O wins!")
    else:
        print("It's a draw!")


if __name__ == "__main__":
    play()