Module chillow.service.ai

class AIOptions(Enum):
    """Enumeration that holds possible options for the AIs."""
    max_distance = range(1)

class NotKillingItselfAI(ArtificialIntelligence):
    """AI implementation to choose an action that simply does not kill the player for the next rounds.

    It does not consider the opponent's player actions.

    Attributes:
        player: The player associated with this AI.
    """

    def __init__(self, player: Player, options: List[AIOptions], max_speed: int, max_worse_distance: int,
                 depth: int):
        """Creates a new object of the NotKillingItselfAI.

        Args:
            player: The player assigned to the AI.
            options: List of possible options to change the behavior of the AI.
            max_speed: The maximum speed the AI can reach.
            max_worse_distance: A tolerance, whereby more than just the best action is calculated. Actions which are
            worse, but within this tolerance, are also considered.
            depth: Number of player actions that are looked into the future.
        """
        super().__init__(player, max_speed)
        self.__options = options
        self.__max_worse_distance = max_worse_distance

        assert depth > 0, "depth must be greater than 0"
        self.__depth = depth

    def get_information(self) -> str:
        """See base class."""
        return (super().get_information() + ", max_worse_distance=" + str(self.__max_worse_distance)
                + ", depth=" + str(self.__depth))

    def create_next_action(self, game: Game, return_value: Value):
        """See base class."""
        self._turn_ctr += 1

        game_service = GameService(game)
        game_service.turn.turn_ctr = self._turn_ctr

        surviving_actions = self.find_surviving_actions_with_best_depth(game_service)
        if AIOptions.max_distance in self.__options:
            max_distance_actions = self.calc_action_with_max_distance_to_visited_cells(game_service, surviving_actions)
            action = choice(max_distance_actions) if max_distance_actions is not None and len(
                max_distance_actions) > 0 else Action.change_nothing
        else:
            action = choice(surviving_actions) if surviving_actions is not None and len(
                surviving_actions) > 0 else Action.change_nothing

        return_value.value = action.get_index()

    def calc_action_with_max_distance_to_visited_cells(self, game_service: GameService,
                                                       actions: List[Action]) -> List[Action]:
        """Calculates a list of actions that have the property to have as many free cells as possible in front of them
        while running straight after the action has been executed.

        Args:
            game_service: The game service used for simulation of actions.
            actions: The actions to be checked

        Returns:
            List of best actions with the property having as many free cells as possible in front of the player.
        """
        max_straight_distance = 0
        best_actions: Dict[Action, int] = {}
        for action in actions:
            gs_copy = copy.deepcopy(game_service)
            try:
                player = gs_copy.game.get_player_by_id(self.player.id)
                gs_copy.visited_cells_by_player[player.id] = gs_copy.get_and_visit_cells(player, action)

                straight_distance = 0
                horizontal_multiplier, vertical_multiplier = GameService.get_horizontal_and_vertical_multiplier(player)

                for i in range(max(gs_copy.game.height, gs_copy.game.width)):
                    x = player.x + (i + 1) * horizontal_multiplier
                    y = player.y + (i + 1) * vertical_multiplier
                    if x in range(gs_copy.game.width) and y in range(gs_copy.game.height) and (
                            gs_copy.game.cells[y][x].players is None or len(gs_copy.game.cells[y][x].players) == 0):
                        straight_distance += 1
                    else:
                        break

                if len(best_actions) == 0 or straight_distance > max_straight_distance:
                    max_straight_distance = straight_distance
                    best_actions[action] = straight_distance
                    updated_best_actions: Dict[Action, int] = {}
                    for (act, dist) in best_actions.items():  # new max_straight_distance. Remove worth options
                        if dist >= max_straight_distance - self.__max_worse_distance:
                            updated_best_actions[act] = dist
                    best_actions = updated_best_actions
                elif straight_distance >= max_straight_distance - self.__max_worse_distance:  # still good option
                    best_actions[action] = straight_distance
            except InvalidPlayerMoveException as ex:
                logging.warning(ex)
                continue

        return list(best_actions.keys())

    def find_surviving_actions(self, game_service: GameService, depth: int) -> List[Action]:
        """Finds all actions that will let the player survive for the next rounds.

        Args:
            game_service: The game service used for simulation of actions.
            depth: The number of rounds the player should survive at least.

        Returns:
            Actions that will not kill the player in the next rounds.
        """
        result: List[Action] = []
        for action in Action:
            gs_copy = pickle.loads(pickle.dumps(game_service))
            try:
                player = gs_copy.game.get_player_by_id(self.player.id)
                if player.speed == self._max_speed and action == Action.speed_up:
                    continue
                gs_copy.visited_cells_by_player[player.id] = gs_copy.get_and_visit_cells(player, action)
            except InvalidPlayerMoveException:
                continue
            gs_copy.check_and_set_died_players()
            if player.active:
                interim_result = []
                if depth > 1:
                    # recursive call to look further into the future
                    interim_result = self.find_surviving_actions(gs_copy, depth - 1)

                if len(interim_result) > 0 or depth == 1:
                    result += [action]

        return result

    def find_surviving_actions_with_best_depth(self, game_service: GameService) -> List[Action]:
        """Finds all actions that won't kill the player in the next rounds.
        The number of pre-calculated player moves is reduced until surviving actions are found.

        Args:
            game_service: The game service used for simulation of actions.

        Returns:
            Actions that will not kill the player in the next rounds.
        """
        result: List[Action] = []
        for current_depth in reversed(range(1, self.__depth + 1)):
            result = self.find_surviving_actions(game_service, current_depth)
            if len(result) > 0:
                break

        return result

