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

[Vincent Diepeveen <diep@xxxxxxxxx>]

How about profiling?

I get a bit less NPS as that, but i'm also doing
influence function incrementally, which takes all
the system time.

At 04:19 PM 1/2/01 -0500, you wrote:
>
>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
>
>
>