Slashdot Mirror
Cracking Go
prostoalex writes "IEEE Spectrum looks at current trends in artificial technology to crack the ancient Chinese game of Go, which theoretically has 10^60 potential endings. Is conquering the game via exhaustive search of all possibilities possible? 'My gut feeling is that with some optimization a machine that can search a trillion positions per second would be enough to play Go at the very highest level. It would then be cheaper to build the machine out of FPGAs (field-programmable gate arrays) instead of the much more expensive and highly unwieldy full-custom chips. That way, university students could easily take on the challenge.'"
A computer will never beat a kid possessed by the ghost of an Edo period Spirit!
Ask not what you can do for your country. Ask what your country did to you
Using an exhaustive method is silly in a realm of 10^60 possibilities. Obviously human players, with much more finite resources (computationally that is) can do a much better job. Why not spend more time and being able to analyze the board better, and mimic the decision making patterns of the masters. I realize this has already been tried, and is still being worked on, but exhaustive search just seems like a waste of time and effort. My .02
je suis parce que j'aime
My favorite game.
First time I played online I had my ass handed to me by a precocious 12 year old. Ah well, the memories.
*Alot* more complex and tactical then Chess, believe it.
See the rules at: http://www.britgo.org/intro/booklet.pdf
Play online here: http://www.pandanet.co.jp/English/
I recommend installing glGo and having a go vs. computer (on the easiest setting there is).
Enjoy, I do.
I'm not an active Go player anymore, but I used to me. And the current state of artificial Go intelligence is pretty sad. The best junior players in the world (10-13 or so, IIRC) can beat the very strongest computer Go programs, and they're literally orders of magnitude worse than the best human players.
Playing Go is more than just searching a lot of positions. The game is _very_ subtle. To even understand how a professional 9 dan player (i.e. the very highest ranked players) plays every move in a game, you really need to be at least a 7 dan or so -- anything less than that and the moves just won't make a lot of sense. I have the feeling that it will be at least a decade (but probably much longer) before computer opponents can beat professional players, and even longer than that until they can beat the very best human player.s
#include ".signature"
Let's just take the final position of a game of Go. It takes a certain level of Go knowledge merely to determine which groups are alive, which are dead, which can be taken off the board, etc. in order to determine the final score. Beginning Go players will often not be able to determine this on their own and will have to "prove" to themselves that a group really is dead. And then there are the rare cases of dual life, which beginning Go players are frequently not warned about at all. Programming this stuff is HARD. There's a reason why the scoring portion of playing a Go game online is still done interactively (each player taking turns marking dead stones)... it's because there are no algorithms as of yet that can do it accurately enough. With this in mind, I have no idea why they would believe that searching huge numbers of positions would be helpful when computers are extremely hard pressed to come up with useful information about the score of the game at any given stage.
It's a running joke that in artificial intelligence that to solve a problem you almost have to know the answer already. When you consider all the possible ways to be intelligent as a search space, the process of evolution has "narrowed down" what it is "almost" like to be a human and we as individuals fine-tune the rest of the answer starting from birth. The human mind is a remarkable pattern processing machine and the day a computer can play go against a human master and win is the day we truly understand how to replicate sentience in a machine.
Shh.
The fact that we're talking about trillion move/second machines rather than even attempting to do it the way humans do it ought to tell us what the current trend in artificial intelligence is.
Basically, the current trend is the same as it was 20/30/50 years ago. This IS NO science of artificial intelligence. We don't have a freaking clue how intelligence works. I think we will someday, but it's going to take a fundamental breakthrough in theory. A "Principia Intelligentsia" (I'm probably mutilating the Latin) by some genius that throws out all the fumbling and finally Explains It All.
Sometimes it's best to just let stupid people be stupid.
I'm a reasonably strong Go player myself (4. dan) and I've studied computational complexity - my gut feeling is that computers will not beat humans at Go in my lifetime even if Moore's law continues to apply. The only possibility is that someone comes up with a completely new approach, a bit like when alpha-beta search was invented for Chess. At the moment the most interesting approach is Monte Carlo methods applied to Go which has so far lead to a gain of at least two stones strength for the current programs. The strongest Monte Carlo based program is currently MoGo by Sylvain Gelly et al. which you can find more information about at http://www.lri.fr/~gelly/MoGo.htm.
The interactive way to Go -- http://www.playgo.to/iwtg/en/
I have played a lot of go and am a programmer. This will not be solved anytime soon unless there is a very big breakthrough in AI.
Go is challenging to program for many reasons:
1) There is a ridiculous number of moves. As mentioned in the article.. there are 361 factorial moves as the game progresses. Many of these would never be done (a player would not move on the outer most edge of the board in the early stages). Some extra moves can happen as you kill groups and move new pieces into their positions. And of course.. both players pass well before the game is over.. so the board will never be filled up. So there are some limits on this huge number.. but whatever it turns out to be... it is crazy bigger than chess's possible moves.
2) The rule set is much less restricted. In chess... you are very restricted.. each of the 6 types of pieces have very specific rules. All except the knight is blocked by other pieces. In go.. you can move almost anywhere you want (it may not be the best idea but there are no rules about not moving to an empty spot). I say almost because you cannot actually kill you piece by placing it into a spot that would immediately kill it. These spots however are small in number to the number of spots you can move.
3) It is extremely difficult to decide the current state of the game with regards to one position being better than another. In the article he mentioned being able to shorten the move search tree by neglecting paths that led to worse positions. The earlier parts of the game are extremely difficult to decide. In fact.. there is probably no correct answer. This is probably one of this biggest issues with getting a computer to play effectively. There are probably spots that the computer with proper algorithms could deem as not so good.. but what about the 500,000 other positions that may turn out good.. may turn out bad. I think it would have a difficult choice when it has so many positions that it cannot grade as good or bad.
4) The delicate balance between whole board and small area (strategy vs. tactics). He mentions in the article that the computer could focus on a small subsection of the board at a time. This is fine and dandy when the computer can magically know which of the small subsections is vital. As a 19x19 game progresses (especially earlier in the game) there are for example 20 zones of the board that could become hot very fast. If one player takes initiative in a section.. they may only play 3-8 moves there and then jump to a completely different section of the board. These to positions (potentially) will collide.. and the way that the player built these two sections and the way they collide is very important.. this will greatly hinder the computer simply focusing on a subset on the board... that would be to focus on tactics.. and strategy and tactics are constantly balancing back and forth in the human players mind.
5) The human player makes new algorithms as they learn more about the game. One of the trickiest things about go is that there are no sets of rules that define a good move. There are "proverbs" which sometimes are philosophical about the game. Sometimes these are even contradictory. I doubt very much that people will find the golden set of algorithms that describe good play.. at least in a way that a modern computer interprets language.
In the end... I think one day we will have a computer that will be better than people at go. The only thing is.. I am very sure that it will be a very long time from now.. or after a breakthrough happens in AI. Anyone who has played the game for at least 20 games on a 19x19 will see the amazing explosion of possible moves. They will feel how sometimes there are 10 hotspots that you just wish you could move, but you only have one. They have felt what it feels like to be focused on an area of the board and suddenly, due to their opponents craftiness, jump to a whole different area of the board and suddenly.. that area becomes vital. A single move can make a relatively safe area dreadfully
No folly is more costly than the folly of intolerant idealism. - Winston Churchill
On complexity: perhaps the best definition (for matching our intuitive feeling for how complex a game is) I've come across for game complexity is this: Imagine a novice player who avoids glaringly wrong moves (e.g. sacrificing a queen for no benefit in chess) but otherwise randomly choses from the legal moves available to them. Call this a 'level 0' player. Now a player who is smart enough to beat the level zero player 2/3 of the time is a level 1 player, someone who beats a level 1 player 2/3 of the time is level 2 etc. Then the game's complexity is the level of the best human player. If I recall correctly, this gives naughts-and-crosses/tic-tac-toe a complexity of 1, chess was about 20 and go was about 40. Unfortunately, this is all from memory, I haven't found the right magic words to feed Google to get more information.)
So yes, the game-state complexity can be a very poor measure of actual complexity, but go still has a very strong claim to being the most complex common human game. (An extreme example of high game-state complexity but trivial actual complexity would be a large game of "Brussel Sprouts".
On the Diplomacy/Axis and Allies comparison. The three games being compared are very different in nature (although they are all zero-sum.)
Go is two player, complete information, deterministic (as are chess, checkers, hex, naughts-and-crosses/tic-tac-toe) Such a game can, in theory, be completely analysed.
Diplomacy is multi-player, deterministic, incomplete information because moves are simultaneous. I'm not sure if or how this could be analysed.
Axis and Allies is (effectively) two player, probabilistic. It could (theoretically) be completely analysed as a very large dynamic programming problem. From a game-theoretical point of view, it resembles Yahtzee.
Quattuor res in hoc mundo sanctae sunt: libri, liberi, libertas et liberalitas.
I like that.
Sometimes I imagine Go as the essence of life, distilled into a binary adversarial form. Of course, I snap out of it when my neighbours explain I can't just take their cars because "they had no liberties" when I double-park.
What is is all that is. Isn't that obvious?
Meanwhile, the exhaustive search is really the least interesting way you could possibly do it, and won't likely provide you with much insight on Go, or related matters. *yawn*
Exhaustive search may be boring, but it is also the only theoretically sound method. Aggressive forward pruning of game trees always has a danger factor (you might prune a move that looks bad at depth 5 but is actually a win at depth 10), and this danger is massively increased in games with large branching factors like Go. Basically you are greatly amplifying the horizon effect.
Methods such as Prob-Cut and Multi-Prob-Cut have proven useful in games with extremely high branching factors where the evaluation function has strong correlations between depths (games like Amazons, which has an initial branching factor of 2176, far larger than Go's 361). However there is always risk associated with statistical pruning methods.
Really, the only theoretically sound method of forward pruning is to define a specific evaluation function and then produce proofs that certain board configurations cannot cause an increase in the evaluation. But these proofs are hard or impossible to construct and often they only apply in positions which are already clearly bad.
In my opinion, it's not that computers are terribly bad at Go. It's that humans are unusually good at it. I am regularly whomped by my own Amazons-playing program and that program can't even look to ply 2 at the opening of the game. On the other hand, I destroy most of the simpler Go programs, even though I absolutely suck at Go.
Let's say I am going to bubble-sort a list that is n items long. The most aggressive (lowest) upper bound I can put on this operation is that it will take n(n+1)/2 swaps, so it will take O(n^2) time. Now, let's say that I know that the list is 10 items long. At this point, I can estimate the number of swaps will be at most 10*11/2 = 55.
Now, 55 is O(1), because there is d*1 for some d that is larger than 55 everywhere. Therefore, a bubble-sort run specifically on a list that is 10 items long is constant time.
There is an algorithm to find the median of a list that operates with a surprisingly low time-complexity (Iirc, it's O(n), but I might be wrong) that relies on the fact that a sorting problem of fixed size runs in constant time.
No, he was going to say "what about a bewb", because bewbs are the best thing evar. But then he thought better of it.
Heheh. Bewbiez.
Rampant carbon sequestration destroyed the Dinosaurs' tropical paradise. I'm here to help repair the damage.