pacai.core.search

This file provides the core infrastructure for search problems.

  1"""
  2This file provides the core infrastructure for search problems.
  3"""
  4
  5import abc
  6import random
  7import typing
  8
  9import pacai.core.action
 10import pacai.core.board
 11import pacai.util.comparable
 12
 13class SolutionNotFoundError(Exception):
 14    """ An error for when a search problem solver cannot find a solution. """
 15
 16class SearchNode(abc.ABC, pacai.util.comparable.SimpleComparable):
 17    """
 18    A node or "state" in a search problem/tree.
 19    A search node represents one possible state of the problem.
 20
 21    It is common to refer to search nodes as "search states" or "states".
 22    To avoid confusion with game states, this project will use "node" when referencing search problems.
 23    """
 24
 25NodeType = typing.TypeVar('NodeType', bound = SearchNode)  # pylint: disable=invalid-name
 26
 27class SuccessorInfo(typing.Generic[NodeType]):
 28    """
 29    A possible search node (and related information) that can be reached from another node in a search problem.
 30    """
 31
 32    def __init__(self,
 33            node: NodeType,
 34            action: pacai.core.action.Action,
 35            cost: float,
 36            **kwargs: typing.Any) -> None:
 37        self.node = node
 38        """ The search node of this successor. """
 39
 40        self.action = action
 41        """ The action that was taken at the old node to reach this successor. """
 42
 43        self.cost = cost
 44        """ The cost of taken the action that lead to this successor. """
 45
 46class SearchProblem(abc.ABC, typing.Generic[NodeType]):
 47    """
 48    This class outlines the structure of a search problem.
 49    Any search problem will need to provide answers to the following questions:
 50    1) Where should the search start?
 51    2) Is some specific search node a goal (are we done?)?
 52    3) What moves are possible from a given search node?
 53
 54    The answers to these questions are provided by implementing
 55    the methods of this class.
 56    """
 57
 58    def __init__(self, **kwargs: typing.Any) -> None:
 59        self.expanded_node_count: int = 0
 60        """
 61        The number of search nodes that have been expended.
 62        It is important that subclasses accurately keep this count up-to-date.
 63        """
 64
 65        self.visited_nodes: set[NodeType] = set()
 66        """
 67        Keep track of the board positions that have been visited.
 68        This can help agents quickly check where they have previously been.
 69        """
 70
 71        self.position_history: list[pacai.core.board.Position] = []
 72        """
 73        Keep track of the order that positions have been visited.
 74        This let's us know exactly how the agent has moved about.
 75        """
 76
 77    def complete(self, goal_node: NodeType) -> None:
 78        """ Notify this search problem that the solver choose this goal node. """
 79
 80    @abc.abstractmethod
 81    def get_starting_node(self) -> NodeType:
 82        """ Get the starting node for the search problem. """
 83
 84    @abc.abstractmethod
 85    def is_goal_node(self, node: NodeType) -> bool:
 86        """ Check if this node is a valid goal node. """
 87
 88    @abc.abstractmethod
 89    def get_successor_nodes(self, node: NodeType) -> list[SuccessorInfo[NodeType]]:
 90        """
 91        Get all the possible successors (successor nodes) to the current node.
 92        This action can be though of expanding a search node,
 93        or getting the children of a node in the search tree.
 94        """
 95
 96class SearchSolution(typing.Generic[NodeType]):
 97    """
 98    A potential solution to a search problem.
 99    This does not have to be an optimal (or even correct) solution,
100    but just what a solver returns.
101    """
102
103    def __init__(self,
104            actions: list[pacai.core.action.Action],
105            cost: float,
106            goal_node: NodeType | None = None,
107            ) -> None:
108        self.actions: list[pacai.core.action.Action] = actions
109        """
110        The actions to take for this solution.
111        These actions should guide the agent from its starting location (SearchProblem.get_starting_node())
112        to the goal (SearchProblem.is_goal_node()).
113        If the agent is just moving, you can think of this as it's "path".
114        """
115
116        self.cost: float = cost
117        """ The cost of this solution. """
118
119        self.goal_node: NodeType | None = goal_node
120        """
121        The node that the search was ended on.
122        May be None in cases where the solver does not use search nodes.
123        """
124
125    def get_path(self, start_position: pacai.core.board.Position) -> list[pacai.core.board.Position]:
126        """
127        Given the starting locatrion, get the path this search solution represents.
128        The resulting path will start at the starting position.
129        It is assumed that unknown actions will not result in a move.
130        """
131
132        path = [start_position]
133
134        for action in self.actions:
135            path.append(path[-1].apply_action(action))
136
137        return path
138
139@typing.runtime_checkable
140class CostFunction(typing.Protocol):
141    """
142    A function that computes the cost associated with a specific search node.
143    """
144
145    def __call__(self, node: SearchNode, **kwargs: typing.Any) -> float:
146        ...
147
148@typing.runtime_checkable
149class SearchHeuristic(typing.Protocol):
150    """
151    A heuristic function attempts to score a search node in the context of a problem.
152    """
153
154    def __call__(self, node: SearchNode, problem: SearchProblem, **kwargs: typing.Any) -> float:
155        ...
156
157@typing.runtime_checkable
158class SearchProblemSolver(typing.Protocol):
159    """
160    A function that solves a search problem and returns a solution.
161    Not all solvers will need to heuristic or RNG,
162    but they will always be provided (even if the heuristic is a null heuristic).
163    If no solution/path can be found, a SolutionNotFoundError exception should be raised.
164    """
165
166    def __call__(self,
167            problem: SearchProblem,
168            heuristic: SearchHeuristic,
169            rng: random.Random,
170            **kwargs: typing.Any) -> SearchSolution:
171        ...
class SolutionNotFoundError(builtins.Exception): 
14class SolutionNotFoundError(Exception):
15    """ An error for when a search problem solver cannot find a solution. """

