Poll
Loading ...
Disclaimer
The opinions expressed herein are my own personal opinions and do not represent anyone else's view in any way, including those of my employer.
© Copyright 2009
Loading ...The opinions expressed herein are my own personal opinions and do not represent anyone else's view in any way, including those of my employer.
© Copyright 2009
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:
XHTML:
More Options ...
Categories
Tag Cloud
Blog RSS
Comments RSS
Void « Default
Life 
Earth 
Wind 
Water 
Fire Light 
Previous: 
Next: 
Comment Meta:
Last 50 Posts 
Back
10:25 am - March 11th, 2009
Hi Mile,
I used to agree with you that we would not have a strong go program until we had “real”, general-purpose AI, that go was beyond any sort of brute-force search (though I did not agree that tackling go was a good route to getting general-purpose AI).
However, today’s Monte-Carlo-based programs are orders of magnitude stronger than their immediate predecessors. They still work by brute force, just a different sort of brute force than worked for chess.
Yes, they do currently need several-stone handicaps to beat pros. But nonetheless, it’s now clear that it’s only a matter of time. Moore’s law + algorithmic improvements will without a doubt allow professional-level go-playing programs that contain no “real” AI, and do nothing to illuminate intuition or intelligence. It may still take a couple of decades, but it will happen; the clock is ticking. It’s still conceivable that real AI will get there first. But it’s no longer possible to argue that it’s necessary.
11:01 am - March 11th, 2009
Hi!
Good to have an expert in the field comment!
I reread my article, and I realized that it suggested that machined required `intuition’ to play go. What I meant to say was that they needed to be able to doing something to mimic intuition (and that is arguably possible with an sophisticated search method together with power machines).
You’re quite right, the Monte Carlo based algorithms certainly do hold a lot of promise. However, in a way, I do think that they shed light on machine intelligence from a certain perspective. Sure, they remain brute search, but a much more intelligent way to search. Should they, allow with computer power, allow them to beat a professional in go, I think they’re much more widely applicable to other optimization problems.
To me, that is good enough for machine intelligence. I really have doubts that there can be some sort of `true’ AI that cannot in the end be reduced to some sort of search principle.
Of course Monte Carlo algorithms for Go has potential limitations. I’m not an expert in the field, but if my understanding is correct, the work by sampling a massive number of moves from a lot of games. A move is rated good if it leads to good results of the most number of games? Thus a move good still appear good if it leads to victories in most games, though an specific (and possibly obvious) sequence could lead to disaster.
I still have my doubts on whether improved sampling size afforded by Moore’s law can get to a point where professional are unable to spot these sequences before Moore’s law hits the quantum limit. (But hey, there’s quantum computers by then hopefully
)
Another thing of interest is that if you increased the board size to say, 21×21. The complexity of the game increased drastically, yet it doesn’t too badly affect human go players. Can a computer program capable of beating humans on a 19×19 board, work equally well against humans are we scale the size of the board?
2:14 pm - March 11th, 2009
Hi Mile,
I agree that the Monte Carlo programs display more of what seems like human intuition than earlier go programs did. In fact they even seem to have a distinct style of play, that’s similar to the “cosmic go” favored by top pro Takemiya.
I will disagree about there being a “true AI” that cannot be reduced to a search principle, but there time will have to tell. At least, I’ll say that brains don’t seem to work that way, except when they’re forced to solve very particular kinds of formalized problems.
The math behind the Moore’s Law calculation is straightforward. Assuming expected increases in processing power, and based on what win rate a one-stone handicap corresponds to, it should take about 28 years for computers to beat the top pros on even. However, the algorithms are also improving, so it will probably be sooner than that. One benefit of the Monte Carlo approach is that it is very parallelizalbe. So throwing more processors at it, not just faster ones, also helps. But yes, it’s possible Moore’s Law will run out before then.
The idea of 21×21 go is interesting. Actually, though it might seem strange, playing on this size board *is* much, much harder for humans, at least for the best ones. My intuition (though I don’t have much to support it) is that computers would fare at least as well against pros at 21×21 as at 19×19, possibly better.
2:52 pm - March 11th, 2009
I will be interested in how the skill of Humans scale with board size. However, isn’t it true that computers are much tougher for humans more on 9×9 than 19×19? Perhaps this is due to intense human study of 19×19 games, but I personally would not be surprised that the heuristics provided by human intuition scale better with board size than brute search.
I am sure humans will find 21×21 much harder to play, however, there’s no definite measure of hardness. The only way really is to get a human to play a computer on the larger board size… I would be fascinated with the result of such experiments.
I must play a game of go against MoGo sometime!
3:39 pm - March 11th, 2009
Yes, in fact computers have already beaten pros in even 9×9 games. There, the computers are closer to being able to read out the whole game.
The problem is that for 21×21, it becomes much harder to keep in mind a high-level representation of what’s going on on the board. There are just too many possibilities. 19×19 exists for a reason; it’s the “right” size to make an interesting game for humans.
Also, for pros in particular, a lot of their go knowledge is highly specialized for 19×19.
3:53 pm - March 11th, 2009
… to follow up on that last point, I have a 3d go set that I set up every year at the US Go Congress. One year I talked a 6-dan pro into playing a game against a 6-kyu amateur. The gulf there is tremendous — I could give the 6k a 7-stone handicap, and the pro could give me about a 7-stone handicap. But in this game, the 6k won! This despite the fact that the rules were exactly the same as in ordinary go; only the particular graph played on was different. (BTW, it was a tetrahedral (diamond) lattice, not a cubic lattice, which doesn’t work very well. On a diamond lattice, internal intersections still have 4 liberties.)
The lesson is that a pro’s go knowledge is very highly specialized, and it was useless in this game.
7:22 pm - March 11th, 2009
I can certainly believe that standard Go knowledge would be quite useless on a 3d board! Of hand, I have trouble even envisions where some common go structures have their equivalents! (Would love to try it sometimes).
But I don’t have thought 21×21 makes such a drastic differences… granted I play only at a amateur 2-3 dan level so I’m hardly authoritative! It could well take away some of the edge between say a professional 9 dan and a 1 dan (due to specialist knowledge), but amateurs such as myself at least don’t consciouslessly use any specialist 19×19 knowledge (Though say, I might play say, 4×5 pr 4×4 more aften than 3×4 in beginning moves).
Of course, for a fair comparison, you would need the computer to challenge a person who spent a equal experience playing boards of two separate sizes. So perhaps a better way is to get it to play someone on 15×15, 17×17, 21×21 boards, and observing its performance against the person.
I’d like to see whether the computer performs better or worse myself! I don’t suppose the current available versions of MoGo already allow this variable board size? In any case, the modifications doesn’t sound (from a naive perspective) to difficult. (When I was a kid, I use to play on L shaped and toroidal boards for fun).
7:10 am - April 4th, 2009
[...] Hearn , an AI scholar, commenting in Mile Gu’s article on AI & WeiQi, tells how he took his 3-dimensional Go set to US Go Congress where he talked a 6-dan pro into [...]
4:02 am - March 25th, 2010
[...] Why You Should Consider Online Tutoring for Your Child | Tutoring and Tutors in Education Towards more meaningful math notation :: squareCircleZBest Education » How to Choose a Math Tutor in New YorkYusof Family’s Official Blog » Blog Archive » Getting kids to enjoy learningnumber model everyday math | LottoAssist.com Pinoy social justice : Laws that "benefit" the less fortunateWar Kids Relief | Dina’s New Year Update on the HCMFOf Go (Weiqi), intuition, and Artificial Intelligence | MileGu.com [...]
3:22 am - August 18th, 2010
I will be interested in how the skill of Humans scale with board size. However, isn’t it true that computers are much tougher for humans more on 9×9 than 19×19? Perhaps this is due to intense human study of 19×19 games, but I personally would not be surprised that the heuristics provided by human intuition scale better with board size than brute search.
However, today’s Monte-Carlo-based programs are orders of magnitude stronger than their immediate predecessors. They still work by brute force, just a different sort of brute force than worked for chess.