Program like it’s 1970!

A little throwback to what AI used to be

Machine learning is all the rage these days! CNNs, GANs and LSTMs are what all the cool kids are doing right now. What a lot of people forget is that Artificial Intelligence != Machnine learning and that AI has been around a long time before the big Deep Learning hype in the 2010s. I want to take you back and illustrate an AI method of past days using a simple example.

Map coloring

“Map-coloring” is a famous toy problem from cartography where we want to color a map in a way that two neighbouring states always have a different color (image 1).

For illustrative purposes, we will try to color the states of Australia in the following sections (as there are only eight of them).

Interestingly, for a long time people “knew” that a minimum of four colors is required to solve this task. But there has not been a mathematical proof until the late 90s.

Constraint satisfaction problems

The map coloring problem belongs to a special class of problems that are called “Constraint satisfaction problems” or CSPs for short. These types of problems consist of three different components:

1. Variables: the placeholders we want to find values for. In our case, these are the Australian states and territories: NSW (New South Wales), Q (Queensland), V (Victoria), WA (Western Australia), SA (South Australia), NT (Northern Territory), ACT (Australian Capital Territory) and T (Tasmania)
2. Domains: these are the possible values of our variables. In this case the domains of all the variables are the same. Each state can be colored in one of the four colors red, green, blue or yellow.
3. Constraints: these constraints are not to be violated by the variables. For example the colors of Victoria and New South Wales have to be different because these are two neighboring states.

In general, there are two different strategies to solve a CSP:

1. Inference
2. Search

It is important that often CSPs can only partially be solved by inference so that search is required. In short, a CSP is solely solvable by inference if we do not have to make some kind of random guesses to find the solution. A typical example of this is the game of sudoku. We have our variables (the empty fields), domain (numbers between 1 and 9) and several constraints that cannot be violated (not the same number in a row, column or square). Here we never have to pick some numbers randomly but we can solve the whole puzzle by applying the constraints in the right order. With our map-coloring problem we are unfortunately not so lucky: to find a proper solution we inevitably have to make some guesses.

The usual way: Backtracking

The common way to solve CSPs like this is to use the backtracking algorithms. This is the algorithm implemented in Python:

We will now go through the code line by line to make sure we understand what is going in here:

As described above, our CSP consists of variables, domain values and constraints. It is important to notice that constraints are usually converted to binary constraints if possible to make thins easier. A binary constraint describes the relation between two variables. In our Python implementation they are of the form [(‘NSW’, ‘V’), (‘NSW’, ‘Q’), (‘NSW’, ‘SA’), …, (‘T’, ‘V’)].

If we have as many assignments as we have variables that means we have assigned a value to every variable and have therefore solved the problem!

We now have to pick a still unassigned variable that we want to find a value for now. How to pick this value will be discussed further down below.

After picking an unassigned variable we also have to choose an order in which we want to try out the values for this variable.

If the value we picked for our variables is consistent with our binary constraints we add this to our lists with all the assignments. And now the really cool part: we just call the backtracking function again, so this is a recursive function. We found a valid assignment to a variable so now it is time to find a value for the next variable.

It might happen, that we get a ‘None’ as the result of a recursive call. This means that the value we assigned to our variable was at this time locally consistent but it is not possible to find an overall consistent solution with this value. So we remove this value from our list of assignments. If we cannot find a single consistent solution we return None to the recursive function above. In case all recursive calls return None this means that the problem is unsolvable.

Oof, enough of that theory. Let’s see how this algorithm performs if we let it run on our map-coloring problem:

Well … our algorithm doesn’t seem to go anywhere. Spoiler: it will eventually find a solution but it takes so long that this is not shown in the gif above. Why is this? Because we still didn’t answer an important question from above: how do we choose the next variable to assign a value to? In the above image, the algorithm just chooses an unassigned value randomly. Obviously this is not the best approach. To select a variable we should select a better heuristic. We implement the Minimum-Remaining-Values heuristic or MRV -heuristic. This one is pretty self-explanatory: the next variable we choose is always the one with the least valid values remaining. This also makes sense intuitively. If for example we can only color New South Wales in red but we can still color Western Australia in red, green and blue we should color New South Wales first because if we color another state there might not be any valid color left for New South Wales anymore. So let’s try again with this heuristic:

Whoah, this works much better!

Comparing a random selection and MRV-heuristic (image 3) we can see that the latter is usually much more time-efficient.

But to be honest, coloring Australia is not so interesting as there are just 8 territories. So, just for the fun of it, let us try to color Germany, a country with twice as many states:

This also works like a charm!

The short-cut: Prolog

So, until now this whole process has been quite cumbersome: we need to write all this backtracking code (recursive functions can be tricky at times!) and even come up with a good heuristic. Isn’t there a better solution? Introducing: Prolog.

Chances are, you as an average programmer (just like me) have dealt with quite some programming languages: Java, Python, C, C#, JavaScript, you name them. All of them might be quite different but they all belong to the same class of programming languages: imperative programming. Prolog, however, belongs to the group of declarative programming languages or even more precise to the group of logical programming languages. So what’s the difference? In “normal” programming languages you specify how things should be done. In Prolog, you specify what should be done. Take a look at the example below:

Two of the most important constructs in Prolog are facts and rules . At the beginning of the program we state some facts, e.g. that Henry is male and that Mary is a parent of Michael. Further down we have some rules. For example, we state that Y is a father of X if Y is male and Y is a parent of X. Important: all variables have to start with an upper-case. Lower-case names are set constants.

When we enter the Prolog console we can ask our Prolog program some questions. We can find out who the mother of Michael is:

?- mother(michael, X).
X = mary.

or who the grandfather of Michael is:

?- grandfather(michael, X).
X = henry ;

Now let us write a program to color Australia:

This is really straight-forward! First of all, we define which states should be colored differently. Diffx is just a helper function that helps us to define if color A is different from B, then B is also different from A. In the end, we just state that all of the colors are different from each other (obviously). That’s it! 15 lines of code and we just need to state rules and facts, no algorithms required.

So let’s load this program and ask for variable assignments:

?- map_coloring(WA, NT, SA, NSW, V, Q, T, ACT).
WA = NSW, NSW = T, T = blue,
NT = V, V = ACT, ACT = red,
SA = green,
Q = yellow

Putting these values in a map looks like this:

Indeed, we get a valid solution!

Conclusion

When I usually deal with AI it has to do something with a neural net so it was quite interesting for me to have a look at what people decades ago understood under the term “Artificial Intelligence”. Especially programming with Prolog was quite unique for me. Solving CSPs and similar problems is obviously very easy. The main issue I have with this language that I am never really sure what is going on. I just state some facts and rules but never explicitly tell the program what to do. So if the task fails it is nearly impossible to trace the error and debug the problem.