Intro to AI - Search
ai search cs50Definitions
agent | An agent is an entity that perceives its environment and acts upon that environment. |
state | A state is a configuration of the agent and its environment. |
initial state | The 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. |
transition model | The Transition model is a description of what state results from performing an applicable action state. |
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 search | Is a search strategy that uses no problem specific knowledge. |
informed search | Is a search strategy that uses problem-specific knowledge to find solutions more efficiently. |
Adversarial search | Is 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.
Depth-First Search
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.
Breadth-First Search
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.
Greedy Best-First Search
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:
maze | manhattan distance |
chess | number of chess pieces |
8-puzzle | number 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.
A* Search
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 search
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.