An error for when a search problem solver cannot find a solution.

class SearchNode(abc.ABC, pacai.util.comparable.SimpleComparable): 
17class SearchNode(abc.ABC, pacai.util.comparable.SimpleComparable):
18    """
19    A node or "state" in a search problem/tree.
20    A search node represents one possible state of the problem.
21
22    It is common to refer to search nodes as "search states" or "states".
23    To avoid confusion with game states, this project will use "node" when referencing search problems.
24    """

A node or "state" in a search problem/tree. A search node represents one possible state of the problem.

It is common to refer to search nodes as "search states" or "states". To avoid confusion with game states, this project will use "node" when referencing search problems.

class SuccessorInfo(typing.Generic[~NodeType]): 
28class SuccessorInfo(typing.Generic[NodeType]):
29    """
30    A possible search node (and related information) that can be reached from another node in a search problem.
31    """
32
33    def __init__(self,
34            node: NodeType,
35            action: pacai.core.action.Action,
36            cost: float,
37            **kwargs: typing.Any) -> None:
38        self.node = node
39        """ The search node of this successor. """
40
41        self.action = action
42        """ The action that was taken at the old node to reach this successor. """
43
44        self.cost = cost
45        """ The cost of taken the action that lead to this successor. """

A possible search node (and related information) that can be reached from another node in a search problem.

SuccessorInfo( node: ~NodeType, action: pacai.core.action.Action, cost: float, **kwargs: Any) 
33    def __init__(self,
34            node: NodeType,
35            action: pacai.core.action.Action,
36            cost: float,
37            **kwargs: typing.Any) -> None:
38        self.node = node
39        """ The search node of this successor. """
40
41        self.action = action
42        """ The action that was taken at the old node to reach this successor. """
43
44        self.cost = cost
45        """ The cost of taken the action that lead to this successor. """
node

The search node of this successor.

action

The action that was taken at the old node to reach this successor.

cost

The cost of taken the action that lead to this successor.

