Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Generating attack tables: Is this code good?

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.