import copy


class ExamplePlayer:

    __FINISHING_HEXES = {
        'r': {(3,-3), (3,-2), (3,-1), (3,0)},
        'g': {(-3,3), (-2,3), (-1,3), (0,3)},
        'b': {(-3,0),(-2,-1),(-1,-2),(0,-3)},
    }

    def __init__(self, colour):
        """
        This method is called once at the beginning of the game to initialise
        your player. You should use this opportunity to set up your own internal
        representation of the game state, and any other information about the
        game state you would like to maintain for the duration of the game.

        The parameter colour will be a string representing the player your
        program will play as (Red, Green or Blue). The value will be one of the
        strings "red", "green", or "blue" correspondingly.
        """
        # TODO: Set up state representation.

        # To let AI know the colour they are playing and the board infomation

        #The colour of the AI
        self.my_colour = colour[0]

        #The starting board information
        self._BOARD = {
            'r': {(-3,3), (-3,2), (-3,1), (-3,0)},
            'g': {(0,-3), (1,-3), (2,-3), (3,-3)},
            'b': {(3, 0), (2, 1), (1, 2), (0, 3)},
        }

        #The information with the number of exits of all players
        self._EXITS = {
            'r': 0,
            'g': 0,
            'b': 0,
        }

    def action(self):
        """
        This method is called at the beginning of each of your turns to request
        a choice of action from your program.

        Based on the current state of the game, your player should select and
        return an allowed action to play on this turn. If there are no allowed
        actions, your player must return a pass instead. The action (or pass)
        must be represented based on the above instructions for representing
        actions.
        """

        # AI will only Exit if we have enough pieces to win otherwise
        # it will not exit the piece
        # e.g. we already exit two pieces, there is only on on the board,
        #      we will try not to exit and try eat others to have enough pieces to win
        if(self._EXITS[self.my_colour] + len(self._BOARD[self.my_colour]) >= 4):
            for piece in self._BOARD[self.my_colour]:
                if piece in self.__FINISHING_HEXES[self.my_colour]:
                    return ('EXIT',piece)

        #calculating the best move using minimax with depth of 2
        myaction = self.minimax(self._BOARD,self.my_colour,2,True)

        # re-format the best action to provide to the referee
        if(myaction[0][0] == 'PASS'):
            return ("PASS", None)
        if(myaction[0][1] == 'EXIT'):
            return ('EXIT',myaction[0][0])

        if(abs(myaction[0][1][0] - myaction[0][0][0]) <= 1 and abs(myaction[0][1][1] - myaction[0][0][1]) <= 1):
            return(('MOVE',myaction[0]))
        else:
            return(('JUMP',myaction[0]))


    def update(self, colour, action):

        """
        This method is called at the end of every turn (including your player’s
        turns) to inform your player about the most recent action. You should
        use this opportunity to maintain your internal representation of the
        game state and any other information about the game you are storing.

        The parameter colour will be a string representing the player whose turn
        it is (Red, Green or Blue). The value will be one of the strings "red",
        "green", or "blue" correspondingly.

        The parameter action is a representation of the most recent action (or
        pass) conforming to the above in- structions for representing actions.

        You may assume that action will always correspond to an allowed action
        (or pass) for the player colour (your method does not need to validate
        the action/pass against the game rules).
        """
        # TODO: Update state representation in response to action.

        #update the inforamtion given to the AI's board

        if action[0] != 'PASS':
            if colour == 'red':
                if action[0] == 'EXIT':
                    self._BOARD['r'].remove(action[1])
                    self._EXITS['r'] += 1
                elif action[0] == 'JUMP':
                    self._BOARD['r'].remove(action[1][0])
                    self._BOARD['r'].add(action[1][1])
                    #setting the peice that is jumped
                    pos = self.find_middle(action[1][0],action[1][1])
                    for key in self._BOARD:
                        if(pos in self._BOARD[key]):
                            self._BOARD[key].remove(pos)
                            self._BOARD['r'].add(pos)
                else:
                    self._BOARD['r'].add(action[1][1])
                    self._BOARD['r'].remove(action[1][0])
            elif colour == 'green':
                if action[0] == 'EXIT':
                    self._BOARD['g'].remove(action[1])
                    self._EXITS['g'] += 1
                elif action[0] == 'JUMP':
                    self._BOARD['g'].remove(action[1][0])
                    self._BOARD['g'].add(action[1][1])
                    #setting the peice that is jumped
                    pos = self.find_middle(action[1][0],action[1][1])
                    for key in self._BOARD:
                        if(pos in self._BOARD[key]):
                            self._BOARD[key].remove(pos)
                            self._BOARD['g'].add(pos)

                else:
                    self._BOARD['g'].remove(action[1][0])
                    self._BOARD['g'].add(action[1][1])
            else:
                if action[0] == 'EXIT':
                    self._BOARD['b'].remove(action[1])
                    self._EXITS['b'] += 1
                elif action[0] == 'JUMP':
                    self._BOARD['b'].remove(action[1][0])
                    self._BOARD['b'].add(action[1][1])
                    #setting the peice that is jumped
                    pos = self.find_middle(action[1][0],action[1][1])
                    for key in self._BOARD:
                        if(pos in self._BOARD[key]):
                            self._BOARD[key].remove(pos)
                            self._BOARD['b'].add(pos)

                else:
                    self._BOARD['b'].remove(action[1][0])
                    self._BOARD['b'].add(action[1][1])




    #currentpos means the position we are currently at
    #pos refers to where we are going to and return all the surroundings for analysis
    def get_surr(self,currentpos,pos,show_all_pos):
        hex = []
        if self.on_board(pos[0],pos[1] - 1):
            hex.append((pos[0],pos[1] - 1))
        if self.on_board(pos[0] + 1,pos[1] - 1):
            hex.append((pos[0] + 1,pos[1] - 1))
        if self.on_board(pos[0] + 1,pos[1]):
            hex.append((pos[0] + 1,pos[1]))
        if self.on_board(pos[0],pos[1] + 1):
            hex.append((pos[0],pos[1] + 1))
        if self.on_board(pos[0] - 1,pos[1] + 1):
            hex.append((pos[0] - 1,pos[1] + 1))
        if self.on_board(pos[0] - 1,pos[1]):
            hex.append((pos[0] - 1,pos[1]))
        if not show_all_pos:
            hex.remove(currentpos)
        return hex

    # Check if the coordinate is inside the board
    def on_board(self,x, y):
        if x == 0 and -3 <= y <= 3:
            return True
        elif x == -1 and -2 <= y <= 3:
            return True
        elif x == -2 and -1 <= y <= 3:
            return True
        elif x == -3 and 0 <= y <= 3:
            return True
        elif x == 1 and -3 <= y <= 2:
            return True
        elif x == 2 and -3 <= y <= 1:
            return True
        elif x == 3 and -3 <= y <= 0:
            return True
        else:
            return False

    #get hex distance from a (x,y) to b (x,y)
    def get_hex_distance(self,a,b):
        return max(abs(a[0] - b[0]),abs(a[1] - b[1]), abs((-1*a[0]-a[1]) - (-1*b[0]-b[1])))



    #calulating the shortest hex distance to the goals  best (1 of 4)
    def get_shortest_hex_distance(self,a,colour):
        min = 37
        for items in self.__FINISHING_HEXES[colour]:
            new_dis = self.get_hex_distance(a,items)
            if(new_dis < min):
                min = new_dis
        return min


    #calulating the shortest hex distance to the other pieces
    def get_shortest_att_distance(self,a,colour,board):
        min = 37
        pieces = set()
        for co in ('r','b','g'):
            if co != colour:
                pieces.update(board[co])
        for items in pieces:
            new_dis = self.get_hex_distance(a,items)
            if(new_dis < min):
                min = new_dis
        return min

    # find the middle coordinate between two coordinates A:(x,y) and B:(x,y)
    def find_middle(self, a,b):
        x = a[0]
        y = a[1]
        if b[0]-a[0] == 2:
            x = a[0] + 1
        elif b[0]-a[0] == -2:
            x = a[0] - 1
        if b[1]-a[1] == 2:
            y = a[1] + 1
        elif  b[1]-a[1] == -2:
            y = a[1] - 1
        return (x,y)

    #to check if A:(x,y) can jump over B:(x,y)
    def can_be_jump(self,board,a,b):
        new_pos = (b[0] + (b[0] - a[0]),b[1] + (b[1] - a[1]))
        if self.on_board(new_pos[0],new_pos[1]):
            for key in board:
                if new_pos in board[key]:
                    return False
            return True
        else:
            return False


    #Evaluation function of the board used by the minimax
    def get_total_score(self,board,colour):
        final = []
        #creating all the position of other pieces
        pieces = set()
        for key in board:
            if key != colour:
                pieces.update(board[key])

        #calulating the scaore of each piece of ours
        for i in board[colour]:
            total = 0
                # The steps to the goals with exiting move
            total += -1000*(self.get_shortest_hex_distance(i,colour)+1)

            for sur in self.get_surr(i,i,True):
                if sur in board[colour]:
                    #score for the own colour near this piece
                    total += 250
                    if (sur[0] + (sur[0] - i[0]),sur[1] + (sur[1] - i[1])) in pieces:
                        # score for protecting our own piece, in case of get eaten by other piece
                        total += 1000
                if sur in pieces:
                    if self.can_be_jump(board, sur, i):
                        # we may get eat by other colour
                        total -= 2000
                    if (sur[0] + (sur[0] - i[0]),sur[1] + (sur[1] - i[1])) in pieces:
                        # we block others way from jumping
                        total += 500
            final.append(total)


        # only calulate the best four score of our piece that is needed to win,
        #since we only need to win exiting four pieces

        final_score = 0
        index = 0
        for i in sorted(final, reverse = True):
            if index < len(self._BOARD[colour]):
                final_score += i
                index += 1

        # the score of each piece
        # the more piece we have , the higher score we got
        final_score += 3000*(len(self._BOARD[colour])+self._EXITS[colour])

        return final_score


    # check if B:(x,y) is closer to the goal of certain colour A:(x,y)
    def is_closer(self,a,b,colour):
        return self.get_shortest_hex_distance(a,colour) < self.get_shortest_hex_distance(b,colour)

    # change the given board information
    # e.g. make the move
    def make_move(self,board,a,b):
        for co in ('r','g','b'):
            if a in board[co]:
                if b == "EXIT":
                    board[co].remove(a)
                    return
                else:
                    board[co].remove(a)
                    board[co].add(b)
                    return

    # geting all the possiable move of a colour return the  list  with the move
    # e.g. [(a,b),(a,c)] NOTE: a can move to b and c
    def get_valid_move(self,board, colour):
        vaild_move = []
        pieces = set()
        #put all the pieces in pieces for checking the position
        for key in board:
            pieces.update(board[key])
        for items in board[colour]:
            #if we can exit
            # if items in self.__FINISHING_HEXES[colour]:
            #     vaild_move.append((items,'EXIT'))
            sur = self.get_surr(items,items,True)
            for pos in sur:
                # check if they can move to this position
                if pos not in pieces:
                    vaild_move.append((items,pos))
                #CHECK if they can jump over
                elif (pos[0]+(pos[0]-items[0]),pos[1]+(pos[1] - items[1])) not in pieces and self.on_board(pos[0]+(pos[0]-items[0]),pos[1]+(pos[1] - items[1])):
                    vaild_move.append((items,(pos[0]+(pos[0]-items[0]),pos[1]+(pos[1] - items[1]))))
        return vaild_move

    # our minimax function
    def minimax(self,board, colour, depth, maximizing):
        vaild_move = self.get_valid_move(board, colour)
        others_move = []
        colours = ['r','b','g']
        colours.remove(colour)
        temp_move = self.get_valid_move(board,colours[0])
        temp_colour = colours[0]
        if len(temp_move) == 0 and len(colours) > 1:
            temp_move = self.get_valid_move(board,colours[1])
            temp_colour = colours[1]
        others_move += temp_move
        colours.remove(temp_colour)
        unmoved_colour = colours[0]


        # Need to add a or condition for terminal state
        if depth == 0:
            #Termonal state
            #if AI(me) is winning return large value
            #if other is winning return low value
            #else
            #game over return 0

            return (None,self.get_total_score(board,colour))


        #maximizing part
        if maximizing:
            value = -999999
            move = ('PASS',None)
            for moves in vaild_move:
                temp_board = copy.deepcopy(board)
                self.make_move(temp_board,moves[0],moves[1])
                new_score = self.minimax(temp_board,colour,depth-1,False)[1]
                if new_score > value:
                    value = new_score
                    move = moves
            return (move,value)
        # minimizing part
        else:
            value = 999999
            move = ('PASS',None)
            for moves in others_move:
                temp_board = copy.deepcopy(board)
                self.make_move(temp_board,moves[0],moves[1])
                unmoved_colour_moves = self.get_valid_move(temp_board, unmoved_colour)
                for sec_moves in unmoved_colour_moves:
                    temp_board_2 = copy.deepcopy(temp_board)
                    self.make_move(temp_board_2,sec_moves[0],sec_moves[1])
                    new_score = self.minimax(temp_board_2,colour,depth-1,True)[1]
                    if new_score < value:
                        value = new_score
                        move = moves
            return (move,value)