On 12/13/2011 07:57 PM, Peter Drake wrote:
An exercise for the combinators and combinatrices out there:
How many different 2x2 Go games are there?
An unnamed source claims 386,356,909,593, but I don't find this credible.
I found a source for this via Wikipedia:
http://en.wikipedia.org/wiki/Go_and_mathematics
Which refers to a 1999 article from rec.games.go by John Tromp:
http://groups.google.com/group/rec.games.go/browse_thread/thread/161ff6e5922e1124/c90e5b4a61ea0602?lnk=st
A game therefore involves at most 56
non-passing moves (as one more would violate superko).
Now consider how many permutations you get by re-arranging the moves. On
Tromp's solving 2x2 page he links to a program and says:
"This program solves the game of Go played on a 2x2 board using area
rules and positional superko. It demonstrates the enormous importance of
good move ordering in exhaustive alpha beta search. With the given
ordering of passing last, as many as 19397529 nodes are searched, up to
a depth of 58. But putting passes first requires the search of only 1446
nodes, to a depth of no more than 22. Minimax, which doesn't depend on
move ordering, takes over a week while searching a few trillion nodes."
http://homepages.cwi.nl/~tromp/java/go/twoxtwo.html
_______________________________________________
Computer-go mailing list
[email protected]
http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
