One of my current research projects have lead me to an rather interesting side problem. The basic idea is this:

If you’re given some random data streams from an unknown physical object… can you make a good argument to say that the object works on quantum principles? Obviously, there’s always a classical explanation, given that classical computers can simulate quantum computers, albeit inefficiently. However, could you call upon Occam’s Razor and argue that the simplest explanation is quantum?

To do this, one needs first a good mathematical formulation of Occam’s Razor for classical systems. It turns out that one good candidate are what’s called epsilon machines. So, I thought I’d write a quick research note of these objects:

• Epsilon Machines: Formalizing Occam’s Razor

Now… just need to find a meaningful way of quantizing it!

When Deep Blue beat Kasporav in Chess on 1997, it was a important for artificial intelligence. Often regarded as one of the perennial tests of intelligence, here is one of the milestones that seemed to indicate that computers are capable surpassing human intellect, a sign of true artificial intelligence… or was it?

Despite its successes in the abstract world of chess, ambitious attempts of machine intelligence in other areas of life has been met with dissappointment. Even the simple task of identifying a 3D object in the everyday world proved tricky… much less a computer capable of surviving all by itself in society. Terminator, unfortunately (or fortunately) is not something that is going to happen anytime soon.

Chess is arguably a game of tactics. To win, a player simply need to compute a dozen or so moves ahead. Such tasks, while tricky for most  humans, is ideal for computers. All a processor needs to do is systematically search through every decision tree, a task that a computer does every day when you attempt to find that elusive file on your hard drive. Thus, while the achievements of Deep Blue are spectacular, it was only a little  more than a glorified search on a decision tre, a far from any semblance of actual `intelligent thought’. There was no need more human qualities, such as intuition or creativity.

So, is there actually board game, whose success depends on such qualities?

The answer could quite well be Go (alternatively referred to as Weiqi).

In comparison to Chess, a blind search of decisions trees in Go could well be futile.  A typical Chess game involves around 30 possible moves each turn, while a typical Go game will involve about 300. Escalate this by the fact that there are typically many more turns in a game of Go, and you arrive with a probability space that is inconceivably larger.  Where’s a Chess game can end in about possible ways, a game of go has possible endings. That’s orders of magnitude higher. And if we’re talking about the number of paths that a game can possibly take… well, the number skyrockets to . 

If we could fit a computer capable of beating a Human player using brute search into a single atom, we would still need a computer with the mass of universes to beat a Human player is a game of Go.

With Go being such an complex game, a capable human player is certainly doing a lot more than just brute search. There is a lot of differences between playing Go and playing Chess. Chess is a game of absolutes, you win by capturing the enemy king, what is left is simply how you get there, and the majority of the thought is pattern recognition, and the capacity to compute all the possible ways to reach favorable patterns.

In contrast, though abilities are also crucial in Go, much more is involved. Victory is not defined by a capture, but by the accumulation of territory. There are simply too many possibilities to predict the outcome of any particular skirmish, and the key to identifying good moves comes from what professionals refer to as `intuition’. While in a professional Chess game, the loss of a single pawn can mean the difference between victory and defeat, Go is game of many battles, where the analogue a dead `pawn’ still has its role to play.

The outcome of a particular battle may be unfavourable locally, but its structure can potentially be exploited for profound implications hundreds of moves down the track. This effect is impossible to determine by brute force, and the king distinguishing between armature chess covert and a professional Go player is their capacity to judge how to steer a battles by `intuition’. Indeed, recent studies demonstrate that the right hemisphere of the brain activated far more in game of Go, which suggests that Go calls upon the intuitive, in addition the the computational aspects of the brain.

It is this human quality that has elevated Go into one of the perennial positions of Chinese culture amongst the educated class throughout history, while the Chinese variant of chess was often regarded as a game for the commoners. Indeed, in ancient China, Go is regarded as one of the four qualities of a gentlemen, on par with calligraphy, art, and poetry. And thus, for many computer scientists, the construction of a computer program capable of defeating professional Go players would be one of the great milestones in artificial intelligence.

So far, however, despite two decades of dedicated research, their target is still far from the horizon.

The current top computers, running a massive networks, has made a notable mark by defeating a Human professional 9-dan with a 7 stone handicap and a 1-dan with a 6 stone handicap [link]. While this may sound impressive, a 7 stone handicap is akin to playing a game of chess with your Queen and a Rook removed. Even capable 12 year olds are able to achieve this feat. Indeed, when I had professional Go training at the age of 10 with a professional 7 Dan, the handicap given was at around the 7 stone mark, where games were won and lost on a 50/50 basis.  And what of software that run on standard PCs? Well, I (who is nowhere near professional level) can beat the downloadable GnuGO easily while giving it a 9 stone handicap.

In order to program a capable Go AI, programmers need to mimic human intuition, and that makes the pursuit of an AI for Go worthy science. The methods gleamed in the development of a capable artificial Go player could well be applied to tasks considered intractable today.

There’s a long road ahead, and meanwhile, I invite anyone to give the game of Go a try. For many, such as my housemate and fellow researcher here at NUS (who was one of the finalists in youth Chess competitions), makes Chess look remarkably 1-dimensional. And besides, the Nobel Prize winner in physics, Anderson, holds a 1-Dan in Go… so you’re in good company!

References:

1. Wikipedia on Go - Where I got facts for this article from!
2. Sensei’s Go Library - A good online resource for go
3. Hikaru no Go - A great Anime that accurately portrays the world of Go.

So we all know that the Game of Life is universal… able to process a stream of gliders and zeroes and ones. Too bad it doesn’t look nearly as impressive to the general public. But what if the Game of Life can talk? Well now it can!  Behold the glory of `Golly’ gliders. 

And you thought Lego was just for kids… The good folks at Arhus University has decided to reveal the true importance of this innocent looking toy by constructing a fully functional Turing machine using nothing but Lego pieces. The remarkable piece of engineering has firmly established that we can now stay the entire universe using Lego pieces alone. 

The silly scientists from the 1950s are certain to turn in their graves. Why didn’t they use lego blocks instead of vacuum tubes?