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.'"
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.
Ditto. As long as we're going with gut feelings, my "gut feeling" is that this is a futile endeavor.
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?
Apology to Ubuntu forum.
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.
...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 would be an interesting solution. For example, if a program would actually be able to handle a concept like aji, roughly (latent) potential - now, that would be elegant, that would be interesting.
"Hannibal's plans never work right. They just work." Amy/A-Team
In the last year the UCT algorithm has really come of its own. It's a monte-carlo variant with weighting for winning lines. On 9x9 boards the programs play at the dan level. 19x19 requires roughly 32x the computing resources for the same level of performance: current machines simply can't handle the load. But MC scales nicely with additional computing power. 32x is only 5 doublings by Moore's law: it's not unreasonable to think that within a decade computers will be giving the masters a run for their money.
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
A much better comparison: A typical star contains *only* about 10^57 atoms
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.
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.