pacai.student.singlesearch

  1"""
  2In this file, you will implement code relating to simple single-agent searches.
  3"""
  4
  5import random
  6import typing
  7
  8import pacai.agents.searchproblem
  9import pacai.core.agent
 10import pacai.core.agentaction
 11import pacai.core.board
 12import pacai.core.gamestate
 13import pacai.core.search
 14import pacai.pacman.board
 15import pacai.search.common
 16import pacai.search.food
 17import pacai.search.position
 18
 19def depth_first_search(
 20        problem: pacai.core.search.SearchProblem,
 21        heuristic: pacai.core.search.SearchHeuristic,
 22        rng: random.Random,
 23        **kwargs: typing.Any) -> pacai.core.search.SearchSolution:
 24    """
 25    A pacai.core.search.SearchProblemSolver that implements depth first search (DFS).
 26    This means that it will search the deepest nodes in the search tree first.
 27    See: https://en.wikipedia.org/wiki/Depth-first_search .
 28    """
 29
 30    # *** Your Code Here ***
 31    raise NotImplementedError('depth_first_search')
 32
 33def breadth_first_search(
 34        problem: pacai.core.search.SearchProblem,
 35        heuristic: pacai.core.search.SearchHeuristic,
 36        rng: random.Random,
 37        **kwargs: typing.Any) -> pacai.core.search.SearchSolution:
 38    """
 39    A pacai.core.search.SearchProblemSolver that implements breadth first search (BFS).
 40    This means that it will search nodes based on what level in search tree they appear.
 41    See: https://en.wikipedia.org/wiki/Breadth-first_search .
 42    """
 43
 44    # *** Your Code Here ***
 45    raise NotImplementedError('breadth_first_search')
 46
 47def uniform_cost_search(
 48        problem: pacai.core.search.SearchProblem,
 49        heuristic: pacai.core.search.SearchHeuristic,
 50        rng: random.Random,
 51        **kwargs: typing.Any) -> pacai.core.search.SearchSolution:
 52    """
 53    A pacai.core.search.SearchProblemSolver that implements uniform cost search (UCS).
 54    This means that it will search nodes with a lower total cost first.
 55    See: https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm#Practical_optimizations_and_infinite_graphs .
 56    """
 57
 58    # *** Your Code Here ***
 59    raise NotImplementedError('uniform_cost_search')
 60
 61def astar_search(
 62        problem: pacai.core.search.SearchProblem,
 63        heuristic: pacai.core.search.SearchHeuristic,
 64        rng: random.Random,
 65        **kwargs: typing.Any) -> pacai.core.search.SearchSolution:
 66    """
 67    A pacai.core.search.SearchProblemSolver that implements A* search (pronounced "A Star search").
 68    This means that it will search nodes with a lower combined cost and heuristic first.
 69    See: https://en.wikipedia.org/wiki/A*_search_algorithm .
 70    """
 71
 72    # *** Your Code Here ***
 73    raise NotImplementedError('astar_search')
 74
 75class CornersSearchNode(pacai.core.search.SearchNode):
 76    """
 77    A search node the can be used to represent the corners search problem.
 78
 79    You get to implement this search node however you want.
 80    """
 81
 82    def __init__(self) -> None:
 83        """ Construct a search node to help search for corners. """
 84
 85        # *** Your Code Here ***
 86        # Remember that you can also add argument to your constructor.
 87
 88class CornersSearchProblem(pacai.core.search.SearchProblem[CornersSearchNode]):
 89    """
 90    A search problem for touching the four different corners in a board.
 91
 92    You may assume that very board is surrounded by walls (e.g., (0, 0) is a wall),
 93    and that the position diagonally inside from the walled corner is the location we are looking for.
 94    For example, if we had a square board that was 10x10, then we would be looking for the following corners:
 95     - (1, 1) -- North-West / Upper Left
 96     - (1, 8) -- North-East / Upper Right
 97     - (8, 1) -- South-West / Lower Left
 98     - (8, 8) -- South-East / Lower Right
 99    """
