Re: Bitmaps vs Lists

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

At 04:03 PM 3/28/99 +0300, Antti Huima wrote:
>On Sat, 27 Mar 1999, David Fotland wrote:
>
>> Many Faces of Go:
>> 
>> language: Ansi C
>> compiler: MSVC++ 6.0
>> OS: windows 98
>> CPU: Pentium II 450 Mhz
>> 
>> Doing and undoing moves for tactical search:
>> 
>> 40 us.
>> 

...

>> string sizes
>
>(Number of stones in a string?) We don't update this information
>(explicitly; every group data structure contains a bitmask of the stones
>in the group).

Yes.  The number of stones in a string.  This is used in tactical
move generation, which takes much more time than the update/remove pair.
Better to try to capture a bigger enemy group, and move sorting is based
on the number of new liberties gained, so when capturing, I need to know
the size of the group.

>
>> liberty counts per string
>
>Not explicitly updated, see below.

This is used a lot.  If I didn't record this count, and I had to recalculate
it every time, the program would be much slower.  I count 300 references to
this data in the tactical move generator, and 600 references in the whole
program.

>
>> lists of liberty points per string
>
>We do that.
>
>> lists of enemy neighbor string numbers, per string
>
>No.

This is also used alot in move generation, so it is faster to keep
an incremental list than to discover it again each time.  I count
45 references to this data in the move generator.

>
>> ko point
>
>Yes.
>
>> list of captured string numbers
>
>(When capturing?) Yes and no. Yes in the sense that the captured groups
>must be put to the undo data structure so that they can be later added
>back. No in the sense that the function that adds a stone to the board
>does not return the pointers to the captured group structures.

This data is just kept for the undo later.  It's not used for any other
purpose.

>
>> number of adjacent points of each color and empty at each point
>
>Not explicitly, although calculating these from the bitmask representation
>is very easy.

But still takes time.  I find that I use these a lot.  I count 250 references
to the number of adjacent empty points and 150 references to the number
of adjacent points of a particular color in the tactical move generator.
Incrementally changing it once is much, much faster than recalculating it
each time.

>
>> list of adjacent empty points at each point
>
>Also.
>
>> lists of adjacent string numbers, by color, at each point
>
>If I understand correctly, such lists have at most 4 elements. I can't see
>why it is useful to keep an explicit list instead of just checking the
>four group data pointers around the given point. Anyway, no, I think...

For speed.  90 references to this data in the move generators.  I can quickly
tell if an empty point with two stones adjacent of the same color, has two
groups
or one group for example.

I use a 19x19 board representation, so checking the 2 or 3 or 4 adjacent
points
has a little bit of overhead.  If I had to start over I would use a 21x21
board
to make this faster, but it's too late now to rewrite all that code :(

David