Activité pratique

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import pprint

# PyRat imports
from pyrat import Game
from players.Random5 import Random5

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Instantiate a game with a few arguments
    game_config = {"mud_percentage": 0.0,
                   "maze_width": 13,
                   "maze_height": 10,
                   "nb_cheese": 1,
                   "random_seed": 42,
                   "trace_length": 1000}

    # Instantiate a game with specified arguments
    game = Game(**game_config)

    # Instantiate the player
    player = Random5()
    game.add_player(player)

    # Start the game
    stats = game.start()
    pprint.pprint(stats)

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import random

# PyRat imports
from pyrat import Player, Maze, GameState, Action

##########################################################################################
######################################### CLASSES ########################################
##########################################################################################

class Random5 (Player):

    """
    *(This class inherits from* ``Player`` *).*

    This player is an improvement of the ``Random4`` player.
    A limitation of ``Random4`` is that it gets stuck in areas when all neighbors have been visited.
    To avoid this, we keep track of the trajectory of the player, and when we are stuck, we go back to the last cell in the trajectory.
    """

    ##################################################################################
    #                                   CONSTRUCTOR                                  #
    ##################################################################################

    def __init__ ( self,
                   *args:    object,
                   **kwargs: object
                 ) ->        None:

        """
        Initializes a new instance of the class.
        Here, in addition to the attributes developed in the ``Random4`` player, we also create an attribute for our trajectory.

        Args:
            args:   Arguments to pass to the parent constructor.
            kwargs: Keyword arguments to pass to the parent constructor.
        """

        # Inherit from parent class
        super().__init__(*args, **kwargs)

        # We create an attribute to keep track of visited cells
        # We will initialize it in the ``preprocessing()`` method to allow the game to be reset
        # Otherwise, the set would keep the cells visited in previous games
        self.visited_cells = None

        # We also create an attribute for the reduced maze
        self.reduced_maze = None

        # We create an attribute for the player's trajectory
        self.trajectory = None

    ##################################################################################
    #                                  PYRAT METHODS                                 #
    ##################################################################################

    def preprocessing ( self,
                        maze:       Maze,
                        game_state: GameState,
                      ) ->          None:
        
        """
        *(This method redefines the method of the parent class with the same name).*

        This method is called once at the beginning of the game.
        Here, we use it to create a reduced maze that contains only the cells that are not dead-ends.
        We define a dead-end as a cell that has only one neighbor and does not contain cheese or the player.
        Note that this is not the best way to define a dead-end, but it is a simple one.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        """

        # Initialize visited cells
        self.visited_cells = set()

        # Reduce the maze
        my_location = game_state.player_locations[self.get_name()]
        self.reduced_maze = self.remove_dead_ends(maze, [my_location] + game_state.cheese)

        # Initialize the trajectory
        self.trajectory = [my_location]

    ##################################################################################

    def turn ( self,
               maze:       Maze,
               game_state: GameState,
             ) ->          Action:

        """
        *(This method redefines the method of the parent class with the same name).*

        It is called at each turn of the game.
        It returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        We also update the set of visited cells at each turn.
        Now, we work with the reduced maze to find the next action.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        
        Returns:
            One of the possible actions.
        """

        # Mark current cell as visited
        my_location = game_state.player_locations[self.get_name()]
        if my_location not in self.visited_cells:
            self.visited_cells.add(my_location)

        # Add current location to trajectory
        self.trajectory.append(my_location)

        # Return an action
        action = self.find_next_action(self.reduced_maze, game_state)
        return action
    
    ##################################################################################
    #                                  OTHER METHODS                                 #
    ##################################################################################

    def find_next_action ( self,
                           maze:       Maze,
                           game_state: GameState,
                         ) ->          Action:

        """
        This method returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        Here, the action is chosen randomly among those that don't hit a wall, and that lead to an unvisited cell if possible.
        If no such action exists, we come back to the last cell in the trajectory and pop it.
        
        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.

        Returns:
            One of the possible actions that leads to a valid neighbor.
        """

        # Go to an unvisited neighbor in priority
        my_location = game_state.player_locations[self.get_name()]
        neighbors = maze.get_neighbors(my_location)
        unvisited_neighbors = [neighbor for neighbor in neighbors if neighbor not in self.visited_cells]
        if len(unvisited_neighbors) > 0:
            neighbor = random.choice(unvisited_neighbors)
            
        # If there is no unvisited neighbor, go back in the trajectory
        # We pop the last cell in the trajectory, which is the current cell
        # Then, we pop again to get the previous cell, which is where we want to go back
        else:
            self.trajectory.pop()
            neighbor = self.trajectory.pop()
        
        # Retrieve the corresponding action
        action = maze.locations_to_action(my_location, neighbor)
        return action
    
    ##################################################################################

    def remove_dead_ends ( self,
                           maze:              Maze,
                           locations_to_keep: list[tuple[int, int]]
                         ) ->                 Maze:
        
        """
        This method returns a new maze that contains only the cells that are not dead-ends.
        A dead-end is defined as a cell that has only one neighbor and does not contain cheese or the player.

        Args:
            maze:              An object representing the maze in which the player plays.
            locations_to_keep: A list of locations to keep in the reduced maze.

        Returns:
            A new maze with only the cells that are not dead-ends.
        """

        # Initialize the reduced maze as the original one
        # We do not need to make a copy of the maze, as the game sends a copy of the maze at each turn.
        updated_maze = maze
        
        # Iteratively remove dead-ends from the maze
        # We still keep dead ends that contain locations to keep
        removed_something = True
        while removed_something:
            removed_something = False
            for vertex in updated_maze.get_vertices():
                if len(updated_maze.get_neighbors(vertex)) == 1 and vertex not in locations_to_keep:
                    updated_maze.remove_vertex(vertex)
                    removed_something = True

        # Return the updated maze
        return updated_maze

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import tqdm.auto as tqdm
import matplotlib.pyplot as pyplot
import scipy.stats as scstats

