# Othello.py
# Hyung-Joon Kim, CSE, University of Washington

import time

def introduce():
    return "My name is 'Blue MoJo', and I'm a sloppy A.I. player programmed by "+\
           "Hyung-Joon Kim."

def nickname(): return "Blue MoJo"

INIT_BOARD = [[' ',' ',' ',' ',' ',' ',' ',' '],
              [' ',' ',' ',' ',' ',' ',' ',' '],
              [' ',' ',' ',' ',' ',' ',' ',' '],
              [' ',' ',' ','W','B',' ',' ',' '],
              [' ',' ',' ','B','W',' ',' ',' '],
              [' ',' ',' ',' ',' ',' ',' ',' '],
              [' ',' ',' ',' ',' ',' ',' ',' '],
              [' ',' ',' ',' ',' ',' ',' ',' ']]

COLUMN_IDX =  "    0    1    2    3    4    5    6    7"
ROW_IDX = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H']
ROW_IDX_DICT = {'A':0, 'B':1, 'C':2, 'D':3, 'E':4, 'F':5, 'G':6, 'H':7}
ROW_IDX_DICT2 = { 0:'A', 1:'B', 2:'C', 3:'D', 4:'E', 5:'F', 6:'G', 7:'H'}

def printBoard(board):
    print "   "+COLUMN_IDX
    for i in range(0,8):
        print "  "+ROW_IDX[i] + "  " + str(board[i]) + "  " + ROW_IDX[i]
        if i != 7: print
    print "   "+COLUMN_IDX; print

def opponent(whoseMove):
    if whoseMove == 'B': return 'W'
    elif whoseMove == 'W': return 'B'

#   NW  N  NE
#     \ | /
#  W -- D -- E
#     / | \
#   SW  S  SE

N = 0; NE = 1; E = 2; SE = 3;
S = 4; SW = 5; W = 6; NW = 7;
DIRECTION = [N, NE, E, SE, S, SW, W, NW]

def checkForfeit(board, whoseMove): 
    return successors(board, whoseMove) == []

def getFreeCells(board):
    vacant = [] # All free cells, not guaranteed legal move
    # Find all free cells
    for i in range(8):
        for j in range(8):
            if board[i][j] == ' ':                   
                vacant.append((i,j))
    return vacant

def showLegalCells(board, whoseMove = 'B'):
    vacant = getFreeCells(board)
    legal = legalMove(board, vacant, whoseMove)
    legal_cells = legal[0]
    if legal_cells != []:
        string = ""
        for cell in legal_cells:
            string = string + "("+ROW_IDX_DICT2[cell[0]]+","+str(cell[1])+") "
        return string
    return None
    
def successors(board, whoseMove):
    '''Return all the successors in the current state of the given board'''     
    move = []         # List of possible moves
    reversiList = []  # List of reversi's that will be fliped over
    success = []
    
    vacant = getFreeCells(board)
    # Given all the free cells, find the list of legal moves only
    successive = legalMove(board, vacant, whoseMove)
    move = successive[0]
    reversiList = successive[1]

    numMove = 0 
    for reversi in reversiList:
        newBoard = copyBoard(board)
        for r in reversi:  # Flip over all discs in the list 'reversi'       
            i = r[0]
            j = r[1]
            newBoard[i][j] = whoseMove
        pos = move[numMove]
        newBoard[pos[0]][pos[1]] = whoseMove  # Make a legal move
        numMove = numMove + 1
        success.append(newBoard)
    return success


def legalMove(board, vacant, whoseMove):
    '''Return the list which consists of the list of all legal moves and
    the list of all the opponent's discs which will be flanked by a legal move'''
    move = []
    reversiList = []
    other = opponent(whoseMove)
    # Given all free cells, find all valid moves that flanks
    # the opponent's discs
    for v in vacant:
        for d in DIRECTION:
            currCell = getAdjacentCell(v[0], v[1], d)
            if currCell != []:
                row = currCell[0];  col = currCell[1]
            currReversi = []
            # For each direction, collect all opponent's discs
            # that can be possibly fliped over.
            while currCell != [] and board[row][col] == other:                
                currReversi.append((row, col))
                currCell = getAdjacentCell(row, col, d)
                if currCell != []:
                    row = currCell[0];  col = currCell[1]
            # If the collected discs in a row or diagnol end with
            # the player's disc, this vacant cell is valid for
            # a legal move that flanks all the collected discs.
            if currCell !=[] and board[row][col] == whoseMove and currReversi != []:               
                reversiList.append(currReversi)
                move.append(v)                
    return [move, reversiList]    


