pacai.search.food
1import typing 2 3import pacai.core.board 4import pacai.core.gamestate 5import pacai.core.search 6 7class FoodSearchNode(pacai.core.search.SearchNode): 8 """ 9 A search node for the food search problem. 10 The state for this search problem will be 11 the current position and the remaining food positions. 12 """ 13 14 def __init__(self, 15 position: pacai.core.board.Position, 16 remaining_food: typing.Iterable[pacai.core.board.Position]) -> None: 17 self.position: pacai.core.board.Position = position 18 """ The current position being searched. """ 19 20 self.remaining_food: tuple[pacai.core.board.Position, ...] = tuple(sorted(list(remaining_food))) 21 """ 22 The food left to eat. 23 This is kept sorted to ensure that underlying comparison checks run cleanly. 24 """ 25 26 def __lt__(self, other: object) -> bool: 27 if (not isinstance(other, FoodSearchNode)): 28 return False 29 30 return ((self.position, self.remaining_food) < (other.position, other.remaining_food)) 31 32 def __eq__(self, other: object) -> bool: 33 if (not isinstance(other, FoodSearchNode)): 34 return False 35 36 return ((self.position == other.position) and (self.remaining_food == other.remaining_food)) 37 38 def __hash__(self) -> int: 39 return hash((self.position, self.remaining_food)) 40 41class FoodSearchProblem(pacai.core.search.SearchProblem[FoodSearchNode]): 42 """ 43 A search problem associated with finding the a path that collects all of the "food" in a game. 44 """ 45 46 def __init__(self, 47 game_state: pacai.core.gamestate.GameState, 48 start_position: pacai.core.board.Position | None = None, 49 **kwargs: typing.Any) -> None: 50 """ 51 Create a food search problem. 52 53 If no start position is provided, the current agent's position will be used. 54 """ 55 56 super().__init__() 57 58 self.state: pacai.core.gamestate.GameState = game_state 59 """ Keep track of the enire game state. """ 60 61 if (start_position is None): 62 start_position = game_state.get_agent_position() 63 64 if (start_position is None): 65 raise ValueError("Could not find starting position.") 66 67 self.start_position = start_position 68 """ The position to start from. """ 69 70 def get_starting_node(self) -> FoodSearchNode: 71 return FoodSearchNode(self.start_position, self.state.board.get_marker_positions(pacai.pacman.board.MARKER_PELLET)) 72 73 def is_goal_node(self, node: FoodSearchNode) -> bool: 74 return (len(node.remaining_food) == 0) 75 76 def complete(self, goal_node: FoodSearchNode) -> None: 77 # Mark the final node in the history. 78 self.position_history.append(goal_node.position) 79 80 def get_successor_nodes(self, node: FoodSearchNode) -> list[pacai.core.search.SuccessorInfo]: 81 successors = [] 82 83 # Check all the non-wall neighbors. 84 for (action, position) in self.state.board.get_neighbors(node.position): 85 new_remaining_food = list(node.remaining_food).copy() 86 if (position in new_remaining_food): 87 new_remaining_food.remove(position) 88 89 next_node = FoodSearchNode(position, new_remaining_food) 90 successors.append(pacai.core.search.SuccessorInfo(next_node, action, 1.0)) 91 92 # Do bookkeeping on the states/positions we visited. 93 self.expanded_node_count += 1 94 if (node not in self.visited_nodes): 95 self.position_history.append(node.position) 96 97 return successors
8class FoodSearchNode(pacai.core.search.SearchNode): 9 """ 10 A search node for the food search problem. 11 The state for this search problem will be 12 the current position and the remaining food positions. 13 """ 14 15 def __init__(self, 16 position: pacai.core.board.Position, 17 remaining_food: typing.Iterable[pacai.core.board.Position]) -> None: 18 self.position: pacai.core.board.Position = position 19 """ The current position being searched. """ 20 21 self.remaining_food: tuple[pacai.core.board.Position, ...] = tuple(sorted(list(remaining_food))) 22 """ 23 The food left to eat. 24 This is kept sorted to ensure that underlying comparison checks run cleanly. 25 """ 26 27 def __lt__(self, other: object) -> bool: 28 if (not isinstance(other, FoodSearchNode)): 29 return False 30 31 return ((self.position, self.remaining_food) < (other.position, other.remaining_food)) 32 33 def __eq__(self, other: object) -> bool: 34 if (not isinstance(other, FoodSearchNode)): 35 return False 36 37 return ((self.position == other.position) and (self.remaining_food == other.remaining_food)) 38 39 def __hash__(self) -> int: 40 return hash((self.position, self.remaining_food))
A search node for the food search problem. The state for this search problem will be the current position and the remaining food positions.
FoodSearchNode( position: pacai.core.board.Position, remaining_food: Iterable[pacai.core.board.Position])
15 def __init__(self, 16 position: pacai.core.board.Position, 17 remaining_food: typing.Iterable[pacai.core.board.Position]) -> None: 18 self.position: pacai.core.board.Position = position 19 """ The current position being searched. """ 20 21 self.remaining_food: tuple[pacai.core.board.Position, ...] = tuple(sorted(list(remaining_food))) 22 """ 23 The food left to eat. 24 This is kept sorted to ensure that underlying comparison checks run cleanly. 25 """
remaining_food: tuple[pacai.core.board.Position, ...]
The food left to eat. This is kept sorted to ensure that underlying comparison checks run cleanly.
42class FoodSearchProblem(pacai.core.search.SearchProblem[FoodSearchNode]): 43 """ 44 A search problem associated with finding the a path that collects all of the "food" in a game. 45 """ 46 47 def __init__(self, 48 game_state: pacai.core.gamestate.GameState, 49 start_position: pacai.core.board.Position | None = None, 50 **kwargs: typing.Any) -> None: 51 """ 52 Create a food search problem. 53 54 If no start position is provided, the current agent's position will be used. 55 """ 56 57 super().__init__() 58 59 self.state: pacai.core.gamestate.GameState = game_state 60 """ Keep track of the enire game state. """ 61 62 if (start_position is None): 63 start_position = game_state.get_agent_position() 64 65 if (start_position is None): 66 raise ValueError("Could not find starting position.") 67 68 self.start_position = start_position 69 """ The position to start from. """ 70 71 def get_starting_node(self) -> FoodSearchNode: 72 return FoodSearchNode(self.start_position, self.state.board.get_marker_positions(pacai.pacman.board.MARKER_PELLET)) 73 74 def is_goal_node(self, node: FoodSearchNode) -> bool: 75 return (len(node.remaining_food) == 0) 76 77 def complete(self, goal_node: FoodSearchNode) -> None: 78 # Mark the final node in the history. 79 self.position_history.append(goal_node.position) 80 81 def get_successor_nodes(self, node: FoodSearchNode) -> list[pacai.core.search.SuccessorInfo]: 82 successors = [] 83 84 # Check all the non-wall neighbors. 85 for (action, position) in self.state.board.get_neighbors(node.position): 86 new_remaining_food = list(node.remaining_food).copy() 87 if (position in new_remaining_food): 88 new_remaining_food.remove(position) 89 90 next_node = FoodSearchNode(position, new_remaining_food) 91 successors.append(pacai.core.search.SuccessorInfo(next_node, action, 1.0)) 92 93 # Do bookkeeping on the states/positions we visited. 94 self.expanded_node_count += 1 95 if (node not in self.visited_nodes): 96 self.position_history.append(node.position) 97 98 return successors
A search problem associated with finding the a path that collects all of the "food" in a game.
FoodSearchProblem( game_state: pacai.core.gamestate.GameState, start_position: pacai.core.board.Position | None = None, **kwargs: Any)
47 def __init__(self, 48 game_state: pacai.core.gamestate.GameState, 49 start_position: pacai.core.board.Position | None = None, 50 **kwargs: typing.Any) -> None: 51 """ 52 Create a food search problem. 53 54 If no start position is provided, the current agent's position will be used. 55 """ 56 57 super().__init__() 58 59 self.state: pacai.core.gamestate.GameState = game_state 60 """ Keep track of the enire game state. """ 61 62 if (start_position is None): 63 start_position = game_state.get_agent_position() 64 65 if (start_position is None): 66 raise ValueError("Could not find starting position.") 67 68 self.start_position = start_position 69 """ The position to start from. """
Create a food search problem.
If no start position is provided, the current agent's position will be used.
71 def get_starting_node(self) -> FoodSearchNode: 72 return FoodSearchNode(self.start_position, self.state.board.get_marker_positions(pacai.pacman.board.MARKER_PELLET))
Get the starting node for the search problem.
77 def complete(self, goal_node: FoodSearchNode) -> None: 78 # Mark the final node in the history. 79 self.position_history.append(goal_node.position)
Notify this search problem that the solver choose this goal node.
81 def get_successor_nodes(self, node: FoodSearchNode) -> list[pacai.core.search.SuccessorInfo]: 82 successors = [] 83 84 # Check all the non-wall neighbors. 85 for (action, position) in self.state.board.get_neighbors(node.position): 86 new_remaining_food = list(node.remaining_food).copy() 87 if (position in new_remaining_food): 88 new_remaining_food.remove(position) 89 90 next_node = FoodSearchNode(position, new_remaining_food) 91 successors.append(pacai.core.search.SuccessorInfo(next_node, action, 1.0)) 92 93 # Do bookkeeping on the states/positions we visited. 94 self.expanded_node_count += 1 95 if (node not in self.visited_nodes): 96 self.position_history.append(node.position) 97 98 return successors
Get all the possible successors (successor nodes) to the current node. This action can be though of expanding a search node, or getting the children of a node in the search tree.