# PyRat imports
from pyrat import Game, GameMode
from players.Random1 import Random1
from players.Random2 import Random2
from players.Random3 import Random3
from players.Random4 import Random4
from players.Random5 import Random5
from players.Random6 import Random6
from players.Random7 import Random7

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Determines how many games will be played for each player
    nb_games = 1000

    # Customize the game elements
    game_config = {"mud_percentage": 0.0,
                   "nb_cheese": 1,
                   "game_mode": GameMode.SIMULATION}

    # Run the games for each player class
    players = [Random1(), Random2(), Random3(), Random4(), Random5(), Random6(), Random7()]
    results = {player.get_name(): [] for player in players}
    for player in players:
        for seed in tqdm.tqdm(range(nb_games), desc=player.get_name()):

            # Make the game with given seed
            game = Game(random_seed=seed, **game_config)
            game.add_player(player)
            stats = game.start()

            # Store the number of turns needed
            results[player.get_name()].append(stats["turns"])

    # Visualization of cumulative curves of numbers of turns taken per program
    max_turn = max([max(results[player]) for player in results])
    pyplot.figure(figsize=(10, 5))
    for player in results:
        turns = [0] + sorted(results[player]) + [max_turn]
        games_completed_per_turn = [len([turn for turn in results[player] if turn <= t]) * 100.0 / nb_games for t in turns]
        pyplot.plot(turns, games_completed_per_turn, label=player)
    pyplot.title("Comparison of turns needed to complete all %d games" % (nb_games))
    pyplot.xlabel("Turns per game")
    pyplot.ylabel("% of games completed")
    pyplot.xscale("log")
    pyplot.legend()
    pyplot.savefig("evaluate_random_players.png")

    # Formal statistics to check if these curves are statistically significant
    for i, player_1 in enumerate(results):
        for j, player_2 in enumerate(results):
            if j > i:
                test_result = scstats.mannwhitneyu(results[player_1], results[player_2], alternative="two-sided")
                print("Mann-Whitney U test between turns of program '%s' and of program '%s':" % (player_1, player_2), test_result)

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# PyRat imports
from pyrat import Player, Maze, GameState, Action

##########################################################################################
######################################### CLASSES ########################################
##########################################################################################

