wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Go
        
(Message started by: temporary on Jan 24^th, 2008, 9:24pm)

Title: Go
Post by temporary on Jan 24^th, 2008, 9:24pm

What should komi be set to for double optimal play to end in a tie? Is it optimal to go first or second? Provide evidence. Thishttp://en.wikipedia.org/wiki/Go_%28board_game%29
might help. I wasn't sure whether to put it in putnam(pure math) or hard, so feel free to move it to putnam if necessary.

Title: Re: Go
Post by rmsgrey on Jan 25^th, 2008, 1:51pm

If you want a warm-up puzzle, you could consider "solving" Chess...

Title: Re: Go
Post by ThudanBlunder on Jan 25^th, 2008, 3:39pm

on 01/25/08 at 13:51:17, rmsgrey wrote:

If you want a warm-up puzzle, you could consider "solving" Chess...

...or the much simpler Othello (Reversi).

Title: Re: Go
Post by temporary on Jan 25^th, 2008, 5:56pm

Checkers has already been solved, but only in computers. Is it possible for a human to understand the optimal move without having to memorize every possible board position? Also, Go is much simpler since pieces never move or change form in any way.

Title: Re: Go
Post by Icarus on Jan 25^th, 2008, 6:01pm

Chess has not been solved, even by computers. The best that has been accomplished is creating a computer program that can play on the same level as a grandmaster. This is a very far cry from a computer that can play a perfect game.

Title: Re: Go
Post by ThudanBlunder on Jan 25^th, 2008, 6:42pm

on 01/25/08 at 17:56:17, temporary wrote:

Also, Go is much simpler since pieces never move or change form in any way.

Nonsense, the average number of possible moves during a game of chess is about 35. For go it is much greater.

on 01/25/08 at 18:01:28, Icarus wrote:

The best that has been accomplished is creating a computer program that can play on the same level as a grandmaster.

Grandmasters' Elo (http://chessbase.com/newsdetail.asp?newsid=4326) ratings vary from 2500 to 2856, Kasparov's best mark. Most experts agree that we have now been overtaken by the top engines running on fast hardware with access to modern openings databases and 6-man endgame tablebases. An average grandmaster can now get generous odds (draw counts as win and always plays White) and still be beaten.

http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=3049

http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=2937

Title: Re: Go
Post by Icarus on Jan 25^th, 2008, 7:10pm

I notice now that temporary said "checkers", not "chess". I don't know what has been done with checkers. But even so, I believe Go is more complex, despite its simpler rules. The table for Go is much bigger than it is for checkers.

In any case, the article to which temporary linked includes the line:

Quote:

While the strongest computer chess software has defeated top players (Deep Blue beat the world champion in 1997), the best Go programs only manage to reach an average amateur level.

This seems a pretty clear indication that Go is a very difficult challenge for game theory.

Title: Re: Go
Post by Eigenray on Jan 25^th, 2008, 8:25pm

Checkers has been [link=http://www.cs.ualberta.ca/~chinook/]solved[/link] in the sense that the program will never lose (as either player) playing from the starting position, but it doesn't know the optimal move for an arbitrary position.

Title: Re: Go
Post by temporary on Jan 25^th, 2008, 8:28pm

Why is it that humans can program computers for optimal play, but they themselves cannot obtain it?

Title: Re: Go
Post by Icarus on Jan 25^th, 2008, 8:39pm

Same reason humans can program computers to calculate billions of digits of http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/pi.gif, but have only calculated a few hundred by hand. And essentially the same reason we can build planes to fly all over the world, but can't seem to get anywhere at all by flapping our arms.