100
101    def __init__(self,
102            game_state: pacai.core.gamestate.GameState,
103            **kwargs: typing.Any) -> None:
104        super().__init__(**kwargs)
105
106        # *** Your Code Here ***
107
108    def get_starting_node(self) -> CornersSearchNode:
109        # *** Your Code Here ***
110        raise NotImplementedError('CornersSearchProblem.get_starting_node')
111
112    def is_goal_node(self, node: CornersSearchNode) -> bool:
113        # *** Your Code Here ***
114        raise NotImplementedError('CornersSearchProblem.is_goal_node')
115
116    def get_successor_nodes(self, node: CornersSearchNode) -> list[pacai.core.search.SuccessorInfo]:
117        # *** Your Code Here ***
118        raise NotImplementedError('CornersSearchProblem.get_successor_nodes')
119
120def corners_heuristic(node: CornersSearchNode, problem: CornersSearchProblem, **kwargs: typing.Any) -> float:
121    """
122    A heuristic for CornersSearchProblem.
123
124    This function should always return a number that is a lower bound
125    on the shortest path from the state to a goal of the problem;
126    i.e. it should be admissible.
127    (You need not worry about consistency for this heuristic to receive full credit.)
128    """
129
130    # *** Your Code Here ***
131    return pacai.search.common.null_heuristic(node, problem)  # Default to a trivial solution.
132
133def food_heuristic(node: pacai.search.food.FoodSearchNode, problem: pacai.search.food.FoodSearchProblem, **kwargs: typing.Any) -> float:
134    """
135    A heuristic for the FoodSearchProblem.
136    """
137
138    # *** Your Code Here ***
139    return pacai.search.common.null_heuristic(node, problem)  # Default to a trivial solution.
140
141class ClosestDotSearchAgent(pacai.agents.searchproblem.GreedySubproblemSearchAgent):
142    """
143    Search for a path to all the food by greedily searching for the next closest food again and again
144    (util we have reached all the food).
145
146    This agent is left to you to fill out.
147    But make sure to take your time and think.
148    The final solution is quite simple if you take your time to understand everything up until this point and leverage
149    pacai.agents.searchproblem.GreedySubproblemSearchAgent and pacai.student.problem.AnyMarkerSearchProblem.
150    pacai.agents.searchproblem.GreedySubproblemSearchAgent is already implemented,
151    but you should take some time to understand it.
152    pacai.student.problem.AnyMarkerSearchProblem (below in this file) has not yet been implemented,
153    but is the quickest and easiest way to implement this class.
154
155    Hint:
156    Remember that you can call a parent class' `__init__()` method from a child class' `__init__()` method.
157    (See pacai.student.problem.AnyMarkerSearchProblem for an example.)
158    Child classes will generally always call their parent's `__init__()` method
159    (if a child class does not implement `__init__()`, then the parent's `__init__()` is automatically called).
160    This call does not need to be the first line in the method,
161    and you can pass whatever you want to the parent's `__init__()`.
162    """
163
164    # *** Your Code Here ***
165
166class AnyMarkerSearchProblem(pacai.search.position.PositionSearchProblem):
167    """
168    A search problem for finding a path to any instance of the specified board marker (e.g., food, wall, power capsule).
169
170    This search problem is just like the pacai.search.position.PositionSearchProblem,
171    but has a different goal test, which you need to fill in below.
172    You may modify the `__init__()` if you want, the other methods should be fine as-is.
173    """
174
175    def __init__(self,
176            game_state: pacai.core.gamestate.GameState,
177            target_marker: pacai.core.board.Marker = pacai.pacman.board.MARKER_PELLET,
178            **kwargs: typing.Any) -> None:
179        super().__init__(game_state, **kwargs)
180
181        # *** Your Code Here ***
182
183    def is_goal_node(self, node: pacai.search.position.PositionSearchNode) -> bool:
184        # *** Your Code Here ***
185        raise NotImplementedError('CornersSearchProblem.is_goal_node')
186
187class ApproximateSearchAgent(pacai.core.agent.Agent):
188    """
189    A search agent that tries to perform an approximate search instead of an exact one.
190    In other words, this agent is okay with a solution that is "good enough" and not necessarily optimal.
191    """