Hi All,
In computer chess there is a thing called perft (http://homepages.caverock.net.nz/~peter/perft.htm) for testing the move generation and tree traversal functionality of a chess program.
Has anyone done this in Go?
I've been working on a Go program and would like to verify that my core code is working OK. It does incremental updating of chains etc so there is a fair chance of bugs :-)
According to my program, for 9x9 Go, there are:
81 ways of playing a 1ply game,
6,480 ways of playing a 2ply game,
511,920 ways of playing a 3ply game,
I agree so far
The obvious, and wrong, number to give here is 81*80*79*78 = 39,929,760. This has to be reduced by the cases where White can't play on a 1-1 point because there are black stones on both the adjacent 1-2 points. How many such cases are there? I make it 4 (the number of corners where it can happen) * 2 (the number of orders the two black stones could have been played in) * 79 (the number of points where the first white stone could have been played) = 632. This leaves 39,929,128. Your number is eight more than this.39,929,136 ways of playing a 4ply game,
3,074,496,080 ways of playing a 5 ply game.
Oh, that is excluding passing at all nodes. Maybe its a bad idea to exclude pass moves? But I thought it would make things simpler and it meant I didn't have to think about what to do after 2 consecutive passes.
Similarly for 5x5 Go there are 2,411,088,112 ways of playing a 7ply game.
Is anyone able to verify those numbers?
cheers,
Peter McKenzie
-- Nick Wedd nick@xxxxxxxxxxxxxxxxx _______________________________________________ computer-go mailing list computer-go@xxxxxxxxxxxxxxxxx http://www.computer-go.org/mailman/listinfo/computer-go/