class Random6 (Player):

    """
    *(This class inherits from* ``Player`` *).*

    This player is an improvement of the ``Random5`` player.
    A limitation of ``Random5`` is that it gives equal importance to all unvisited neighbors.
    However, some may reduce the distance to the cheese, while others may increase it.
    """

    ##################################################################################
    #                                   CONSTRUCTOR                                  #
    ##################################################################################

    def __init__ ( self,
                   *args:    object,
                   **kwargs: object
                 ) ->        None:

        """
        Initializes a new instance of the class.

        Args:
            args:   Arguments to pass to the parent constructor.
            kwargs: Keyword arguments to pass to the parent constructor.
        """

        # Inherit from parent class
        super().__init__(*args, **kwargs)

        # We create an attribute to keep track of visited cells
        # We will initialize it in the ``preprocessing()`` method to allow the game to be reset
        # Otherwise, the set would keep the cells visited in previous games
        self.visited_cells = None

        # We also create an attribute for the reduced maze
        self.reduced_maze = None

        # We create an attribute for the player's trajectory
        self.trajectory = None

    ##################################################################################
    #                                  PYRAT METHODS                                 #
    ##################################################################################

    def preprocessing ( self,
                        maze:       Maze,
                        game_state: GameState,
                      ) ->          None:
        
        """
        *(This method redefines the method of the parent class with the same name).*

        This method is called once at the beginning of the game.
        Here, we use it to create a reduced maze that contains only the cells that are not dead-ends.
        We define a dead-end as a cell that has only one neighbor and does not contain cheese or the player.
        Note that this is not the best way to define a dead-end, but it is a simple one.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        """

        # Initialize visited cells
        self.visited_cells = set()

        # Reduce the maze
        my_location = game_state.player_locations[self.get_name()]
        self.reduced_maze = self.remove_dead_ends(maze, [my_location] + game_state.cheese)

        # Initialize the trajectory
        self.trajectory = [my_location]

    ##################################################################################

    def turn ( self,
               maze:       Maze,
               game_state: GameState,
             ) ->          Action:

        """
        *(This method redefines the method of the parent class with the same name).*

        It is called at each turn of the game.
        It returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        We also update the set of visited cells at each turn.
        Now, we work with the reduced maze to find the next action.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        
        Returns:
            One of the possible actions.
        """

        # Mark current cell as visited
        my_location = game_state.player_locations[self.get_name()]
        if my_location not in self.visited_cells:
            self.visited_cells.add(my_location)

        # Add current location to trajectory
        self.trajectory.append(my_location)

        # Return an action
        action = self.find_next_action(self.reduced_maze, game_state)
        return action
    
    ##################################################################################
    #                                  OTHER METHODS                                 #
    ##################################################################################

    def find_next_action ( self,
                           maze:       Maze,
                           game_state: GameState,
                         ) ->          Action:

        """
        This method returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        Here, the action is chosen by prioritizing unvisited neighbors that reduce the distance to the closest cheese.
        If no such action exists, we come back to the last cell in the trajectory and pop it.
        
        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.

        Returns:
            One of the possible actions that leads to a valid neighbor.
        """

        # Go to an unvisited neighbor in priority
        # We sort the unvisited neighbors by their Euclidean distance to the closest cheese
        my_location = game_state.player_locations[self.get_name()]
        neighbors = maze.get_neighbors(my_location)
        unvisited_neighbors = [neighbor for neighbor in neighbors if neighbor not in self.visited_cells]
        if len(unvisited_neighbors) > 0:

            # Find the closest cheese in case there are multiple
            my_x, my_y = maze.i_to_rc(my_location)
            distances_player_cheese = {}
            for cheese in game_state.cheese:
                cheese_x, cheese_y = maze.i_to_rc(cheese)
                distances_player_cheese[cheese] = ((my_x - cheese_x) ** 2 + (my_y - cheese_y) ** 2) ** 0.5
            closest_cheese = min(distances_player_cheese, key=distances_player_cheese.get)
            closest_cheese_x, closest_cheese_y = maze.i_to_rc(closest_cheese)

            # Compute distances to the closest cheese for each unvisited neighbor
            distances_neighbor_cheese = {}
            for neighbor in unvisited_neighbors:
                neighbor_x, neighbor_y = maze.i_to_rc(neighbor)
                distances_neighbor_cheese[neighbor] = ((neighbor_x - closest_cheese_x) ** 2 + (neighbor_y - closest_cheese_y) ** 2) ** 0.5

            # Choose the neighbor that reduces the distance to the closest cheese the most
            neighbor = min(distances_neighbor_cheese, key=distances_neighbor_cheese.get)

        # If there is no unvisited neighbor, go back in the trajectory
        # We pop the last cell in the trajectory, which is the current cell
        # Then, we pop again to get the previous cell, which is where we want to go back
        else:
            self.trajectory.pop()
            neighbor = self.trajectory.pop()
        
        # Retrieve the corresponding action
        action = maze.locations_to_action(my_location, neighbor)
        return action
    
    ##################################################################################

    def remove_dead_ends ( self,
                           maze:              Maze,
                           locations_to_keep: list[tuple[int, int]]
                         ) ->                 Maze:
        
        """
        This method returns a new maze that contains only the cells that are not dead-ends.
        A dead-end is defined as a cell that has only one neighbor and does not contain cheese or the player.

        Args:
            maze:              An object representing the maze in which the player plays.
            locations_to_keep: A list of locations to keep in the reduced maze.

        Returns:
            A new maze with only the cells that are not dead-ends.
        """

        # Initialize the reduced maze as the original one
        # We do not need to make a copy of the maze, as the game sends a copy of the maze at each turn.
        updated_maze = maze
        
        # Iteratively remove dead-ends from the maze
        # We still keep dead ends that contain locations to keep
        removed_something = True
        while removed_something:
            removed_something = False
            for vertex in updated_maze.get_vertices():
                if len(updated_maze.get_neighbors(vertex)) == 1 and vertex not in locations_to_keep:
                    updated_maze.remove_vertex(vertex)
                    removed_something = True

        # Return the updated maze
        return updated_maze

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import pprint

