Re: Bitmaps vs Lists

["P.J.Leonard" <P.J.Leonard@xxxxxxxxxx>]

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.

 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. 

 You also need to take into account the search method used. The PN
search I have
played around with tends to do a bit of work locally then it may switch
to 
a remote branch. The ratio of moves traversing the tree to evaluation of
postitions
is also important.

 I have done some bench marks on my list based board engines.
I think your speed is certainly faster by about a factor of 5 (that's a
guess) 
than my C based board manager and considerably faster the  C++ based
engine I now use,
(OO and optimisation do not live together that well). 

 However even the simple analyse functions that I have implemented
dominate the search time
( I looked at the profile information ).

 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 ?


-- 
 Cheers Paul.                                        


  Tel: +44 1225 826108
  Fax: +44 1225 826305
snail: P.J.Leonard
       Applied Electromagnetic Research Centre
       Bath University,
       BATH, UK   BA2 7AY