#Decision-making algorithms by C.Hayes, 10/14/05 to 1/25/06
#Othello referee by Torbert, 12/2/04, modified by Hayes and Schafer, 5/05

from os import *
#from time import time 
from random import choice
#from random import shuffle
#from copy import deepcopy

#Othello Referee

black, white, empty, outer = 1, 2, 0, 3
directions = [-11, -10, -9, -1, 1, 9, 10, 11]
negInf = -1000000
posInf = 1000000
numPlayers = 12
numGames = 5
numParts = 4

def printState(board, lastMove, currTest, b, w, s, bl, wl):
	if board[currTest] == black:
		if currTest == lastMove:
			return bl
		else:
			return b
	if board[currTest] == white:
		if currTest == lastMove:
			return wl
		else:
			return w
	if board[currTest] == empty:
		return s

def display(state, lastMove):
	start = chr(27) + "[32;42m" + chr(27) + "[1m"
	end = chr(27) + "[0m"
	LeftUpperCorner = start + "+" + end
	LeftSide = start + "|" + end
	LeftInterSection = start + "+" + end
	LeftLowerCorner = start + "+" + end
	RightUpperCorner = start + "+" + end
	RightSide = start + "|" + end
	RightInterSection = start + "+" + end
	RightLowerCorner = start + "+" + end
	LowerSide = start + "-" + end
	LowerInterSection = start + "+" + end
	UpperSide = start + "-" + end
	UpperInterSection = start + "+" + end
	VerticalBar = start + "|" + end
	HorizontalBar = start + "-" + end
	MiddleInterSection = start + "+" + end

	blackMarker = chr(27) + "[30;42m" + chr(27) + "[1m" + " * " + chr(27) + "[0m"
	whiteMarker = chr(27) + "[37;42m" + chr(27) + "[1m" + " * " + chr(27) + "[0m"
	spaceMarker = chr(27) + "[31;42m" + chr(27) + "[1m" + "   " + chr(27) + "[0m"
	blackLast = chr(27) + "[30;46m" + chr(27) + "[1m" + " * " + chr(27) + "[0m"
	whiteLast = chr(27) + "[37;46m" + chr(27) + "[1m" + " * " + chr(27) + "[0m"

	string = ""

	string += LeftUpperCorner
	string += UpperSide
	string += UpperSide
	string += UpperSide
	for i in range(7):
		string += UpperInterSection
		string += UpperSide
		string += UpperSide
		string += UpperSide
	string += RightUpperCorner
	string += "\n"

	for i in range(7):
		string += LeftSide
		for j in range(7):
			string += printState(state, lastMove, 10*i+j+11, blackMarker, whiteMarker, spaceMarker, blackLast, whiteLast)
			string += VerticalBar
		string += printState(state, lastMove, 10*i+18, blackMarker, whiteMarker, spaceMarker, blackLast, whiteLast)
		string += RightSide
		string += "\n"

		string += LeftInterSection
		string += HorizontalBar
		string += HorizontalBar
		string += HorizontalBar
		for i in range(7):
			string += MiddleInterSection
			string += HorizontalBar
			string += HorizontalBar
			string += HorizontalBar
		string += RightInterSection
		string += "\n"

	string += LeftSide
	for j in range(7):
		string += printState(state, lastMove, 81+j, blackMarker, whiteMarker, spaceMarker, blackLast, whiteLast)
		string += VerticalBar
	string += printState(state, lastMove, 88, blackMarker, whiteMarker, spaceMarker, blackLast, whiteLast)
	string += RightSide
	string += "\n"
	string += LeftLowerCorner
	string += LowerSide
	string += LowerSide
	string += LowerSide
	for i in range(7):
		string += LowerInterSection
		string += LowerSide
		string += LowerSide
		string += LowerSide
	string += RightLowerCorner
	string += "\n"
	
	print string

def bracket(board, player, square):
	opp = opponent_color(player)
	for d in directions:
		k = square + d
		if board[k] is not opp:
			continue
		while board[k] is opp:
			k = k + d
		if board[k] is player:
			k = k - d
			while k != square:
				board[k] = player
				k = k - d

