AI – perspiration or inspiration?

Posted: 14/11/2017

Does intelligence suddenly pop into existence, like switching on a light bulb? Or is it an emergent property dependent on sheer volume of calculations?

Can perspiration result in inspiration?

As it happens, we have a good way of testing the effectiveness of brute force processing – the game of chess.
For years, chess was the holy grail of AI – the ultimate proof of human superiority. As supreme chess champion, Garry Kasparov was a natural target for AI researchers. And in 1997, the relentless advances in computer power finally enabled an upgraded Deep Blue to beat Garry Kasparov.
Luckily, I already had my own chess program.

Computer chess techniques

Computer chess programs have a position evaluation function. This is an estimate of how good a position is. This approximation is enhanced by a depth first search.
Computer chess programs look at possible moves (a 1-ply search) and possible replies to those moves (a 2-ply search) – and possible replies to those moves (a 3-ply search) – up to the search depth.
Ending the search is tricky because of the horizon problem: who gets the last word? It is tempting to make a bold capture on the last move in the search, as there is no depth left for the withering response! A quiescence search is a slimmed down search which ends at a stable position.
The possible moves at each ply give rise to a search tree – which is chess has a branching factor of around 40.
Looking at this tree, the minimax algorithm looks for the principal variation – the best moves and responses for each player.
A deeper search leads to better play, but the tree grows exponentially. Even at two ply, you are looking at 40×40=1600 positions, and a ten ply search gives around 10000000000000000 positions.
The remarkable alpha-beta algorithm gives a move with the same score as minimax, while reducing the number of positions evaluated to (if you are lucky) the square root of the original number. 10000000000000000 positions could become 100000000 positions – billions of times faster.
Alpha-beta works effectively when looking at the best moves first so sorting the moves is important. As shallow searches are so much faster than deeper ones, sequential searches at increasing depth – iterative deepening – helps in ordering moves.
It turns out the search tree is more of a thicket: transposing moves can often get you to the same position. You can lop off entire branches if you recognise a position you have been in before. Storing positions in a hash table, allowing quick access, gives a huge improvement.

Optimisations

To understand the effect of depth alone, my algorithm delivered an exhaustive search at each depth. On an early home computer, to get to an exhaustive 12 ply search, I had to invoke many algorithmic optimisations and extreme programming.
With the techniques listed above, an ultra simple evaluation function with alpha-beta windowing gave an exhaustive search with a branching factor typically around 4.
Optimised ARM machine code which tested moves in just over 1 CPU instruction each and generated moves in 5-10 CPU instructions allowed it to crunch millions of positions.
While the so-called God’s algorithm is currently unknown in most chess positions, I was now ready to see what happens when you increase exhaustive search depth.

Results

At 3 ply, the computer was easy to beat, but it was very unforgiving of simple mistakes, snaffling loose pawns or pieces off beginners at every opportunity. This was a early sign of the immense power of exhaustive search.
I could now crank up the IQ in stages – by increasing the search depth. I felt like the Time Traveller compelled to move into an unknown future.
Changing up a gear to 4 ply ruled out my simple tricks. At 5 ply it was almost as good as me. Each ply was making a noticeable difference in its ability.
6 ply beat me most of the time. In the First International Computer Games Olympiad, it repeatedly survived against better but slower programs, like James Bond at his best, through a series of implausible escapes.
With improvements to the code – and the StrongARM CPU – the program was crunching through up to 50 million moves per second, making even 12 ply easily testable, and 18 ply taking less than a second per move in the end game.
Its discipline improved my play enough to equal it at 8 ply, but above that it seemed indestructible.
And now we can see how the program got better with each extra ply: by looking deeper, an understanding was emerging. At 4 ply, it could not only follow every one of its pieces for two moves, it could look at every combination of two pieces working together (and two of the opponent’s pieces likewise). At 6 ply, it was coordinating three pieces in an attacking (or defensive) move. By twelve ply it has six pieces working together. From mere moves a plan emerges.
This ability to combine multiple ideas into a bigger concepts is key to intelligence.
So now it was time to bring in a real chess player – my father. A mathematician, the youngest (full) Professor at London University in the 20th century, he played chess internationally when a student. By his hundredth international tournament game in Switzerland, he could remember every move in every game. He used to play my school friends blindfold four at a time, and win every game.
Well, he played my program at all the plies up to 12. His comment was: they are chess moves, but it isn’t chess. He easily won all the games.

Conclusions

My program’s exhaustive search was reinventing its strategy every move. Like a child who hasn’t practised, it was sight reading at every piano lesson. It had speed but not the crucial element: experience.
AI needs the ability to compress knowledge into a simple form for use in a more sophisticated search: it needs the ability to learn.
My chess experiments gave a glimpse of an unlimited AI. Each extra ply of search gives an improvement in conceptual depth. Intelligence is not a on-off switch. Intelligence is an emergent property.
Unusually designed as it was, my chess program was good enough to beat almost everyone on Earth at chess.
And so yes: perspiration does indeed lead to inspiration.
Stephen B Streater
Founder and Director of R&D