Heuristics and A.I.

So far, in our previous examples, we have looked at Machine learning with a Structured Supervised Learning approach. This means that we, the ‘Humans’ know the all answers and we the ‘Humans’ wish to teach the Machine by us, knowing the answers, we let the Machine learn by correcting it when the answers are wrong. This can be seen when we trained our Perceptron in the previous section, and we knew which Data Point was a ‘Star’ and which point was a ‘Planet’ – and when the A.I. got the answer wrong, the A.I. corrected itself until all the answers were deemed correct. At this point we could introduce new data and ask the Machine the pertinent question – is this a Star or a Planet or possibly a brown dwarf? ? So far – All is good.

However, this situation is great when we know the answers of the questions presented to the Machine but, what happens when even we, the ‘Humans’, do not know the outcome of a particular situation? For example, say, we are playing a Game of Chess or Drafts / Checkers or Poker perhaps- No one knows who will win the game – So, how can WE teach a Machine to play a game when WE ourselves do not know the outcome – until it happens? How to teach an A.I. when we the ‘Humans’ have no answers? Is problematic yes?…

This is where we need another algorithm – another strategy – a strategy that can be incorporated within Machine Learning to accentuate Machine Intelligence – this is where Game Theory and Heuristics come in…

There are forms of Game Play where the computer can be programmed with the rules of the game, the computer will play predictability. In these cases the computer can play an ideal game and be very hard to beat. These predictable rules form what is called a Logic Tree or a Decision Tree. Certain games can be broken down into predictable rules and outcomes these rules and outcomes can assist the computer in winning the game – mostly all the time. For our first example we will take a look at the game of ‘Nim’:

The game of Nim.

Nim is a simple game because each player has a equal chance to win – as long as you know the strategy enabling you to win – Nim is a game beloved of the Scammer’s and the Chancer’s – the Chancer’s will take you on a bet, one that you will not win – even though Nim is a fair game at root the Scammer’s will cheat. The game is also played in prisons with cigarettes, for cigarettes. Nim, despite being a very old game, is one of the more beloved of Games used in Game Theory and A.I. Nim is a simple game to play and fairly easy to program and has a programmable winning strategy that is extremely effective – and a real bummer to beat.

Here it is Try it out for yourself :

Now, to find out how to play the game press the ‘instructions’ button but, all you need to do here is take as many coins / tokens as you like from each row and the one who is left with the last coin is the looser – best of luck!!-

Now despite this being an ‘educational’ site I am not going to explain to you how to win at Nim – It is classed by some as a simple Subtraction Strategy. There are many, many, many explanations of how to win at Nim – they are all freely available on the internet. However, despite reading all the articles about how to win – I have never beaten the computer yet.

Now, we got an original version of Nim from the Archimedes lab org – to go to look at the Archimedes site you can Click Here . We did ask if we could use their original copy but there was no response so Bishop reprogrammed the whole thing and now it looks and runs nothing like the original – And yes, I know it looks a bit ‘blocky’ with BIG buttons but, this is to enable it to run on them ‘Smart’ phones (Yawn). And I don’t know if he put extra code in there for the computer to be able to win all the time – he won’t say…. But it looks fair to me. However if you are really keen on finding out how to win at Nim – then you can go to the original Archimedes explanation by Clicking Here.

However, the point of this article is not to look at how computers play Nim- the point is that the game Nim, as played by the computer, is NOT Artificial Intelligence – it is not Machine Learning – it is simply a pre-programmed, adaptable use of a Strategic algorithm. If Nim was a true M.L. Game then, it would have to learn, from its mistakes, how to win at Nim. This could be achieved by the ‘Strategic’ computer teaching a ‘virgin’ A.I. how to win at Nim by trial and error – the result of which would produce an artificially Intelligently produced strategy of winning.

In other words – a strategical based algorithm could teach machine learning to an A.I. machine without human intervention and these types of algorithm – although, in themselves not A.I. could help and augment the processes of Machine Learning.

Many times I have seen ‘examples’ of A.I which are not A.I. they are simply strategic, algorithmic coding.

The Mini Max Algorithm.

Here is an algorithm that is half way between strategy and Machine Learning – again it is not pure A.I. however it is a fundamental part of machine learning and game theory. It contains within itself a strategy which seeks to to maximize the minimum gain within a zero sum game. (Similar to Nim) However the MiniMax algorithm is quite complex and if you wish to read more then you are welcome to read the Wikipedia article by Clicking Here.

So, the Mini Max algorithm is not strictly A.I. but it is much more advanced than a simple algorithm ( like Nim ) and, as such, it can be seen to be an aid to A.I.- especially when the outcome of an event is not predictable nor easily taught or learned. To repeat, there are many examples of ‘Machine Intelligence’ that exist where there is no Machine Learning as such but, the computer displays a high level of ‘intelligence’ an algorithm that is very complex and can easily beat an average ‘Human’ mind.

And here we have an example:

This is the Classic game of Connect Four. It is written in P5js and uses the Mini Max algorithm with depth / heuristics. It was programmed by Kobe Liesenborgs. With a small additional component created by Bishop so that it can be played on them ‘smart’ phones.

The Mini Max algorithm is rather sophisticated and if you play the game above a few times then you will see that it doesn’t simply go for the kill of going for four tokens each time – it lays a strategic plan towards a best move and eventually catches you in a ‘pincer’ movement where by, what ever counter you block the Machines next move will win.

There is however a ( possible ) flaw in the game play above – a ‘bug’ – whenever you get a draw or a tie the game has a hissy fit and freezes – don’t know why it does it – we didn’t program it. If this happens, just press the ‘space’ key at any time and it will reset the game.

So what does the Mini Max algorithm above do: Here is a diagram we got from Wikipedia: As you can see it uses the Heuristic Logic Tree that we mentioned in the opener:

Hosted on Wikipedia

Heuristics.

In the examples above we mentioned Heuristics – now we need to examine Heuristics in a little more detail – You can always read the sublime article on Heuristics on Wikipedia by Clicking Here. But in essence Heuristics are strategies based on Trial and Error. If you watch the Gif above you will see the Logic Tree operating Logically but, in essence, each logical step down the tree is made by ‘trying’ each node of the tree in turn and ‘testing’ for the best outcome – good outcomes are given a higher numerical value than bad outcomes – it simply uses a logical sequence of trial, error and Heuristics.

When we, as Humans, play a game of Nim or perhaps even, just live our lives, we partly respond to situations by applying the knowledge we have already learned but, if the situation goes beyond that which we know, we respond ‘Heuristically’ – with ‘Gut Instinct’ – we guess, we try, we fail or hopefully, eventually, we succeed.

So it is with Machine Learning – we can look at the previous examples of our Perceptron. Where the Perceptron was taught using structured learning. However, this learning is fixed and absolute – any deviation to the input date would be problematic. In the examples above there is no Machine Learning as such – all of the strategies were pre-determined – even the Heuristics were determined. Here we have seen examples of Machine based Artificial Intelligence that is not A.I. No learning was involved yet, it appears as intelligent but, it is not:- it is simply an Heuristic algorithm.

Real Artificial Intelligences need to be based on a combination of Structured, Learned information, together with a healthy dose of Logical Heuristic guesswork – after all, this is how, we ‘Humans’ Function throughout most, if not all, of our lives.

Well this was a small but, hopefully entertaining, section on machine learning. The next bit looks at using our simple Perceptron in a multi – layered mega structured method that gets us a little more towards how the Brain works and, how machines can replicate deep thought.

Acknowledgments: