Re: [computer-go] Designing faster, better influence functions

[Don Dailey <drd@xxxxxxx>]

Evan,

I  have  several different  versions  of my  GO  programs  where I  am
experimenting with data structures.

One version  incrementally updates everything and maintains  a list of
strings.  I store the number of liberties, the number of stones in the
string, the color and a representative stone (it could be any stone in
the string.)   

One of the other versions was written with the goal of making the data
really small.  It's basically just an array of values, only 4 possible
states, white, black, empty, off_board.

The  real simple  version  is almost  3X  faster, when  coded to  play
exactly like the  incremental version.  All of this  depends of course
on exactly what  you need your program to do.   The simple version has
to calculate  the number of liberties (and  basically everything else)
from scratch.  Neither version makes really heavy use of liberty count
information, but if  they did, the incremental version  would start to
look  better I'm  sure.   I doubt  it  would cover  the 3X  difference
though.

The incremental version  is much more pleasant to  work and experiment
with.  It's  not that  I can't write  convienece functions to  make it
easier to  work with, but I am  much more reluctant to  try new things
when I know the program has  to work to make the calculations.  In the
incremental version  these things are basically free  since the bullet
has already been  bitten.  When I code up ideas in  the fast version I
have to constantly be thinking about how to keep the code fast.

There is  always of course  a tradeoff.  It  takes time to  maintain a
more  complex data  structure and  there are  more  tests (conditional
branching.)

I also  have a bitboard version  of the program mainly  as a curiosity
that can be compiled for any  size board.  The board is represented as
two very  large integers, one for  black and one for  white.  Each set
bit of  the large integer represents  a stone somewhere.   Of course I
have to simulate very large integers because 32 or even 64 bits is not
nearly enough  for the bigger boards.  I  mainly did this as  a way to
make myself think  about the problem a little  differently and to have
some fun.  Bit boards put you in  the mood to try things you might not
think about otherwise.   In theory you can manipulate  the whole board
in  parallel (but  in practice  it's  not really  parallel unless  you
happen to have a 512 bit computer!)

The bitboard program is actually  a little faster than the incremental
version until you get to the bigger board sizes.  Most of the code for
the program  is generated automatically by another  program.  The code
generator program builds efficient routines for bit manipulation based
on the board size I compile for and also builds most of the primitives
like the move-maker, routines to display the board, etc.

- Don



   X-Original-To: computer-go@xxxxxxxxxxxxxxxxx
   DomainKey-Signature: a=rsa-sha1; q=dns; c=nofws; s=beta; d=gmail.com;
	   h=received:message-id:date:from:reply-to:to:subject:in-reply-to:mime-version:content-type:content-transfer-encoding:references;
	   b=DGezZ1xNlKBU5gI/oH9ruhj5SkCFbAGybJSp2MYlU2NL2+9LAJyo/UcpFSIbNgBTcWB9M5uygxe3LPx+77Z6X8FCkjGyjPOIwGvc++bUspmmuS6pgOjU1j5uha3A1aQ7CAUyUO1Z1rl0wOqIja+39/AqttzLhg+YpHsdLRLulbA=
   Date: Mon, 1 Nov 2004 20:32:31 -0500
   From: Evan Daniel <evanbd@xxxxxxxxxxxxxxxxx>
   Reply-To: evand@xxxxxxxxxxxxxxxxx, computer-go <computer-go@xxxxxxxxxxxxxxxxx>
   Sender: computer-go-bounces@xxxxxxxxxxxxxxxxx
   X-Scanned-By: MIMEDefang 2.42

   On Tue, 2 Nov 2004 02:14:52 +0100, Mark Boon <tesuji@xxxxxxxxxxxxxxxxx> wrote:
   > I don't think I would want to get into using CPU-specific instructions. But
   > I must say I've sometimes thought about what could be useful to have in
   > terms of Go-specific hardware. In Tsume-Goliath I think I found that the
   > single most expensive function was getNlib(), which would retrieve the
   > number of liberties of a chain at a certain coordinate and put the
   > coordinates of those liberties in a little list, with a maximum of 'n'
   > liberties. A very simple and basic function, used in a lot of different
   > places. The total time spent in this one function was something like 20 or
   > 30%.

   Have you looked at how GNU Go deals with the problem?  The GNU Go
   board code keeps incremental updates of things like liberty counts,
   liberty locations, etc.  I don't really remember how fast it is, but I
   don't think it spends that much of the runtime on it.

   Evan Daniel
   _______________________________________________
   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/