def getAdjacentCell(row, col, direction):
    '''Return the indices of an adjacent cell to the given cell'''
    if direction == N:
        if row > 0: return [row-1, col]
        else: return []
    elif direction == NE:
        if row > 0 and col < 7: return [row-1, col+1]
        else: return []
    elif direction == E:
        if col < 7: return [row, col+1]
        else: return []
    elif direction == SE:
        if row < 7 and col < 7: return [row+1, col+1]
        else: return []
    elif direction == S:
        if row < 7: return [row+1, col]
        else: return []
    elif direction == NW:
        if row > 0 and col > 0: return [row-1, col-1]
        else: return []
    elif direction == W:
        if col > 0: return [row, col-1]
        else: return []
    elif direction == SW:
        if row < 7 and col > 0: return [row+1, col-1]
        else: return []
    else: return []    


def copyBoard(board):
    return [board[0][:], board[1][:], board[2][:], board[3][:],
            board[4][:], board[5][:], board[6][:], board[7][:]]


def userMove(board, row, col, whoseMove='B'):
    '''Return a new Board in which the user's move is applied.
    If the move is not valid, return null'''
    row = row.upper()
    row = ROW_IDX_DICT[row]    
    if board[row][col] != ' ': # the cell is not vacant
        return []
    else:
        successive = legalMove(board, [[row,col]], whoseMove)        
        move = successive[0]
        reversiList = successive[1]        
        if move != []:
            # Legal move, so make move and flip the opponent's disc over
            success = copyBoard(board)
            pos = move[0]
            for reversi in reversiList:
                for r in reversi:
                    i = r[0]
                    j = r[1]
                    success[i][j] = whoseMove
            success[pos[0]][pos[1]] = whoseMove
            return success
        else:  # Illegal move which doesn't flank the opponent's discs
            return [] 


# Global variables for search statistics    
NUM_BOARD_POSITIONS = 0
NUM_ALPHA_CUTOFFS = 0
NUM_BETA_CUTOFFS = 0
MAX_PLY = 5

def aiMove(board, whoseMove='W'):
    '''Return a new board that represents the result of
    A.I.'s making one move. This function calls the minimax function
    to evaluate the values of each of possible successors to the
    given board.'''
    global NUM_BOARD_POSITIONS
    global NUM_ALPHA_CUTOFFS, NUM_BETA_CUTOFFS
    global MAX_PLY    
    NUM_BOARD_POSITIONS = 0
    NUM_ALPHA_CUTOFFS, NUM_BETA_CUTOFFS = 0,0    
    alpha = -100000; beta = 100000
    
    t = time.time()
    bestMove = minimax(board, whoseMove, MAX_PLY, alpha, beta)
    t = time.time() - t
    
    newBoard = bestMove[0]
    statList = ["* Best-move is searched with Maximum depth of "+str(MAX_PLY),
               "* "+str(NUM_BOARD_POSITIONS)+" board positions"+\
               " evaluated for searching a best-move.\n"+\
               "* "+str(NUM_ALPHA_CUTOFFS)+" Alpha cutoff(s), "+\
               str(NUM_BETA_CUTOFFS)+" Beta cutoff(s) found.",
               "* "+str(t)+" milliseconds consumed during the search."]
    strComment = expression(newBoard)
    
    return [newBoard, statList, strComment]

def expression(board):
    n = staticValue(board)
    if n > 0: return "It's favorable to you.\n" 
    elif n == 0: return "It's a close game, isn't it?\n"    
    else: return "I guess, things are going well for me, human.\n"


def minimax(board, whoseMove, maxPly, alpha, beta):
    '''Peform minimax search to a depth of maxPly from the
    given board. Then, return a provisional value which would
    be favorable for a certain checker.'''
    global NUM_BOARD_POSITIONS
    global NUM_ALPHA_CUTOFFS, NUM_BETA_CUTOFFS
    bestMove = []
    
    if maxPly == 0:
        return [board, staticValue(board)]
    if whoseMove == 'B': provisional = -100000        
    else: provisional = 100000

    # To increase the tendancy of cutoffs, order the subtress of
    # the current board state in best-first fashion.
    successorList = bestFirstOrder(successors(board, whoseMove))
    
    for s in successorList:
        NUM_BOARD_POSITIONS += 1
        # Node represents a board position
        # in form of [board, provisional number]        
        node = minimax(s, opponent(whoseMove), maxPly-1, alpha, beta)
        newVal = node[1]
        
        if whoseMove == 'B' and newVal > provisional:          
            provisional = newVal
            bestMove = s
            if provisional > alpha:
                if provisional >= beta:  # Alpha cutoff occured                 
                    NUM_ALPHA_CUTOFFS += 1
                    break
                else:
                    alpha = provisional
        elif whoseMove == 'W' and newVal < provisional:
            provisional = newVal
            bestMove = s
            if provisional < beta:
                if provisional <= alpha:  # Beta cutoff occured
                    NUM_BETA_CUTOFFS +=1
                    break
                else:
                    beta = provisional;
                    
    return [bestMove, provisional]        


