Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic
 
PerlMonks  

RE: AI and GO

by royalanjr (Chaplain)
on Jul 25, 2000 at 18:11 UTC ( #24277=note: print w/ replies, xml ) Need Help??


in reply to AI and GO

Why would Go be tougher than chess? I have played GO a couple times but apparantly I am missing something of the game if indeed it is that much tougher than chess.

Roy Alan


Comment on RE: AI and GO
GO vs. Chess
by gryng (Hermit) on Jul 25, 2000 at 18:39 UTC
    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.

    Ciao,
    Gryn

    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 :)

      First, in chess you have an 8x8 board, and only 16 peices, so at worst 16 moves to consider.

      This is wrong. You probabably meant "16 pieces to consider moving", but for instance the first move of the game both white and black have 8+8+2+2 moves, and the number of possible moves increases until the midgame resolves itself, where it drops and then increases again as the board clears leaving strong pieces like rooks and queens and bishops a clear run of the board. (An unrestricted queen has at most 7+7+8+6 possible squares that it can move to, an unrestricted horse has 8 squares it can move to, thus if you have a king a queen and a horse on an open board you have (6)+(7+7+8+6)+(8) possible squares you could move to, a lot more than 16 :-).

      But your point does have merit. GO does represent a larger search space, but not because of the number of pieces. After all Go pieces dont move once placed.

      ---
      demerphq

        After all Go pieces dont move once placed.

        True, but it is possible for a go piece to be taken, freeing up the square for another piece to be placed there. This doesn't happen often though.

      The amount of moves possible doesn't necessary give a good indication of the difficulty of the game. Consider for instance tic-tac-toe on a billion by billion board. Far, far more moves possible than on a Go board. Any computer program that would "look at all the moves" would take too much time. Yet the game is a simple win for whoever goes first.

      I'm not at all convinced that the fact computers are "futher" in chess than in go is purely because of the number of moves to consider (and your numbers for chess are way off - in the opening, both white and black have 20 moves available, giving 400 different positions after the first move. Of course, still less than the 129960 different go positions after the first move). I get the impression more people are interested in chess than in go, and more research in (computer)chess has been done than in (computer)go. Which will also contribute in the difference.

      Personally, I don't find the discussion whether go is more difficult than chess (why is it always go players that bring this up - at any game site I go to, some go player has to come up with this - it's like Python or PHP saying of their language that it isn't Perl) interesting. I know the rules of both games. I like to play one of them, and I don't find the other interesting.

      Anyone fancy a game of Catan?

        Probably you should take in mind that this article is about difficulty to implement computer player. Not event to implement, but to make it efficient. And this task is more resource hungry for Go than for chess.

        Also heuristics for Go are less ... uniform (not sure of right the word). The concepts of liberties, claimed territories and such are more abstract than heuristics concepts in chess, or so I've heard.

        But I completely agree with you that the fact that much more effort has been put into chess software R&D than is has been done for Go software is an important point and has to be considered in comparison.

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://24277]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others making s'mores by the fire in the courtyard of the Monastery: (4)
As of 2014-10-26 01:12 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (149 votes), past polls