Author: KarinsDad
Date: 09:11:41 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. I am doing something similar, but I have more operations, so I will have to look at yours carefully to see if it works better. Effectively, my equation for white to move is: xorWB = W XOR B Table = TABLE(xorWB, position of moving piece) Answer = Table XOR (Table AND W) For black to move: Answer = Table XOR (Table AND B) I then shift Answer to acquire every move. TABLE is 2040 bytes large (255 possible xorWB times 8 potential starting positions in a row/column/diagonal). So, I have one table lookup, two XORs and one AND. I did it this way since I was hoping that the fewer table lookups I use, the faster it would be. Also, the xorWB variable is stored on the stack and then re-used by the evalutation code and Table is placed in a register for speed. KarinsDad :)
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.