Every other person in the field of Artificial Intelligence is finding some way to search efficiently. Why we are so much focused on this particular topic? There are so many things that intelligent beings do. But why algorithm can't see anything beyond search? Maybe because there is nothing beyond search! Yes, we claim that all the various problems faced by us can be reduced to searching problems. This seems to be a very big claim. And we are excited to explore further.

The thing that is more important than solving a problem is understanding the problem and modelling it well. These two things are pre-requisite before attempting to find a solution. We all know what it means to understand the problem. Actually, we don't. Most of the times, we don't have a clear picture in our mind. In order to verify if we have understood the problem, the best we can do is to formulate it. This means making a black-box model, with proper inputs and outputs. Once we have formulated the problem, we can now attempt to think of various ways to solve it.

Black box is something which takes some input and throws some output. What happens inside it is hidden. Read more here.

Modelling a Problem

There are generally many ways to formulate a single problem. Let us take few examples.

4-queens problem : We are given a chess board of size 4 x 4. Now the challenge is to place 4 queens on this board such that no queen attacks the other queens. Queen can attack along horizontal, vertical and diagonals.

Black-Box model 1 : Let us define state as some unique combination of 4 queens on the chessboard. So, our input will be any random combination of the queens i.e. any random state. And output will be any one of the states where the queens don't attack each other.

Black-Box model 2: Let us define our state differently this time. A state will now constitute of two things. First, the chessboard (which can constitute of 4 or lesser number of queens on it). Lets call it node. And secondly, the directions in which we may travel to other nodes. We can call them as directed edges. Thus, we actually give a graph as input. And the output is the path that starts from starting node to the resulting node. Starting node can be the empty chessboard and ending node is the chessboard with 4 queens, not attacking any one.

15 puzzle : This is a very famous puzzle, that most of us would have played in our childhood, or are playing now on mobiles. Here, again, we can model it in two ways.

Black-Box model 1 : Input is defined as all different permutations of blocks that are possible. And the output is just one. And that is shown in the figure below.

Black-Box model 2: Input is a graph this time. Here, nodes are the different permutations of blocks. And outward edges are at most 4 from each node. The output in this case is, like the previous example, a path connecting starting and the ending node. We can see the ending node in above figure and we can have any random node as our starting node.

Concluding the Search

As we can see in the above examples, we did a very simple thing. First, we defined a state. Then, we converted the whole problem into searching our desired state from a set of states. AI people believe that all the problems of the world can be reformulated into search problem. So what they do is the following. They put all their time and energy in finding the best way to search. Basically, we need to search in the least time using least amount of memory.

In this search, we have got an amazing algorithm named A*. It was discovered way back in 1960s but is relevant even today. Such is the power of search algorithms.