tic_tac_toe.py

#
# tic_tac_toe.py - tic-tac-toe game
#
# 2014-02-07 Steven Wart created this file
#

from sys import stdout
from math import sqrt

# Print out an 3x3 tic-tac-toe board showing the positions of the pieces
def draw_board(board, scores=None):
	n = int(sqrt(len(board)))
	stdout.write("  ")

	i = 0
	for cell in range(len(board)):
		if ((cell % n) == 0):
			stdout.write('\n')
			stdout.write("   +")
			for col in range(n):
				stdout.write("---+")
			stdout.write('\n')
			stdout.write("   |")

		# traversal path starts at 1
		if (board[cell] == -1):
			stdout.write(" O |")
		elif (board[cell] == 1):
			stdout.write(" X |")
		elif scores:
			stdout.write("{0:>3}|".format(scores[i]))
			i = i + 1
		else:
			stdout.write("   |")

	stdout.write('\n')
	stdout.write("   +")
	for col in range(n):
		stdout.write("---+")
	stdout.write('\n')

#
# return a score value for the board
# Simple as possible: if X has won, return 1, if O has won return -1, otherwise return 0
# 
def score_board(board):
	rows = [[0, 1, 2], [3, 4, 5], [6, 7, 8]]
	for cells in rows:
		score = sum([board[cell] for cell in cells])
		if score == 3:
			return 1
		elif score == -3:
			return -1
	cols = [[0, 3, 6], [1, 4, 7], [2, 5, 8]]
	for cells in cols:
		score = sum([board[cell] for cell in cells])
		if score == 3:
			return 1
		elif score == -3:
			return -1
	diagonals = [[0, 4, 8], [2, 4, 6]]
	for cells in diagonals:
		score = sum([board[cell] for cell in cells])
		if score == 3:
			return 1
		elif score == -3:
			return -1
	return 0

#
# return True if there is an empty space on the board
#
def can_play(board):
	for cell in board:
		if cell == 0:
			return True

	return False

# global cache for memoizing board evaluations
evaluations = {}

#
# Return a string identifying the token and the board for memoization
#
def eval_key(token, board):
	return player_string(token) + ":" + "".join([str(cell) for cell in board])

#
# traverse the tree, placing the token at the best possible position for
# for the corresponding player
#
def evaluate_board(token, board):

	choices = [pos for pos in range(len(board)) if board[pos] == 0]

	# otherwise, return the best score in the subtree of all the choices
	scores = []
	for choice in choices:
		board_copy = board[:]
		board_copy[choice] = token
		score = score_board(board_copy)
		if can_play(board_copy) and score != 1 and score != -1:
			key = eval_key(token * -1, board_copy)
			if key in evaluations:
				subtree_evaluation = evaluations[key]
			else:
				subtree_evaluation = evaluate_board(token * -1, board_copy)

			# best score is the worst score until we find a better one
			best_score = token
			for index in range(len(subtree_evaluation[1])):
				score = subtree_evaluation[1][index]
				if score == token * -1:
					best_score = token * -1
					break
				elif score == 0 and best_score == token:
					best_score = 0
			scores.append(best_score)
		else:
			scores.append(score)

	key = eval_key(token, board)
	evaluations[key] = (choices, scores)

	return (choices, scores)

#
# Convert -1 to "O", 1 to "X", 0 is an invalid index
#
def player_string(token):
	return ["*", "X", "O"][token]

#
# traverse the tree, placing the token at the best possible position for
# for the corresponding player
#
def play(token, board):

	if not can_play(board):
		return

	evaluation = evaluate_board(token, board)
	best_score = token * -1
	pos = evaluation[0][0]
	for index in range(len(evaluation[1])):
		score = evaluation[1][index]
		# we have a winning move
		if score == token:
			best_score = token
			pos = evaluation[0][index]
			break
		# we have a tying move
		elif score == 0 and best_score == token * -1:
			best_score = 0
			pos = evaluation[0][index]

	if board[pos] == 0:
		board[pos] = token
		return
	else:
		print "Error pos=%d contains %d" % (pos, board[pos])
		for key in evaluations:
			print key, evaluations[key]
		exit()

#
# Have the game play a human
#
def play_game():
	board = [0, 0, 0, 0, 0, 0, 0, 0, 0]
	score = 0
	player = 1
	
	print chr(27)+"[2J"
	draw_board(board)

	while can_play(board) and score != 1 and score != -1:
		nb = raw_input("%s plays - Enter a number between 0 and 9: " % player_string(player))
		if nb == "q" or nb == "Q":
			exit()
		try:
			number = int(nb)
		except ValueError:
			print "Invalid number"
			continue

		if number > len(board) - 1 or number < 0:
			print "Invalid number"
			continue

		if board[number] != 0:
			print "That cell is already in use"
			continue

		board[number] = player
		draw_board(board)
		score = score_board(board)
		if score != 0:
			break

		player = player * -1
		print chr(27)+"[2J"
		print "%s plays" % player_string(player)
		play(player, board)
		draw_board(board)
		score = score_board(board)
		player = player * -1

	if score == 1:
		print "X wins"
	elif score == -1:
		print "O wins"
	else:
		print "Tie game"

play_game()