# Python 2.7.7 Code
# Jonathan Frech, 31st of March 2017
#          edited  1st of April 2017

# import
import random, sys, time

# determine whose turn it is
turn = lambda board: not board.count(-1)%2

# print board
def p(board):
	b = map(lambda n: ("X", "O", " ")[n], board)
	for _ in (b[0:3], b[3:6], b[6:9]):
		print "{%s }" % " |".join(_)
	print

# determine a board's winner
def winner(board):
	for a, b, c in ((0, 1, 2), (3, 4, 5), (6, 7, 8), (0, 3, 6), (1, 4, 7), (2, 5, 8), (0, 4, 8), (2, 4, 6)):
		if board[a] == board[b] == board[c] != -1:
			return board[a]
	return -1

# calculate the board's endstate (winner) assuming both players play perfectly
def endstate(board):
	if board.count(-1) <= 0 or winner(board) != -1:
		return winner(board)
	else:
		t = turn(board)
		win = False
		draw = False
		loss = False
		for _ in range(9):
			if board[_] == -1:
				b = board[:]
				b[_] = t
				e = endstate(b)
				if e == t:
					win = True
				elif e == (not t):
					loss = True
				elif e == -1:
					draw = True
		if win:
			return t
		elif draw:
			return -1
		return not t

# run the game
def game():
	# header
	print 
	print "========================"
	print " IMPOSSIBLE TIC-TAC-TOE "
	print "========================"
	print "  > You cannot win. <   "
	print "       > Never. <       "
	print "========================"
	print
	
	# initialize board (-1: empty, draw)
	board = [-1]*9
	
	# player: 0, computer: 1
	ply = 0
	com = 1
	
	# main game loop
	while -1 in board and winner(board) == -1:
		# print board
		p(board)
		
		# human's turn
		if turn(board) == ply:
			# get input, place piece
			i = ""
			while i == "":
				i = raw_input("Player's turn. ")
				if i in ("0", "1", "2", "3", "4", "5", "6", "7", "8"):
					i = int(i)
					if board[i] == -1:
						board[i] = ply
					else:
						print "This position is already occupied."
						i = ""
				else:
					print "Please place your mark."
					i = ""
		
		# computer's turn
		else:
			# winning positions (one gets pseudo-randomly chosen for more interesting gameplay)
			wins = []
			draws = []
			
			# consider all valid positions
			for _ in range(9):
				if board[_] == -1:
					# calculate endstate if piece placed at postion
					b = board[:]
					b[_] = com
					
					# winning endstate!
					e = endstate(b)
					if e == com:
						wins.append(_)
					elif e == -1:
						draws.append(_)
			
			# choose choice, computer talk
			if len(wins) > 0:
				choice = random.choice(wins)
				pool = ["Calculating odds of defeating you... @100%.", "Probability of me loosing this battle... @0.0000000%.", "If I win, I @win.", "I will crush you."]
			elif len(draws) > 0:
				choice = random.choice(draws)
				pool = ["Considering position %d..." % random.choice(wins+draws), "Planning to end humanity...", "Processing placing at position %d..." % random.choice(wins+draws), "Your tactics are truly @pathetic.", "If I were you, I would @surrender.", "Found strong evidence for this game ending in a @draw.", "The best you can do is achieve a draw.", "You poor human have no chance."]

			# computer talk
			msg = "Computer's turn. "
			sys.stdout.write(msg)
			sys.stdout.flush()
			for _ in random.choice(pool):
				# longer delay
				if _ == "@":
					time.sleep(.3)
				
				else:
					sys.stdout.write(_)
					sys.stdout.flush()
					time.sleep(.1)
			time.sleep(1)
			
			# choose position, place
			sys.stdout.write("\r\033[K%s%d" % (msg, choice))
			sys.stdout.flush()
			time.sleep(1)
			
			# pick a winning endstate
			board[choice] = com
		
		print "\n"*3
	
	# game ended, announce winner
	p(board)
	w = winner(board)
	if w == -1:
		print "The game ended in a draw."
	else:
		print "The winner is %s." % "XO"[winner(board)]
	print

# run
if __name__ == "__main__":
	try:
		game()
	
	# handle keyboard interrupt
	except KeyboardInterrupt:
		print