Module `pacai.student.searchAgents`

This file contains incomplete versions of some agents that can be selected to control Pacman. You will complete their implementations.

Good luck and happy searching!

Functions

def cornersHeuristic(state, problem)

Expand source code

def cornersHeuristic(state, problem):
    """
    A heuristic for the CornersProblem that you defined.

    This function should always return a number that is a lower bound
    on the shortest path from the state to a goal of the problem;
    i.e. it should be admissible.
    (You need not worry about consistency for this heuristic to receive full credit.)
    """

    # Useful information.
    # corners = problem.corners  # These are the corner coordinates
    # walls = problem.walls  # These are the walls of the maze, as a Grid.

    # *** Your Code Here ***
    return heuristic.null(state, problem)  # Default to trivial solution

A heuristic for the CornersProblem that you defined.

This function should always return a number that is a lower bound on the shortest path from the state to a goal of the problem; i.e. it should be admissible. (You need not worry about consistency for this heuristic to receive full credit.)

def foodHeuristic(state, problem)

Expand source code

def foodHeuristic(state, problem):
    """
    Your heuristic for the FoodSearchProblem goes here.

    This heuristic must be consistent to ensure correctness.
    First, try to come up with an admissible heuristic;
    almost all admissible heuristics will be consistent as well.

    If using A* ever finds a solution that is worse than what uniform cost search finds,
    your heuristic is *not* consistent, and probably not admissible!
    On the other hand, inadmissible or inconsistent heuristics may find optimal solutions,
    so be careful.

    The state is a tuple (pacmanPosition, foodGrid) where foodGrid is a
    `pacai.core.grid.Grid` of either True or False.
    You can call `foodGrid.asList()` to get a list of food coordinates instead.

    If you want access to info like walls, capsules, etc., you can query the problem.
    For example, `problem.walls` gives you a Grid of where the walls are.

    If you want to *store* information to be reused in other calls to the heuristic,
    there is a dictionary called problem.heuristicInfo that you can use.
    For example, if you only want to count the walls once and store that value, try:
    ```
    problem.heuristicInfo['wallCount'] = problem.walls.count()
    ```
    Subsequent calls to this heuristic can access problem.heuristicInfo['wallCount'].
    """

    position, foodGrid = state

    # *** Your Code Here ***
    return heuristic.null(state, problem)  # Default to the null heuristic.

Your heuristic for the FoodSearchProblem goes here.

This heuristic must be consistent to ensure correctness. First, try to come up with an admissible heuristic; almost all admissible heuristics will be consistent as well.

If using A ever finds a solution that is worse than what uniform cost search finds, your heuristic is not* consistent, and probably not admissible! On the other hand, inadmissible or inconsistent heuristics may find optimal solutions, so be careful.

The state is a tuple (pacmanPosition, foodGrid) where foodGrid is a Grid of either True or False. You can call foodGrid.asList() to get a list of food coordinates instead.

If you want access to info like walls, capsules, etc., you can query the problem. For example, problem.walls gives you a Grid of where the walls are.

If you want to store information to be reused in other calls to the heuristic, there is a dictionary called problem.heuristicInfo that you can use. For example, if you only want to count the walls once and store that value, try:

problem.heuristicInfo['wallCount'] = problem.walls.count()

Subsequent calls to this heuristic can access problem.heuristicInfo['wallCount'].

Classes

class AnyFoodSearchProblem (gameState, start=None)

Expand source code

class AnyFoodSearchProblem(PositionSearchProblem):
    """
    A search problem for finding a path to any food.

    This search problem is just like the PositionSearchProblem,
    but has a different goal test, which you need to fill in below.
    The state space and successor function do not need to be changed.

    The class definition above, `AnyFoodSearchProblem(PositionSearchProblem)`,
    inherits the methods of `pacai.core.search.position.PositionSearchProblem`.

    You can use this search problem to help you fill in
    the `ClosestDotSearchAgent.findPathToClosestDot` method.

    Additional methods to implement:

    `pacai.core.search.position.PositionSearchProblem.isGoal`:
    The state is Pacman's position.
    Fill this in with a goal test that will complete the problem definition.
    """

    def __init__(self, gameState, start = None):
        super().__init__(gameState, goal = None, start = start)

        # Store the food for later reference.
        self.food = gameState.getFood()

A search problem for finding a path to any food.

This search problem is just like the PositionSearchProblem, but has a different goal test, which you need to fill in below. The state space and successor function do not need to be changed.

The class definition above, AnyFoodSearchProblem(PositionSearchProblem), inherits the methods of PositionSearchProblem.

You can use this search problem to help you fill in the ClosestDotSearchAgent.findPathToClosestDot() method.

Additional methods to implement:

