Introduction

The goal of science and technology has always been to understand our surroundings which consequently made our pursuit of knowledge easier. With the advent of Artificial Intelligence (henceforth referred to as AI), computational systems have been exhibiting increased learning capabilities. Over the years, “Learned” computational systems have beaten Professional Go players. Few years back, Google’s DeepMind AlphaGo AI took on top human players at chess and poker ¹. Drawing inspiration from human cognition, the field of AI aims to replicate human capacity for reasoning, learning, problem solving, and perception. This would let the computational systems tackle complex problems.

Given that the aim of AI is to enable intelligent decision making, many search algorithms, with applications in route-optimisation, problem solving etc are often used in the field of AI. Google Maps (henceforth referred to as GMaps) is one of the most innovative and widely used services in the world today. It has been helping people to find the shortest and most convenient routes to their desired destinations. GMaps incorporate Graph data structures in order to compute the shortest path between two points. ² For this purpose, Dijikstra’s Algorithm is used to navigate the shortest path to reach a destination. Apart from this, A*(A-star) algorithm is currently being used by GMaps for its wide range of dealings with larger graphs.

In the Minesweeper game, search algorithms play an important role in finding the safe squares and avoiding mines. It is a logic-based game where the players are required to clear the grid without falling into the hidden mines. Once a mine is triggered, the game ends. Once you click on any unexplored region, the square reveals a number, which indicates the number of mines adjacent to this particular square. Search algorithms like DFS, BFS, and more advanced ones can help to identify and enhance the game’s decision-making process. For example, DFS is useful for exploring deeper into the grid. We can exploit this fact to uncover a sequence of safe squares. It might start by visiting neighbouring squares until a dead end or a clue is met, thus, backtracking to the safe position to find new paths. It is quite possible to emulate these search algorithms to help in rational decision making while increasing the chances of success at the Minesweeper game.

Alcuin’s River Crossing Problem is a 1000 years old puzzle ³ that involves a wolf, a goat, and a few cabbages. The objective is to ferry all three from one bank of the river to the other, on a boat, which only has enough room for one of the three at a time. Also, if left alone:

The Wolf would devour the Goat
The Goat shall eat the Cabbage

Thus, one has to come up with a set of steps to ensure that the aforementioned does not happen and all the three passengers reach the other side of the river safely.

Each such problem have certain frequently occurring elements associated with them:

State: A State is a configuration or a position which represents a specific condition or situation of the problem or its solution.
Start State: A state from where the problem solving/search begins.
State Space: It is the set of all possible states where one can be during solving the problem.
Goal State: The state which will be achieved if the problem is solved correctly.

Now, any State can be represented as a node of a graph with each node being a member of the State Space. Having said that, to find the Goal State, one has to traverse through the graph. This graph is termed as State Space Graph. Thus, the State Space is a graph structure. With this as the context, we define a few more elements associated with State Space Search:

Move Generator Function (MoveGen): MoveGen captures the moves that can be made in the given state. These moves help us to move from one node (or State) to another in the State Space Graph. Each move adds to the number of edges in the graph.
Goal Sate Function: The Goal State Function checks whether the current state is the Goal State.
Cost: Cost is the expense of moving from one state to another, usually expressed in numerical values linked to each edge.

A Search Algorithm navigates through the State Space using MoveGen and Goal State Functions. If we take Alcuin’s problem, then:

The Wolf, the Goat, and the Cabbage at the initial bank would give us the Start State.
Them being on the other side of the river would give the Goal State.
Each boat ride will be a MoveGen Function.

Thus, I cannot stress enough the importance of search algorithms’ applications in various domains, from optimising routes in Google Maps to solving puzzles like river crossing. Thus, it highlights the power and relevance of these computational methods. These algorithms help in enhanced decision making, optimising the solutions, achieving desired results in an efficient manner. Understanding these algorithms in depth and utilising them in practical applications will enhance the problem solving capabilities. Also, it will drive the future innovation drive in varied fields.

Footnotes

McConnachie, J. (2022). Man vs machine: How Artificial Intelligence beats us in board games. TLS. Times Literary Supplement, (6202), 23-24. Link ↩︎
Mehta, H., Kanani, P., & Lande, P. (2019). Google maps. International Journal of Computer Applications, 178(8), 41-46. Link ↩︎
Lampis, M., & Mitsou, V. (2007). Generalizing Alcuin’s River Crossing Problem. In 11th Panhellenic Conference in Informatics (pp. 617-626). Link ↩︎