May 02, 2020

Intro to AI - Search

ai search cs50

Definitions

agentAn agent is an entity that perceives its environment and acts upon that environment.
stateA state is a configuration of the agent and its environment.
initial stateThe initial state is the state in which the agent begins, the first state.
actions

Actions are the choices that can be made in a state by the agent.
We define a function ACTIONS(s) to return the set of possible actions that can be executed in a state s.

transition model

The Transition model is a description of what state results from performing an applicable action state.
RESULT(s, a) returns the state resulting from performing action a` in state s``

state space

The state space is the set of all states reachable from the initial state by any possible sequence of actions.

goal test

Is a way to determine whether a given state is a goal state.

a path

Is the transition from one state to another state by executing an action.

path cost

Is a numerical cost associated with a given path.

solution

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

optimal solution

Is a solution that has the lowest path cost among all solutions.

uninformed searchIs a search strategy that uses no problem specific knowledge.
informed searchIs a search strategy that uses problem-specific knowledge to find solutions more efficiently.
Adversarial searchIs a search, where we examine the problem which arises when we try to plan ahead of the world and other agents are planning against us.

Search Problems

A Search Problem consists of:

  • initial state
  • transition model including actions
  • goal test
  • path cost function

Data Structure

To implement an algorithm for finding a solution to a search problem, we use the following data structures:

Node

A node is 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)

Frontier

The frontier is a list of nodes that are currently under investigation in order to find a solution for a search problem.

Explored Set

The set of nodes that have been visited during the search for the solution. This data structure is necessary in order to prevent searching in an endless loop by visiting the same set of states over and over again. This way we notice when running in a circle.

Algorithm

  • Start with a frontier that contains the initial state.
  • Start with an empty explored set.
  • Repeat:
    • If the frontier is empty, then no solution.
    • Remove a node from the frontier.
    • If node contains goal state, return the solution.
    • Add the node to the explored set.
    • Expand node, add resulting nodes to the frontier if they aren’t already in the frontier or the explored set.

Is a search algorithm that always expands the deepest node in the frontier first, the deepest node is the node that has been put into the frontier last. Since we start at the top of the search tree and proceed by going deeper by selecting always one of the current node’s child nodes.
This means for the frontier we use a data structure that returns the last element first. Such a data structure is a stack (last-in first-out)

Depth First = Nodes entered X later, must be generated on the tree first: Frontier is a stack.

Problem:
The found solution might not be the best solution because we have no way of knowing about alternatives.

Is a search algorithm that always expands the shallowest node in the frontier first, the shallowest node are the nodes that have been put into the frontier first. Since we start at the top of the search tree and proceed by checking all the children of the current node before going deeper and proceeding with the children of one of the children.
THis means for the frontier we use a data structure that return the first elements first. Such a data structure is a queue (first-in first-out)

Breadth First = Nodes entered X earlier, have to be generated on the tree first: Frontier is a queue.

Problem:
The number of nodes in the frontier might grow too big because we have to explore all possible child nodes in each step.

Is a search algorithm that expands the node that is closest to the goal, as estimated by a heuristic function h(n) This means when picking the node from the frontier we always pick the one with the best value for h(node).
Greedy Best-First Search is an example of an informed search algorithm because we use problem specific information to implement the heuristic.

Examples for heuristic functions:

mazemanhattan distance
chessnumber of chess pieces
8-puzzlenumber of tiles in position

Problem:
The solution might not be the best solution because finding the best step with the heuristic function might turn out to be the wrong choice in some cases.

Is a search algorithm that picks node n from the frontier with lowest value of g(n) + h(n) where

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

This means a local minimum might we overruled by the costs to reach that minimum or by the costs to proceed with the nodes after picking the minimum, and we choose to give up the search path and proceed with an alternative node from the frontier with a higher h(n) but a lower cost to reach g(n).

A* Search is optimal if:

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

Minimax is a search algorithm that is used in decision-making and game theory to find the optimal move for a player, assuming that your opponent also plays optimally.
The maximizer (MAX) tries to get the highest score possible while the minimizer (MIN) tries to do the opposite and get the lowest score possible.

Given a state s:

  • MAX picks action \$a\$ in \$ACTIONS(s)\$ that produces highest value of \$MIN-VALUE(RESULT(s, a))\$
  • MIN picks action \$a\$ in \$ACTIONS(s)\$ that produces smallest value of \$MAX-VALUE(RESULT(s, a))\$

maximizer evaluation

  function MAX-VALUE(state):
    if TERMINAL(state):
      return UTILITY(state)
    value = -∞
    for action in ACTIONS(state):
      value = MAX(value, MIN-VALUE(RESULT(state, action)))
    return value

minimizer evaluation

  function MIN-VALUE(state):
    if TERMINAL(state):
      return UTILITY(state)
    value = +∞
    for action in ACTIONS(state):
      value = MIN(value, MAX-VALUE(RESULT(state, action)))
    return value

initial state evaluation

It is important to get the initial step for evaluating the state right:

  • For the MAX player the best move is calculated by iterating through all the possible moves, calling the MIN function on the new state created by this move. This means to determine the best possible (MIN) value for each of the opponent’s moves. Then pick the maximum value from them to use as next move. In addition to the MIN-VALUE and MAX-VALUE functions where we just store the best evaluation value between -1 and +1 we also need to keep track of the action to know which move to take.
  function BEST-MOVE(state):
    if TERMINAL(state):
      return None

    if player == MAX:
      value = -∞
      move = None
      for action in ACTIONS(state):
        new = MIN-VALUE(RESULT(state, action))
        if (new > value):
          value = new
          move = action

    if player = MIN:
      value = +∞
      move = None
      for action in ACTIONS(state):
        new = MAX-VALUE(RESULT(state, action))
        if (new < value):
          value = new
          move = action

    return move

Alpha-Beta Pruning

Is an optimization of the Minimax search. It stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.

Depth-Limited Minimax

Instead of searching the state space until we reach a goal node we limit the number of analyzed nodes by their depth from the start node.
In order to be able to find the best action like this we need an evaluation function that returns the value of a given state.

evaluation function

This is a function that estimates the expected utility of the game of a given state.