Author: Robert Hyatt
Date: 13:49:58 10/06/98
Go up one level in this thread
On October 06, 1998 at 16:32:38, James Robertson wrote: >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. > >No; one 64 bit value can hold bits for one type of piece or pieces, say white >knights, or black queens/rooks. > >> >>In the case of 8 bits on a particular rank: We can mask off those 8 bits >>(files seem more complicated) > >files and diagonals are done by rotating the board 90, 45, -45 degress. > >>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. But then >>for each square we can a tables of 256 entries, each containing a single >>bit mask of 64 bits.. > >Correct...... > >>We could have two sets of >>tables, > >Here you get off. We need 4 sets of tables. Don't think about bitmaps as "rook" >or "queen" moves. Think of them as ranks, files, 2 diagonals. We combine these >to make moves; I.e. a rook is a combination of rank and file; Bishop is >diagonal1 and diagonal2; Queens are all four. >The arrays look like this: > >UINT64 rank[64][256]; >UINT64 file[64][256]; >UINT64 diag1[64][256]; >UINT64 diag2[64][256]; > >To find moves for a certain rank, follow these steps: > >Extract a 8-bit number with a representation of the rank we want. Say it looks >like this example: If the Rook we are trying to find moves for is on bit 4... > >bit# 01234567 > 10101100 > >10110100 = 180 in decimal, so we go to look up the 64-bit bitmap >in rank[4][180]. (4 is the square with the piece we are interested in) > >rank[4][180] = 11001011 > 11111111 > 11111111 > 11111111 > 11111111 > 11111111 > 11111111 > 11111111 >, with 0's meaning legal moves, and 1's not legal. >Right now, we can still capture friendly pieces, so bitwise-or it with a bitmap >of friendly pieces. If bit 2, say, is a friendly piece, then bit 2 becomes a 1. >Bitwise-and this bitmap with a bitmap to find the rank moves. Finally, >bitwise-invert it. Our final rook bitmap may then look something like this: > >00010100 >00001000 >00001000 >00001000 >00001000 >00000000 >00000000 >00000000 > >Send this into a function which turns all set (1) bits into a move list! This is >where a knowledge of assembler can come in handy. > >>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? > >A lot of operations, but the increase in speed is tremendous. It also then >becomes a piece of cake to make attacks, detect check, mobility, etc. For a MUCH >MUCH better explanation, ask Mr. Hyatt. He is really good at this kind of thing! > >> >>John Coffey > > >Hope I helped.... > >James actually you did quite well. give yourself two pats on the back. :)
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.