[computer-go] incremental liberty counts

[Łukasz Lew]

Hi,

On 8/31/06, Antoine de Maricourt <antoine.de-maricourt at m4x.org> wrote:
>
> > I propose to introduce a benchamrk for a board implementation.
> > playouts / second (pps)
> > and
> > moves / second
> >
> > To deal with different hardware let's use crazyStone benchmark as a
> > reference
> > http://remi.coulom.free.fr/CrazyStone/CrazyStone-0006-9x9.exe
> >
> > (On Celeron M 1.4Ghz (laptop) Crazy stone makes 8k pps)
> >
> > $ echo "crazy-analyst MonteCarlo benchmark 100000" | wine
> > ./CrazyStone-0006-9x9.exe
> > = 100000 simulations in 12.49 seconds.
> > 8006.41 simulations per second
> > h = 13708747238564438213
> > TotalBlackScore = -789416
> If one wants to benchmark a board implementation, one should
> also provide the relative time spent into move playing routine. Running
> a Monte Carlo simulation like this provides information about the whole
> process. Not only the board implementation.
>
> I never tried Monte-Carlo, but I used a random play benchmark when
> I was optimizing my board implementation.
>
> Currently the board can play / undo 350 moves from an initial empty
> position on a 19x19 board, at the average rate of 300 cc (clock cycles)
> per move. This value does not really depend on the processor speed.
> I started  with a Pentium 3 @ 866 MHz, then a Celeron 650 Mhz, and
> now a Celeron 1.5 GHz, and still get 300 cc per play+undo. I suspect
> that using a 64-bit architecture could yields to a 10-20 % speedup (in
> terms of cc), but that's another story...
>
> Among the 300 cc, 2/3 are spent in the play routine, and 1/3 in the undo
> routine. If I didn't care about undo, and if I removed all information
> unecessary for Monte-Carlo runs that are currently updated by my play
> routine, I could maybe speedup the play routine by 20-30 % or so.
>
> There is also a small speedup for smaller boards (9x9 for instance).
>
> Anyway, let's assume the conservative value of 175 cc per move after
> removing the saving of unecessary undo information, and using a smaller
> board.
>
> Assume 110 moves per game.
>
> You get for a 1.5 GHz processor:
>  - pure board: 8.6M mps / 78k pps
>  - 25 % of the time spent in playing routine : 2.1M mps / 19k pps
>  - 50 % of the time spent in playing routine : 4.3M mps / 39k pps
>  - 75 % of the time spent in playing routine : 6.4M mps / 58k pps
> ...
>

Is it written in C/C++ without asm?

> Regarding implementation:
> - I do not update liberty count
> - in order to know if a move is a capture or not, I use the pseudo
> liberty count: easy to build / drops to zero means dead stones
> - example of extra information I update are: B/W stone count on
> board, whole B/W/empty bitmap representation, small surrounding
> bitmap (8-bit, depth 2) to represent 8-neighbourhood status around
> every point.

How do You share the liberties of a whole group?

>
> If I had to reimplement a board for fast play, without undo, and
> without extra information I would very seriously consider a bitmap
> representation (especially for a 9x9 specialized version)

What would You gain if You use pseudo-liberites anyway?

Łukasz

>
> I use bitmaps in other parts of my code for point list representation
> and this is very efficient (initialy I used a linked list structure,
> and found out that bitmaps were more efficient when using sets of more
> than 3 or 4 points).
>
> Antoine.
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/
>