import games

import random

import util



def getOthelloAgent():

   return FixedDepthHeuristicGameAgent(AlphaBeta(), comboHeuristic, 5)



class GameAgent:

   """ Abstract GameAgent class. Your agents should inherit from this class

       and override the getAction method.  """



   def getAction(self, gameState):

       """  Return a move in gameState.actions(), where gameState is an instance of a subclass of GameState. """

       abstract



class UtilityDirectedGameAgent(GameAgent):

   """ A game agent that chooses the action with the highest utility  """

   def __init__(self, searcher):

       self.searcher = searcher;



   def getAction(self, currentState):

       bestAction, value = self.searcher.getBestActionAndValue(currentState)

       print "Got state value %s with best action %s" % (value, bestAction)

       return bestAction





class GameTreeSearcher:

   """ Interface for classes that search the game tree exhaustively,

       returning a maximum-utility action and its value (or a bound thereupon) """



   def getBestActionAndValue(self, currentState):

       """ Return the best action and its value in currentState for currentState.currentPlayer() """

       abstract





class FixedDepthHeuristicGameAgent(UtilityDirectedGameAgent):

   """A game agent that chooses the action with the max expected utility

      according to heiristicEvalFn, after looking ahead by searchDepth ply.

      You will create instances of this class to use your heuristic functions,

      but you don't need to understand how it works in detail. """



   def __init__(self, searcher, heuristicEvalFn, searchDepth):

       self.searcher = searcher;

       self.heuristicEvalFn = heuristicEvalFn

       self.searchDepth = searchDepth



   def getAction(self, currentState):

       wrappedState = games.FixedDepthHeuristicGameStateAdapter(currentState, self.heuristicEvalFn, self.searchDepth)

       return UtilityDirectedGameAgent.getAction(self, wrappedState)



"""class newFixedDepthHeuristicGameAgent(UtilityDirectedGameAgent):



   def __init__(self, searcher, heuristicEvalFn, searchDepth):

       self.searcher = searcher;

       self.heuristicEvalFn = heuristicEvalFn

       self.searchDepth = searchDepth



   def getAction(self, currentState):

       wrappedState = games.FixedDepthHeuristicGameStateAdapter(currentState, self.heuristicEvalFn, self.searchDepth)

       size = wrappedstate.boardSize

       availMoves = state.actions()

       if((0,0) in availMoves):

           return (0,0)

       elif((0,size-1_ in availMoves):

           return (0,size-1)

       elif((size-1, 0) in availMoves):

           return (size-1,0)

       elif((size-1, size-1) in availMoves):

           return (size-1, size-1)

       else:

           return UtilityDirectedGameAgent.getAction(self, wrappedState)

           """



class AlphaBeta(GameTreeSearcher):

   """

       A game agent that picks the best action by exhaustively searching the game tree,

       backing up values according to the minimax algorithm, and pruning unnecessary

       branches using the Alpha-Beta Pruning algorithm



       TODO (Q4): Fill in the implementation of this class.

       When complete, it should be able to prove that Tic Tac Toe is a draw

       from the starting position, significantly faster than ordinary Minimax.



       You can assume that all utilities are in the range [-1, 1].

       If you do, please don't forget this when you implement your heuristic functions later.



       As for Minimax, you can opt for a mutually recursive two-function approach,

       or take advantage of the fact that we are only interested in zero-sum games

       to implement a single recursive "Negamax" version.

   """



   def getBestActionAndValue(self, currentState):

       """ Return the best action and its value in currentState for currentState.currentPlayer() """

       # TODO (Q4): Write this method

       neginfinity = -float("infinity")

       return self.minimax(currentState, neginfinity, neginfinity)



   def minimax(self, currentState, alpha, beta):

       moves = currentState.actions()

       maxSoFar = None

       maxPair = None

       utility = currentState.currentPlayerUtility()

       if utility != None:

           return None, utility

       else:

           for action in moves:

               oppAction, oppUtility = self.minimax(currentState.successor(action), beta, alpha)

               oppUtility = -oppUtility

               if (oppUtility >= (-beta)):

                   return None, oppUtility

               elif (oppUtility > maxSoFar):

                   maxSoFar = oppUtility

                   alpha = maxSoFar

                   maxPair = action

           return maxPair, maxSoFar



