#Decision-making algorithms by C.Hayes, 10/14/05
#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 = 3

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 play_one(flag, bPlayer, wPlayer, bStrat, bDepth, wStrat, wDepth):
	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:
		if player == black:
			square = bStrat(board[:], black, bDepth)
		else:
			square = wStrat(board[:], white, wDepth)
		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 bStrat, bDepth, wStrat, wDepth
			print "power", power(board, black)
			print "mobility", mobility(board, black)
			print "stability", stability(board, black)
			print "corners", corner_stability(board, black)
			print "edges", edge_stability(board, black)
			print "basic", basic_value(board, black)
			###############
			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

#Algorithms	
	
def random(board, player, depth):
	moves = get_legal_moves(board, player)
	if len(moves) == 0:
		return None
	else:
		return choice(moves)
			
def greedy(board, player, depth):
	return minimax(board, player, power, depth)

def mobile(board, player, depth):
	return minimax(board, player, mobility, depth)

def stable(board, player, depth):
	return minimax(board, player, stability, depth)

def corners(board, player, depth):
	return minimax(board, player, stable_corners, depth)

def edges(board, player, depth):
	return minimax(board, player, stable_edges, depth)

def basic(board, player, depth):
	return minimax(board, player, basic_value, depth)
	
#Minimax with Alpha-Beta	

def minimax(board, player, utility, depth):
	if player == 1:
		value, move = maxchoice(board, utility, depth, negInf, posInf)
	if player == 2:
		value, move = minchoice(board, utility, depth, negInf, posInf)
	return move
	
