TicTacToe.py

import random

########################## SOLVER ##########################

def findBestMove(node, color, getChildren, getValue, maxDepth = 8, maxValue = 1000):
	def negamax(node, depth, alpha, beta, color):
		children = getChildren(node, color)
		if len(children) == 0 or depth == 0: # no moves left or too deep
			return getValue(node) * color
		else:
			for child in children:
				value = -negamax(child, depth-1, -beta, -alpha, -color)
				if value >= beta:
					return value
				if value > alpha:
					alpha = value
			return alpha
	children = getChildren(node,color)
	if len(children) == 0: # no moves left
		return node
	return min(children, key=lambda child : negamax(child, maxDepth, -maxValue, maxValue, -color))

########################## SOLVER ##########################

####################### tic tac toe ########################

def tictactoe():
	return [0] * 9

def printtictactoe(bord):
	print ""
	print "      %s" %  "|".join(map(lambda x : " X " if x > 0 else " O " if x < 0 else "   ", bord[0:3]))
	print "      ---+---+---"
	print "      %s" %  "|".join(map(lambda x : " X " if x > 0 else " O " if x < 0 else "   ", bord[3:6]))
	print "      ---+---+---"
	print "      %s" %  "|".join(map(lambda x : " X " if x > 0 else " O " if x < 0 else "   ", bord[6:9]))
	print ""

####################### tic tac toe ########################

def makeMove(bord,move,player):
	bord = list(bord)
	bord[move] = player
	return bord

def getWinner(bord):
	wins = [[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 max([ bord[win[0]]+bord[win[1]]+bord[win[2]]  for win in wins ]) == 3:
		return 1
	elif min([ bord[win[0]]+bord[win[1]]+bord[win[2]]  for win in wins ]) == -3:
		return -1
	else:
		return 0

def getPossiableMoves(bord, lastmove=None):
	if getWinner(bord) != 0:
		return []
	return [i for i in [0,2,6,8,4,1,3,5,7] if bord[i] == 0]

def nextBords(bord, player):
	return 	[makeMove(bord,move,player) for move in getPossiableMoves(bord)]

def valueBord(bord):
	return getWinner(bord) * 999

def AIvsAI2(bord, player):
	print "  ### AI vs AI ###"
	printtictactoe(bord)
	while getWinner(bord) == 0 and len(getPossiableMoves(bord))>0:
		bord = findBestMove(bord, player, nextBords, valueBord)
		printtictactoe(bord)
		player = -player
	
	if getWinner(bord) == 0:
		print "         DRAW!"
	elif getWinner(bord) == -1:
		print "        O Wins!"
	else:
		print "        X Wins!"


def AIvsPlayer(bord, player):
	print "  ### player vs AI ###"
	printtictactoe(bord)
	def doMove(bord, player):
		if player > 0:
			inputs = { '1':6,'2':7,'3':8,'4':3,'5':4,'6':5,'7':0,'8':1,'9':2 }
			move = raw_input("    Play move: ")
			while move not in inputs or inputs[move] not in getPossiableMoves(bord):
				print "    nope!"
				move = str(raw_input("    Play move: "))
			bord = makeMove(bord,inputs[move],player)
		else:
			bord = findBestMove(bord, player, nextBords, valueBord)
		return bord

	while getWinner(bord) == 0 and len(getPossiableMoves(bord))>0:
		bord = doMove(bord, player)
		printtictactoe(bord)
		player = -player

	if getWinner(bord) == 0:
		print "         DRAW!"
	elif getWinner(bord) == -1:
		print "        O Wins!"
	else:
		print "        X Wins!"

_bord = tictactoe()
#bord = [0,1,1,0,-1,0,0,0,-1]
#bord =  [1,0,0,-1,0,0,0,0,0]
#bord =  [1,1,0,-1,0,0,0,0,0]
#bord =  [-1,-1,0,0,0,0,0,1,1]
#bord = [-1,-1,1,0,0,0,0,1,1]

#bord = [1,-1,0,0,0,0,0,0,0]
#bord = [-1,-1, 1, 0, 1, 0, 0, 1, 0]
#bord = [ 0, 0,-1, 1,-1, 1, 0, 1,-1]
#bord = [ 1,-1, 1, 0,-1, 0, 0, 1, 0]

#AIvsAI2(_bord, 1)
AIvsPlayer(_bord, random.randint(0,1)*2-1)