class SearchProblem(abc.ABC, typing.Generic[~NodeType]): 
47class SearchProblem(abc.ABC, typing.Generic[NodeType]):
48    """
49    This class outlines the structure of a search problem.
50    Any search problem will need to provide answers to the following questions:
51    1) Where should the search start?
52    2) Is some specific search node a goal (are we done?)?
53    3) What moves are possible from a given search node?
54
55    The answers to these questions are provided by implementing
56    the methods of this class.
57    """
58
59    def __init__(self, **kwargs: typing.Any) -> None:
60        self.expanded_node_count: int = 0
61        """
62        The number of search nodes that have been expended.
63        It is important that subclasses accurately keep this count up-to-date.
64        """
65
66        self.visited_nodes: set[NodeType] = set()
67        """
68        Keep track of the board positions that have been visited.
69        This can help agents quickly check where they have previously been.
70        """
71
72        self.position_history: list[pacai.core.board.Position] = []
73        """
74        Keep track of the order that positions have been visited.
75        This let's us know exactly how the agent has moved about.
76        """
77
78    def complete(self, goal_node: NodeType) -> None:
79        """ Notify this search problem that the solver choose this goal node. """
80
81    @abc.abstractmethod
82    def get_starting_node(self) -> NodeType:
83        """ Get the starting node for the search problem. """
84
85    @abc.abstractmethod
86    def is_goal_node(self, node: NodeType) -> bool:
87        """ Check if this node is a valid goal node. """
88
89    @abc.abstractmethod
90    def get_successor_nodes(self, node: NodeType) -> list[SuccessorInfo[NodeType]]:
91        """
92        Get all the possible successors (successor nodes) to the current node.
93        This action can be though of expanding a search node,
94        or getting the children of a node in the search tree.
95        """

This class outlines the structure of a search problem. Any search problem will need to provide answers to the following questions: 1) Where should the search start? 2) Is some specific search node a goal (are we done?)? 3) What moves are possible from a given search node?

The answers to these questions are provided by implementing the methods of this class.

expanded_node_count: int

The number of search nodes that have been expended. It is important that subclasses accurately keep this count up-to-date.

visited_nodes: set[~NodeType]

Keep track of the board positions that have been visited. This can help agents quickly check where they have previously been.

position_history: list[pacai.core.board.Position]

Keep track of the order that positions have been visited. This let's us know exactly how the agent has moved about.

def complete(self, goal_node: ~NodeType) -> None: 
78    def complete(self, goal_node: NodeType) -> None:
79        """ Notify this search problem that the solver choose this goal node. """

Notify this search problem that the solver choose this goal node.

@abc.abstractmethod
def get_starting_node(self) -> ~NodeType: 
81    @abc.abstractmethod
82    def get_starting_node(self) -> NodeType:
83        """ Get the starting node for the search problem. """

Get the starting node for the search problem.

@abc.abstractmethod
def is_goal_node(self, node: ~NodeType) -> bool: 
85    @abc.abstractmethod
86    def is_goal_node(self, node: NodeType) -> bool:
87        """ Check if this node is a valid goal node. """

Check if this node is a valid goal node.

@abc.abstractmethod
def get_successor_nodes( self, node: ~NodeType) -> list[SuccessorInfo[~NodeType]]: 
89    @abc.abstractmethod
90    def get_successor_nodes(self, node: NodeType) -> list[SuccessorInfo[NodeType]]:
91        """
92        Get all the possible successors (successor nodes) to the current node.
93        This action can be though of expanding a search node,
94        or getting the children of a node in the search tree.
95        """

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.

class SearchSolution(typing.Generic[~NodeType]): 
 97class SearchSolution(typing.Generic[NodeType]):
 98    """
 99    A potential solution to a search problem.
100    This does not have to be an optimal (or even correct) solution,
101    but just what a solver returns.
102    """
103
104    def __init__(self,
105            actions: list[pacai.core.action.Action],
106            cost: float,
107            goal_node: NodeType | None = None,
108            ) -> None:
109        self.actions: list[pacai.core.action.Action] = actions
110        """
111        The actions to take for this solution.
112        These actions should guide the agent from its starting location (SearchProblem.get_starting_node())
113        to the goal (SearchProblem.is_goal_node()).
114        If the agent is just moving, you can think of this as it's "path".
115        """
116
117        self.cost: float = cost
118        """ The cost of this solution. """
119
120        self.goal_node: NodeType | None = goal_node
121        """
122        The node that the search was ended on.
123        May be None in cases where the solver does not use search nodes.
124        """
125
126    def get_path(self, start_position: pacai.core.board.Position) -> list[pacai.core.board.Position]:
127        """
128        Given the starting locatrion, get the path this search solution represents.
129        The resulting path will start at the starting position.
130        It is assumed that unknown actions will not result in a move.
131        """
132
133        path = [start_position]
134
135        for action in self.actions:
136            path.append(path[-1].apply_action(action))
137
138        return path

