Cracking Go 328
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.'"
Good luck with positional evaluation (Score:5, Interesting)
Re:Exhaustive? (Score:4, Interesting)
So you can brute force a victory on a game with 10^60 possible endings? Okay, then I'll invent a game with a much bigger space to search and a bigger decision tree. Then what?
You've found a way to weed out fruitless branches, so it collapses into a problem that requires only 10^12 flops to solve? And this method isn't in use yet? Submit it to a journal, and add it to the corpus of Go algorithms.
So what's the breakthrough here?
Organizing the search space... (Score:5, Interesting)
Logical Extreme (Score:3, Interesting)
This is exactly the method that Spock would utilize while playing 3-D Chess, [speculist.com] 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.
Re:Not Any Time Soon (Score:3, Interesting)
Re:why check everything (Score:3, Interesting)
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.
Re:Exhaustive? (Score:4, Interesting)
...and is just awfully boring. The whole chess/go playing thing, as far as I am concerned, is a mean to get new intelligent solutions to decision making/inference/... problems.
A not so successful program that would actually incorporate traditional strategic concepts [wikipedia.org] would be an interesting solution. For example, if a program would actually be able to handle a concept like aji [wikipedia.org], roughly (latent) potential - now, that would be elegant, that would be interesting.
More like an RTS (Score:2, Interesting)
Here we go again... (Score:2, Interesting)
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!
no, we won't do it by brute force (Score:3, Interesting)
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 [wikipedia.org]
Re:Not Any Time Soon (Score:5, Interesting)
As a go developer (Score:3, Interesting)
Re:Here we go again... (Score:3, Interesting)
I agree... no time soon.. (Score:5, Interesting)
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
Re:Not Any Time Soon (Score:5, Interesting)
Game complexity (Score:5, Interesting)
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" [wikipedia.org].
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.
Re:Read an article to this effect.... (Score:5, 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*
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.
Re:I don't care how good it is (Score:3, Interesting)
A: All their liberties were removed.
Or the more serious corollary:
When all your liberties have been removed, only your life remains to be taken.
Or perhaps:
That is not dead which can eternal lie. And with strange aeons even dead stones become useful.
Go is like some heavy political commentary, with life lessons thrown in.
Re:Game complexity (Score:4, Interesting)
This argument is intuitively appealing, and imho it has a lot to say for it. However, it has one major shortcoming:
Define the game of 3-go to be playing 3 consecutive games of go; the winner of the 3-go match is the winner of the majority of the go games. If player A is 1 level better than player B at go, they will be more than one level better at 3-go, since their winning probability is up to 74% instead of 67%. So, by this definition 3-go is noticeably more complex than go. However, I can think of no meaningful way in which this is actually true.
Also, if you count steps from a human player who knows the rules and has played a couple games to a human expert, you get 40-50 ranks. But that human player is easily 30 ranks about the true "random but no suicides" computer player. It doesn't take much work to build a computer program 20 ranks stronger than the random player, but that is still a truly *awful* program.
In the early days of go programming, a very simple algorithm was defined. This is from memory, so it's probably wrong, but it went something like this. If you can capture an opponent's stone, capture a group chosen at random from the largest capturable groups. Failing this, if you have a group in atari that you can rescue from atari, rescue the largest such group. Failing this, if an opponent has a group with less than 4 liberties, play one of its liberties. Failing this, play a random legal move. This turned out to be remarkably potent against early programs, and will absolutely destroy a random player -- yet still lose to even the weakest of human players.
Re:yay! (Score:3, Interesting)
True, but the richness of Go comes from the interplay of the moves permitted by an extremely SIMPLE set of moves. There are exactly 2 major rules and one minor rule in Go:
1. you take turns placing pieces.
2. pieces or groups of pieces "surrounded" by other pieces are captured.
3. the board state cannot be repeated in two successive moves.
From this simple specification emerges an amazingly beautiful game. There are particular structures and patterns which emerge with concrete properties, advantages and disadvantages. Watching interplay between these structures as a game evolves is like watching a dance.
Now, this is all true for chess as well, but the ruleset for chess obfuscates it and hides it. Go takes the idea of a strategy game and strips it down to the barest essentials. That's what makes it so amazing for me. The sheer purity of it, the intuitiveness of the rules, and the depth of play that emerges from that.
I'm an Indian. Chess is what I grew up playing. I love chess. I played it very frequently as a child and into my teens (and stopped playing after I got busy with school and also found it hard to find opponents in high school). I've spent hundreds of dollars on chess sets carved from ebony and sandalwood.
All that said, Go blew me away when I learned it. I suck at the game, but every play is intense. At the end of every game I feel like I've participated in something majestic. More so than I ever felt with chess. Go is certainly a richer experience than chess.
True, and another observation... (Score:3, Interesting)
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.)
Re:Exhaustive? (Score:2, Interesting)
A: AI's greatest disappointment is the failure to come up with a general theory of intelligence, or anything like a general theory of intelligence. In 1970, if you had asked what's the general theory of intelligence, you would have gotten answers like, ``It's all means-ends analysis,'' or ``It's all theorem proving,'' but there are very few people nowadays who say it's all anything. There's just no answer to that question. I don't see anything on the horizon that will provide that kind of theory in the future.
(c.f. [acm.org])
Which is why brute force is popular.
CC.
P.S.: good.luck@conference.edu