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

[Don Dailey <drd@xxxxxxx>]

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

- 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

      _________________________________________________________________
      Is your PC infected? Get a FREE online computer virus scan from McAfee® 
      Security. http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963

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

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