The landscape of Artificial Intelligence (henceforth referred to as AI), is rapidly evolving. The ability of AI to reason and make decisions are just a tip of the iceberg. As more and more AI systems are being challenged with complex problem-solving, the underlying methods which define these systems are more exciting and paramount to understand. In this brief article, we will be discussing about one such system – Search Algorithms. As the name suggests, these algorithms try to search for the solution in a particular space with or without the help of a heuristic. They happen to play a very crucial role in the intricately complex decision-making systems.
A classical and age-old problem in AI known as Cabbage, Wolf, Sheep, and Man puzzle, appreciates the need and significance of search algorithms. In this problem, the man must transport a cabbage, a wolf, and a sheep, across a river. But there are few constraints. The first constraint being he can take only one of them at a given point of time. The challenge increases, wolf will eat the sheep if left together and the sheep will consume cabbage if the man is absent.
Well, the answer for this problem do already exist. I will leave the amusement of the possibility for the readers to explore. But this problem does clearly define the intricacies that AI reasons extensively and has the ability to search in the solution space to find the systematic search strategies to explore all the possible moves. Further, this proves that the solution (more often than not) involves extensive planning and a complete examination of the problem space. Also, it shows how to create plausible action sequences, explaining the necessity to understand the need of different kinds of search algorithms. In this introductory guide, we will look into three major types of search algorithms, with the help of examples to solve an 8-Puzzle Game.
Uninformed Search Algorithms
Uninformed search algorithms are a subspace of search algorithms that tend to explore the search space without any heuristic (helper functions) and domain specific knowledge. It relies solely on the information given in hand. Generally, they explore the search space in its entirety by finding all the possible solutions, until and unless the final goal is reached. Since, they do not use any heuristics, they are more or less “blind” (in terms of direction) in the search space. These algorithms might terminate or not – depending on the path taken. But, since they explore the entire space, they are not space and time efficient. The two most common uninformed search algorithms are Breadth First Search (BFS) and Depth First Search (DFS).
- BFS – As the name suggests, it explore the search space in a level-by-level fashion. Once, the present level is exhausted, it moves to the nodes on the next depth level. The basic assumption is that the cost of each step is equal. If the solution exists, then it is a complete algorithm. It is implemented with a queue (FIFO – First in First Out) to maintain the remaining nodes to explore [3].
- DFS – It explores one branch of the tree to its maximum depth. Once that particular branch is exhausted, it backtracks. It uses a stack data structure (helps in recursion) to keep the path track. This leads to better memory efficiency than BFS but it is less time efficient in terms of finding the optimal solution. If a particular branch has infinites nodes or presence of cyclic branch, the algorithm will never terminate [3].
Informed Search Algorithms
Informed Search Algorithms form a different class of strategies that uses some additional information, generally known as heuristic functions, along with the uninformed search algorithm. These tend to take the search process in more cost-effective and promising paths. The heuristic function varies with each algorithm and they tend to incorporate the domain-specific knowledge. Consequently, these algorithms are mostly complete and help to find the optimal solution in time and cost-effective manner. Some commonly used algorithms are A*, Best First Search, Greedy Search, etc.
- A* – It is one of the most popular informed search techniques. The heuristic function of A* is f(n) = g(n) + h(n). It is also called as the evaluation function. It combines both actual cost and estimated cost from the initial node to the goal state. A* guarantees to provide the most optimal solution if and only if the evaluation function is admissible (it should never overestimate the actual cost) [3].
- Best First Search – Another algorithm that selects the next node to be visited based on the heuristic values. The evaluation function for this algorithm takes a node, which has the lowest heuristic value, while going towards the goal, i.e. h(n). Unlike A*, this algorithm only takes estimated cost into account. Because of this, it creates scenarios where it runs faster than A*, but does not guarantee an optimal solution [3].
Adversarial Search Algorithms
This class of search algorithms more or less focus on multi-agent systems like games (Chess, Checkers, Go, etc.). They tend to solve problems wherein multiple agents with conflicting goals interact with each other. The aim is not only to consider and play your own moves but also to anticipate and counter the opponents’ moves and strategies. The decision making takes place in the state of uncertainty. They are modelled as trees, with nodes as game state possibilities, edges as players’ moves, and leaf node as the final result with one player winning or losing.
- MiniMax – It works in a recursive fashion by exploring the entire game tree, considering both the players are rational and take the best possible moves in account. A value is assigned to each leaf node based on a win/loss/draw (1/-1/0) and the algorithm propagates these values upwards [3].
- AlphaBeta – It is an optimized version of Minimax algorithm. It prunes the branches or nodes that needs to be evaluated in the process by eliminating those that will never influence the final decision. Since, further exploration is not needed after pruning, it makes the search more efficient with increasing its optimality [3].
Conclusion
Search Algorithms in any form are a crucial part of the problem-solving approach in AI. They enable the systems to explore vast search spaces in an efficient and cost-effective manner. Understanding these algorithms in depth is essential to develop intelligent systems that can reason, plan, and make decisions effectively and simultaneously. As AI is continuing to advance, their role will only grow important, providing a better start for smarter, more efficient solutions across diverse domains.
By: Puneet
Write and Win: Participate in Creative writing Contest & International Essay Contest and win fabulous prizes.