A potential solution to a search problem. This does not have to be an optimal (or even correct) solution, but just what a solver returns.

SearchSolution( actions: list[pacai.core.action.Action], cost: float, goal_node: Optional[~NodeType] = None) 
104    def __init__(self,
105            actions: list[pacai.core.action.Action],
106            cost: float,
107            goal_node: NodeType | None = None,
108            ) -> None:
109        self.actions: list[pacai.core.action.Action] = actions
110        """
111        The actions to take for this solution.
112        These actions should guide the agent from its starting location (SearchProblem.get_starting_node())
113        to the goal (SearchProblem.is_goal_node()).
114        If the agent is just moving, you can think of this as it's "path".
115        """
116
117        self.cost: float = cost
118        """ The cost of this solution. """
119
120        self.goal_node: NodeType | None = goal_node
121        """
122        The node that the search was ended on.
123        May be None in cases where the solver does not use search nodes.
124        """
actions: list[pacai.core.action.Action]

The actions to take for this solution. These actions should guide the agent from its starting location (SearchProblem.get_starting_node()) to the goal (SearchProblem.is_goal_node()). If the agent is just moving, you can think of this as it's "path".

cost: float

The cost of this solution.

goal_node: Optional[~NodeType]

The node that the search was ended on. May be None in cases where the solver does not use search nodes.

def get_path( self, start_position: pacai.core.board.Position) -> list[pacai.core.board.Position]: 
126    def get_path(self, start_position: pacai.core.board.Position) -> list[pacai.core.board.Position]:
127        """
128        Given the starting locatrion, get the path this search solution represents.
129        The resulting path will start at the starting position.
130        It is assumed that unknown actions will not result in a move.
131        """
132
133        path = [start_position]
134
135        for action in self.actions:
136            path.append(path[-1].apply_action(action))
137
138        return path

Given the starting locatrion, get the path this search solution represents. The resulting path will start at the starting position. It is assumed that unknown actions will not result in a move.

@typing.runtime_checkable
class CostFunction(typing.Protocol): 
140@typing.runtime_checkable
141class CostFunction(typing.Protocol):
142    """
143    A function that computes the cost associated with a specific search node.
144    """
145
146    def __call__(self, node: SearchNode, **kwargs: typing.Any) -> float:
147        ...

A function that computes the cost associated with a specific search node.

CostFunction(*args, **kwargs) 
1953def _no_init_or_replace_init(self, *args, **kwargs):
1954    cls = type(self)
1955
1956    if cls._is_protocol:
1957        raise TypeError('Protocols cannot be instantiated')
1958
1959    # Already using a custom `__init__`. No need to calculate correct
1960    # `__init__` to call. This can lead to RecursionError. See bpo-45121.
1961    if cls.__init__ is not _no_init_or_replace_init:
1962        return
1963
1964    # Initially, `__init__` of a protocol subclass is set to `_no_init_or_replace_init`.
1965    # The first instantiation of the subclass will call `_no_init_or_replace_init` which
1966    # searches for a proper new `__init__` in the MRO. The new `__init__`
1967    # replaces the subclass' old `__init__` (ie `_no_init_or_replace_init`). Subsequent
1968    # instantiation of the protocol subclass will thus use the new
1969    # `__init__` and no longer call `_no_init_or_replace_init`.
1970    for base in cls.__mro__:
1971        init = base.__dict__.get('__init__', _no_init_or_replace_init)
1972        if init is not _no_init_or_replace_init:
1973            cls.__init__ = init
1974            break
1975    else:
1976        # should not happen
1977        cls.__init__ = object.__init__
1978
1979    cls.__init__(self, *args, **kwargs)
@typing.runtime_checkable
class SearchHeuristic(typing.Protocol): 
149@typing.runtime_checkable
150class SearchHeuristic(typing.Protocol):
151    """
152    A heuristic function attempts to score a search node in the context of a problem.
153    """
154
155    def __call__(self, node: SearchNode, problem: SearchProblem, **kwargs: typing.Any) -> float:
156        ...

