def new_board():
	"""Create a tuple representing a tic-tac-toe board:
	- first element is the current player (0 or 1)
	- the other elements are three tuple representing the rows of the grid (which elements are 0 or 1 or None)
	"""
	return (0,
		(None,) * 3,
		(None,) * 3,
		(None,) * 3,
	)


def move(board, row_index, column_index):
	"""Create a new board where the current player has moved in the given position (zero-indexed) and the current player is updated.
	"""
	player, *grid = board
	try:
		row = grid[row_index]
		if row[column_index] is not None:
			raise ValueError
	except IndexError:
		raise ValueError("Illegal move: the position is not on the grid")
	except ValueError:
		raise ValueError("Illegal move: the cell is not empty")
	new_row = (player if j == column_index else x for j, x in enumerate(row))
	grid[row_index] = tuple(new_row)
	new_player = 1 - player
	return new_player, *grid


def legal_moves(board):
	"""Return a list of the free positions on the board if nobody has won, else an empty list.
	"""
	if winner(board) is not None:
		return []
	return [(i,j)
		for i, row in enumerate(board[1:])
		for j, x in enumerate(row)
		if x is None
	]


configurations = (
	tuple((i, i) for i in range(3)),
	tuple((i, 2-i) for i in range(3)),
	*(tuple((i, j) for j in range(3)) for i in range(3)),
	*(tuple((j, i) for j in range(3)) for i in range(3))
)

def winner(board):
	"""Return the winning player if somebody won else None.
	"""
	grid = board[1:]
	for player in range(2):
		if any(
			all(grid[i][j] == player for i, j in c)
			for c in configurations
		):
			return player
	return None


def engine(board, fuel = 2, memory = ({}, {}, {}), verbose = False):
	"""Simulate all moves from this position (iterating one time for each unit of fuel) and update memory.
	Return:
	- a winnig move if one is known
	- else a move not known, if any
	- else a move known to give a drawing game to the opponent, if any
	- else the first available move, if any
	- else None
	"""

	# is this a known position?
	for d in memory:
		if board in d:
			return d[board]

	moves = legal_moves(board)
	if verbose:
		print(f"\t{moves = }")

	# this is a final position
	if not moves:
		winning_player = winner(board)
		index = 2 if winning_player is None else winning_player
		memory[index][board] = None
		return None

	# memorize in depth analisys
	if fuel:
		for i, j in moves:
			new_board = move(board, i, j)
			engine(new_board, fuel - 1, memory, False)

	# choose next move
	player = board[0]
	draw, unknown = None, None
	for m in reversed(moves):
		i, j = m
		new_board = move(board, i, j)
		if new_board in memory[player]:
			if verbose:
				print(f"\t{m} wins")
			memory[player][board] = m
			return m
		if new_board in memory[1 - player]:
			if verbose:
				print(f"\t{m} loses")
			continue
		if new_board in memory[2]:
			if verbose:
				print(f"\t{m} draws, set")
			draw = m
			continue
		if verbose:
			print(f"\t{m} unknown, set")
		unknown = m
	if unknown is None:
		if draw is None:
			memory[1 - player][board] = moves[0]
			return moves[0]
		memory[2][board] = draw
		return draw
	return unknown


player_symbol = {0: 'X', 1: 'O', None: ' '}

def print_board(board):
	"""Print the game board.
	"""
	player, *grid = board
	print(player_symbol[player], "to move:")
	lines = [f' {" | ".join(player_symbol[x] for x in row)} ' for row in grid]
	print("\n---+---+---\n".join(lines))
	print()


def new_player(name = None):
	"""Return a function that asks the player a move and returns it, or the engine if no player name is provided.
	"""
	if name is None:
		return engine
	def player(board):
		print_board(board)
		move = None
		while move is None:
			move = input(f"player {name}, chose your move: ")
			move = move.split()
			if len(move) != 2:
				print("give two numbers, please")
				move = None
				continue
			if move[0] not in set("123") or move[1] not in set("123"):
				print("give values from 1 to 3, please")
				move = None
				continue
			x, y = map(int, move)	# convert from str to int
		return x-1, y-1
	player.name = name
	return player

def game(player1, player2, board = None):
	"""Run a game of tic-tac-toe (noughts and crosses) between player1 and player2
	"""
	board = new_board() if board is None else board
	players = player1, player2
	while legal_moves(board):
		player = players[board[0]]
		m = player(board)
		try:
			board = move(board, *m)
		except ValueError as e:
			print(e)
			continue
		print()
	print_board(board)
	winner_index = winner(board)
	if winner_index is None:
		message = "It's a draw!"
	else:
		try:
			name = players[winner_index].name
		except AttributeError:
			name = f"Player {winner_index + 1}"
		message = f"{name} is the winner!"
	print(message, end = "\n\n")

def main():
	"""Ask the player name and start a game against the computer.
	"""
	name = input("Set your name: ")
	human = new_player(name)
	computer = new_player()
	game(human, computer)

if __name__ == "__main__":
	main()