Re: Bitmaps vs Lists

[Antti Huima <huima@xxxxxx>]

On Fri, 26 Mar 1999, P.J.Leonard wrote:

> 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.
> 
> I am not to sure what can be gained by a comparison with taking other
> factors into account. It is my belief that the major time saving is in
> pruning the search tree. I think we will find the most time will
> (should) be spent in the evaluation of each board position for
> suggesting moves and stratergy changes.

This is true. Anyway, the board implementation itself can also be
considered to be an interesting object to be implemented efficiently.

> So a fair comparison of board speeds must take into account what
> information is maintained by the board manager and how useful this
> information is to the analysis functions.

Yes, you are right. Our board implementation maintains information for
each group including where its liberties are but then not much more.

> I would concentrate on constructing a flexible software structure that
> allows you to play about with different ideas easily. If you think
> that this can be built from a bit mapped representation then that is
> fine. My own feeling is that a string based representation is a higher
> level representation that should be part of the information maintained
> by the low level board manager. You might need to build a layer on top
> of your bit stuff to do this ?

As I mentioned, group information is maintained. However, for the ease of
doing pattern matching etc, the bit-map presentation needs to be actually
exported in a non bit-map format. This adds a little overhead, although
parts of the export procedure are also incremental.

-- 
Antti Huima
SSH Communications Security Oy