class PathfindingAI(NotKillingItselfAI):
    """AI implementation that chooses actions which will allow it to survive a certain number of moves.

    It does not consider enemy actions. Furthermore, the AI avoids running into too small areas or dead ends.

    Attributes:
        player: The player associated with this AI.
    """

    def __init__(self, player: Player, max_speed: int, count_paths_to_check: int):
        """Creates a new object of the PathfindingAI.

        Args:
            player: The player assigned to the AI.
            max_speed: The maximum speed the AI can reach.
            count_paths_to_check: The number of paths used to avoid dead ends.
        """
        super().__init__(player, [], max_speed, 0, 3)
        self.__count_paths_to_check = count_paths_to_check

    def get_information(self) -> str:
        """See base class."""
        return "max_speed=" + str(self._max_speed) \
               + ", count_paths_to_check=" + str(self.__count_paths_to_check)

    def create_next_action(self, game: Game, return_value: Value):
        """See base class."""
        self._turn_ctr += 1
        actions = self.create_next_actions_ranked(game)
        action = actions[0][0] if actions is not None and len(actions) > 0 else Action.get_random_action()
        return_value.value = action.get_index()

    def create_next_actions_ranked(self, game: Game) -> Optional[List[Tuple[Action, int]]]:
        """Calculates all actions with the number of reachable paths, with which the AI won't lose in the next turn.

        Args:
            game: The game object in which the AI is located and which contains the current status of the game.

        Returns:
            A list with actions and the corresponding number of accessible paths.
        """
        game_service = GameService(game)
        game_service.turn.turn_ctr = self._turn_ctr

        surviving_actions = self.find_surviving_actions_with_best_depth(game_service)

        return self.find_actions_by_best_path_connection(surviving_actions, game)

    def find_actions_by_best_path_connection(self, actions: List[Action], game: Game) -> Optional[
            List[Tuple[Action, int]]]:
        """ Calculates for the passed actions how many paths are still accessible after the execution of the action.

        For this purpose, points are randomly generated on the playing field and an algorithm for finding paths is
        used to check whether the point can be reached.

        Args:
            actions: List of actions to check.
            game: The game that contains the current state of the game.

        Returns:
            List of actions with the accessible paths.
        """
        if actions is None or len(actions) == 0:
            return None
        # shuffle the actions, so that different actions are chosen if they have the same quality and the AI is not so
        # easily predictable.
        shuffle(actions)
        actions_with_possible_paths: List[Tuple[Action, int]] = []
        free_cells_for_pathfinding = self.get_random_free_cells_from_playground(game)

        path_finder = BestFirst(diagonal_movement=DiagonalMovement.never)

        for action in actions:
            game_copy = game.copy()
            game_service = GameService(game_copy)
            try:
                player = game_service.game.get_player_by_id(self.player.id)
                game_service.visited_cells_by_player[player.id] = game_service.get_and_visit_cells(player, action)
            except InvalidPlayerMoveException:
                continue

            matrix = game_copy.translate_cell_matrix_to_pathfinding_matrix()
            current_possible_paths = 0
            length_free_cells = len(free_cells_for_pathfinding)
            for i in range(length_free_cells):
                grid = Grid(matrix=matrix)
                start = grid.node(player.x, player.y)
                end = grid.node(free_cells_for_pathfinding[i][0], free_cells_for_pathfinding[i][1])
                path, _ = path_finder.find_path(start, end, grid)
                if len(path) > 0:  # a path exists
                    current_possible_paths += 1

            actions_with_possible_paths.append((action, current_possible_paths))
        # Action with most accessible paths at index 0
        actions_with_possible_paths.sort(key=operator.itemgetter(1), reverse=True)
        return actions_with_possible_paths

    def get_random_free_cells_from_playground(self, game: Game) -> List[Tuple[int, int]]:
        """Calculates up to count_paths_to_check many points of all free fields on the playing field.

        Args:
            game: The game that contains the current state of the game.

        Returns:
            List of coordinates with x- and y-value.
        """
        free_cells: List[(int, int)] = []
        for x in range(game.width):
            for y in range(game.height):
                if game.cells[y][x].players is None or len(game.cells[y][x].players) == 0:
                    free_cells.append((x, y))
        shuffle(free_cells)  # shuffle the coordinates to get a random distribution
        return free_cells[:min(self.__count_paths_to_check, len(free_cells))]

    def _get_count_paths_to_check(self) -> int:
        return self.__count_paths_to_check