# PyRat imports
from pyrat import Game
from players.Random6 import Random6

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Instantiate a game with a few arguments
    game_config = {"mud_percentage": 0.0,
                   "maze_width": 13,
                   "maze_height": 10,
                   "nb_cheese": 1,
                   "random_seed": 42,
                   "trace_length": 1000}

    # Instantiate a game with specified arguments
    game = Game(**game_config)

    # Instantiate the player
    player = Random6()
    game.add_player(player)

    # Start the game
    stats = game.start()
    pprint.pprint(stats)

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import tqdm.auto as tqdm
import matplotlib.pyplot as pyplot
import scipy.stats as scstats

# PyRat imports
from pyrat import Game, GameMode
from players.Random5 import Random5
from players.Random6 import Random6

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Determines how many games will be played for each player
    nb_games = 1000

    # Define the wall percentages to test
    wall_percentages = [0.0, 10.0, 20.0, 30.0, 40.0, 50.0, 60.0, 70.0, 80.0, 90.0, 100.0]

    # Customize the game elements
    game_config = {"mud_percentage": 0.0,
                   "nb_cheese": 1,
                   "game_mode": GameMode.SIMULATION}

    # Run the games for each player class
    players = [Random5(), Random6()]
    results = {walls: {player.get_name(): [] for player in players} for walls in wall_percentages}
    for walls in wall_percentages:
        print(f"Wall percentage: {walls}%")
        for player in players:
            for seed in tqdm.tqdm(range(nb_games), desc=player.get_name()):

                # Make the game with given seed
                game = Game(random_seed=seed, wall_percentage=walls, **game_config)
                game.add_player(player)
                stats = game.start()

                # Store the number of turns needed
                results[walls][player.get_name()].append(stats["turns"])

    # Visualization of cumulative curves of numbers of turns taken per program
    max_turn = max([max(results[walls][player]) for walls in results for player in results[walls]])
    pyplot.figure(figsize=(10, 5))
    for (i_player, player) in enumerate(results[walls]):
        for (i_walls, walls) in enumerate(results):
            turns = [0] + sorted(results[walls][player]) + [max_turn]
            games_completed_per_turn = [len([turn for turn in results[walls][player] if turn <= t]) * 100.0 / nb_games for t in turns]
            pyplot.plot(turns,
                        games_completed_per_turn,
                        label="%s (walls=%.1f%%)" % (player, walls),
                        linestyle="-" if i_player == 0 else "--",
                        color=pyplot.cm.viridis(i_walls / (len(results) - 1)))
    pyplot.title("Comparison of turns needed to complete all %d games" % (nb_games))
    pyplot.xlabel("Turns per game")
    pyplot.ylabel("% of games completed")
    pyplot.xscale("log")
    pyplot.legend(bbox_to_anchor=(1.05, 1), loc="upper left", ncol=2)
    pyplot.tight_layout()
    pyplot.savefig("walls_impact_on_random5_random6.png")

    # Plot statistical significance as a function of wall percentage
    p_values = []
    for walls in results:
        stat, p_value = scstats.mannwhitneyu(results[walls]["Random5"], results[walls]["Random6"], alternative="greater")
        p_values.append(p_value)
    pyplot.figure(figsize=(10, 5))
    pyplot.plot(wall_percentages, p_values, marker='o')
    pyplot.axhline(y=0.05, color='r', linestyle='--', label='Significance threshold (0.05)')
    pyplot.title("Statistical significance of Random6 vs Random5")
    pyplot.xlabel("Wall percentage")
    pyplot.ylabel("p-value (Mann-Whitney U test)")
    pyplot.yscale("log")
    pyplot.legend()
    pyplot.savefig("walls_impact_on_random5_random6_p_values.png")

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# PyRat imports
from pyrat import Player, Maze, GameState, Action

