Author: James Robertson
Date: 13:32:38 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.
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
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.