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

[Don Dailey <drd@xxxxxxx>]

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/