|laziness, impatience, and hubris|
GO vs. Chessby gryng (Hermit)
|on Jul 25, 2000 at 18:39 UTC||Need Help??|
GO isn't so bad for humans to play, but it is indeed much harder to master GO than Chess even for a human(which can be seen by the GO Masters that reside in Asia always kicking the bootie of any US master, as US masters don't start playing when they are around 8 or so).
The reason for GO being harder for a computer is really a matter of the types of AI techniques, and types of computer processors we have available.
First, the computer processors, they are linear and parallel processors are paltry compared to biological equivalents (such as our brains). So this limits the techiniques we can use programming-wise.
Second, our computer techiniques for AI are really reudimentary. The computers that play chess consist of two basic parts, the search engine, and the state/move heuristic (please forgive me if I over-simplify here, I didn't want to type for two days). Basically the computer just asks the state/move heuristic for a rating of the current board, as well as which moves are 'probably' good. It then proceeds to search down these different moves, asking the heuristic for more moves, and then cutting off the search when it runs out of time, or finds a 'good enough' move.
The problem with this approach on GO is a matter of tree growth and heuristics inaccuracy. First, in chess you have an 8x8 board, and only 16 peices, so at worst 16 moves to consider. Most good chess programs get this number down to 2-4 on average. So we have a search tree that grows at about 3^N. That is, if we want to search 10 moves deep we have to pay 3^10 cost (59,049), looking 20 moves deep is 3^20 cost (3,486,784,401).
This isn't that bad and this is why computers can play chess. (They typically can and need to look 14 or so moves ahead to beat a grand master).
However, GO is a 19x19 board. And since you place stones you would at worst have 360 moves to consider, though with a heuristic most people bring that number down to around 30. But still this s 30^N cost, 10 moves cost 10 billion times as much as a branching factor of 3. So branching factor is one reason GO is harder.
Heurist development is also harder, with chess not only do you only have the job of bring the number 16 down to 3 (instead of 360 down to 30), but you also have the opportunity to store a large chunk of chess boards in a database and having the heuristic just look up the cost for that particular board state. (You do this by storing end board states, when there are fewer peices and thus fewer possibilities). Then for boards that are not in the state database, you can come up with a simple approximation function.
Well GO makes all of this harder. End game won't happen for many many moves, so until then you have to rely on a heuristic. But capturing peices in GO isn't as straightforward as in chess. Chess requires only one move, or a trade -- in GO, you have to surround in multiple moves, and you trade in multiple moves. The sheer size of the problem is really the hinderance -- using the same techiniques as used in chess.
Personally I think these techiniques that have gotten popular becuase of chess (mini-max and others) are just a fluke. Chess and checkers have some unique properties that make them interesting to play for humans, but easy enough for computers to applies these search techniques and play well using them. However, chess and checkers don't really map well to other real world problems, and I think AI has suffered from the reliance of these techniques that were developed for chess and checkers.
Use of heuristic techniques like automata and neural nets, and search techniques like genetic algorythms really show much more promise at these sorts of large problems. Of course, it's not to say one should abandon all use of a search, but it's reliance is really what, in my opinion, makes GO harder to program an AI for than chess.
p.s. No I'm not telling you how I'm writing mine :) at least not until I have a player that doesn't embarass me by losing to a random number generator :)