Re: Bitmaps vs Lists

[David Fotland <fotland@xxxxxxxxxxxxxxx>]

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:

string numbers at each point (new string created, two strings merged or
separated)
string sizes
liberty counts per string
lists of liberty points per string
lists of enemy neighbor string numbers, per string
ko point
list of captured string numbers
number of adjacent points of each color and empty at each point
list of adjacent empty points at each point
lists of adjacent string numbers, by color, at each point
testing for legality

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.

David

At 12:10 PM 3/26/99 +0200, Antti Huima wrote:
>I would be interested to know the actual relative speeds of the different
>board implementations around.
>
>Our bitmap-based board implementation has the following statistics:
>
>          language: C
>          compiler: GNU C
>  operating system: NetBSD
>               CPU: 166 MHz Pentium
>  
>Average total time for making a move, preparing if for undoing and undoing
>it (this includes capturing, returning captured strings back on the board
>when undoing, and updating the ko ban information, and checking for the
>move's legality):
>
>     9-10 microseconds
>
>I don't claim this to be a very good figure. I would like to hear
>especially of the execution speeds of well-written non-bitboard
>implementations so as to compare the relative merits of the two methods.
>
>-- 
>Antti Huima
>SSH Communications Security Oy
>
>
>