#!/usr/bin/env python

# Monte Carlo Tic Tac Toe
# Thomas Liu
# May 14, 2009

import random

# 1: X
# 0: empty
# -1: O

pieces = {1: 'X', 0: '-', -1: 'O'}

# Pretty print the board
def print_board(board):
	out = ""
	for x in range(3):
		for y in range(3):
			out += pieces[board[x][y]]
			if y < 2:
				out += "|"
		if x < 2:
			out += "\n"
	print out


# Is the game over?
def is_board_full(board):
	for x in range(3):
		for y in range(3):
			if board[x][y] == 0:
				return False
	return True

# -1 for O, 1 for X, 0 for tie or no win
def get_result(board):
	# Horizontal rows 
	for x in range(3):
		total = board[x][0] + board[x][1] + board[x][2]
		if abs(total) == 3:
			return total/3

	# Vertical rows
	for y in range(3):
		total = board[0][y] + board[1][y] + board[2][y]
		if abs(total) == 3:
			return total/3

	# Diagonal, NW to SE
	total = board[0][0] + board[1][1] + board[2][2]
	if abs(total) == 3:
		return total/3

	# Diagonal, NE to SW
	total = board[2][0] + board[1][1] + board[0][2]
	if abs(total) == 3:
		return total/3

	return 0

def copy_board(board1, board2):
	for x in range(3):
		for y in range(3):
			board2[x][y] = board1[x][y]

class GameTreeNode:

	def __init__(self, parent, board, last_move):
		self.board = [[0, 0, 0],[0, 0, 0],[0, 0, 0]]
		copy_board(board, self.board)
		self.parent = parent
		self.children = []
		self.last_move = last_move
		self.wins = 0
		self.losses = 0
		self.ties = 0

	def add_child(self, child_node):
		self.children.append(child_node)
	
def get_random_move(board):
	random.seed()
	x = random.randrange(0, 3)
	y = random.randrange(0, 3)
	if board[x][y] == 0:
		return (x, y)
	
	return get_random_move(board)


class ComputerTicTacToe:

	def __init__(self, color, sims):
		self.sims = sims
		self.color = color
		self.game_tree = None
	
	# Find a best move given a board
	def find_best_move(self, board):
		
		print "Computer is thinking..."

		# start a tree.
		self.game_tree = GameTreeNode(None, board, None)
	
		for x in range(3):
			for y in range(3):
				if board[x][y] == 0:
					board[x][y] = self.color
					self.game_tree.add_child(GameTreeNode(self.game_tree, board, (x,y)))
					# restore the board
					board[x][y] = 0
	
		results = []
		for node in self.game_tree.children:
			results.append(self.simulate_games(self.sims, node))
	
		best_node = results[0]
		best = best_node.wins - best_node.losses + 0.5 * best_node.ties
		for node in results:
			#print node.last_move, " - ", node.wins, "/", node.losses, "/", node.ties, " - ", node.wins - node.losses + 0.5 * node.ties 
			if node.wins - node.losses + 0.5 * node.ties > best:
				best = node.wins - node.losses + 0.5 * node.ties
				best_node = node

		return best_node.last_move

	def simulate_games(self, num_games, node):
		for games in range(num_games):
			board = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
			copy_board(node.board, board)
					
			# play a random game until the board is full or there is a winner
			curr_color = self.color 
			
			while is_board_full(board) == False and get_result(board) == 0:
				curr_color = curr_color * -1
				x, y = get_random_move(board)
				board[x][y] = curr_color
			
			# tally wins and losses
			if get_result(board) == self.color:
				node.wins += 1

			if get_result(board) == self.color * -1:
				node.losses += 1

			if get_result(board) == 0:
				node.ties += 1
		
		if node.losses == 0 and node.wins == 0:
			node.losses = 10000
			node.wins = 1
		if node.losses == 0:
			node.losses = 1
		return node


# play with thec computer
valid_input = ['1', '2', '3', '4', '5', '6', '7', '8', '9']
global_board = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]

user_color = random.randrange(2)
if user_color == 0:
	user_color = -1
else:
	user_color = 1


computer = ComputerTicTacToe(user_color * -1, 250)
print "You are", pieces[user_color]
print "Computer is", pieces[computer.color]

if user_color == -1:
	x, y = computer.find_best_move(global_board)
	global_board[x][y] = computer.color
	print "Computer plays at", x, ",", y


while is_board_full(global_board) == False and get_result(global_board) == 0:
	print_board(global_board)
	inp = raw_input("Your move (1-9): ")
	if inp not in valid_input:
		continue
	move = int(inp)
	x = (move - 1) / 3
	y = (move - 1) % 3
	if global_board[x][y] == 0:
		global_board[x][y] = user_color
		if is_board_full(global_board) == True or get_result(global_board) != 0:
			continue
		x, y = computer.find_best_move(global_board)
		global_board[x][y] = computer.color


print_board(global_board)
print
if get_result(global_board) == -1 * user_color:
	print "You lose!"
elif get_result(global_board) == 0:
	print "Tie!"
else:
	print "You win!"

print