class PathfindingSearchTreeAI(PathfindingAI, SearchTreeAI):
    """This AI combines the PathfindingAI and the SearchTreeAI by favoring the former.

    Therefore it ranks all actions based on the PathfindingAI and checks finds the first surviving action with the
    SearchTreeAI.

    Attributes:
        player: The player associated with this AI.
    """

    def __init__(self, player: Player, max_speed: int, count_paths_to_check: int, depth: int,
                 paths_tolerance: float = 0.75, distance_to_check: int = 0):
        """Creates a new object of the PathfindingSearchTreeAI.

        Args:
            player: The player assigned to the AI.
            max_speed: The maximum speed the AI can reach.
            count_paths_to_check: The number of paths used to avoid dead ends.
            depth: Depth pre-calculating actions.
            paths_tolerance: A tolerance, whereby more than just the best action is calculated. Actions which are
                worse, but within this tolerance, are also considered.
                depth: Number of player actions that are looked into the future.
            distance_to_check: Distance an enemy player is allowed to be at maximum distance, so that he is taken into
                account in the calculations.
        """
        PathfindingAI.__init__(self, player, max_speed, count_paths_to_check)
        SearchTreeAI.__init__(self, player, depth, max_speed, distance_to_check=distance_to_check)
        self.__paths_tolerance = paths_tolerance

    def get_information(self) -> str:
        """See base class."""
        return "max_speed=" + str(self._max_speed) \
               + ", paths_tolerance=" + str(self.__paths_tolerance) \
               + ", count_paths_to_check=" + str(self._get_count_paths_to_check()) \
               + ", depth=" + str(self._get_depth()) \
               + ", distance_to_check=" + str(self._get_distance_to_check())

    def create_next_action(self, game: Game, return_value: Value):
        """See base class."""
        self._turn_ctr += 1

        pathfinding_actions = self.create_next_actions_ranked(game)
        self.set_best_action(pathfinding_actions, [], return_value)
        search_tree_actions = self.create_all_next_surviving_actions(game)
        self.set_best_action(pathfinding_actions, search_tree_actions, return_value)

    def set_best_action(self, pathfinding_actions: List[Tuple[Action, int]], search_tree_actions: List[Action],
                        return_value: Value):
        """Saves the best action from the list of actions from PathfindingAI and SearchTreeAI.

        Args:
            pathfinding_actions: List of actions calculated by PathfindingAI.
            search_tree_actions: List of actions calculated by SearchTreeAI
            return_value: Object to save the result of the calculation.
        """
        best_action = self.get_best_action(pathfinding_actions, search_tree_actions)
        return_value.value = best_action.get_index() if best_action is not None else return_value.value

    def get_best_action(self, pathfinding_actions: List[Tuple[Action, int]],
                        search_tree_actions: List[Action]) -> Optional[Action]:
        """Calculates the best action from the list of actions from PathfindingAI and SearchTreeAI.

        Args:
            pathfinding_actions: List of actions calculated by PathfindingAI.
            search_tree_actions: List of actions calculated by SearchTreeAI

        Returns:
            Best action if there is any.
        """
        if search_tree_actions is None or len(search_tree_actions) == 0:
            if pathfinding_actions is not None and len(pathfinding_actions) > 0:
                return pathfinding_actions[0][0]
            return None
        elif pathfinding_actions is None or len(pathfinding_actions) == 0:
            return search_tree_actions[0]

        for (action, possible_paths) in pathfinding_actions:
            if action in search_tree_actions:
                if possible_paths == pathfinding_actions[0][1]:
                    return action  # best path and surviving guaranteed
                elif possible_paths >= pathfinding_actions[0][1] * self.__paths_tolerance:
                    return action  # good path and surviving guaranteed
                else:
                    break

        return pathfinding_actions[0][0]

