Author: Roberto Waldteufel
Date: 15:10:17 10/06/98
Go up one level in this thread
On October 06, 1998 at 14:27:17, Robert Hyatt wrote: >On October 06, 1998 at 13:41:15, Roberto Waldteufel wrote: > >> >>On October 06, 1998 at 13:06:32, Robert Hyatt wrote: >> >>>On October 06, 1998 at 11:55:01, Roberto Waldteufel wrote: >>> >>>> >>>>On October 06, 1998 at 09:50:07, Frank Schneider wrote: >>>> >>>>>Hi John, >>>>> >>>>>On October 05, 1998 at 16:49:07, John Coffey wrote: >>>>> >>>>>>Like most chess programs, I have a data structure that represents the current >>>>>>state of the board. Some programs have bitboards, but instead I use information >>>>>>for each square. My data structure could easily grow into 300 to 500 bytes. >>>>>> >>>>>>I am just now starting to write my search routines. If I am in my routine >>>>>>"SearchForWhite()" and it tries a move and then calls "SearchForBlack()" (These >>>>>>names are hypothetical at this point) then it needs to pass the current state >>>>>>of the board to "SearchForBlack()." >>>>>> >>>>>>Question: >>>>>> >>>>>>Is it more efficient to .... >>>>>> >>>>>>1. Only have one copy of the current state, and have "SearchForBlack()" >>>>>>restore the board back to its previous state before returning to >>>>>>"SearchforWhite()"? >>>>>> >>>>>>or >>>>>> >>>>>>2. "SearchForWhite" passes the whole data structure on the stack as a copy of >>>>>>the original so that "SearchForBlack()" doesn't have to restore the board? >>>>>> >>>>>>John Coffey >>>>>Gromit uses your method 2. It currently searches about 20K nps on K6/200 and >>>>>the copying of the datastructures (about 1KB per move) takes 10-15% of total >>>>>cpu-time. It may take more if you take into account the cache-effects. >>>>> >>>>>Just to give you an idea how expensive it roughly is. >>>>> >>>>>Frank >>>> >>>>Hi Frank, >>>> >>>>Have you tried both methods for comparison and chosen method 2, or have you not >>>>tried method 1? I use method 1 and always have - I just assumed without testing >>>>that passing the whole board data structure on the stack would be too expensive. >>>>Maybe I should have tested this out. Method 2 is cetainly easier to program >>>>because you never need to unmake any moves. The question really is whether it is >>>>quicker to unmake moves or copy data. >>>> >>>>In Rabbit I avoid a lot of the overhead involved in move retraction by a trick I >>>>use in my move generation. Whenever two successive moves have the same >>>>from-square, I don't retract the move, but just move the piece from the old >>>>to-square to the new to-square. Also, if two successive moves share the same >>>>to-square, then there is no need to recalculate attack maps of sliding pieces >>>>through the to-square between the moves. >>>> >>>>Best wishes, >>>>Roberto >>> >>> >>> >>>Or, you can use "rotated bitmaps" and *never* "recalculate attack maps of >>>sliding pieces..." >>> >>>:) >> >>Hi Bob, >> >>Do you mean that you calculate your attack maps "on the fly" rather than >>incrementally update them? I incrementally update my attack maps, so that my >>code for making and unmaking moves (mostly in assembler) has to extend sliding >>attacks through newly vacated squares and truncate them through newly occupied >>squares, but I think my code does this quite efficiently. Maybe it is better to >>avoid this and calculate attack maps for sliding pieces on the fly, but I would >>have thought that would be more expensive, since the same attack maps then have >>to be recalculated many times. >> >>Best wishes, >>Roberto > > > >simply stated, this is correct. Think about rook moves along a rank. If >you isolate the 8 bits for the rank you are looking at generating rook moves >for, you can, before the fact, create 256 unique bitmaps that would show which >squares the rook on square X attacks, given the 256 (actually only 128 different >states since we know where the rook is) unique states of the occupied squares >on that rank. IE to generate rook moves, shift the proper rank to the right >end of a register, mask all but 8 bits, then probe into the above table to get >the bitmap for the rook on that square, based on the occupied squares on that >rank. I do this for all sliding pieces by keeping 4 unique occupied_squares >bitmaps... > >The idea came about when I started a grad seminar on computer chess in the >Fall of 1994 when work on "crafty" started... it eliminates any incremental >attack stuff at all... if you want more details, let me know. I have an >almost-completed paper for the ICCAJ written... Hi Bob, Yes I most definately am interested. I understand the principal of rotated bitboards, but I use a different method myself, based on an "extension map". Basically for every ordered pair (x,y) of squares, I have a precomputed bitboard of the "extension squares" from x to y, so that if a sliding piece on square x attacks square y, and then the occupancy status of square y changes, the affected squares are given by the bitboard extendattack(x,y), so I just xor this precomputed bitboard with the currant attack map from square x. However, I also maintain attacks to all the squares, and I have to execute a loop to update all these. I need the attack-to bitmaps for check detection and to generate my captures in the MVV/LVA order. If there is a better way, I want to know all about it! Maybe the added overhead of maintaining four bitboards instead of one is less than the saved effort of updating the attack maps (especially the attack-to maps). Perhaps you could e-mail your article to me? (RWaldteufe@aol.com) Best wishes, Roberto
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.