def would_bracket(board, player, square):
	opp = opponent_color(player)
	for d in directions:
		k = square + d
		if board[k] is not opp:
			continue
		while board[k] is opp:
			k = k + d
		if board[k] is player:
			return True
	return False

def get_legal_moves(board, player):
	possible = []
	for row in range(10, 90, 10):
		for col in range(1, 9):
			square = row + col
			if board[square] is not empty:
				continue
			if would_bracket(board, player, square):
				possible.append(square)
	return possible

def opponent_color(player):
	if player is black: 
		return white
	return black

def count(board, player):
	total = 0
	for row in range(10, 90, 10):
		for col in range(1, 9):
			square = board[row + col]
			if square is player:	
				total = total + 1
	return total
			
def random(board, player, depth):
	moves = get_legal_moves(board, player)
	if len(moves) == 0:
		return None
	else:
		return choice(moves)
	
#Heuristics and other functions

def result_of_move(board, player, square):
	result = board[:]
	opp = opponent_color(player)
	for d in directions:
		k = square + d
		if board[k] is not opp:
			continue
		while board[k] is opp:
			k = k + d
		if board[k] is player:
			k = k - d
			while k != square:
				result[k] = player
				k = k - d
	return result

def power(board, player):
	x = count(board, black)
	y = count(board, white)
	if player == black:
		return ((1.0+x)/(2.0+x+y))*2.0-1.0
	else:
		return ((1.0+y)/(2.0+x+y))*2.0-1.0

def mobility(board, player):
	x = len(get_legal_moves(board, black))
	y = len(get_legal_moves(board, white))
	if player == black:
		return ((1.0+x)/(2.0+x+y))*2.0-1.0
	else:
		return ((1.0+y)/(2.0+x+y))*2.0-1.0

def frontier(board, player):
	opp = opponent_color(player)
	x = 0.0
	y = 0.0
	for square in range(100):
		if board[square] == empty:
			next_to_p = False
			next_to_o = False
			for direction in directions:
				if board[square + direction] == player:
					next_to_p = True
				elif board[square + direction] == opp:
					next_to_o = True
			if next_to_p == True:
				y += 1.0
			if next_to_o == True:
				x += 1.0
	return ((1.0+x)/(2.0+x+y))*2.0-1.0
			
def keysquares(board, player):
	opp = opponent_color(player)
	x = 0.0
	y = 0.0
	for s in range(100):
		if board[s] == player:
			if s == 11 or s == 18 or s == 81 or s == 88:
				x += 20.0
			if (s/10) == 1 or (s/10) == 8 or (s%10) == 1 or (s%10) == 8:
				x += 2.0
			if (s == 12 or s == 21 or s == 22) and board[11] == empty:
				y += 4.0
			if (s == 17 or s == 28 or s == 27) and board[18] == empty:
				y += 4.0
			if (s == 71 or s == 82 or s == 72) and board[81] == empty:
				y += 4.0
			if (s == 78 or s == 87 or s == 77) and board[88] == empty:
				y += 4.0
			if (s == 13 or s == 31 or s == 33) and board[11] == empty:
				x += 2.0
			if (s == 16 or s == 38 or s == 36) and board[18] == empty:
				x += 2.0
			if (s == 61 or s == 83 or s == 63) and board[81] == empty:
				x += 2.0
			if (s == 68 or s == 86 or s == 66) and board[88] == empty:
				x += 2.0
		if board[s] == opp:
			if s == 11 or s == 18 or s == 81 or s == 88:
				y += 20.0
			if (s/10) == 1 or (s/10) == 8 or (s%10) == 1 or (s%10) == 8:
				y += 2.0
			if (s == 12 or s == 21 or s == 22) and board[11] == empty:
				x += 4.0
			if (s == 17 or s == 28 or s == 27) and board[18] == empty:
				x += 4.0
			if (s == 71 or s == 82 or s == 72) and board[81] == empty:
				x += 4.0
			if (s == 78 or s == 87 or s == 77) and board[88] == empty:
				x += 4.0
			if (s == 13 or s == 31 or s == 33) and board[11] == empty:
				y += 2.0
			if (s == 16 or s == 38 or s == 36) and board[18] == empty:
				y += 2.0
			if (s == 61 or s == 83 or s == 63) and board[81] == empty:
				y += 2.0
			if (s == 68 or s == 86 or s == 66) and board[88] == empty:
				y += 2.0
	return ((1.0+x)/(2.0+x+y))*2.0-1.0
			