A heuristic function attempts to score a search node in the context of a problem.

SearchHeuristic(*args, **kwargs) 
1953def _no_init_or_replace_init(self, *args, **kwargs):
1954    cls = type(self)
1955
1956    if cls._is_protocol:
1957        raise TypeError('Protocols cannot be instantiated')
1958
1959    # Already using a custom `__init__`. No need to calculate correct
1960    # `__init__` to call. This can lead to RecursionError. See bpo-45121.
1961    if cls.__init__ is not _no_init_or_replace_init:
1962        return
1963
1964    # Initially, `__init__` of a protocol subclass is set to `_no_init_or_replace_init`.
1965    # The first instantiation of the subclass will call `_no_init_or_replace_init` which
1966    # searches for a proper new `__init__` in the MRO. The new `__init__`
1967    # replaces the subclass' old `__init__` (ie `_no_init_or_replace_init`). Subsequent
1968    # instantiation of the protocol subclass will thus use the new
1969    # `__init__` and no longer call `_no_init_or_replace_init`.
1970    for base in cls.__mro__:
1971        init = base.__dict__.get('__init__', _no_init_or_replace_init)
1972        if init is not _no_init_or_replace_init:
1973            cls.__init__ = init
1974            break
1975    else:
1976        # should not happen
1977        cls.__init__ = object.__init__
1978
1979    cls.__init__(self, *args, **kwargs)
@typing.runtime_checkable
class SearchProblemSolver(typing.Protocol): 
158@typing.runtime_checkable
159class SearchProblemSolver(typing.Protocol):
160    """
161    A function that solves a search problem and returns a solution.
162    Not all solvers will need to heuristic or RNG,
163    but they will always be provided (even if the heuristic is a null heuristic).
164    If no solution/path can be found, a SolutionNotFoundError exception should be raised.
165    """
166
167    def __call__(self,
168            problem: SearchProblem,
169            heuristic: SearchHeuristic,
170            rng: random.Random,
171            **kwargs: typing.Any) -> SearchSolution:
172        ...

A function that solves a search problem and returns a solution. Not all solvers will need to heuristic or RNG, but they will always be provided (even if the heuristic is a null heuristic). If no solution/path can be found, a SolutionNotFoundError exception should be raised.

SearchProblemSolver(*args, **kwargs) 
1953def _no_init_or_replace_init(self, *args, **kwargs):
1954    cls = type(self)
1955
1956    if cls._is_protocol:
1957        raise TypeError('Protocols cannot be instantiated')
1958
1959    # Already using a custom `__init__`. No need to calculate correct
1960    # `__init__` to call. This can lead to RecursionError. See bpo-45121.
1961    if cls.__init__ is not _no_init_or_replace_init:
1962        return
1963
1964    # Initially, `__init__` of a protocol subclass is set to `_no_init_or_replace_init`.
1965    # The first instantiation of the subclass will call `_no_init_or_replace_init` which
1966    # searches for a proper new `__init__` in the MRO. The new `__init__`
1967    # replaces the subclass' old `__init__` (ie `_no_init_or_replace_init`). Subsequent
1968    # instantiation of the protocol subclass will thus use the new
1969    # `__init__` and no longer call `_no_init_or_replace_init`.
1970    for base in cls.__mro__:
1971        init = base.__dict__.get('__init__', _no_init_or_replace_init)
1972        if init is not _no_init_or_replace_init:
1973            cls.__init__ = init
1974            break
1975    else:
1976        # should not happen
1977        cls.__init__ = object.__init__
1978
1979    cls.__init__(self, *args, **kwargs)