import copy

def evaluate(perspective, whose_turn, other_player, board):
  # perspective 'X' or 'O': who is running this simulated game and wants to win
  # whose_turn 'X' or 'O': in this simulated game, whose turn is it?
  # other_player 'X' or 'O': different from whose_turn
  # board is an N x N array of ' ', 'X', or 'O'
  w = winner(board)
  if w == whose_turn:
    if perspective == w:
      return +1
    else:
      return -1
  elif w != ' ':
    if perspective == w:
      return -1
    else:
      return +1
  else:
    loss = False
    tie = False
    win = False
    for pnb in possible_next_boards(board, other_player):
      e = evaluate(perspective, other_player, whose_turn, pnb)
      if e == -1:
        loss = True
      elif e == +1:
        win = True
      else:
        tie = True
    if win and not loss and not tie:
      return +1
    elif (win or tie) and not loss:
      return 0
    else:
      return -1

def winner(board):
  # I'm sure this could be done a lot more efficiently
  N = len(board)

  win = True
  first = board[0][0]
  for i in range(1, N):
    if board[i][i] != first:
      win = False
  if win and first != ' ':
    return first

  win = True
  first = board[0][N - 1]
  for i in range(1, N):
    if board[i][N - 1 - i] != first:
      win = False
  if win and first != ' ':
    return first

  for r in range(0, N):
    win = True
    first = board[r][0]
    for i in range(1, N):
      if board[r][i] != first:
        win = False
    if win and first != ' ':
      return first

  for c in range(0, N):
    win = True
    first = board[0][c]
    for i in range(1, N):
      if board[i][c] != first:
        win = False
    if win and first != ' ':
      return first

  return ' '

def ended(board):
  if winner(board) != ' ':
    return True
  N = len(board)
  for r in range(0, N):
    for c in range(0, N):
      if board[r][c] == ' ':
        return False
  return True

def possible_moves(board):
  N = len(board)
  result = []
  for r in range(0, N):
    for c in range(0, N):
      if board[r][c] == ' ':
        result.append((r, c))
  return result

def move(board, whose_turn, rowcol):
  board = copy.deepcopy(board)
  board[rowcol[0]][rowcol[1]] = whose_turn
  return board

def utility(board, player):
  w = winner(board)
  if w == player:
    return +1
  elif w == ' ':
    return 0
  else:
    return -1

def minimax(board, perspective, whose_turn, other_player):
  if ended(board):
    return (utility(board, perspective), None)
  max_score = -2
  min_score = +2
  max_move = None
  min_move = None
  for rowcol in possible_moves(board):
    new_board = move(board, whose_turn, rowcol)
    (score, the_move) = minimax(new_board, perspective, other_player, whose_turn)
    if score > max_score:
      max_score = score
      max_move = rowcol
    if score < min_score:
      min_score = score
      min_move = rowcol
  if whose_turn == perspective:
    return (max_score, max_move)
  else:
    return (min_score, min_move)

def new_board(N):
  return [ [' '] * N for i in range(0, N) ]

def play(N, human = 'A'):
  board = new_board(N)
  whose_turn = 'X'
  other_player = 'O'
  if whose_turn == human:
    print_board(board)
  moves = 0
  while True:
    poss = empty_spaces(board)
    if not poss:
      print("tie")
      break
    if whose_turn == human:
      print("your move (row then column, both 0 to ", N, ")? ", sep = "", end = "")
      rc = input().split()
      if len(rc) == 2 and rc[0].isdigit() and rc[1].isdigit():
        r = int(rc[0])
        c = int(rc[1])
      else:
        r = -1
      empties = empty_spaces(board)
      if r < 0 or r >= N or c < 0 or c >= N or (r, c) not in empties:
        print("invalid move")
        continue
      rowcol = (r, c)
    else:
      (score, rowcol) = minimax(board, whose_turn, whose_turn, other_player)
    next = move(board, whose_turn, rowcol)
    moves += 1
    print("result of move", moves)
    print_board(next)
    result = winner(next)
    if result != ' ':
      print(result, "won")
      break
    (whose_turn, other_player) = (other_player, whose_turn)
    board = next

def print_board(board):
  N = len(board)
  bar = "-+" * (N - 1) + "-"
  print("|".join(board[0]))
  for i in range(1, N):
    print(bar)
    print("|".join(board[i]))
  print()
  
def empty_spaces(board):
  N = len(board)
  empties = []
  for r in range(0, N):
    for c in range(0, N):
      if board[r][c] == ' ':
        empties.append((r, c))
  return empties