def corner_stability(board, player):
	opp = opponent_color(player)
	score = [0.0,0.0]
	for color in [player, opp]:
		if color == player:
			z = 0
		else:
			z = 1	
		if board[11] == color:
			score[z] += 1
			if board[12] == color and board[21] == color:
				score[z] += 2
				if board[13] == color and board[22] == color and board[31] == color:
					score[z] += 3
					if board[14] == color and board[23] == color and board[32] == color and board[41] == color:
						score[z] += 4
		if board[18] == color:
			score[z] += 1
			if board[17] == color and board[28] == color:
				score[z] += 2
				if board[16] == color and board[27] == color and board[38] == color:
					score[z] += 3
					if board[15] == color and board[26] == color and board[37] == color and board[48] == color:
						score[z] += 4
		if board[81] == color:
			score[z] += 1
			if board[82] == color and board[71] == color:
				score[z] += 2
				if board[83] == color and board[72] == color and board[61] == color:
					score[z] += 3
					if board[84] == color and board[73] == color and board[62] == color and board[51] == color:
						score[z] += 4
		if board[88] == color:
			score[z] += 1
			if board[87] == color and board[78] == color:
				score[z] += 2
				if board[86] == color and board[77] == color and board[68] == color:
					score[z] += 3
					if board[85] == color and board[76] == color and board[67] == color and board[58] == color:
						score[z] += 4
	x = score[0]
	y = score[1]
	return ((1.0+x)/(2.0+x+y))*2.0-1.0
					
def edge_stability(board, player):
	opp = opponent_color(player)
	score = [0.0, 0.0]
	for color in [player, opp]:
		if color == player:
			z = 0
		else:
			z = 1
		square = 11
		if board[square] == color:
			score[z] -= 1
		while True:
			if board[square] != color:
				break
			score[z] += 1
			square += 1
			if square == 18 and board[18] == color:
				score[z] -= 8
		square = 11
		while True:
			if board[square] != color:
				break
			score[z] += 1
			square += 10
			if square == 81 and board[81] == color:
				score[z] -= 8
		square = 18
		if board[square] == color:
			score[z] -= 1
		while True:
			if board[square] != color:
				break
			score[z] += 1
			square += -1
		square = 18
		while True:
			if board[square] != color:
				break
			score[z] += 1
			square += 10
		square = 81
		if board[square] == color:
			score[z] -= 1
		while True:
			if board[square] != color:
				break
			score[z] += 1
			square += 1
		square = 81
		while True:
			if board[square] != color:
				break
			score[z] += 1
			square += -10
		square = 88
		if board[square] == color:
			score[z] -= 1
		while True:
			if board[square] != color:
				break
			score[z] += 1
			square += -1
			if square == 81 and board[81] == color:
				score[z] -= 8
		square = 88
		while True:
			if board[square] != color:
				break
			score[z] += 1
			square += -10
			if square == 18 and board[18] == color:
				score[z] -= 8
	x = score[0]
	y = score[1]
	return ((1.0+x)/(2.0+x+y))*2.0-1.0
			
#Genetic Setup

def new_strategy(allHeuristics):
	weight_opt = []
	weights = {}
	a = range(2001)
	for x in a:
		weight_opt.append(x-1000)	
	for heuristic in allHeuristics:
		weights[heuristic] = [choice(weight_opt), choice(weight_opt), choice(weight_opt), choice(weight_opt)]
	return weights
	