##########################################################################################
######################################### CLASSES ########################################
##########################################################################################

class Random7 (Player):

    """
    *(This class inherits from* ``Player`` *).*

    This player is an improvement of the ``Random6`` player.
    A limitation of ``Random6`` is that it can enter mud by goint north then west, while going west then north would avoid the mud.
    We improve this by checking weights leading to cells that reduce the distance to the closest cheese.
    """

    ##################################################################################
    #                                   CONSTRUCTOR                                  #
    ##################################################################################

    def __init__ ( self,
                   *args:    object,
                   **kwargs: object
                 ) ->        None:

        """
        Initializes a new instance of the class.

        Args:
            args:   Arguments to pass to the parent constructor.
            kwargs: Keyword arguments to pass to the parent constructor.
        """

        # Inherit from parent class
        super().__init__(*args, **kwargs)

        # We create an attribute to keep track of visited cells
        # We will initialize it in the ``preprocessing()`` method to allow the game to be reset
        # Otherwise, the set would keep the cells visited in previous games
        self.visited_cells = None

        # We also create an attribute for the reduced maze
        self.reduced_maze = None

        # We create an attribute for the player's trajectory
        self.trajectory = None

    ##################################################################################
    #                                  PYRAT METHODS                                 #
    ##################################################################################

    def preprocessing ( self,
                        maze:       Maze,
                        game_state: GameState,
                      ) ->          None:
        
        """
        *(This method redefines the method of the parent class with the same name).*

        This method is called once at the beginning of the game.
        Here, we use it to create a reduced maze that contains only the cells that are not dead-ends.
        We define a dead-end as a cell that has only one neighbor and does not contain cheese or the player.
        Note that this is not the best way to define a dead-end, but it is a simple one.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        """

        # Initialize visited cells
        self.visited_cells = set()

        # Reduce the maze
        my_location = game_state.player_locations[self.get_name()]
        self.reduced_maze = self.remove_dead_ends(maze, [my_location] + game_state.cheese)

        # Initialize the trajectory
        self.trajectory = [my_location]

    ##################################################################################

    def turn ( self,
               maze:       Maze,
               game_state: GameState,
             ) ->          Action:

        """
        *(This method redefines the method of the parent class with the same name).*

        It is called at each turn of the game.
        It returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        We also update the set of visited cells at each turn.
        Now, we work with the reduced maze to find the next action.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        
        Returns:
            One of the possible actions.
        """

        # Mark current cell as visited
        my_location = game_state.player_locations[self.get_name()]
        if my_location not in self.visited_cells:
            self.visited_cells.add(my_location)

        # Add current location to trajectory
        self.trajectory.append(my_location)

        # Return an action
        action = self.find_next_action(self.reduced_maze, game_state)
        return action
    
    ##################################################################################
    #                                  OTHER METHODS                                 #
    ##################################################################################

    def find_next_action ( self,
                           maze:       Maze,
                           game_state: GameState,
                         ) ->          Action:

        """
        This method returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        Here, the action is chosen by prioritizing unvisited neighbors that reduce the distance to the closest cheese.
        If no such action exists, we come back to the last cell in the trajectory and pop it.
        
        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.

        Returns:
            One of the possible actions that leads to a valid neighbor.
        """

        # Go to an unvisited neighbor in priority
        # We sort the unvisited neighbors by their Euclidean distance to the closest cheese
        my_location = game_state.player_locations[self.get_name()]
        neighbors = maze.get_neighbors(my_location)
        unvisited_neighbors = [neighbor for neighbor in neighbors if neighbor not in self.visited_cells]
        if len(unvisited_neighbors) > 0:

            # Find the closest cheese in case there are multiple
            my_x, my_y = maze.i_to_rc(my_location)
            distances_player_cheese = {}
            for cheese in game_state.cheese:
                cheese_x, cheese_y = maze.i_to_rc(cheese)
                distances_player_cheese[cheese] = ((my_x - cheese_x) ** 2 + (my_y - cheese_y) ** 2) ** 0.5
            closest_cheese = min(distances_player_cheese, key=distances_player_cheese.get)
            closest_cheese_x, closest_cheese_y = maze.i_to_rc(closest_cheese)

            # Compute distances to the closest cheese for each unvisited neighbor
            distances_neighbor_cheese = {}
            for neighbor in unvisited_neighbors:
                neighbor_x, neighbor_y = maze.i_to_rc(neighbor)
                distances_neighbor_cheese[neighbor] = ((neighbor_x - closest_cheese_x) ** 2 + (neighbor_y - closest_cheese_y) ** 2) ** 0.5
            
            # Among neighbors that reduce the distance to the closest cheese, choose the closest one from current location
            # If no neighbor reduces the distance to the closest cheese, we do as Random6
            valid_neighbors = {neighbor: maze.get_weight(my_location, neighbor) for neighbor in unvisited_neighbors if distances_neighbor_cheese[neighbor] < distances_player_cheese[closest_cheese]}
            if len(valid_neighbors) > 0:
                neighbor = min(valid_neighbors, key=valid_neighbors.get)
            else:
                neighbor = min(distances_neighbor_cheese, key=distances_neighbor_cheese.get)

        # If there is no unvisited neighbor, go back in the trajectory
        # We pop the last cell in the trajectory, which is the current cell
        # Then, we pop again to get the previous cell, which is where we want to go back
        else:
            self.trajectory.pop()
            neighbor = self.trajectory.pop()
        
        # Retrieve the corresponding action
        action = maze.locations_to_action(my_location, neighbor)
        return action
    
    ##################################################################################

    def remove_dead_ends ( self,
                           maze:              Maze,
                           locations_to_keep: list[tuple[int, int]]
                         ) ->                 Maze:
        
        """
        This method returns a new maze that contains only the cells that are not dead-ends.
        A dead-end is defined as a cell that has only one neighbor and does not contain cheese or the player.

        Args:
            maze:              An object representing the maze in which the player plays.
            locations_to_keep: A list of locations to keep in the reduced maze.

        Returns:
            A new maze with only the cells that are not dead-ends.
        """

        # Initialize the reduced maze as the original one
        # We do not need to make a copy of the maze, as the game sends a copy of the maze at each turn.
        updated_maze = maze
        
        # Iteratively remove dead-ends from the maze
        # We still keep dead ends that contain locations to keep
        removed_something = True
        while removed_something:
            removed_something = False
            for vertex in updated_maze.get_vertices():
                if len(updated_maze.get_neighbors(vertex)) == 1 and vertex not in locations_to_keep:
                    updated_maze.remove_vertex(vertex)
                    removed_something = True

        # Return the updated maze
        return updated_maze

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import pprint