class RandomAI(ArtificialIntelligence):
    """AI that randomly chooses an action ignoring the state of the game.

    Attributes:
        player: The player associated with this AI.
    """

    def create_next_action(self, game: Game, return_value: Value):
        """See base class."""
        self._turn_ctr += 1
        action = Action.get_random_action()
        return_value.value = action.get_index()

    def get_information(self) -> str:
        """See base class."""
        return ""

class RandomWaitingAI(RandomAI):
    """AI that randomly chooses an action ignoring the state of the game and waits five seconds.

    Attributes:
        player: The player associated with this AI.
    """

    def create_next_action(self, game: Game, return_value: Value):
        time.sleep(5)
        super().create_next_action(game, return_value)

class SearchTreeAI(ArtificialIntelligence):
    """The SearchTreeAI tries to create a tree by simulating different actions for all player for the next rounds.

    If there is an initial action that lets the player survive for the next rounds not depending on which action
    the other players will make, this action will be chosen.

    Attributes:
        player: The player associated with this AI.
    """

    def __init__(self, player: Player, depth: int, max_speed: int = 10, randomize: bool = False,
                 distance_to_check: int = 0):
        """ Creates a new object of the SearchTreeAI.

        Args:
            player: The player assigned to the AI.
            max_speed: The maximum speed the AI can reach.
            depth: Depth pre-calculating actions.
            randomize: Indicating whether to calculate actions in tree in random order.
            distance_to_check:
                Distance an enemy player is allowed to be at maximum distance, so that he is taken into
                account in the calculations.
        """

        super().__init__(player, max_speed)
        self.__depth = depth
        self.__randomize = randomize
        self.__distance_to_check = distance_to_check

    def get_information(self) -> str:
        """See base class."""
        return (super().get_information() +
                ", depth=" + str(self.__depth) +
                ", randomize=" + str(self.__randomize) +
                ", distance_to_check=" + str(self.__distance_to_check))

    def create_next_action(self, game: Game, return_value: Value):
        """See base class."""
        self._turn_ctr += 1

        root = SearchTreeRoot(game.copy())
        player_ids_to_watch = game.get_other_player_ids(self.player, self.__distance_to_check, True)
        combinations = Action.get_combinations(len(player_ids_to_watch))

        action = root.calculate_action(self.player, player_ids_to_watch, combinations, self.__depth, self._turn_ctr,
                                       True, [], self._max_speed, self.__randomize)
        return_value.value = (action if action is not None else Action.get_random_action()).get_index()

    def create_all_next_surviving_actions(self, game: Game) -> List[Action]:
        """Calculates not only one but all actions that will let the player survive for the next rounds.

        Args:
            game: The current state of the game.

        Returns:
            A list of actions which will let the player survive for the next rounds.
        """

        root = SearchTreeRoot(game.copy())
        player_ids_to_watch = game.get_other_player_ids(self.player, self.__distance_to_check, True)
        combinations = Action.get_combinations(len(player_ids_to_watch))

        search_tree_actions = []

        for action in Action.get_actions():
            if root.calculate_action(self.player, player_ids_to_watch, combinations, self.__depth, self._turn_ctr, True,
                                     [action], self._max_speed, True) is not None:
                search_tree_actions.append(action)

        return search_tree_actions

    def _get_depth(self) -> int:
        return self.__depth

    def _get_distance_to_check(self) -> int:
        return self.__distance_to_check