def total_value(movenum, board, player, weights):
	sum = 0.0
	for heuristic in weights:
		if movenum <= 15:
			sum += heuristic(board, player) * weights[heuristic][0]
		elif movenum <= 30:
			sum += heuristic(board, player) * weights[heuristic][1]
		elif movenum <= 45:
			sum += heuristic(board, player) * weights[heuristic][2]
		else:
			sum += heuristic(board, player) * weights[heuristic][3]
	return sum

def minimax2(movenum, board, player, weights, depth):
	if player == 1:
		value, move = maxchoice2(movenum, board, weights, depth, negInf, posInf)
	if player == 2:
		value, move = minchoice2(movenum, board, weights, depth, negInf, posInf)
	return move
	
def maxchoice2(movenum, state, weights, rem_depth, alpha, beta):
	if rem_depth == 0:
		return total_value(movenum, state, black, weights), None
	value = negInf
	moves = get_legal_moves(state, black)
	if len(moves) == 0:
		new_value, new_move = minchoice2(movenum, state, weights, rem_depth-1, alpha, beta)
		value = new_value
		move_choice = None
	for move in moves:
		next_state = result_of_move(state, black, move)
		new_value, new_move = minchoice2(movenum, next_state, weights, rem_depth-1, alpha, beta)
		if new_value > value:
			value = new_value
			move_choice = move
		if value >= beta:
			return value, move
		if value > alpha:
			alpha = value
	return value, move_choice
		
def minchoice2(movenum, state, weights, rem_depth, alpha, beta):
	if rem_depth == 0:
		return total_value(movenum, state, black, weights), None
	value = posInf
	moves = get_legal_moves(state, white)
	if len(moves) == 0:
		new_value, new_move = maxchoice2(movenum, state, weights, rem_depth-1, alpha, beta)
		value = new_value
		move_choice = None
	for move in moves:
		next_state = result_of_move(state, white, move)
		new_value, new_move = maxchoice2(movenum, next_state, weights, rem_depth-1, alpha, beta)
		if new_value < value:
			value = new_value
			move_choice = move
		if value <= alpha:
			return value, move
		if value < beta:
			beta = value
	return value, move_choice

def play_weights_vs_random(flag, bPlayer, wPlayer, bWeights, bDepth):
	whiteForfeit = 64
	blackForfeit = -64
	board = [empty] * 100
	board[0:10] = [outer] * 10
	board[90:100] = [outer] * 10
	for k in range(10, 90, 10):
		board[k + 0] = outer
		board[k + 9] = outer
	board[44], board[55] = white, white
	board[45], board[54] = black, black
	if flag:
		system("clear")
		display(board, None)
	player, squares, stuck = black, 4, 0
	one, two = 0, 0
	while squares < 64 and stuck < 2:
		movenum = squares-3
		if player == black:
			square = minimax2(movenum, board[:], black, bWeights, bDepth)
		else:
			square = random(board[:], white, 1)
		possible = get_legal_moves(board, player)
		if square is not None:
			if square not in possible:
				if player is white:
					if flag:
						print "White is disqualified for an illegal move."
					return whiteForfeit
				else:
					if flag:
						print "Black is disqualified for an illegal move."
					return blackForfeit
			board[square] = player
			bracket(board, player, square)
			squares += 1
			stuck = 0
		elif len(possible) == 0:
			stuck += 1
		else:
			if player is white:
				if flag:
					print "White is disqualified for passing illegally."
				return whiteForfeit
			else:
				if flag:
					print "Black is disqualified for passing illegally."
				return blackForfeit			
		player = opponent_color(player)
		if flag:
			system("clear")
			###############
			print bWeights[power], "power", power(board, black)
			print bWeights[mobility], "mobility", mobility(board, black)
			print bWeights[corner_stability], "corners", corner_stability(board, black)
			print bWeights[edge_stability], "edges", edge_stability(board, black)
			print bWeights[frontier], "frontier", frontier(board, black)
			print bWeights[keysquares], "key squares", keysquares(board, black)
			print "total", total_value(board, black, bWeights)
			###############
			display(board, square)
			w, b = count(board, white), count(board, black)
	w, b = count(board, white), count(board, black)
	if flag:
		system("clear")
		display(board, None)
		print "Black (" + bPlayer + "): "+str(b)
		print "White (" + wPlayer + "): "+str(w)
		print
	return b-w

