Re: computer-go: Languages for programming go are?

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

I  did some  more  investigating,  to  determine where  my program was
spending its time.  I tried a couple of simple things to start with:

  1) To get a rough idea of how expensive my state copy is, I run
     some tests on a much smaller board.  This has the effect of
     sharply reducing the size of the state and also sharply reduces
     the size of the array that keeps up with string information.
     The reduction is approximately 6 to 1.   If copying state is
     where my program spends most of its time, I should get a
     substantial speedup.   

     . The 19x19 program does about 330,000 nodes per second in the
       opening position.

     . The 7x7 version with sharply reduced state does 420,000 in the
       same position.   

     Conclusion:  I am spending roughly 20% of my time copying state.
                  This buys me a lot,  unmake is free and the move
                  make logic is greatly simplified.  I still don't know
                  if it's a win in terms of performance,  but I do know
                  based on this test, that there is very little I could
                  hope to gain by updating in place.

  2) As a test, I removed the global evaluator.  The routine actually does
     very little, but much to my surprise the program is spending a substantial
     amount of time here.  I am able to achieve about 550,000 nodes per second
     on the 19x19 version with big state!

Everything  is relative.  If I isolate  everything to just the process
of making moves   without evaluation or  any  other factors, then  the
state copy  is fairly significant.  I  don't know  if the speedup that
results from simpler move appliction and free unmakes is worth it, but
I know that I don't really care if my program  is spending most of its
time doing other things.  It's  certainly not worth the resulting bugs
and complexities  of dealing   with  a crufty  un-maker  and  all  the
associated logic.

Of course none of this has to do with how badly my program plays!  How
fast you can make moves has little if  anything to do  with how good a
program plays.  My  stuff   is fast because    it doesn't do  much  of
anything.  I incrementally maintain  string counts, and liberty counts
for each string existing  on the board and that's  about it.   Most of
the move making decisions are made before the search even begins.


Don




   From: Don Dailey <drd@xxxxxxxxxxxxxxxxx>

      From: "Anders Kierulf" <anders@xxxxxxxxxxxxxxxxx>

      > Anyway, I'm curious about what other knowledge is incrementally updated
      > by my fellow Go programmers, and how, if you don't mind.

      SmartGo currently keeps the following information up-to-date:
      - Number of black and white stones on the board.
      - Zobrist hash code (64 bits).
      - Number of empty neighbors for each point.
      - The stones in each block (in a circular linked list).
      - The anchor (smallest stone in a block) of each stone.
      - The liberties and liberty count of each block (in an array).
      - (Optional) Bitboards for all black, white, and empty points.

      > Just for some sporty fun, my Go program on PIII-500 can execute about
      > one million random moves in under 5 seconds:
      >
      > Board::TimingTests()
      > ---> Playing Random Game
      > ***> 1000000 Turns
      > ***> 4.625 seconds.
      > ***> 216216 turns per second.

      Can you elaborate on what you mean by playing random games? To make it a
      more realistic test, it should probably include taking back the moves
      played, and also check some random liberty counts and iterate through
      liberties between moves.

      Anders Kierulf
      www.smartgo.com


   Are these numbers based on taking back moves or just making them?

   I would like to emphasize that my test  does both.  Even though taking
   back moves is free for me,  I presumably pay for this  up front with a
   slower move maker.   (Actually, is my move  maker really slower?   I'm
   not convinced of   this  because every   program  has to  provide   an
   equivalent mechanism  and extra logic for taking  back moves.)

   I get 300,000 nodes per second, on a pentium II  laptop running at 400
   MGH which includes evaluation,  which is  fast  and simple, but  by no
   means free.

   Phil's program  is  doing some  work mine does  not do,  because he is
   keeping some  bit boards  updated too.   So it's  hard to construct an
   apples to apples test unless he can  turn that stuff  off.  I have yet
   to see a good   reason to turn   my program into  a hackery  of global
   variables that are updated  in place, but I would  do this if it meant
   extra speed.  I don't know of a fair way to test this without actually
   going through this excercise, but I  need a lot of motivation, because
   I think my program is at least pretty fast, if nothing else.


   Don