On Tue, 24 Jun 2008, Peter St. John wrote:
On a finite board, the game eventually becomes local; in fact "contact
plays" are common after about the first dozen moves, but they are
inescapable later. But the possibilities are horrible, the numbers are huge,
for tree-searching. The new thing is monte carlo; to consider a move, the
machine actually plays that position against itself a few hundred times
(with a trivial, not recursive, algorithm) and weighs the move by the
percentage of outcomes. It's weird, to me.
It makes sense to me. It's in some sense more like humans play. In
fact, if one can come up with any (even very simple) "local" rules to
semi-prune the tree, you can imagine an importance-sampling monte carlo
algorithm.
However, if I were going to try, it would be genetic algorithm all the
way. Don't explore trees exhaustively; too many of them. Don't sample
them (especially if you can't create a canonical weight to do importance
sampling); too many of them. Breed them. There are still too many, but
again, if one can generate ANY sort of fitness function, maybe one can
get the N^3 and exponential growth of favorable possibilities that are
like "making a decision".
Fortunately, I'm not going to try. Neural nets are much more fun. And
MIGHT be able to manage the complexity -- especially one built with a
GA...;-)
rgb
Peter
On Tue, Jun 24, 2008 at 9:22 PM, Robert G. Brown <[EMAIL PROTECTED]> wrote:
On Tue, 24 Jun 2008, Peter St. John wrote:
Programming a computer to play Go (an Asian strategy boardgame) has been
difficult; some people say it's proof that Go is better or harder than
chess, since computers can beat masters at chess but struggle at Go. (I
think that statistically a game of go is about equivalent to a two-game
match of chess; both games empty your brain quickly of course). My view is
that while go may be somewhat harder to reduce to tree-searching, the main
advantage of computer chess was an early start, e.g. von Neumann.
I thought that Go was combinatorially vastly, vastly more difficult than
chess. Both because of the extremely large number of move permutations
that make it very difficult to follow trees and because Go is a
fundamentally nonlocal game -- one can imagine a "perfect" Go strategy
in which pieces are never played close to each other as the board
gradually fills in with higher and higher still disconnected density,
culminating in the winner completely unravelling the loser or
precipitating out to win by a single small amount. Yet nobody can even
come close to playing that way -- most games start out that way for a
while and then transform into local dogfights that are STILL often
resolved by long range connections.
This article:
http://www.usgo.org/resources/downloads/CogApdx%20II-2.pdf
describes recent trends in computer Go and mentions a 32-node cluster, 8
cores per node. Apparently MPI parallelization is recent for them and they
are making good progress.
Interesting. I'll have to look. Last time I read up on this (in the
context of a conversation with you, IIRC:-) nobody could make a computer
go player that could beat even a very bad human player, where computers
back to maybe 386's have been able to play chess well enough to win at
least sometimes against weak humans (and win "often" against weak human
players by now). I suck at chess (but can still beat a lot of the
people I -- rarely -- play) and modern computers can beat me pretty
easily. I suck at Go, too -- but I can't even find a BAD go player to
run on a PC to try to get better.
rgb
Peter
The game Go: http://en.wikipedia.org/wiki/Go_%28game%29
AGA (American Go Association): http://www.usgo.org
--
Robert G. Brown Phone(cell): 1-919-280-8443
Duke University Physics Dept, Box 90305
Durham, N.C. 27708-0305
Web: http://www.phy.duke.edu/~rgb <http://www.phy.duke.edu/%7Ergb>
Book of Lilith Website:
http://www.phy.duke.edu/~rgb/Lilith/Lilith.php<http://www.phy.duke.edu/%7Ergb/Lilith/Lilith.php>
Lulu Bookstore: http://stores.lulu.com/store.php?fAcctID=877977
--
Robert G. Brown Phone(cell): 1-919-280-8443
Duke University Physics Dept, Box 90305
Durham, N.C. 27708-0305
Web: http://www.phy.duke.edu/~rgb
Book of Lilith Website: http://www.phy.duke.edu/~rgb/Lilith/Lilith.php
Lulu Bookstore: http://stores.lulu.com/store.php?fAcctID=877977
_______________________________________________
Beowulf mailing list, Beowulf@beowulf.org
To change your subscription (digest mode or unsubscribe) visit
http://www.beowulf.org/mailman/listinfo/beowulf