# PyRat imports
from pyrat import Game
from players.Random7 import Random7

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Instantiate a game with a few arguments
    game_config = {"mud_percentage": 0.0,
                   "maze_width": 13,
                   "maze_height": 10,
                   "nb_cheese": 1,
                   "random_seed": 42,
                   "trace_length": 1000}

    # Instantiate a game with specified arguments
    game = Game(**game_config)

    # Instantiate the player
    player = Random7()
    game.add_player(player)

    # Start the game
    stats = game.start()
    pprint.pprint(stats)

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# External imports
import pprint

# PyRat imports
from pyrat import Game, StartingLocation
from players.WallFollower import WallFollower

##########################################################################################
######################################### SCRIPT #########################################
##########################################################################################

if __name__ == "__main__":

    # Instantiate a game with a few arguments
    game_config = {"mud_percentage": 0.0,
                   "wall_percentage": 70.0,
                   "cell_percentage": 100.0,
                   "fixed_cheese": [0],
                   "maze_width": 13,
                   "maze_height": 10,
                   "random_seed": 42,
                   "trace_length": 1000}

    # Instantiate a game with specified arguments
    game = Game(**game_config)

    # Instantiate the player
    player = WallFollower()
    game.add_player(player, location=StartingLocation.BOTTOM_RIGHT)

    # Start the game
    stats = game.start()
    pprint.pprint(stats)

##########################################################################################
##########################################################################################

##########################################################################################
########################################## INFO ##########################################
##########################################################################################

