Author: Robert Hyatt
Date: 14:00:46 09/29/99
Go up one level in this thread
On September 29, 1999 at 10:02:27, Sven Reichard wrote: > >> >>Still sounds very fast. IE you are generating all the moves, which means you >>are doing a very good job of handling sliders already... When I first tried >>this, I had a loop that went thru the 4 directions one at a time to locate the >>'blocking piece'. And required 4 calls to bsf/bsr (depending on the direction) >>to find this blocking square so that a mask could be used to cut off attacks >>beyond that point... >> > >An idea to avoid this loop: >Let us generate horizontal rook moves for simplicity. We have bitboards for each >color. Assume we have White. If we remove the black pieces from our rank, the >white pieces allow a certain set of moves, represented by an 8-bit mask. This >mask, let's call it m_own, depends only on the mask of white pieces and the >position of the rook; so these 2^8*2^3=2048 masks can be stored in a table. > >Now we just look at the black pieces; we do a similar thing to get a mask of >moves m_other; another 2^11 masks are stored for this. > >Now the following claim is easily checked: For the mask of pseudo-legal moves >m_moves we have >m_moves = m_own & m_other, >and no further cut-offs are necessary. > >We can use these masks also for vertical moves; for the bishops, we need to >distinguish every square on the board. Thus the whole table takes >rooks: 2(colors)*2^3(squares)*2^8(masks) = 2^12 = 4k >bishops: 2(colors)*2^6(squares)*2^8(masks) = 2^15 = 32k >a total of 36 kBytes, which I think is reasonable. >For cpu time, we need (for each line) two table lookups and one binary operation >to get the mask; from that we can get the move list. > >I sort of implemented it, but haven't tested it extensively yet. > >Any comments? > >Sven. that is what I do in 'rotated bitmaps' in crafty already...
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.