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
class FoodSearchNode(pacai.core.search.SearchNode):
 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        """

The current position being searched.

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.

Keep track of the enire game state.

start_position

The position to start from.

def get_starting_node(self) -> FoodSearchNode:
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.

def is_goal_node(self, node: FoodSearchNode) -> bool:
74    def is_goal_node(self, node: FoodSearchNode) -> bool:
75        return (len(node.remaining_food) == 0)

Check if this node is a valid goal node.

def complete(self, goal_node: FoodSearchNode) -> None:
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.

def get_successor_nodes( self, node: FoodSearchNode) -> list[pacai.core.search.SuccessorInfo]:
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.