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.
Carried to its logical extreme, the tree would grow until it exhausted every legal continuation, leaving the program nothing to do but examine the end positions to see which of them were wins--that is, checkmates--and which were draws, then work backward along the branching structure to choose the line that led to the best outcome, assuming that both sides play perfectly.
This is exactly the method that Spock would utilize while playing 3-D Chess, and he would always win. However, due to his reputation for winning by always going to this logical extreme, noone ever would want to play with him.
In the end, it was deemed a highly illogical method, since it killed his ability to play the game.
He who knows best knows how little he knows. - Thomas Jefferson
... What you do is design a nice directed heuristic, say, a multi objective algorithm, and train this to compute a reasonable set of possible moves from the current state. There is no need to describe an idea end state, just a decent ongoing performance requirement. Let me just tell you that a stone displaced by a mere one position can lead to very, very sure loss. Besides heuristics are good when we have at better understanding of the mechanics. All top books and players about go talk about "harmony", "beauty", "balance"You are right about evolutionary algorithms, they could be used to solve the game. If you have the computational power to let them evolve, that is.
Go is believed by many to be the last bastion of man's mind after what Deep Blue did could be accurately described as "beat the crap out of" Kasparov. I do believe we'll have to develop an AI before the computers get good enough to beat the world champion in Go.
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.
Go is not NPC. The Japanese Rules are EXPTIME-complete. Go Endgames are PSPACE-hard, and ladders are PSPACE-complete. Under the Chinese rules it is thought that the game might be EXPSPACE-complete, but this has not yet been proven.
We also have yet to develop heuristics that even evaluate one position very well, especially during the opening or middle game. Machine learning is not a cure-all here: there's a combinatoric explosion that happens very quickly with this game which makes most of the techniques difficult to train even under the best of circumstances.
Not to say that such won't eventually be possible, but it's handwaving.
Integrate Keynote and LaTeX
...theoretically has 10^60 potential endings. Is conquering the game via exhaustive search of all possibilities possible?No.
A typical star is made up of ~10^57 hyrdogen atoms. If you could store an all the information you needed about a single ending position in a single atom, you'd need storage that had the mass of thousands of stars.
This is one of the worst articles about computer-Go I've ever read. The author seems to completely overlook the recent advances in the field which made possible huge gains by replacing n-ply reading and evaluation by monte-carlo sampling of possible end positions. This is indeed some sort of brute-force but allows to avoid the proble of evaluating a partial position, which is very hard.
:)
Still far from the best human players, but at least improving
I read an article to this effect in an AI class. Apparently the Latest Thing in solving things like Go is to take a good random sampling of just a few thousand (or tens of thousands of) possibilities in the future, and try to see what sort of move looks better, rather than trying to be exhaustive about the entire thing. I thought this was Quite Interesting. 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*
The World Wide Web is dying. Soon, we shall have only the Internet.
Not any more than solving 128-bit cipher is a constant-time problem.
Using the Japanese rules Go has been proven to be EXPTIME-complete.
Integrate Keynote and LaTeX
It is, and never will be, a question of optimisation - no matter how stochastic, fuzzy, or hardware based. Chess was only "solved" in this way - it wasn't solved the way we actually play it.
Go... is all about pattern matching.
The tigers mouth, the ladder, the bamboo joint, the turn... that's how I play.
Just as the brain makes sense of our world. We make sense of go through the patterns we see.
And no - I don't mean just throw a ANN at it:-) And yet, something stirs in the heart of AI... Something within the new approaches to statistical pattern matching...
No, it ain't solved yet!
The best fp devices top out under 10^15 operations / second. in a computer sized box.
Lets assume we can design a go-specialized device that can outperform that by another 10^20th power (ridiculous, but let's imagine).
We build 10^9th such devices (a billion!), and wire them all together to play go.
It will still take 10^16th seconds (317,097,919 years) to figure out go.
So no, it won't happen that way.
Worse, I don't think go is that simple:
http://en.wikipedia.org/wiki/Go_complexity
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
It's definitely an interesting problem. I spent years researching Chess engines eventually ditching it for Go. If you want to really be on the bleeding edge check out the computer-go mailing list. We're all there. http://computer-go.org/mailman/listinfo/computer-go
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/
Actually, if you are going for speed you do want to use an FPGA. Even though there is an inherant iteration problem associated with determining the best move for Go, you can create a very parrallel algorithm that would search many different paths at the same time. Now if you are refering to the clock speed of FPGA's, then that is not an issue either. Even though most modern dual core and quad core processors can run at 2.4+ Ghz, they are most times limited to several levels of pipelining. This limits each processor to maybe 10 billion opperations per second.
Now with FPGA's, an average clock cycle that it would be run at would be around 200 Mhz. This may seem slow at first but once you realize that at this 200 Mhz clock speed you are calculating several thousand computations you will see that you can easily crush the 10 billion opperations per second of a normal processor and reach several trillion opperations per second with a single FPGA.
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
In that context, I don't wonder that it's hard for computers to handle Go. The game has facets that are hard to quantify. It's hard for intelligent humans, too. Much like life.
Sort of makes you wonder; if a computer can figure out Go, how far from that point is real AI? Or does that question even mean anything?
What is is all that is. Isn't that obvious?
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?
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.
The article says *chess* has about 10^60 positions. Go actually has 10^170. Now all the people that have made silly arguments about how 10^60 means the game is untreatable should apologize, I suppose. Oh, and go will fall too. My bet is 20 years before a computer beats the best human players. We know more about how to write a go program than most people think.
Speaking of how hard it is to even decide if a board position is good or bad, there are three more things I can add:
1. One of the key concepts of Go is "influence". Stones literally radiate influence. Different groupings of stones, in different regions of the board, and in opposition to other groupings, radiate differing amounts of influence. And in a Heisenberg-ish kind of way (at least during the early stages of a game) pushing too strongly for influence will create less space and pushing too strongly for space will lead to less influence. The master strives for just enough more influence or space to win.
For example, fencing in areas near the edge of the board early on. You may be solidifying space -- though no guarantees if you are not very certain of what you are doing -- but you are giving your opponent great influence -- if they play well, no guarantees.
No doubt chess has a similar concept (pieces, control, development potential), but it just feels different... Not as fluid or symmetrical in so many ways.
In some sense, you are creating your pieces by placing atoms on the board. No doubt chess has a similar concept, say having a bishop and a knight work together, or two rooks, etc, but the small size of the board and the severe movement restrictions and clutter makes these chess meta-pieces much more awkward than Go.
2. Sente (initiative) is a very important part of the game. You may jump around the board making five or six moves in sente, then finally go back to patch up a weakness in gote (yielding sente). One of the difficulties of the game is deciding how urgent moves are, and thus when you should yield sente in order to address them. (Of course, the perfect solution is to figure a way to make the urgent moves in sente, but...)
Of course, in Go it is always advantageous to move if you can -- as opposed to, say, chess -- and the Go board is large-enough scale that it's easily possible to have a dozen places you'd LIKE to move but you have to rank them and decide how long you can postpone most of those moves so you retain sente. I just don't see this in chess -- though perhaps I don't know it well enough.
3. Go has an aesthetic sense. You might say that it's simply a different word for intuition and chess is no different. But I don't think so, because chess does not allow you to move pieces arbitrarily to fulfill "balance" or other aesthetic concepts. I am only an intermediate Go player, but I have been amazed at the number of high-level games I've viewed over the years and I've been able to see where a move must go, based almost entirely on an aesthetic sense that the move somehow balances or fills in something.
(The problem of course is sente -- WHEN should that move be made -- as well as playing the entire rest of the game at that same level of insight, stringing together move after move. Perhaps that's one way that Go is like golf. One of the reasons that golf is so addictive, IMO, is that any good player occasionally hits a shot that's as good as Tiger Woods. The rest of the game does not go that well, but they get a tantalizing taste of greatness for an instant and that's very addictive.)
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.
The greatest shortcoming of the human race is our apparent inability to understand the exponential function. You, the parent, the grandparent, and the summary seem to all not understand the nature of an intractable problem. "Trillions" of operations a second means nothing when the search space is that big, and no advance in computing (assuming we remain limited by Moore's law and level off in the foreseeable future) will help.
So while you, the parent, and the grandparent were trying to be funny, you were all grossly understating the difficulty. Although I like that Self->Grandchildren->Species is possibly an exponential progression - I would have been annoyed if it had been Self->Grandchildren->GreatGreatGrandchildren.
Evidently, the key to understanding recursion is to begin by understanding recursion. The rest is easy.
WOPR can solve it one digit at a time, 60 digits is no problem.
And did you exchange a walk on part in the war for a lead role in a cage? - Pink Floyd.