#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]

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):
	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 = strategy_black(board[:],player)
		else:
			square = strategy_white(board[:],player)
		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")
			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 strategy_black(board, player):
	return basic(board, player)
	
def strategy_white(board, player):
	return random(board, player)
	
def random(board, player):
	moves = get_legal_moves(board, player)
	if len(moves) == 0:
		return None
	else:
		return choice(moves)

def greedy(board, player):
	moves = get_legal_moves(board, player)
	if len(moves) == 0:
		return None
	else:
		bestvalue = -10000
		bestmove = None
		for move in moves:
			result = result_of_move(board, player, move)
			value = power(result, player)
			if value > bestvalue:
				bestvalue = value
				bestmove = move
	return bestmove

def mobile(board, player):
	moves = get_legal_moves(board, player)
	if len(moves) == 0:
		return None
	else:
		bestvalue = -10000
		bestmove = None
		for move in moves:
			result = result_of_move(board, player, move)
			value = mobility(result, player)
			if value > bestvalue:
				bestvalue = value
				bestmove = move
	return bestmove

def stabile_corners(board, player):
	moves = get_legal_moves(board, player)
	if len(moves) == 0:
		return None
	else:
		bestvalue = -10000
		bestmove = None
		for move in moves:
			result = result_of_move(board, player, move)
			value = corner_stability(result, player)
			if value > bestvalue:
				bestvalue = value
				bestmove = move
	return bestmove

def stabile_edges(board, player):
	moves = get_legal_moves(board, player)
	if len(moves) == 0:
		return None
	else:
		bestvalue = -10000
		bestmove = None
		for move in moves:
			result = result_of_move(board, player, move)
			value = edge_stability(result, player)
			if value > bestvalue:
				bestvalue = value
				bestmove = move
	return bestmove

def basic(board, player):
	moves = get_legal_moves(board, player)
	if len(moves) == 0:
		return None
	else:
		bestvalue = -10000
		bestmove = None
		for move in moves:
			result = result_of_move(board, player, move)
			valueA = corner_stability(result, player)
			valueB = edge_stability(result, player)
			valueC = mobility(result,player)
			valueD = power(result, player)
			value = 10*valueA + 5*valueB + 2*valueC + valueD
			if value > bestvalue:
				bestvalue = value
				bestmove = move
	return bestmove	

#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):
	if player == black:
		return count(board, black) - count(board, white)
	else:
		return count(board, white) - count(board, black)

def mobility(board, player):
	return len(get_legal_moves(board, player))

def corner_stability(board, player):
	opp = opponent_color(player)
	score = 0
	for color in [player, opp]:
		if color == player:
			x = 1
		else:
			x = -1	
		if board[11] == color:
			score += x
			if board[12] == color and board[21] == color:
				score += 2*x
				if board[13] == color and board[22] == color and board[31] == color:
					score += 3*x
					if board[14] == color and board[23] == color and board[32] == color and board[41] == color:
						score += 4*x
		if board[18] == color:
			score += x
			if board[17] == color and board[28] == color:
				score += 2*x
				if board[16] == color and board[27] == color and board[38] == color:
					score += 3*x
					if board[15] == color and board[26] == color and board[37] == color and board[48] == color:
						score += 4*x
		if board[81] == color:
			score += x
			if board[82] == color and board[71] == color:
				score += 2*x
				if board[83] == color and board[72] == color and board[61] == color:
					score += 3*x
					if board[84] == color and board[73] == color and board[62] == color and board[51] == color:
						score += 4*x
		if board[88] == color:
			score += x
			if board[87] == color and board[78] == color:
				score += 2*x
				if board[86] == color and board[77] == color and board[68] == color:
					score += 3*x
					if board[85] == color and board[76] == color and board[67] == color and board[58] == color:
						score += 4*x
	return score

def edge_stability(board, player):
	opp = opponent_color(player)
	score = 0
	for color in [player, opp]:
		if color == player:
			x = 1
		else:
			x = -1
		square = 11
		if board[square] == color:
			score -= x
		while True:
			if board[square] != color:
				break
			score += x
			square += 1
			if square == 18 and board[18] == color:
				score -= 8*x
		square = 11
		while True:
			if board[square] != color:
				break
			score += x
			square += 10
			if square == 81 and board[81] == color:
				score -= 8*x
		square = 18
		if board[square] == color:
			score -= x
		while True:
			if board[square] != color:
				break
			score += x
			square += -1
		square = 18
		while True:
			if board[square] != color:
				break
			score += x
			square += 10
		square = 81
		if board[square] == color:
			score -= x
		while True:
			if board[square] != color:
				break
			score += x
			square += 1
		square = 81
		while True:
			if board[square] != color:
				break
			score += x
			square += -10
		square = 88
		if board[square] == color:
			score -= x
		while True:
			if board[square] != color:
				break
			score += x
			square += -1
			if square == 81 and board[81] == color:
				score -= 8*x
		square = 88
		while True:
			if board[square] != color:
				break
			score += x
			square += -10
			if square == 18 and board[18] == color:
				score -= 8*x
	return score


#Main Function

def main():
	sum = 0
	for n in range(100):
		sum += play_one(True, "black", "white")
	print sum/100.0
	
	
if __name__ == "__main__":
	main()