PositionSearchProblem.isGoal(): The state is Pacman's position. Fill this in with a goal test that will complete the problem definition.

Args

gameState: A AbstractGameState.
costFn: A function from a search state (x, y) to a non-negative number.
goal: The target position.

Ancestors

Methods

def actionsCost(self, actions): Inherited from: PositionSearchProblem.actionsCost

Returns the cost of a particular sequence of actions. If those actions include an illegal move, return 999999.
def isGoal(self, state): Inherited from: PositionSearchProblem.isGoal

Answers the question: Is this state a goal? …
def startingState(self): Inherited from: PositionSearchProblem.startingState

Answers the question: Where should the search start? …
def successorStates(self, state): Inherited from: PositionSearchProblem.successorStates

Returns successor states, the actions they require, and a constant cost of 1.

class ApproximateSearchAgent (index, **kwargs)

Expand source code

class ApproximateSearchAgent(BaseAgent):
    """
    Implement your contest entry here.

    Additional methods to implement:

    `pacai.agents.base.BaseAgent.getAction`:
    Get a `pacai.bin.pacman.PacmanGameState`
    and return a `pacai.core.directions.Directions`.

    `pacai.agents.base.BaseAgent.registerInitialState`:
    This method is called before any moves are made.
    """

    def __init__(self, index, **kwargs):
        super().__init__(index, **kwargs)

Implement your contest entry here.

Additional methods to implement:

BaseAgent.getAction(): Get a PacmanGameState and return a Directions.

BaseAgent.registerInitialState(): This method is called before any moves are made.

Ancestors

BaseAgent
abc.ABC

Static methods

def loadAgent(name, index, args={}): Inherited from: BaseAgent.loadAgent

Load an agent with the given class name. The name can be fully qualified or just the bare class name. If the bare name is given, the class should …

Methods

def final(self, state): Inherited from: BaseAgent.final

Inform the agent about the result of a game.
def getAction(self, state): Inherited from: BaseAgent.getAction

The BaseAgent will receive an AbstractGameState, and must return an action from Directions.
def observationFunction(self, state): Inherited from: BaseAgent.observationFunction

Make an observation on the state of the game. Called once for each round of the game.
def registerInitialState(self, state): Inherited from: BaseAgent.registerInitialState

Inspect the starting state.

class ClosestDotSearchAgent (index, **kwargs)

Expand source code

class ClosestDotSearchAgent(SearchAgent):
    """
    Search for all food using a sequence of searches.
    """

    def __init__(self, index, **kwargs):
        super().__init__(index, **kwargs)

    def registerInitialState(self, state):
        self._actions = []
        self._actionIndex = 0

        currentState = state

        while (currentState.getFood().count() > 0):
            nextPathSegment = self.findPathToClosestDot(currentState)  # The missing piece
            self._actions += nextPathSegment

            for action in nextPathSegment:
                legal = currentState.getLegalActions()
                if action not in legal:
                    raise Exception('findPathToClosestDot returned an illegal move: %s!\n%s' %
                            (str(action), str(currentState)))

                currentState = currentState.generateSuccessor(0, action)

        logging.info('Path found with cost %d.' % len(self._actions))

    def findPathToClosestDot(self, gameState):
        """
        Returns a path (a list of actions) to the closest dot, starting from gameState.
        """

        # Here are some useful elements of the startState
        # startPosition = gameState.getPacmanPosition()
        # food = gameState.getFood()
        # walls = gameState.getWalls()
        # problem = AnyFoodSearchProblem(gameState)

        # *** Your Code Here ***
        raise NotImplementedError()

Search for all food using a sequence of searches.

Ancestors

Static methods

def loadAgent(name, index, args={}): Inherited from: SearchAgent.loadAgent

Load an agent with the given class name. The name can be fully qualified or just the bare class name. If the bare name is given, the class should …

Methods

def final(self, state)

Inherited from: SearchAgent.final

Inform the agent about the result of a game.

def findPathToClosestDot(self, gameState)

Expand source code

def findPathToClosestDot(self, gameState):
    """
    Returns a path (a list of actions) to the closest dot, starting from gameState.
    """

    # Here are some useful elements of the startState
    # startPosition = gameState.getPacmanPosition()
    # food = gameState.getFood()
    # walls = gameState.getWalls()
    # problem = AnyFoodSearchProblem(gameState)

    # *** Your Code Here ***
    raise NotImplementedError()

Returns a path (a list of actions) to the closest dot, starting from gameState.

def getAction(self, state)

Inherited from: SearchAgent.getAction

Returns the next action in the path chosen earlier (in registerInitialState). Return Directions.STOP if there is no further action to take.

def observationFunction(self, state)

Inherited from: SearchAgent.observationFunction

