import math

class State:
    def __init__(self, board=None, player='X'):
        if board is None:
            self.board = [[' ' for _ in range(3)] for _ in range(3)]
        else:
            self.board = [row[:] for row in board]
        self.player = player

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

def actions(state):
    actions = []
    for i in range(0,3):
        for j in range(0,3):
            if(state.board[i][j]==' '):
                actions.append((i,j))
    return actions

def result(state, action):
    #board = state.board.copy()
    state.board[action[0]][action[1]]=state.player
    return state

def terminal(state):
    if(utility(state)==0 | utility(state)==1 | utility(state)==-1):
        return True
    return False

def utility(state):
    winStates = [
        ((0,0),(0,1),(0,2)),((1,0),(1,1),(1,2)),((2,0),(2,1),(2,2)),
        ((0,0),(1,0),(2,0)),((0,1),(1,1),(2,1)),((0,2),(1,2),(2,2)),
        ((0,0),(1,1),(2,2)),((0,2),(2,2),(2,0))
        ]
    winner=None
    for a,b,c in winStates:
        if((state.board[a[0]][a[1]]==state.board[b[0]][b[1]]) & (state.board[b[0]][b[1]]==state.board[c[0]][c[1]]) & (state.board[b[0]][b[1]] != ' ')):
            winner=state.board[b[0]][b[1]]
    if(winner=='X'):
        return 1
    elif(winner=='O'):
        return -1
    return 0

def max_value(state):
    if(terminal(state)):
        return utility(state)
    v=float('-inf')
    for a in actions(state):
        currentState = result(state, a)
        v=max(v,min_value(currentState))
    return v

def min_value(state):
    if(terminal(state)):
        return utility(state)
    v=float('inf')
    for a in actions(state):
        currentState = result(state, a)
        v=min(v,max_value(currentState))
    return v

def minimax(state):
    v=float('-inf')
    drawMove = actions(state)[0]
    winMove = actions(state)[0]
    for a in actions(state):
        currentState = result(state, a)
        v=max(v,min_value(currentState))
        if(v>=1):
            winMove=a
        else: drawMove=a
    if(v>=1): return winMove
    else: return drawMove
    

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

    while not terminal(state):
        if state.player == 'O':
            row, col = map(int, input("Enter row and col (0-2 space separated): ").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)

        state.display()

    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()