Beefy Boxes and Bandwidth Generously Provided by pair Networks
Pathologically Eclectic Rubbish Lister
 
PerlMonks  

AI and GO

by gryng (Hermit)
on Jul 24, 2000 at 07:04 UTC ( #24030=perlmeditation: print w/ replies, xml ) Need Help??

Hi guys,

I'm not sure where to post this, as it's not a request for your vastly infinite wisdom, and it's not directly related to the site. However it is written in perl, and I'd like to find a place to discuss it here.

What I have is some perl code that runs a GO server, as well as a sample client that plays GO, also written in perl. (GO is a very old/popular asian board game that is harder/better than chess :) -- check out games.yahoo.com for an online java client). Additionally I have some perl code that I am using to develop an intellegent GO player.

The point behind all of this is, that I'd like to use the GO server as a tool for programmers to develop their skills in AI. It would allow two programmers to pit their best AI program against one another, in order to see who is the better wizard. Or rather, I should say, to allow you to learn which techniques of programming and AI work better, and allow you to grow and learn as a programmer by seeing how you fair against other programmers in an resonably fair contest (some of us do have faster computers than others ;) ).

Anyway, I don't want to go into dreaded detail here, since I'm not sure where I should truely start this thread. Also, my code is only about 90% clean right now, so I still have a few more things to tidy up before I give it out :) .

Hopefully there will be a few people interested in this. The important thing to remember here is that you aren't expected to be an AI or perl expert to participate -- it's supposed to be a learning experience.

Ciao,
Gryn

p.s. Oh since it's networked, AI clients could be written in some language besides perl, but I can't see why you would want to :) .

Comment on AI and GO
RE: AI and GO
by perlmonkey (Hermit) on Jul 24, 2000 at 07:36 UTC
    Well, I dont know GO or any real AI theory, but it sounds fun. Is GO difficult to learn?
    Just last night I was thinking how I would like to see some AI in perl since it is such a natural and flexible language.
    What do you have in mind? Are you planning to post sample code?
      Go is an old chinese game played on a 19x19 lined board with 181 black and 180 white stones. The object is to gain as much territory as possible. It has only a few simple rules.
      You can download the GNU go here. It is written in C and not considered very strong (about 16 kyu).
      Anything else you want to know about Go you will find here.

      /brother t0mas
RE: AI and GO
by PipTigger (Friar) on Jul 24, 2000 at 14:40 UTC
    I've never played GO but I would really love to try to write an AI opponent in Perl. I hope I'll have time once you're ready. It sounds like it would be quite a fine lerning experience and real fun too. Maybe I'll get a GO board for my coffee table to befriend my lonely chess board. Nobody plays me anymore. =( TTFN.

    -PipTigger

    p.s. Kibagami Genjuro is the Man!
RE: AI and GO
by gaggio (Friar) on Jul 24, 2000 at 19:27 UTC
    This is an excellent idea.

    I would suggest that you would write an article about your system in the Tutorials section, since you will have to give us a little more insight about the details of the Perl opponents we will create, and also because it could be a real introduction to writing an AI engine for people who don't know anything about something like this.

    This is a terrific idea. I like it a lot!
RE: AI and GO
by grackle (Acolyte) on Jul 25, 2000 at 10:18 UTC
    This is a great idea! Defeating a computer is more a matter of exploiting the program's quirks than playing well, so human go players generally avoid playing against computers. An all-ai go server will provide a place for ai's to find an opponent of any strength the same way human players do, by logging on and asking for a game. Competing with other ai's is bound to be less frustrating -- and more fun -- than pursuing the "human standard."

    The Ing Prize was $1.5 million to be awarded to the creators of the first program to defeat a Chinese professional in an even match. Unfortunately, the original offer expired at the end of 1999. Does anyone know if the offer has been extended?

RE: AI and GO
by ase (Monk) on Jul 25, 2000 at 14:34 UTC
    as perlmonkey said: where can one see the code? I'm not a "good" GO player but like the game and would be interested in perusing what's been done. I read a paper somewhere that a GO AI is _way_ harder than a chess AI.
    just my $.02 worth,
    -ase
      To answer both your's (ase) and perlmonkey's question, I plan on sending up my GO server code by the end of this week -- once I clean it up. It will also include a very simple sample client (one that connects and then plays by sending random moves).

      I should warn grackle that right now the GO server is not setup in a chat room like connection style. (However I would like to extend it to do so, I just haven't had the time or pressing need to modify it that way). Instead you just run the server on a particular port, or named-socket (which is faster throughput, but only works on a local connection), and then two clients can connect and play one another.

      Anyway, I should be able to clean up the code soon enough, which includes some rudementary documentation on how to use the code, and what the general intent and direction is.

      Thanks everyone for your vibrant support so far :) helps the moral over here ;) (right now my AI I'm working on barely beats my random number generator :P hehe)

      Ciao,
      Gryn

RE: AI and GO
by royalanjr (Chaplain) on Jul 25, 2000 at 18:11 UTC
    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

      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

        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?

RE: AI and GO
by Macphisto (Hermit) on Jul 25, 2000 at 23:20 UTC
    This is a lot like the Roshambeau programming contest. GOod idea!

    The beatings will continue until morale raises.
      I refuse to see the similarities between GO AI's and Paper/Rock/Scissors AI's :)

      -Gryn

        I was merely commenting on the basic idea of it. I was not stating that they are the same, I was saying they are similar, and a good idea. Simmer down.

        The beatings will continue until morale raises.
GO Server Released!
by gryng (Hermit) on Jul 26, 2000 at 06:17 UTC
Re: AI and GO
by artist (Parson) on Feb 15, 2005 at 16:23 UTC
    Computer cracks Go game

    Excerpt: 11 January 2005 -- A computer program that can solve the Go game for a 5x5 playing board. Dutch researcher Erik van der Werf achieved a world first with this program. A complete Go playing board has 19x19 rows. Van der Werf investigated new computing techniques to improve the Go programs with the ultimate aim of beating the best human players.

Re: AI and GO
by artist (Parson) on Oct 06, 2005 at 05:08 UTC
    Any update?
    --Artist

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlmeditation [id://24030]
Approved by ysth
Front-paged by ysth
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (7)
As of 2014-11-27 04:53 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My preferred Perl binaries come from:














    Results (180 votes), past polls