Search

🧠 Introduction to AI

Lecture Notes
Author

Andy Weeger

Published

Feb 12, 2024

Modified

Mar 25, 2024

Search problem

Definition

A search problem can be defined formally as (Russel and Norvig 2022, 83):

  • The state space: a set of possible states2 the environment can be in3
  • The initial state: the state that the agent starts
  • The goal state(s): a state that the agent is trying to reach4
  • A transition model: \(\textrm{RESULT}(s,a)\) (returns the state \(s'\) that results from performing action \(a\) in state \(s\))
  • The successor function: \(\textrm{ACTIONS}(s)\) (returns a set of (action, state) pairs for node \(s\), where the state is the state reachable by taking the action \(a\))
  • An action cost function: \(\textrm{ACTION-COST}(s,a,s')\) (gives the numeric cost of performing action \(a\) in state \(s\) to reach state \(s'\))
  • A path: a sequence of actions
  • A solution: a path from the initial state to the goal state

Modelling

Figure 1: Example: A simplified map of Romania, with road distances in miles; based on Russel and Norvig (2022)

Figure 1 depicts the search problem as model, the state space graph (Russel and Norvig 2022, 82–84):

  • State space: cities (vertices, each state occurs only once)
  • Initial state: Arad
  • Goal state: Bucharest (goal test: \(Is state == Bucharest?\))
  • Actions: directed edges between the vertices (paths)
  • Action costs: numbers on the paths
Abstraction

The model is an abstract mathematical description, here a simple atomic state description. The model is an abstraction as it ignores many details of the reality (e.g., weather and scenery).

A good problem formulation has the right level of detail (i.e., an appropriate level of abstraction).

The choice of a good abstraction involves removing as much detail as possible while retaining validity and ensuring that the abstract actions are easy to carry out. An abstraction is valid if any abstract solution can be elaborated into a solution in the more detailed world.

Search tree

Structure

Figure 2: Example: A partial search tree for finding a route from Arad to Bucharest; based on Russel and Norvig (2022)

Figure 2 visualizes a partial search tree: the first few steps in finding a path from Arad (initial state) to Bucharest (goal).

  • The root node of the search tree is the initial state \(s\) (Arad)
  • The available actions considerd using \(ACTIONS(s)\)
  • New nodes, called child nodes or successor nodes are generated using \(RESULT(s,a)\) (i.e., the root node is expanded)
  • Each child node has Arad as its parent node
  • The child node to be considered next is selected by the minimum value of some evaluation function \(f(n)\) (strategies see below)

In Figure 2, nodes that have been expanded are white with bold letters; nodes on the frontier that have been generated but not yet expanded are in white and regular letters; the set of states corresponding to these two types of nodes are said to have been reached. Nodes that could be generated next are shown in faint dashed lines.

Definition of search trees

A search tree is a “what if” tree of plans and their outcomes.

  • The start state is the root node,
  • children correspond to successors,
  • nodes show states, but correspond to PLANS that achieve those states

There are lots of repeated structure in the search tree. Thus, for most problems, the whole tree can never be actually built. In practice, both state space graphs and search trees are constructed on demand and as little as possible (Russel and Norvig 2022).

Search algorithms require a data structure to keep track of the search tree. A node in the tree is represented by a data structure with four components (Russel and Norvig 2022, 91):

  • node.STATE: the state to which the node corresponds
  • node.PARENT: the node in the tree that generated this node
  • node.ACTION: the action that was applied to the parent’s state to generate this node
  • node.PATH-COST: the total cost of the path from the initial state to generate this node

Following the PARENT pointers back from a node allows to revocer the states and actions along the path to that node. Doing this from a goal node generates the solution.

Example data structure in pseudo code:

var searchTree = {
  node.STATE: "Bucharest"
  node.PARENT: {
    node.STATE: "Pitesti"
    node.PARENT: {
      node.STATE: "Rimmicu Vilcea"
      node.PARENT: {
        node.STATE: "Sibiu"
        node.PARENT: {
          node.STATE: "Arad"
          node.PARENT: NULL
          node.ACTION: NULL
          node.PATH-COST: 0
        }
        node.ACTION: "Arad to Sibiu"
        node.PATH-COST: 140
      }
      node.ACTION: "Sibiu to Rimmicu Vilcea"
      node.PATH-COST: 220
    }
    node.ACTION: "Rimmicu Vilcea to Pitesti"
    node.PATH-COST: 317
  }
  node.ACTION: "Pitesti to Bucharest"
  node.PATH-COST: 418
}

In addition, a data structure to store the fontier is neded. Usually this is realized using a queue with following functions (Russel and Norvig 2022, 91):

  • IS-EMPTY(frontier): returns true only if there are no nodes in the frontier
  • POP(frontier): removes the top node from the frontier and returns it
  • TOP(frontier): returns (but does not remove) the top node from the frontier
  • ADD(node,frontier): inserts node into its proper place in the queue

Search algorithms

Definition

Search algorithms take a search problem as input and return a solution, or an indication of failure (Russel and Norvig 2022, 89).

  • They superimpose a search tree over the state-space graph,
  • form various paths from the initial state, and
  • try to find a path that reaches a goal state

They can implement

  • uninformed search methods, which only have access to the problem definition but not clue about how close a state is to the goal(s).
  • informed search methods, which have access to a heuristic function that gives domain-specific hints about how close a state is to the goal(s) (e.g., using straight-line distance in route-finding problems)

Competitive environments

Deterministic games

The games most commonly studied within AI are deterministic (two-player, turn-taking, fully observable, zero-sum8) (Russel and Norvig 2022, 192).

Possible formalization

  • States: \(S\) (start at \(S_0\))
  • Player: \(\textrm{TO-MOVE}(s)\) (defines which player has the move in state \(s\))
  • Actions: \(\textrm{ACTIONS}(s)\) (the set of legal moves in state \(s\))
  • Transition model: \(\textrm{RESULTS}(s,a)\) (defines the state resulting from action \(a\) in state \(s\))
  • Terminal test: \(\textrm{IS-TERMINAL}(s)\) (is true when the game is over9)
  • Utility function: \(\textrm{UTILITY}(s,p)\) (defines the final numeric value to player \(p\) when the game ends in terminal state \(s\))

The initial state, \(\textrm{ACTIONS}(s)\), and \(\textrm{RESULT}(s,a)\) define the state space graph, where the vertices are states, the edges are moves and the state might be reached by multiple paths.

Optimal decisions

Players (here MIN and MAX, alternate turns) need to have a conditional plan—a contingent strategy specifying a response to each move of the opponent.

  • For games with binary outcomes (win or lose), AND-OR10 search tree can be used
    (see Russel and Norvig 2022, 143)
  • For games with multiple outcome scores, the minimax search algorithm is used

Wrap-up

Search

Search operates over models of the world (which might be observed online)

  • Agents do not try all possible plans
  • Planning is all “in simulation”
  • Search is only as good as the models are

Adversarial search

  • In two-player, discrete, deterministic, turn-taking zero-sum games with perfect information, the minimax algorithm can select optimal moves by a depth-first search in the game tree
  • Efficiency can be improved by using the alpha-beta search algorithm, which eliminates subtrees that are shown to be irrelevant.
  • Monte Carlo tree search evaluates states by playing out the game all the way to the end to see who won. This playout simulation is repeated multiple times. The evaluation is an average of the results.

xkcd

Figure 8: xkcd 1263: reassuring

✏️ Exercises

Definition sequence

Problem formulation must follow goal formulation.

Discuss that statement. Is it true or false? Why?

Problem formulation

Give a complete problem formulation for each of the following problems. Choose a formulation that is precise enough to be implemented.

  • There are six glass boxes in a row, each with a lock. Each of the first five boxes holds a key unlocking the next box in line; the last box holds a banana. You have the key to the first box, and you want the banana.
  • There is an n x n grid of squares, each square initially being either unpainted floor or a bottomless pit. You start standing on an unpainted floor square, and can either paint the square under you or move into an adjacent unpainted floor square. You want the whole floor painted.

Maze

Your goal is to navigate a robot out of a maze. It starts in the center of the maze facing north. You can turn the robot to face north, east, south, or west; direct the robot to move forward a certain distance (it will stop before a wall).

  1. Formally define this problem as a search problem. How large is the state space?
  2. In navigating a maze, the only place we need to turn is at the intersection of two or more corridors. Reformulate this problem using this observation. How large is the state space now?
  3. From each point in the maze, we can move in any of the four directions until we reach a turning point, and this is the only action we need to do. Reformulate the problem using these actions. Do we need to keep track of the robot’s orientation now?
  4. In our initial description of the problem we already abstracted from the real world. Name three such simplifications we made.

Open only if you need help.

Figure 9: Solution note for question 2/3

Concepts

Explain in your own words the following terms:

  • Zero-sum
  • Terminal test
  • Minimax value
  • Selection policy
  • Playout policy
  • Monte Carlo tree
  • Back-propagation

MINIMAX

Explain if the MINIMAX algorithm is complete and optimal.

Can it be beaten by an opponent playing suboptimally? Why (not)?

Come up with a game tree in which MAX will beat a suboptimal MIN.

Open only if you need help.

In two-player, discrete, deterministic, turn-taking zero-sum games with perfect information, the MINIMAX algorithm can select optimal moves by a depth-first emuration, the algorithm is also guaranteed to find a solution when there is one.

The algorithm performs a complete depth-first exploration of the game tree. If the maximum depth of the tree is \(m\) and there are \(b\) legal moves at each point, then the time complexity is \(O(b^m)\) for an algorithm that generates all actions at once, or \(O(m)\) for an algorithm that generates actions on at a time. The exponential complexity makes MINIMAX impractical for complex games. MINIMAX does, however, serve as a basis for the mathematical analysis for games. By approximating the minimax analysis in various ways, we can derive more practical algorithms.

If MIN does not play optimally, then MAX will do at least as well as against an optimal player, possibly better.

Pruning

Read the note about pruning (and consult Russel and Norvig (2022) if necessary).

Explain in your own words, under what conditions a subtree is skipped using Alpha-beta pruning.

Draw an example (game search tree, 3 levels depth).

Literature

Russel, Stuart, and Peter Norvig. 2022. Artificial Intelligence: A Modern Approach. Harlow: Pearson Education.

Footnotes

  1. An atomic representation is one in which each state is treated as a black box with not internal structure, meaning the state either does or does not match what you’re looking for.↩︎

  2. A state is a situation that an agent can find itself in.↩︎

  3. Expressed by a graph whose nodes are the set of all states, and whose links are actions that transform one state into another↩︎

  4. Can be a single goal state, a small set of alternative goal states, or a property that applies to many states (e.g, no dirt in any location)↩︎

  5. first-in-first-out queue first pops the node that was added to the queue first↩︎

  6. last-in-first-out queue (also known as a stack) pops first the most recently added node↩︎

  7. first pops the node with the minimum costs according to \(f(n)\)↩︎

  8. Zero-sum means that what is good for one player is just as bad for the other: there is no “win-win” outcome↩︎

  9. States where the game has ended are called terminal states↩︎

  10. The search tree consists of AND nodes and OR nodes. AND nodes reflect the environment’s choice of action (which all need to be considers), OR nodes the agent’s own choices in each state (where only one needs to be considered). AND and OR nodes alternate. A solution is a conditional plan that considers every nondeterministic outcome and makes a plan for each one.↩︎

  11. Reading recommendation↩︎

  12. guided by the selection policy↩︎

  13. For games with binary outcomes, average utility equals win percentage↩︎

  14. A heuristic evaluation function returns an estimate of the expected utility of state \(s\) to player \(p\).↩︎

  15. Playout policies biases the moves toward good ones. For Go and other games, playout policies have been successfully learned from self-play by using neural networks. Sometimes also game-specific heuristics are used (e.g., take the corner square in Othello)↩︎