CS50 Notes - Search

00 Search

Finding a solution to a problem, like a navigator app that finds the best route from your origin to the destination, or like playing a game and figuring out the next move.

Basic terminology

• initial state

  the state in which the agent begins

  • agent

  entity that perceives its environment and acts upon that environment

  • state

    a configuration of the agent and its environment

• actions

  choices that can be made in a state

  • actions

    ACTIONS(s) returns the set of actions that can be executed in state s

• transition model

  a description of what state results from performing any applicable action in any state

  RESULT(s, a) returns the state resulting from performing action a in state s

  • state space

    the set of all states reachable from the initial state by any sequence of actions

• goal test

  way to determine whether a given state is a goal state

• path cost

  numerical cost associated with a given path

• solution

  a sequence of actions that leads from the initial state to a goal state

• optimal solution

  a solution that has the lowest path cost among all solutions

• evaluation function

  function that estimates the expected utility of the game from a given state

Data structure

1. node (Actually it is not a typical Data structure)

   a data structure that keeps track of - a state - a parent (node that generated this node) - an action (action applied to parent to get node) - a path cost (from initial state to node)

2. stack

   last-in first-out data type

3. queue

   first-in first-out data type

uninformed search

Search strategy that uses no problem- specific knowledge.

They both are always work, and not necessarily a optimal solution.

DFS depth-first search

search algorithm that always expands the deepest node in the frontier, using stack.

• Pros: At best, this algorithm is the fastest. If it “lucks out” and always chooses the right path to the solution (by chance), then depth-first search takes the least possible time to get to a solution.

• Cons: It is possible that the found solution is not optimal. At worst, this algorithm will explore every possible path before finding the solution, thus taking the longest possible time before reaching the solution.

    # Define the function that removes a node from the frontier and returns it.
    def remove(self):
    	  # Terminate the search if the frontier is empty, because this means that there is no solution.
        if self.empty():
            raise Exception("empty frontier")
        else:
        	  # Save the last item in the list (which is the newest node added)
            node = self.frontier[-1]
            # Save all the items on the list besides the last node (i.e. removing the last node)
            self.frontier = self.frontier[:-1]
            return node

BFS breadth-first search

search algorithm that always expands the shallowest node in the frontier, using queue.

• Pros: This algorithm is guaranteed to find the optimal solution.

• Cons: This algorithm is almost guaranteed to take longer than the minimal time to run. At worst, this algorithm takes the longest possible time to run.

# Define the function that removes a node from the frontier and returns it.
    def remove(self):
    	  # Terminate the search if the frontier is empty, because this means that there is no solution.
        if self.empty():
            raise Exception("empty frontier")
        else:
            # Save the oldest item on the list (which was the first one to be added)
            node = self.frontier[0]
            # Save all the items on the list besides the first one (i.e. removing the first node)
            self.frontier = self.frontier[1:]
            return node

informed search

search strategy that uses problem-specific knowledge to find solutions more efficiently

• greedy best-first search

search algorithm that expands the node that is closest to the goal, as estimated by a heuristic function h(n)

It is important to emphasize that, as with any heuristic, it can go wrong and lead the algorithm down a slower path than it would have gone otherwise. It is possible that an uninformed search algorithm will provide a better solution faster, but it is less likely to do so than an informed algorithm.

• A* search

search algorithm that expands node with lowest value of g(n) + h(n)

g(n) = cost to reach node h(n) = estimated cost to goal

optimal if

h(n) is admissible (never overestimates the true cost), and
h(n) is consistent (for every node n and successor n' with step cost c, h(n) ≤ h(n') + c)

Adversarial Search

Minimax

Minimax represents winning conditions as (-1) for one side and (+1) for the other side. Further actions will be driven by these conditions, with the minimizing side trying to get the lowest score, and the maximizer trying to get the highest score.

Representing a Tic-Tac-Toe AI:

S₀: Initial state (in our case, an empty 3X3 board)

Players(s): a function that, given a state s, returns which player’s turn it is (X or O).

Actions(s): a function that, given a state s, return all the legal moves in this state (what spots are free on the board).

Result(s, a): a function that, given a state s and action a, returns a new state. This is the board that resulted from 
performing the action a on state s (making a move in the game).

Terminal(s): a function that, given a state s, checks whether this is the last step in the game, i.e. if someone won or there is a tie. Returns True if the game has ended, False otherwise.

Utility(s): a function that, given a terminal state s, returns the utility value of the state: -1, 0, or 1.

Alpha-Beta Pruning

Alpha-Beta Pruning skips some of the recursive computations that are decidedly unfavorable. After establishing the value of one action, if there is initial evidence that the following action can bring the opponent to get to a better score than the already established action, there is no need to further investigate this action because it will decidedly be less favorable than the previously established one.

Depth-Limited Minimax

considers only a pre-defined number of moves before it stops, without ever getting to a terminal state. However, this doesn’t allow for getting a precise value for each action, since the end of the hypothetical games has not been reached.

To deal with this problem, Depth-limited Minimax relies on an evaluation function that estimates the expected utility of the game from a given state, or, in other words, assigns values to states.