class SearchTreePathfindingAI(PathfindingAI, SearchTreeAI):
    """This AI combines the SearchTreeAI and the PathfindingAI by favoring the former.

    Therefore it finds all actions that let the player survive the next rounds by using the SearchTreeAI and
    afterwards lets the PathfindingAI check which of these is the best action to perform.

    Attributes:
        player: The player associated with this AI.
    """

    def __init__(self, player: Player, max_speed: int, count_paths_to_check: int, depth: int,
                 distance_to_check: int = 0):
        """Creates a new object of the SearchTreePathfindingAI.

        Args:
            player: The player assigned to the AI.
            max_speed: The maximum speed the AI can reach.
            count_paths_to_check: The number of paths used to avoid dead ends.
            depth: Number of pre-calculating actions.
            distance_to_check:
                Distance an enemy player is allowed to be at maximum distance, so that he is taken into
                account in the calculations.
        """
        PathfindingAI.__init__(self, player, max_speed, count_paths_to_check)
        SearchTreeAI.__init__(self, player, depth, max_speed, distance_to_check=distance_to_check)

    def get_information(self) -> str:
        """See base class."""
        return "max_speed=" + str(self._max_speed) \
               + ", count_paths_to_check=" + str(self._get_count_paths_to_check()) \
               + ", depth=" + str(self._get_depth()) \
               + ", distance_to_check=" + str(self._get_distance_to_check())

    def create_next_action(self, game: Game, return_value: Value):
        """See base class."""
        self._turn_ctr += 1

        surviving_actions = self.create_all_next_surviving_actions(game)
        if surviving_actions is not None and len(surviving_actions) > 0:
            return_value.value = choice(surviving_actions).get_index()
            return_value.value = self.find_actions_by_best_path_connection(surviving_actions, game)[0][0].get_index()
        else:
            surviving_pathfinding_actions = self.find_actions_by_best_path_connection(
                self.find_surviving_actions(GameService(game), 1), game)
            return_value.value = surviving_pathfinding_actions[0][0].get_index() \
                if surviving_pathfinding_actions is not None and len(surviving_pathfinding_actions) > 0 \
                else Action.get_default().get_index()