Author: Tim Foden
Date: 03:25:35 12/03/03
Go up one level in this thread
On December 01, 2003 at 06:57:13, Tord Romstad wrote:
>I am currently rewriting my engine from scratch, with the aim of making
>it cleaner, more compact, less buggy and easier to read and modify.
>Right now I am trying to find an efficient way to compute my attack tables.
>I would appreciate if some of the more skillful programmers here could
>give some comments on the below code.
>
>My tables have 16 bits per square. The lower 8 bits of each entry look
>exactly like Ed's table, while the next 6 bits contains info about direct
>attacks (i.e. non-X-ray attacks) for each piece type. The last two bits
>are currently unused. There are two such tables, indexed by the squares
>of the board (I use 256 squares):
>
>uint16 Attacks[256]; /* Attack table for the side to move */
>uint16 XAttacks[256]; /* Attack table for the other side */
>
>Some other information about my data structures:
>
>I visualise the 256-square internal representation of the board as a
>16x16 board, where the "real" board occupies the left half of the middle
>eight ranks. This allows me to use a hybrid 0x88/mailbox architecture.
>In the attack table generation code below, I don't have to worry about
>writing outside the "real" board, because attack information for these
>squares will never be used anyway.
>
>In addition to the Board[] array, I have a Phalanx-style piece list in
>the array Pieces[]. The line:
>
> for(sq=Pieces[colour].next; sq!=255; sq=Pieces[sq].next) {
>
>in my code loops through all the squares occupied by pieces of the
>given colour.
>
>The array Abilities[] contains information about how each piece can
>move. For instance, Abilities[W_BISHOP] contains DIAG_UP|DIAG_DOWN|SLIDING,
>Abilities[W_PAWN] contains DIAG_UP, while Abilities[W_KNIGHT] contains
>KNIGHT_MOVE. This array is used to determine whether an X-ray attack
>through a given piece in a given direction is possible.
>
>My code:
>
>void compute_attacks() {
> int i, colour, *p, sq, tosq, piece;
> uint16 mask, *attacks;
>
> for(p=(int *)(Attacks+64), i=0; i<8; i++, p+=8)
> *p = *(p+1) = *(p+2) = *(p+3) = 0;
> for(p=(int *)(XAttacks+64), i=0; i<8; i++, p+=8)
> *p = *(p+1) = *(p+2) = *(p+3) = 0;
>
> attacks = Attacks;
> for(i=0, colour=Colour; i<2; i++, colour^=1) {
> for(sq=Pieces[colour].next; sq!=255; sq=Pieces[sq].next) {
> for(p = &(PieceDirs[Board[sq]][0]); *p; p++) {
> piece = Board[sq]; mask = PieceMasks[piece];
> tosq = sq + *p;
> while(1) {
> attacks[tosq] |= mask; attacks[tosq]++;
> if(!(Abilities[piece] & SLIDING) || Board[tosq] == OUTSIDE
> || Board[tosq] == WK || Board[tosq] == BK) break;
> if(Board[tosq]) {
> if(PieceColour(Board[tosq]) == PieceColour(piece) &&
> (DirectionType[*p] & Abilities[Board[tosq]])) {
> /* X-ray attack. The &0xFF at the next time masks off
> * the direct attack bits. */
> mask = PieceMasks[max(piece, Board[tosq])] & 0xFF;
> piece = Board[tosq]; }
> else break; }
> tosq += *p; }}}
> attacks = XAttacks; }}
>
>From the initial position, I compute the attack tables about a million
>times per second with this code. From WAC1, the rate drops to about
>700,000 times per second. The high nodes/second count of Rebel (which
>has similar tables) makes me believe that it is possible to do this
>many times faster.
>
>Tord
Hi Tord,
I had a brief look at this code... here are my comments: :)
1. It may be slightly faster to put the "attacks[tosq] =" line after the "if"
that is below it. Try it and see.
2. I feel that it will be slightly more common, and will be quicker to test,
whether the tosq is out of bounds, than to check for sliders. I would therefore
try putting the Board[tosq] == OUTSIDE before the test for a slider.
3. The explicit tests for the Board[tosq] == WK and Board[tosq] == BK seem
strange. This will surely be handled by the slider case anyway, so should never
be true (unless for some reason you have kings as being sliding pieces).
4. Is PieceColour(piece) the same as colour? If so you can replace
PieceColour(piece) with colour.
5. DirectionType[*p] is a constant for each direction. It may be faster to look
this up once rather than many times.
6. Taking constants outside the loops is generally a good idea. It may be
better to reformulate the code so that piece and mask don't change, and use
piece2 and mask2 inside the while loop. I know it isn't quite clear how to do
this, but it may be possible. I.E. don't start the while loop at all for the
non-sliding cases.
Well, thats all for now. I hope some of it actaully helps! :)
Cheers, Tim.
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.