Hello, Search

Our first post in a series teaching you how to code AI.

Photo by Luca Bravo on Unsplash

Welcome to The Code of AI. We’ve built these pages with the goal to introduce you the art and science of artificial intelligence (AI) and machine learning (ML). Each week, we’ll post content covering theory, implementation and applications of AI and ML algorithms. We’ve grouped the posts into related AI topics (such as search, neural networks, and so on). The order of the posts is kind of important, as each piece builds upon the last. I’ll (try to!) keep the posts short (~5 minutes reading time) so that you can easily fit them into your daily schedule without needing a virtual assistant (that secretly longs to be human).

We’re going to assume you know how to code already and we’ll be working in the python programming language. If there’s plenty of interest we can port the code to another language (like C#), or — if you’re a coding ninja — you could try it yourself and submit a pull request. All the code is freely available on our Github.

Introducing Search

We’re always on the clock as coders, so let’s dive right into the first AI topic: search. This long-studied, essential component of AI can be explained through a simple example. In the figure below, imagine the green circle needs to find an efficient way to reach the red circle. Finding the shortest path between the circles is a search problem. Enter searching techniques. These are strategies that look for solutions to a problem in a search space — the abstract parameters constraining the search. Depending on the specific problem, the solutions, also called goal states, can be objects, goals, states or paths to the searched item. In our example, the goal is the square containing the red circle, and the search space is the grid comprising white and black squares.

Connecting the dots.

In this search problem, we try to find a path from the green start point to the red goal state. This is one solution, but is there a better one?

Defining the search problem

In any AI application, the first step is complete comprehension of the problem. We can do this by creating a formal definition of the various elements in our problem.

I’ve defined the elements we need in the bullet points below. In brackets you’ll find how they’re articulated in our pathfinding example.

• Search space — abstract parameters constraining the search (the grid of black and white squares, only the white squares can be searched).
• States — positions or sets of conditions that can be searched (the squares contained in the grid).
• Initial state — initial position or set of conditions (the square with the green circle).
• Goal state — a desirable outcome, or solution (the square with the red circle).
• Actions — strategies to move to different states (move the green circle to the adjacent squares, in any allowable direction).
• Goal test — criteria used to check whether a state is a solution (are we in the bottom right circle?).
• Path cost — Cost of the actions while moving in the search space (one for each move to an adjacent square).

Modelling the search space

Once we’ve defined the problem, we need to think of ways to represent the search space. This is a process known as modelling. For this example we can create a model of the search space with a tree structure representation.

If you imagine a tree growing from out of earth, we first have the trunk of the tree, then some branches and, finally, leaves. To put it a bit more abstractly, a tree structure is a collection of nodes (leaves) linked by edges (branches).

In our model, this tree can model the sequence of actions. The initial state corresponds to the root of the tree, the actions taken form the branches, and the nodes are results of those actions. You might be able to picture the tree like a set of possibilities branching out in front of you.

Let’s code a very simple representation of our search space as a tree structure, just using lists of integers. Let’s start by assigning each state (square) in our space an integer ID.

The search space with numbered IDs for each state.

Notice how some states are inaccessible (the dark squares), but they’re still numbered here. This helps us create a more general model. We could, for instance, test our algorithm on different maps.

Below you’ll find the code for representing the first row of the search space as a simple tree structure, using a one-level nested list and integers. Each element in the first level of the list represents one of the states, and they contain another list, pointing to all the states that it connects to.

Before we get ahead of ourselves

That’s all I’ll discuss for this post. We’ve examined the AI aspect called search, and discussed how it’s important to break down our problem into a problem definition, and create a data representation to model the search space.

I’ll leave you with a few tasks to mull over for next time (the dog ate my homework is a perfectly valid excuse):

1. In the example code above, why do states 4, 5 and 6 contain empty lists?
2. Can you complete the rest of the grid?
3. The tree structure covers the states and actions, but how would you represent the initial state and the goal state of our problem?

You can find the code to the above example, as well as my answers to the three questions in a full solution file in our Git repo.

Next time we’ll get down to the search nitty gritty, when we examine our first AI search algorithm called breadth-first search.

Continue your training to supreme master-level AI coding here.

And give us a follow to receive updates on our latest posts.