Computer Chess Club Archives




Subject: Re: is the

Author: Dan Newman

Date: 11:12:08 07/20/98

Go up one level in this thread

On July 20, 1998 at 02:53:44, Tom Kerrigan wrote:

>A handful of people are using linked lists to keep track of pieces, and they
>delete (capture) a piece by setting a "dead bit" in the linked list record.
>This seems like a good idea because the amount of work required to
>remove/restore an element is basically nil.
>On the other hand, every time you want to loop through pieces, you need to check
>the dead bits, and that isn't free.
>So anyway, I reworked a copy of Stobor so it would actually remove a piece from
>the linked list when it was captured. Overall NPS increased by 4% and in no
>position did the copy run slower than the original. I use a SEE, too, so the
>pieces were inserted in order. Without this restriction, the copy would have
>been even faster.
>Any comments/questions/results from your own program are appreciated. :)

The dead bit is a good idea--but only if you aren't using linked lists.
Whenever I've used linked lists for piece lists it was for the express
purpose of reducing piece list length on-the-fly inside the search.
Otherwise, I'd probably just use an array.  Though I guess linked lists
are also useful if you need to reorder the pieces for different phases
of the game or on pawn promotion.  (Hmm.  I may have to try linked
lists with my latest...)

I'm kind of surprised at the 4% difference--though perhaps I shouldn't
be--I figured it would be break even at best.  It's always nice to get
improved performance from a change that also makes the code cleaner
and clearer.

I tend to get very strange results from attempted improvements to my
program(s).  A change which I think should improve performance will
either do nothing or will hurt.  Another change--to a piece of code
that isn't even being exercized--will give a boost or hurt performance
by a few percent.  Presumably this is due to changing alignments of
data structures, changes to the code generated by the compiler in
interaction with the cpu (instruction scheduling, branch prediction,
etc.)--phase of the moon basically.

I think that I tend to do too much tweeking at too early a stage
when doing chess programming.  One can never tell what the result
will really be once the program is more or less complete.  For
instance, I may test the move generator and measure move generations
per second on a test suite, make a change that gives a few percent
increase but which makes the code more complex.  It becomes very
hard to resist leaving that change in.  Yet, once everything else
is added, that few percent becomes virtually zero, since the move
generator might take only 5% or so.  But the increased complexity
may actually be hurting the other parts of the code...


This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.