class GraphAlphaBeta(GameTreeSearcher):



   def getBestActionAndValue(self, currentState):

       """ Return the best action and its value in currentState for currentState.currentPlayer() """

       # TODO (Q4): Write this method

       neginfinity = -float("infinity")

       self.translocationTable = {}

       table = self.translocationTable

       maxPair, maxSoFar, table = self.minimax(currentState, neginfinity, neginfinity, table)

       return maxPair, maxSoFar



   def minimax(self, currentState, alpha, beta, translocationTable):

       moves = currentState.actions()

       maxSoFar = None

       maxPair = None

       utility = currentState.currentPlayerUtility()

       if utility != None:

           return None, utility, translocationTable

       else:

           for action in moves:

               nextState = currentState.successor(action)

               if translocationTable.has_key(nextState):

                   oppUtility = translocationTable[nextState]

               else:

                   oppAction, oppUtility, translocationTable = self.minimax(nextState, beta, alpha, translocationTable)

                   oppUtility = -oppUtility

                   translocationTable[nextState] = oppUtility

               if (oppUtility >= (-beta)):

                   return None, oppUtility, translocationTable

               elif (oppUtility > maxSoFar):

                   maxSoFar = oppUtility

                   alpha = maxSoFar

                   maxPair = action

           return maxPair, maxSoFar, translocationTable



def uniformSquareValue(size, x, y):

   """ A function that gives all squares an equal weight of 1 """

   return 1





def edgeCornerSquareValue(state, size, x, y):

   """

       A function that returns different values for interior, edge, and corner squares on

       an othello board (0,size-1),  ... ,  (size-1, size-1)

                          ....................

                        (0,0),      (1,0), ... (size-1, 0)



       TODO (Q6): Complete this function so that it gives higher value to corner squares

       than edge squares than interior squares, experimenting with different values to see

       which performs best.  Your function should work for any value of size.

   """

   # TODO (Q6): complete this function

   board = state.board

   val = 0

   if board[size-1][size-1] == " " and x == size-3 and y == size-3:

       val += 2

   elif board[0][size-1] == " " and x == 2 and y == size-3:

       val += 2

   elif board[0][0] == " " and x == 2 and y == 2:

       val += 2

   elif board[size-1][0] == " " and x == size-3 and y == 2:

       val += 2



   if board[size-1][size-1] == " " and x == size-2 and y == size-2:

       val += -8

   elif board[0][size-1] == " " and x == 1 and y == size-2:

       val += -8

   elif board[0][0] == " " and x == 1 and y == 1:

       val += -8

   elif board[size-1][0] == " " and x == size-2 and y == 1:

       val += -8



   val += wedge(state, size, x, y)



   if x == size-1 or x == 0:

       if y == size-1 or y == 0:

           val += 32

           return val

       else:

           val += 4

           return val

   elif y == size-1 or y == 0:

       val += 4

       return val

   else:

       val += 1

       return val



def comboHeuristic(state):

   return .75*edgeCornerOthelloHeuristic(state) + .25*moveCountHeuristic(state)



def moveCountHeuristic(state):

   availMoves = len(state.actions())

   if availMoves < 2:

       return -1

   elif availMoves < 5:

       return -.7

   elif availMoves < 6:

       return -.4

   elif availMoves < 7:

       return -.2

   elif availMoves < 8:

       return 0

   elif availMoves < 9:

       return .2

   elif availMoves < 10:

       return .4

   elif availMoves < 11:

       return .6

   elif availMoves < 12:

       return 1

   else:

       return 1





def wedge(state, size, x, y):

   board = state.board

   rim = size-1

   currentPlayer= state.currentPlayer()

   opponent = None

   if currentPlayer == "W":

       opponent = "B"

   else:

       opponent = "W"



   if x == 0 or x == rim:

       if y != 0 and y != rim:

           if board[x][y-1] == opponent and board[x][y+1] == opponent and y % 2 == 0:

               return 4

   if y == 0 or y == rim:

       if x != 0 and x != rim:

           if board[x-1][y] == opponent and board[x+1][y] == opponent and x % 2 == 0:

               return 4

   return 0





def pieceCountOthelloHeuristic(state, squareValueFn = uniformSquareValue):

   """

       A heuristic evaluation function for Othello that values a position

       by the difference in the number of pieces of the two players, weighted

       by position according to squareValueFn.  By default, uniformSquareValue

       is used, which assigns all squares a weight of 1.

   """

   size = state.boardSize

   currentPlayer = state.currentPlayer()

   board = state.board



   runningTotal = 0.0

   maxPoss = 0.0

   edges = (0, size-1)

   for y in range(size):

       for x in range(size):

           square = board[y][x]

           value = squareValueFn(state,size,x,y)

           maxPoss += value

           if square != " ":

               if square == currentPlayer: runningTotal += value

               else:                       runningTotal -= value



   return runningTotal / maxPoss





def edgeCornerOthelloHeuristic(state):

   """ An Othello heuristic that counts pieces weighted by edgeCornerSquareValue(size, x, y) """

   return pieceCountOthelloHeuristic(state, edgeCornerSquareValue)