Author: Robert Hyatt
Date: 13:35:37 10/06/98
Go up one level in this thread
On October 06, 1998 at 14:50:39, John Coffey wrote: >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... > > >Let me make sure that I understand this. I might not have all the details >correct. > >One 64 bit value can hold bits for the entire board. > >In the case of 8 bits on a particular rank: We can mask off those 8 bits >(files seem more complicated) and then bit shift them down to a value that >is between 0 and 255. Now it seems to me that we need a mask for both >being blocked by white pieces and being blocked by black pieces because the >resulting moves are different. No... first generate the list of squares the rook attacks along the file, which includes attacking a blocker of either color. Then, to get rid of capturing your own piece, just and this attack map with the complement of the bitmap that contains 1's for all of your pieces. That will cut off the bits where you would otherwise capture your own pieces, without doing anything complicated to make this happen... "bit-magic".. :) >But then >for each square we can a tables of 256 entries, each containing a single >bit mask of 64 bits.. We could have two sets of >tables, one for the rook moves blocked by white pieces and one for the rook >moves blocked by black pieces that can be captured. Then we do a bitwise-or on >the two bitmasks to get the >correct moves for the rook along that rank. We have to do something similar >for the file, and bitwise-or the result with the first mask to get all the >moves for the rook. > >Sounds like a lot of operations? yes, so we don't do it that way... we just generate all sliding moves, then eliminate any that slide on top of our own pieces, with one AND operation, and we are done... > >John Coffey
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.