#
# othello.py
#
# 2007/08/01 18:29 othello project start 
# 2007/08/02 0:53 change 1dim_array 
# 2007/08/03 0:44 computer thinking algorithm
# 2007/08/06 3:38 AI program start
# 2007/08/06 7:09 Black AI only???
#

#  ABCDEFGH
# 1
# 2
# ...
# 8

board =[0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 1, 2, 0, 0, 0,
		0, 0, 0, 2, 1, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0,
		0, 0, 0, 0, 0, 0, 0, 0]

BLANK = 0
WHITE = 1
BLACK = 2
BOARD_SIZE = 8
black_num = 2
white_num = 2
MY_TURN = 1
ENEMY_TURN = -1

print len(board)
#
# print board
#
def print_board(board):
	print "   a b c d e f g h "
	print "   0 1 2 3 4 5 6 7 "
	for y in range(BOARD_SIZE):
		print y+1,y,
		for x in range(BOARD_SIZE):
			peace = board[x+(y*BOARD_SIZE)]
			if peace == BLANK:
				print "-",
			if peace == WHITE:
				print "O",
			if peace == BLACK:
				print "*",
		print
	print

#
# set piece
#
def set_piece(board, x, y, piece):
	board[x+(y*8)] = piece

def reverse(board, PIECE, x, y, dir_x, dir_y):
	count = 0
	c_x = x
	c_y = y
	tmp_board = board[:]
	while 1:
		c_x = c_x + dir_x
		c_y = c_y + dir_y
		#board out end
		if (c_x < 0) or (c_x >= BOARD_SIZE) or (c_y < 0) or (c_y >= BOARD_SIZE):
			###print "NG c_x c_y:", c_x, c_y
			count_board = (0, board)
			return count_board
		###print "OK c_x c_y:", c_x, c_y
		check_point = c_x+(c_y*BOARD_SIZE)
		check_piece = tmp_board[check_point]
		#print check_point
		#BLANK end
		if check_piece == BLANK:
			count_board = (0, board)
			return count_board
		#PIECE end
		if check_piece == PIECE:
			if count > 0 :
				tmp_board[x+(y*BOARD_SIZE)] = PIECE
			board = tmp_board[:]
			count_board = (count, board)
			return count_board
		tmp_board[check_point] = PIECE
		count += 1

def check_blank(board, x, y):
	check_piece = board[x+(y*BOARD_SIZE)]
	if check_piece == BLANK:
		return 1
	return 0

def all_reverse(board, PIECE, x, y):
	count = 0
	tmp_count = 0
	
	if check_blank(board, x, y) == 0:
		count_board = (count, board)
		return count_board
	
	tmp_count, board = reverse(board, PIECE, x, y, 1, 0)
	count += tmp_count
	tmp_count, board = reverse(board, PIECE, x, y,-1, 0)
	count += tmp_count
	tmp_count, board = reverse(board, PIECE, x, y, 0, 1)
	count += tmp_count
	tmp_count, board = reverse(board, PIECE, x, y, 0,-1)
	count += tmp_count
	tmp_count, board = reverse(board, PIECE, x, y, 1, 1)
	count += tmp_count
	tmp_count, board = reverse(board, PIECE, x, y,-1, 1)
	count += tmp_count
	tmp_count, board = reverse(board, PIECE, x, y, 1,-1)
	count += tmp_count
	tmp_count, board = reverse(board, PIECE, x, y,-1,-1)
	count += tmp_count
	count_board = (count, board)
	return count_board

def possible_point(board, PIECE):
	count = 0
	stack = []
	tmp_board = board[:]
	for x in range(BOARD_SIZE):
		for y in range(BOARD_SIZE):
			count, tmp_board = all_reverse(board, PIECE, x, y)
			if count > 0 :
				stack.append([x,y,count])
				#print "x y count:", x,y,count
	return stack

