"""Jogo da velha contra minimax. Sem dependências. Execute: python jogo_da_velha.py"""
from functools import lru_cache
LINES = ((0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6))
def winner(board):
    for a,b,c in LINES:
        if board[a] != ' ' and board[a] == board[b] == board[c]:
            return board[a]
    return None
@lru_cache(maxsize=10000)
def minimax(board, turn):
    won = winner(board)
    if won: return 1 if won == 'O' else -1
    if ' ' not in board: return 0
    scores = []
    for i, value in enumerate(board):
        if value == ' ':
            next_board = board[:i] + (turn,) + board[i+1:]
            scores.append(minimax(next_board, 'X' if turn == 'O' else 'O'))
    return max(scores) if turn == 'O' else min(scores)
def best_move(board):
    board = tuple(board)
    if winner(board): return None
    moves = [i for i,v in enumerate(board) if v == ' ']
    return max(moves, key=lambda i:minimax(board[:i]+('O',)+board[i+1:], 'X')) if moves else None
def show(board):
    print()
    for row in range(3):
        print(' | '.join(board[i] if board[i] != ' ' else str(i+1) for i in range(row*3,row*3+3)))
        if row < 2: print('--+---+--')
def main():
    board = [' '] * 9
    print('Você é X. Escolha uma casa de 1 a 9. Q para sair.')
    while True:
        show(board)
        raw = input('Sua jogada: ').strip().lower()
        if raw == 'q': return
        if raw not in '123456789' or len(raw) != 1 or board[int(raw)-1] != ' ':
            print('Casa inválida ou ocupada.'); continue
        board[int(raw)-1] = 'X'
        if winner(board) or ' ' not in board: break
        board[best_move(board)] = 'O'
        if winner(board) or ' ' not in board: break
    show(board)
    won = winner(board)
    print(f'{won} venceu.' if won else 'Empate!')
if __name__ == '__main__':
    try: main()
    except (EOFError, KeyboardInterrupt): print('\nAté a próxima!')