Author: Anthony Cozzie
Date: 04:42:52 12/01/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 I experimented with some incrementally updated attack tables - I gave them up because they were too slow. They took about 1000 ns to update per node on my Athlon XP 1.5 [although this depends greatly on cache misses]. If you want, I'll send you the code. anthony
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.