def depth_search(board, PIECE, depth):
	replica = board[:]
	pp = possible_point(replica, PIECE)
	if depth == 0:
		pack_value = (len(pp), 0, 0)
		return pack_value
	pp_num = 0
	max = -999
	max_x = 0
	max_y = 0
	if len(pp) == 0: #PIECE is pass
		if PIECE == BLACK:
			pp_num,trash,trash = depth_search(replica, WHITE, depth-1)
		else:
			pp_num,trash,trash = depth_search(replica, BLACK, depth-1)
		pp_num = pp_num * -1
		if pp_num > max:
			max = pp_num
	while len(pp) > 0:
		x, y, count = pp.pop()
		ans, replica = all_reverse(replica, PIECE, x, y)#my turn
		if PIECE == BLACK:
			pp_num, trash, trash = depth_search(replica, WHITE, depth-1)
		else:
			pp_num, trash, trash = depth_search(replica, BLACK, depth-1)
		replica = board[:]
		pp_num = pp_num * -1
		if pp_num > max:
			max = pp_num
			max_x = x
			max_y = y
	pack_value = (max, max_x, max_y)
	return pack_value

def last_search(COUNT, board, PIECE, depth):
	if depth == 0:
		pack_value = (board.count(COUNT), 0, 0)
		#print "board.count(PIECE):", board.count(PIECE)
		return pack_value
	replica = board[:]
	pp = possible_point(replica, PIECE)
	pp_num = 0
	max = -999
	max_x = 0
	max_y = 0
	if len(pp) == 0: #PIECE is pass
		if PIECE == BLACK:
			pp_num,trash,trash = last_search(COUNT, replica, WHITE, depth-1)
		else:
			pp_num,trash,trash = last_search(COUNT, replica, BLACK, depth-1)
		pp_num = pp_num * -1
		if pp_num > max:
			max = pp_num

	while len(pp) > 0:
		x, y, count = pp.pop()
		ans, replica = all_reverse(replica, PIECE, x, y)#my turn
		if PIECE == BLACK:
			pp_num,trash,trash = last_search(COUNT, replica, WHITE, depth-1)
		else:
			pp_num,trash,trash = last_search(COUNT, replica, BLACK, depth-1)
		replica = board[:]
		pp_num = pp_num * -1
		if pp_num > max:
			max = pp_num
			max_x = x
			max_y = y
	pack_value = (max, max_x, max_y)
	return pack_value


max, x, y = depth_search(board, BLACK, 5)
print "max, x, y:", max, x, y

print "start othello"

print_board(board)

x, y = 0, 0

turn_num = 64 - 4 #8x8 - start stone
while x < BOARD_SIZE or y < BOARD_SIZE:
	ans = 0
	pass_flg = 0
	while ans == 0:
		#print "BLACK turn"
		pp = possible_point(board, BLACK)
		if len(pp) == 0:
			print "BLACK pass"
			pass_flg += 1
			break
		#print pp
		#x = input("enter x: ")
		#y = input("enter y: ")
		#x, y, count = pp.pop()
		if turn_num > 6:
			x, y, count = pp.pop()
			max, x, y = depth_search(board, BLACK, 2)
		else:
			print "last_search:"
			print_board(board)
			max, x, y = last_search(BLACK, board, BLACK, 6)
		print "max, x, y:", max, x, y
		if max == -999:
			x, y, count = pp.pop()
		ans, board = all_reverse(board, BLACK, x, y)
		#print ans
		turn_num -= 1
		print_board(board)

	ans = 0
	while ans == 0:
		#print "WHITE turn"
		pp = possible_point(board, WHITE)
		if len(pp) == 0:
			print "WHITE pass"
			pass_flg += 1
			break
		#print pp
		x = input("enter x: ")
		y = input("enter y: ")
		#if turn_num > 10:
		#	max, x, y = depth_search(board, WHITE, 2)
		#else:
		#	#print "last_search:"
		#	print_board(board)
		#	max, x, y = last_search(WHITE, board, WHITE, 10)
		#if max == -999:
		#	x, y, count = pp.pop()
		#print "max, x, y:", max, x, y
		ans, board = all_reverse(board, WHITE, x, y)
		#print ans
		turn_num -= 1
		print_board(board)
	
	if pass_flg >= 2:
		break
	print turn_num, "w:", board.count(WHITE), "b:", board.count(BLACK)

#board = all_reverse(board, BLACK, 2, 3)
print "end game"
print turn_num, "w:", board.count(WHITE), "b:", board.count(BLACK)
print_board(board)