Search is a key part of many AI problem-solving strategies that assist in exploring the problem spaces. As explained by Peter Norvig “Normal programming is telling the computer what to do when we know what to do. AI is when we tell the computer what to do when we don’t know what to do.”
Search in AI provides as a first step to start solving many of the problems, either it is finding a sequence of next steps to perform by an agent or deciding on the next game move.
Many search strategies are used in AI for efficient and goal-oriented searches. Let’s have a look at a few popular AI search strategies:
Breadth-First Search (BFS) is the most basic searches and it finds the shortest path with respect to a number of steps between the start and goal. Simple BFS does not consider any edge costs or weights. A queue with FIFO implementation can be used to keep track of the frontier of the explored nodes. BFS is undirected will start expanding the search in all directions from the start and also complete, so it is guaranteed to find the path even in infinite problem space. In terms of storage space, BFS will need to store 2N number of nodes in memory at any given level N, so it is expensive if storage space is stringent especially in larger problem spaces.
Uniform cost search or cheapest first search finds the most optimal path from start to goal w.r.t the edge cost. A priority queue is used normally to get the next lowest cost node to be explored. Like BFS, uniform cost search is undirected, complete and guarantees to find the optimal solution. More or less it also requires a storage space of 2N.
Depth First Search (DFS) finds the longest path reached from the start. It’s non-optimal and can find the way to goal but it might not be the most optimal way to reach the goal. DFS is also not complete. If it gets into an infinite path it is very likely it will never reach the goal. However, it does have an advantage in terms of storage space. DFS will need to store only N nodes of the current path. This is a winner when the problem space is very big and space a constraint. Figure 1 and Figure 2 below illustrate the difference between BFS and DFS for a binary tree search.
A* search is a directed search towards the goal. It expands the path in the direction which has the minimum cost and minimum of the estimated distance towards the goal. It is like adding a little bit of more knowledge to the uniform cost algorithm so that it explores a much less number of nodes to find the optimal path. The estimated distance can be any heuristic such as the direct distance between the node and goal node. For A* to find the optimal path, the heuristic value should be less than the true value of cost for that path. i.e. It should never overestimate the true cost.
Figure 3 and Figure 4 show kind of a contour map for how nodes explored in BFS/UCS and A* and in the direction they are explored from the start to goal nodes.
All the above search strategies are helpful when we are trying to find a sequence of steps like finding out the best possible routes between 2 cities, finding the next step in solving rubric’s cube. Some AI problems also deal with plotting against another AI agent or a human. Like in game playing the AI agent needs to anticipate the move of the opposition player and then search for the most optimal move from the game tree.
Adversarial searches are when the AI agents anticipate and plan ahead of other agents.
The Minimax Search algorithm is an adversarial search algorithm. In this algorithm, we choose the best moves to maximize the chances to win, assuming that the opponent is also playing optimally to win, minimizing our chances. For every action taken by an opponent all the possible actions remaining are evaluated using a game tree till the end game. The win values are propagated as positive when our agent wins and negative when the opponent wins to the top of the tree. At every level where our agent plays (max level), it selects the branch with max value. At every level opponent plays (min level), it selects the branch with min value. The algorithm tries to choose those moves which lead to a win for our agent.
Even for very less complicated games or situations, the minimax tree will approximately visit an exponential number of nodes when evaluated till the end game. For a tree with a branching factor of b and depth of d, the minimax tree needs to visit bd nodes approximately. Most of the situations in AI need the agent to be very responsive. So implementing the minimax till endgame is very expensive.
Depth limited search along with an evaluation function is normally used when implementing minimax. In this case, we calculate how deep in the game tree the agent searches before response limit timeout. So if we calculate the N level for which agent searches safely. At the Nth level, the agent uses an evaluation function which is an estimated measure of the win value of the game. Say for a game of tic-tac-toe it can be the number of moves remaining for the agent. An agent with more moves remaining will mostly win in the win. The value of the evaluation function is then propagated to the top of the tree to calculate the best move.
Iterative deepening is one more strategy where the agent at every level saves the best move calculated. Then again starts from the top of the tree and tries to search for the next level. It keeps on searching deeper in the tree until it reaches the response timeout. Then it returns the last saved move for completely evaluated level. So it is similar to depth limited search, but it continues searching deeper till time remains. It particularly is useful near the end of the game where the branching factor reduces significantly and the agents can search till deeper levels.
Figure 5 illustrates the search level for depth limited and iterative deepening techniques.
Alpha Beta Pruning technique is yet another strategy that ignores a lot of branches in minimax and yet returns exactly the same result as the minimax algorithm. It ignores moves that return less than maximum values at max levels where our agent takes an action. At min levels of a tree where an opponent chooses, it ignores moves that have more than min values at that level. This reduces the number of nodes to be evaluated as much as bd/2 in some cases when best move node ordering is done.
Different search strategies are applied in AI depending upon the problem type, resources available and the applicability of the strategy. A few popular ones are described above.