def bestFirstOrder(successors):
    '''Return a new sorted list of successors in the manner that
    the static values of successors are in best-first order.'''
    staticVal_index_Hash = {}  # e.g. a = { 7: 0, -2: 1, 11: 2 }
    index_successors_Hash = {} # e.g. b = { 0: s1, 1: s2, 2: s3 }
    bestFirst = []             # e.g. c = [ b[2], b[0], b[1] ]
    idx = 0
    for s in successors:  
        staticVal_index_Hash[staticValue(s)] = idx
        index_successors_Hash[idx] = s
        idx += 1
    staticVal = staticVal_index_Hash.keys()
    staticVal.sort()
    staticVal.reverse()
    for val in staticVal:
        idx = staticVal_index_Hash[val]
        bestFirst.append(index_successors_Hash[idx])
    return bestFirst   

# Coefficients of heuristic evaluation function for static values
WEIGHT = [[50 , -1,  5,  2 ,  2,  5, -1, 50],
 	  [-1 ,-10,  1,  1 ,  1,  1,-10, -1],
          [ 5 ,  1,  1,  1 ,  1,  1,  1,  5],
	  [ 2 ,  1,  1,  0 ,  0,  1,  1,  2],
	  [ 2 ,  1,  1,  0 ,  0,  1,  1,  2],
	  [ 5 ,  1,  1,  1 ,  1,  1,  1,  5],
	  [-1 ,-10,  1,  1 ,  1,  1,-10, -1],
	  [50 , -1,  5,  2 ,  2,  5, -1, 50]]

def staticValue(board):
    '''Return a number representing the static value of the
    given board. If this position is favorable for black,
    the number should be positive, and if it is favorable
    for white, the number should be negative.'''
    blackVal = 0;  whiteVal = 0;
    for i in range(8):
        for j in range(8):
            if board[i][j] == 'B':
                blackVal += WEIGHT[i][j]
            elif board[i][j] == 'W':
                whiteVal += WEIGHT[i][j]   
    return blackVal - whiteVal


def justPlayed(old, new, whoseMove = 'W'):
    '''Return the position at which a player just placed a disc'''
    for i in range(8):
        for j in range(8):
            if old[i][j] == ' ' and new[i][j] == whoseMove:                
                return [ROW_IDX_DICT2[i], j]
NUM_BLACK = 0
NUM_WHITE = 0

def reportResult(board):    
    global NUM_BLACK, NUM_WHITE
    NUM_BLACK, NUM_WHITE = 0, 0
    for i in range(8):
        for j in range(8):
            if board[i][j] == 'B':
                NUM_BLACK += 1
            elif board[i][j] == 'W':
                NUM_WHITE += 1
    score = "Score:\n"+"\tBlack = "+str(NUM_BLACK)+", "+"White = "+str(NUM_WHITE)
    if NUM_BLACK > NUM_WHITE: return score+"\n\tBlack wins!\n"
    elif NUM_BLACK < NUM_WHITE: return score+"\n\tWhite wins!\n"
    else: return score+"\n\tDraw!\n"        

# Global variables for optional Settings
SHOW_MOVE = False               # move position just played
SHOW_SEARCH_STATS = False       # num of evaluated board, num of cutoffs
SHOW_SEARCH_TIME = False        # time taken for the serch
SHOW_EVAL_FUNCTION = False      # static value evaluation weight
SHOW_MAXPLY = False             # max depth for the search

def showMove(x): global SHOW_MOVE;  SHOW_MOVE = x
def showStats(x): global SHOW_SEARCH_STATS;  SHOW_SEARCH_STATS = x
def showTime(x): global SHOW_SEARCH_TIME;  SHOW_SEARCH_TIME = x
def showEvalFunc(x): global SHOW_EVAL_FUNCTION;  SHOW_EVAL_FUNCTION = x
def showMaxPly(x): global SHOW_MAXPLY;  SHOW_MAXPLY = x
def setMaxPly(x): global MAX_PLY;  MAX_PLY = x

def initSettings():
    global SHOW_MOVE, SHOW_SEARCH_STATS, SHOW_SEARCH_TIME,SHOW_EVAL_FUNCTION,\
           SHOW_MAXPLY, MAX_PLY
    SHOW_MOVE, SHOW_SEARCH_STATS, SHOW_SEARCH_TIME = False, False, False
    SHOW_EVAL_FUNCTION, SHOW_MAXPLY = False, False
    MAX_PLY = 5