def maxchoice(state, utility, rem_depth, alpha, beta):
	if rem_depth == 0:
		return utility(state, black), None
	value = negInf
	moves = get_legal_moves(state, black)
	if len(moves) == 0:
		new_value, new_move = minchoice(state, utility, 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 = minchoice(next_state, utility, 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 minchoice(state, utility, rem_depth, alpha, beta):
	if rem_depth == 0:
		return utility(state, black), None
	value = posInf
	moves = get_legal_moves(state, white)
	if len(moves) == 0:
		new_value, new_move = maxchoice(state, utility, 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 = maxchoice(next_state, utility, 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			
		

#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 stability(board, player):
	Zempty, Zunstable_b, Zquestionable_b, Zstable_b, Zunstable_w, Zquestionable_w, Zstable_w, Zouter = 0,1,2,3,4,5,6,7
	Zscore_b = 0
	Zscore_w = 0
	smatrix = []
	for square in board:
		if square == outer:
			smatrix.append(Zouter)
		elif square == black:
			smatrix.append(Zquestionable_b)
		elif square == white:
			smatrix.append(Zquestionable_w)
		else:
			smatrix.append(Zempty)
	Zflag = True
	while Zflag == True:
		Zflag = False
		for index in range(len(smatrix)):
			if smatrix[index] == Zquestionable_b:
				stable_test = is_stable(smatrix, index, Zstable_b, Zouter)
				if stable_test == 1:
					smatrix[index] = Zstable_b
					Zflag = True 
				elif stable_test == -1:
					smatrix[index] = Zunstable_b
	
			if smatrix[index] == Zquestionable_w:
				stable_test = is_stable(smatrix, index, Zstable_w, Zouter)
				if stable_test == 1:
					smatrix[index] = Zstable_w
					Zflag = True 
				elif stable_test == -1:
					smatrix[index] = Zunstable_w
	for square in smatrix:
		if square == Zstable_b:
			Zscore_b += 1
		elif square == Zstable_w:
			Zscore_w += 1
	x = Zscore_b
	y = Zscore_w
	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 is_stable(smatrix, index, aa, bb):
	ZZFlag = True
	if smatrix[index-11]!=aa and smatrix[index-11]!=bb and smatrix[index+11]!=aa and smatrix[index+11]!=bb:
		ZZFlag = False
	if smatrix[index-10]!=aa and smatrix[index-10]!=bb and smatrix[index+10]!=aa and smatrix[index+10]!=bb:
		ZZFlag = False
	if smatrix[index-9]!=aa and smatrix[index-9]!=bb and smatrix[index+9]!=aa and smatrix[index+9]!=bb:
		ZZFlag = False	
	if smatrix[index-1]!=aa and smatrix[index-1]!=bb and smatrix[index+1]!=aa and smatrix[index+1]!=bb:
		ZZFlag = False
	return ZZFlag

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
			
def basic_value(board, player):
	valueA = stability(board, player)
	valueB = mobility(board, player)
	valueC = power(board, player)
	return (1.0)*valueA + (0.5)*valueB + (0.3)*valueC
	
#Genetic Setup

def new_strategy():
	weight_opt = []
	weights = {}
	a = range(2001)
	for x in a:
		weight_opt.append(x-1000)	
	for heuristic in [power, mobility, corner_stability, edge_stability, frontier, keysquares]:
		weights[heuristic] = choice(weight_opt)
	return weights
	
def total_value(board, player, weights):
	sum = 0.0
	for heuristic in weights:
		sum += heuristic(board, player) * weights[heuristic]
	return sum

def minimax2(board, player, weights, depth):
	if player == 1:
		value, move = maxchoice2(board, weights, depth, negInf, posInf)
	if player == 2:
		value, move = minchoice2(board, weights, depth, negInf, posInf)
	return move
	
def maxchoice2(state, weights, rem_depth, alpha, beta):
	if rem_depth == 0:
		return total_value(state, black, weights), None
	value = negInf
	moves = get_legal_moves(state, black)
	if len(moves) == 0:
		new_value, new_move = minchoice2(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(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(state, weights, rem_depth, alpha, beta):
	if rem_depth == 0:
		return total_value(state, black, weights), None
	value = posInf
	moves = get_legal_moves(state, white)
	if len(moves) == 0:
		new_value, new_move = maxchoice2(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(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:
		if player == black:
			square = minimax2(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 genetic():
	#uses the genetic algorithm to produce a solution
	printout = True
	mutation_rate = 20
	introduction_rate = 4
	#initializes 'players'
	players = [[{},0],[{},0],[{},0],[{},0],[{},0],[{},0]]
	for i in range(6):
		players[i][0] = new_strategy()
	counter = 0
	while counter < 100:
		#scores each 'player'
		for player in players:
			sum = 0
			for game in range(3):
				sum += playagame2(player[0])
			player[1] = sum
		#bubble sort to rank 'players'
		for i in range(5):
			for j in range(5-i):
				if players[j][1] < players[j+1][1]:
					players[j], players[j+1] = players[j+1], players[j]
		#creates new 'player' from parents; drops worst state
		parent1 = players[0][0]
		parent2 = players[1][0]
		weights = {}
		for heuristic in [power, mobility, corner_stability, edge_stability, frontier, keysquares]:
			weight_opt = []
			a = parent1[heuristic]
			b = parent2[heuristic]
			if a>b:
				c = range(b,a+1)
			else:
				c = range(a,b+1)
			for x in c:
				weight_opt.append(x)	
			weights[heuristic] = choice(weight_opt)
		child = weights
		#mutation and introduction
		if choice(range(100)) < mutation_rate:
			mutated_heuristic = choice([power, mobility, corner_stability, edge_stability, frontier, keysquares])
			weight_opt = []
			weights = {}
			a = range(2001)
			for x in a:
				weight_opt.append(x-1000)	
			child[mutated_heuristic] = choice(weight_opt)
			if printout == True:
				print "mutation"
		if choice(range(100)) < introduction_rate:
			introductionchild = new_strategy()
			child = introductionchild
			if printout == True:
				print "introduction"
		if printout == True:
			print "players:", players
			print "child:", child
			print "counter", counter
			print "\n",
		players[5] = [child, 0]
		#add to counter
		counter += 1
		#stall = raw_input("hit enter to continue\n")

def genetic2():
	#an improved genetic algorithm
	#uses the genetic algorithm to produce a solution
	printout = True
	mutation_rate = 30
	#initializes 'players'
	players = []
	for j in range(numPlayers):
		players.append([{},0])
	for i in range(numPlayers):
		players[i][0] = new_strategy()
	counter = 0
	while counter < 100:
		#scores each 'player'
		if printout == True:
			print "scores\t\t\t\tsum\t\trankscore\t\tp\tm\tc\te\tf\tk"
		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",
			#some memory of previous trials
			player[1] = player[1]*2/3 + sum/3
			if printout == True:
				print "=\t", sum, "\t", "|\t", player[1], "\t",
				print "weights", "\t",
				for heuristic in [power, mobility, corner_stability, edge_stability, frontier, keysquares]:
					print player[0][heuristic], "\t",
				print
		#bubble sort to rank 'players'
		for i in range(numPlayers-1):
			for j in range(numPlayers-1-i):
				if players[j][1] < players[j+1][1]:
					players[j], players[j+1] = players[j+1], players[j]
		#creates new 'player' from parents; drops worst state
		parent1 = players[0][0]
		parent2 = players[1][0]
		weights = {}
		for heuristic in [power, mobility, corner_stability, edge_stability, frontier, keysquares]:
			weight_opt = []
			a = parent1[heuristic]
			b = parent2[heuristic]
			if a>b:
				c = range(b,a+1)
			else:
				c = range(a,b+1)
			for x in c:
				weight_opt.append(x)	
			weights[heuristic] = choice(weight_opt)
		child = weights
		#mutation and introduction
		for mutated_heuristic in [power, mobility, corner_stability, edge_stability, frontier, keysquares]:
			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]-xx)<200 and (child[mutated_heuristic]-xx)>-200:
						weight_opt.append(xx)	
				child[mutated_heuristic] = choice(weight_opt)
				print "mutation - ", mutated_heuristic
		if printout == True:
			print "child:", child
			print "counter", counter
			print "\n",
		players[numPlayers-1] = [child, 0]
		#add to counter
		counter += 1
		#stall = raw_input("hit enter to continue\n")

	
	
def playagame2(weights):
	score = play_weights_vs_random(False, "AI", "random", weights, 1)
	return score
	

#Debugging Functions

def playagame(bStrat, bDepth, wStrat, wDepth):
	print play_one(True, "AI", "random", bStrat, bDepth, wStrat, wDepth)

def playsomegames(bStrat, bDepth, wStrat, wDepth):
	sum = 0
	games = 25
	for n in range(games):
		sum += play_one(True, "AI", "random", bStrat, bDepth, wStrat, wDepth)
		if (n+1)%5 == 0:
			print n+1
	print sum/(games+0.0)
	return sum/(games+0.0)
	
def compare():
	print "greedy:",
	greedy_score = playsomegames(greedy,1,random,1)
	print "greedy forward:",
	greedy_forward_score = playsomegames(greedy,3,random,1)
	system("clear")
	print "greedy:", greedy_score
	print "greedy forward:", greedy_forward_score
	
#Main Function

def main():
	#print playagame2({power: 100, mobility: 200, corner_stability: 300, edge_stability: 200, frontier: 50, keysquares: 100})
	genetic2()
	
if __name__ == "__main__":
	main()