Re: Bitmaps vs Lists

[Antti Huima <huima@xxxxxx>]

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.
> 
> Half of this time is spent in calls to list manipulation routines.
> 
> This includes updating and taking back the following data:
> ...
> 17% of total runtime was spent making and unmaking moves during tactical
> search.
> 
> About 10 times slower, but includes a lot more information.  I presume
> that when your move generators need to know how many liberties a
> string has, or how big it is, they have to do some calculation rather
> than just looking up the value.

Thanks for your response!

Just to make things clearer, I annotated the following list:

> string numbers at each point (new string created, two strings merged or
> separated)

We do that (every intersection is associated with a pointer to a group
data structure). (group =~ string for 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).

> liberty counts per string

Not explicitly updated, see below.

> lists of liberty points per string

We do that.

> lists of enemy neighbor string numbers, per string

No.

> 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.

> number of adjacent points of each color and empty at each point

Not explicitly, although calculating these from the bitmask representation
is very easy.

> 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...

> testing for legality

Yes.

-- 
Antti Huima
SSH Communications Security Oy