def genetic2(printout):
	#an improved genetic algorithm
	#uses the genetic algorithm to produce a solution
	printout = True
	mutation_rate = 30
	#sets heuristics to be used
	allHeuristics = [power, mobility, corner_stability, edge_stability, keysquares]
	#initializes 'players'
	players = []
	for j in range(numPlayers):
		players.append([{},0,0,0])
	for i in range(numPlayers):
		players[i][0] = new_strategy(allHeuristics)
	counter = 0
	while counter < 100:
		#scores each 'player'
		if printout == True:
			print "scores\t\t\t\t\t\tsum\t\trankscore\t\tpwr\tmob.\tcornr\tedge\tkeysq"
		for player in players:
			sum = 0
			for game in range(numGames):
				score_of_game = playagame2(player[0])
				sum += score_of_game
				if printout == True:
					print score_of_game, "\t",
			#average of previous trials
			player[1] += sum
			player[2] += numGames
			if player[2] < 15:
				player[3] = 2*player[1]/(player[2]+15)
			else:
				player[3] = player[1]/player[2]
			if printout == True:
				print "=\t", sum, "\t", "|\t", player[3], "\t",
				print "weights", "\t",
				for gamepart in range(numParts):
					if gamepart != 0:
						print "\t\t\t\t\t\t\t\t\t\t\t",
					for heuristic in allHeuristics:
						print player[0][heuristic][gamepart], "\t",
					movesA = (gamepart)*15 + 1
					movesB = (gamepart + 1)*15
					print "( moves", movesA, "-", movesB, ")"
				print
		#bubble sort to rank 'players'
		for i in range(numPlayers-1):
			for j in range(numPlayers-1-i):
				if (players[j][3]) < (players[j+1][3]):
					players[j], players[j+1] = players[j+1], players[j]
		#creates new 'player' from parents; drops worst state
		if counter >= 5:
			parent1 = players[0][0]
			parent2 = players[1][0]
			weights = {}
			for heuristic in allHeuristics:
				tempparts = [0,0,0,0]
				for gamepart in range(numParts):
					weight_opt = []
					a = parent1[heuristic][gamepart]
					b = parent2[heuristic][gamepart]
					if a>b:
						c = range(b,a+1)
					else:
						c = range(a,b+1)
					for x in c:
						weight_opt.append(x)	
					tempparts[gamepart] = choice(weight_opt)
				weights[heuristic] = tempparts
			child = weights
			#mutation
			for mutated_heuristic in allHeuristics:
				tempparts = [0,0,0,0]
				for gamepart in range(numParts):
					if choice(range(100)) < mutation_rate:
						weight_opt = []
						weights = {}
						a = range(2001)
						for x in a:
							#restricts mutations to a maximum change of 100
							xx = x - 1000
							if (child[mutated_heuristic][gamepart]-xx)<200 and (child[mutated_heuristic][gamepart]-xx)>-200:
								weight_opt.append(xx)	
						tempparts[gamepart] = choice(weight_opt)
						print "mutation - ", mutated_heuristic, "part:", gamepart
					else:
						tempparts[gamepart] = child[mutated_heuristic][gamepart]
				child[mutated_heuristic] = tempparts
			if printout == True:
				print "child:", child
				print "counter", counter
				print "\n",
			players[numPlayers-1] = [child, 0, 0, 0]
		#add to counter
		counter += 1
		#stall = raw_input("hit enter to continue\n")
	resultplayer = {}
	for heuristic in allHeuristics:
		tempparts = [0,0,0,0]
		for gamepart in range(numParts):
			sum = 0
			for i in range(6):
				sum += players[i][0][heuristic][gamepart]
			tempparts[gamepart] = sum/6
		resultplayer[heuristic] = tempparts
	return resultplayer
	
def playagame2(weights):
	score = play_weights_vs_random(False, "AI", "random", weights, 1)
	return score

#Main Function

def main():
	print genetic2(True)
	
if __name__ == "__main__":
	main()