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. :) > >Cheers, >Tom 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... -Dan.
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.