Make an observation on the state of the game. Called once for each round of the game.

def registerInitialState(self, state)

Inherited from: SearchAgent.registerInitialState

Expand source code

def registerInitialState(self, state):
    self._actions = []
    self._actionIndex = 0

    currentState = state

    while (currentState.getFood().count() > 0):
        nextPathSegment = self.findPathToClosestDot(currentState)  # The missing piece
        self._actions += nextPathSegment

        for action in nextPathSegment:
            legal = currentState.getLegalActions()
            if action not in legal:
                raise Exception('findPathToClosestDot returned an illegal move: %s!\n%s' %
                        (str(action), str(currentState)))

            currentState = currentState.generateSuccessor(0, action)

    logging.info('Path found with cost %d.' % len(self._actions))

This is the first time that the agent sees the layout of the game board. Here, we choose a path to the goal. In this phase, the agent should compute …

class CornersProblem (startingGameState)

Expand source code

class CornersProblem(SearchProblem):
    """
    This search problem finds paths through all four corners of a layout.

    You must select a suitable state space and successor function.
    See the `pacai.core.search.position.PositionSearchProblem` class for an example of
    a working SearchProblem.

    Additional methods to implement:

    `pacai.core.search.problem.SearchProblem.startingState`:
    Returns the start state (in your search space,
    NOT a `pacai.core.gamestate.AbstractGameState`).

    `pacai.core.search.problem.SearchProblem.isGoal`:
    Returns whether this search state is a goal state of the problem.

    `pacai.core.search.problem.SearchProblem.successorStates`:
    Returns successor states, the actions they require, and a cost of 1.
    The following code snippet may prove useful:
    ```
        successors = []

        for action in Directions.CARDINAL:
            x, y = currentPosition
            dx, dy = Actions.directionToVector(action)
            nextx, nexty = int(x + dx), int(y + dy)
            hitsWall = self.walls[nextx][nexty]

            if (not hitsWall):
                # Construct the successor.

        return successors
    ```
    """

    def __init__(self, startingGameState):
        super().__init__()

        self.walls = startingGameState.getWalls()
        self.startingPosition = startingGameState.getPacmanPosition()
        top = self.walls.getHeight() - 2
        right = self.walls.getWidth() - 2

        self.corners = ((1, 1), (1, top), (right, 1), (right, top))
        for corner in self.corners:
            if not startingGameState.hasFood(*corner):
                logging.warning('Warning: no food in corner ' + str(corner))

        # *** Your Code Here ***
        raise NotImplementedError()

    def actionsCost(self, actions):
        """
        Returns the cost of a particular sequence of actions.
        If those actions include an illegal move, return 999999.
        This is implemented for you.
        """

        if (actions is None):
            return 999999

        x, y = self.startingPosition
        for action in actions:
            dx, dy = Actions.directionToVector(action)
            x, y = int(x + dx), int(y + dy)
            if self.walls[x][y]:
                return 999999

        return len(actions)

This search problem finds paths through all four corners of a layout.

You must select a suitable state space and successor function. See the PositionSearchProblem class for an example of a working SearchProblem.

Additional methods to implement:

SearchProblem.startingState(): Returns the start state (in your search space, NOT a AbstractGameState).

SearchProblem.isGoal(): Returns whether this search state is a goal state of the problem.

SearchProblem.successorStates(): Returns successor states, the actions they require, and a cost of 1. The following code snippet may prove useful:

    successors = []

    for action in Directions.CARDINAL:
        x, y = currentPosition
        dx, dy = Actions.directionToVector(action)
        nextx, nexty = int(x + dx), int(y + dy)
        hitsWall = self.walls[nextx][nexty]

        if (not hitsWall):
            # Construct the successor.

    return successors

Ancestors

SearchProblem
abc.ABC

Methods

def actionsCost(self, actions)

Expand source code

def actionsCost(self, actions):
    """
    Returns the cost of a particular sequence of actions.
    If those actions include an illegal move, return 999999.
    This is implemented for you.
    """

    if (actions is None):
        return 999999

    x, y = self.startingPosition
    for action in actions:
        dx, dy = Actions.directionToVector(action)
        x, y = int(x + dx), int(y + dy)
        if self.walls[x][y]:
            return 999999

    return len(actions)

Returns the cost of a particular sequence of actions. If those actions include an illegal move, return 999999. This is implemented for you.

def isGoal(self, state)

Inherited from: SearchProblem.isGoal

Answers the question: Is this state a goal? …

def startingState(self)

Inherited from: SearchProblem.startingState

Answers the question: Where should the search start? …

def successorStates(self, state)

Inherited from: SearchProblem.successorStates

Answers the question: What moves are possible from this state? …