"""
This program is a solution to the practical session 1 of the PyRat project:
https://hub.imt-atlantique.fr/ueinfo-fise1a/s5/project/session1/practical/
"""

##########################################################################################
######################################### IMPORTS ########################################
##########################################################################################

# PyRat imports
from pyrat import Player, Maze, GameState, Action

##########################################################################################
######################################### CLASSES ########################################
##########################################################################################

class WallFollower (Player):

    """
    *(This class inherits from* ``Player`` *).*

    This player follows a wall by always keeping its right hand on the wall.
    """

    ##################################################################################
    #                                   CONSTRUCTOR                                  #
    ##################################################################################

    def __init__ ( self,
                   *args:    object,
                   **kwargs: object
                 ) ->        None:

        """
        Initializes a new instance of the class.

        Args:
            args:   Arguments to pass to the parent constructor.
            kwargs: Keyword arguments to pass to the parent constructor.
        """

        # Inherit from parent class
        super().__init__(*args, **kwargs)

        # We remember the previous action performed
        self.previous_action = Action.NOTHING

    ##################################################################################
    #                                  PYRAT METHODS                                 #
    ##################################################################################

    def preprocessing ( self,
                        maze:       Maze,
                        game_state: GameState,
                      ) ->          None:
        
        """
        *(This method redefines the method of the parent class with the same name).*

        This method is called once at the beginning of the game.
        Here, we initialize the previous action to one that leads to a wall.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        """

        # Initialize last action to one that leads to a wall
        my_location = game_state.player_locations[self.get_name()]
        for action in [Action.EAST, Action.NORTH, Action.WEST, Action.SOUTH]:
            if self.action_hits_wall(maze, my_location, action):
                self.previous_action = action
                break

    ##################################################################################

    def turn ( self,
               maze:       Maze,
               game_state: GameState,
             ) ->          Action:

        """
        *(This method redefines the method of the parent class with the same name).*

        It is called at each turn of the game.
        It returns an action to perform among the possible actions, defined in the ``Action`` enumeration.
        We return an action that allows to keep the wall on the right.

        Args:
            maze:       An object representing the maze in which the player plays.
            game_state: An object representing the state of the game.
        
        Returns:
            One of the possible actions.
        """

        # Actions order depends on the last action performed
        actions_order = []
        if self.previous_action == Action.NORTH:
            actions_order = [Action.EAST, Action.NORTH, Action.WEST, Action.SOUTH]
        elif self.previous_action == Action.EAST:
            actions_order = [Action.SOUTH, Action.EAST, Action.NORTH, Action.WEST]
        elif self.previous_action == Action.SOUTH:
            actions_order = [Action.WEST, Action.SOUTH, Action.EAST, Action.NORTH]
        elif self.previous_action == Action.WEST:
            actions_order = [Action.NORTH, Action.WEST, Action.SOUTH, Action.EAST]

        # Test actions in an order that allows to keep the wall on the right
        my_location = game_state.player_locations[self.get_name()]
        for action in actions_order:
            if not self.action_hits_wall(maze, my_location, action):
                self.previous_action = action
                return action
            
        # If all actions hit a wall, we don't move
        return Action.NOTHING
    
    ##################################################################################
    #                                  OTHER METHODS                                 #
    ##################################################################################

    def action_hits_wall ( self,
                           maze:             Maze,
                           current_location: int,
                           action:           Action,
                         ) ->                bool:

        """
        This method indicates whether the given action from the current location hits a wall.
        
        Args:
            maze:             An object representing the maze in which the player plays.
            current_location: The current location of the player.
            action:           The action to perform.

        Returns:
            True if the action hits a wall, False otherwise.
        """

        # Check where the action would lead
        current_location_row, current_location_col = maze.i_to_rc(current_location)
        target_location_row, target_location_col = current_location_row, current_location_col
        if action == Action.NORTH:
            target_location_row -= 1
        elif action == Action.SOUTH:
            target_location_row += 1
        elif action == Action.WEST:
            target_location_col -= 1
        elif action == Action.EAST:
            target_location_col += 1

        # If the target exists, check if we can go there
        if maze.rc_exists(target_location_row, target_location_col):
            target_location = maze.rc_to_i(target_location_row, target_location_col)
            return not maze.has_edge(current_location, target_location)

        # Target does not exist, so we hit a wall
        return True

##########################################################################################
##########################################################################################