[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [computer-go] Testing move generation and tree traversal

From: Don Dailey <drd@xxxxxxxxxxxxxxxxx>
<snip>

You didn't report your boardsize==5  numbers except for the 7 ply case.

Here is my 5 ply data:

(Data for boarsize 5,  2.4 Pentium.  Time given in seconds.)

 1. No KO test.
 2. No pass moves
 3. Suicide illegal


DEPTH    TIME      END NODES
-----  ------   ------------
 1          0             25
 2          0            600
 3          0         13,800
 4          0        303,424
 5          4      6,368,416
 6         94    127,124,176
Thanks Don, I get the same results.

I'm a bit confused by your 6 ply result though as you say 'no KO test' where as I have implemented the ko rule in my program and get the same result as you. Without the ko rule my result is 127,124,208. My other rules are the same as yours namely no suicide and no passing. I don't have any superko rule implemented either.

Here are my results for 5x5, run on a 1Ghz PIII (program written in Java).

Depth; Nodes at Depth; Total Nodes; Time
1; 25; 25; < 1s
2; 600; 625; < 1s
3; 13,800; 14,425; < 1s
4; 303,424; 317,849; < 1s
5; 6,368,416; 6,686,265; 3.4s
6; 127,124,176; 133,810,441; 63.3s
7; 2,411,088,112; 2,544,898,553; 1233s
8; 43,219,574,768; 45,764,473,321; 23821s

Note the need for a 64 bit counter :-)

Of course the time column is not so interesting as its not a speed test. The purpose of the test is to verify correctness. Still, I'm happy enough that my thing isn't too slow although it is very bare bones at the moment (not even updating a hash key yet).

Is anyone able to verify the 7 and 8 ply numbers? In my experience (from computer chess) you never regret building this type of test into your program. It allows one to fearlessly optimise and refactor your program safe in the knowledge that if you do introduce a bug it will be picked up very quickly.

cheers,
Peter


- Don



Date: Thu, 13 Jan 2005 08:29:33 -0500
From: Don Dailey <drd@xxxxxxxxxxxxxxxxx>
CC: computer-go@xxxxxxxxxxxxxxxxx
Reply-to: drd@xxxxxxxxxxxxxxxxx
X-Spam-Score: -4.9
X-Spam-Flag: NO
X-Scanned-By: MIMEDefang 2.42


Hi Peter,

I did the test and came up with slightly different numbers. I thought
I would report this before I check to see what I did wrong.

As far as I can tell I'm not eliminating KO moves (which are not a factor
anyway in this case) but not pass moves.

depth: 1 count: 81
depth: 2 count: 6,561
depth: 3 count: 518,481
depth: 4 count: 40,447,617

You get:
81 ways of playing a 1ply game,
6,480 ways of playing a 2ply game,
511,920 ways of playing a 3ply game,
39,929,136 ways of playing a 4ply game,
3,074,496,080 ways of playing a 5 ply game.


- Don



int count_search( position *p, int depth )
{
int i;
int mv;
position tmp;
int count = 0;

if (depth == 0) return(0);

for (i=0; i<valid_point_count; i++)
{
int x;
int mv = valid_points[i];

tmp = *p;

x = make(&tmp, mv);
if ( x >= 0 )
{
count++;
count += xsearch( &tmp, depth -1 );
}
}

return(count);
}



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,
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

_________________________________________________________________
Listen to music online with the Xtra Broadband Channel http://xtra.co.nz/broadband

_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/