Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: An idea to generate rook moves without rotated BBs

Author: Alessandro Damiani

Date: 10:26:15 10/22/00

Go up one level in this thread


On October 22, 2000 at 11:26:58, Severi Salminen wrote:

>Hi!
>
>I have started again from scratch to program a chess engine, now with C. I came
>to this solution to generate rook moves without rotated bitboards:
>
>I wont show you everything :) but here is some code from my mov_gen routine. E
>holds all the pieces on board, j is the position of our Rook (0=H1 and 63=A8). F
>is an empty bitboard and D holds the horizontal squares which we can move to
>(calculated before this)
>
>
>// Aligning the file info to right corner of bitboard and clearing all other
>// bits:
>        E=(E>>(j&7))&0x0101010101010101;
>
>        for(k=0, F=0;k<8;k++)
>  	{
>	   F|=E;
>	   E>>=7;
>	}
>	F&=0xff;
>
>//After the loop F holds the file info and we can fetch the squares from
>//a pre-compiled table and OR them with the horizontal destination squares
>
>	D|=FileMoves[j>>3][F]<<(j&7);
>
>What I'd like to know if anyone has tried to compare this method with rotated
>bitboards and I'd like to know if this is a lot slower (or faster;). I _must_ do
>this loop (which can be optimized a little...) for every rook but I don't have
>to update rotated bitboards at all after I make moves. Maybe the net speed is
>quite equal and depends on move ordering and so on...Opinions?
>
>Severi

Hi Severi,

Although I already have posted my source code, here it is again. It is very easy
to understand and is added to your code in some minutes. Enjoy.

Alessandro


------------------------------------------------------------------------------------------

                           Attack Detection with Bitboards

                    by Alessandro Damiani (adamiani@econophone.ch)

                                    It is Freeware.

------------------------------------------------------------------------------------------


Needed global data:


BitBoard       AFRhorizontal[64][256],
               AFRvertical[64][256],
               AFBrightup[64][256],
               AFBrightdown[64][256];

with

AFR: AttackFromRook
AFB: AttackFromBishop


unsigned int   SlideIndexH[8],     // horizontal
               SlideIndexV[8],     // vertical
               SlideIndexRU[16],   // right up (RU)
               SlideIndexRD[16];   // right down (RD)



Incremental work:

I use the two routines RemovePiece(.) and SetPiece(.) in Make(.)/Unmake(.). Here
is the part concerning
attack detection:


void RemovePiece (Square s, Piece *p)
  int 					row, file;
  unsigned int 	a, b;

	row= s>>3; file= s & 7;

  // SlideIndex:
	SlideIndexH[row]^= a= 1<<(7-file);
	SlideIndexV[file]^= b= 1<<(7-row);
	SlideIndexRU[row+file]^= a;
	SlideIndexRD[7-row+file]^= b;
}


void SetPiece (Square s, Piece p) {
  int						row, file;
  unsigned int	a, b;

  row= s>>3; file= s & 7;

  // SlideIndex:
	SlideIndexH[row]|= a= 1<<(7-file);
	SlideIndexV[file]|= b= 1<<(7-row);
	SlideIndexRU[row+file]|= a;
	SlideIndexRD[7-row+file]|= b;
}



Macros used in the search and evaluation function:


#define AttackRank(s) (AFRhorizontal[s][SlideIndexH[s>>3]])
#define AttackFile(s) (AFRvertical[s][SlideIndexV[s&7]])
#define AttackDiagRightUp(s) (AFBrightup[s][SlideIndexRU[(s>>3)+(s&7)]])
#define AttackDiagRightDown(s) (AFBrightdown[s][SlideIndexRD[7-(s>>3)+(s&7)]])
#define AttackFromBishop(s) (AttackDiagRightUp(s)|AttackDiagRightDown(s))
#define AttackFromRook(s) (AttackRank(s)|AttackFile(s))
#define AttackFromQueen(s) (AttackFromBishop(s)|AttackFromRook(s))




The following program generates the attack tables AFRhorizontal, AFRvertical,
AFBrightup, AFBrightdown.
"SquareBoard[s]" is the bitboard with bit number s set to one. Square 0 is at
the top left corner.


#include <stdio.h>
#include "system.h"
#include "bitboard.h"


#define SHIFTRIGHT(b) (((b) & ~FILEH)>>1)
#define SHIFTLEFT(b) (((b) & ~FILEA)<<1)
#define SHIFTDOWN(b) ((b)>>8)
#define SHIFTUP(b) ((b)<<8)
#define SHIFTRIGHTDOWN(b) SHIFTDOWN(SHIFTRIGHT(b))
#define SHIFTLEFTDOWN(b) SHIFTDOWN(SHIFTLEFT(b))
#define SHIFTRIGHTUP(b) SHIFTUP(SHIFTRIGHT(b))
#define SHIFTLEFTUP(b) SHIFTUP(SHIFTLEFT(b))


BitBoard AFRhorizontal[64][256],
				 AFRvertical[64][256],
         AFBrightup[64][256],
         AFBrightdown[64][256];


BitBoard IndexToAFRhorizontal (int s, unsigned int i) {
	BitBoard      a, x;
	unsigned int  t;

	a= 0;

	// to the right:
	x= SHIFTRIGHT(SquareBoard[s]); t= (unsigned int) 1<<(7-(s&7)-1);
	while (x) {
		a|= x;
		if (t&i)
			x= 0;
		else {
			x= SHIFTRIGHT(x); t>>= 1;
		}
	};

	// to the left:
	x= SHIFTLEFT(SquareBoard[s]); t= (unsigned int) 1<<(7-(s&7)+1);
	while (x) {
		a|= x;
		if (t&i)
			x= 0;
		else {
			x= SHIFTLEFT(x); t<<= 1;
		}
	};
	return a;
}


BitBoard IndexToAFRvertical (int s, unsigned int i) {
	BitBoard      a, x;
	unsigned int  t;

	a= 0;

	// downward:
	x= SHIFTDOWN(SquareBoard[s]); t= (unsigned int) 1<<(7-(s>>3)-1);
	while (x) {
		a|= x;
		if (t&i)
			x= 0;
		else {
			x= SHIFTDOWN(x); t>>= 1;
		}
	};

	// upward:
	x= SHIFTUP(SquareBoard[s]); t= (unsigned int) 1<<(7-(s>>3)+1);
	while (x) {
		a|= x;
		if (t&i)
			x= 0;
		else {
			x= SHIFTUP(x); t<<= 1;
		}
	};
	return a;
}


BitBoard IndexToAFBrightup (int s, unsigned int i) {
	BitBoard      a, x;
	unsigned int  t;

	a= 0;

	// right up:
	x= SHIFTRIGHTUP(SquareBoard[s]); t= (unsigned int) 1<<(7-(s&7)-1);
	while (x) {
		a|= x;
		if (t&i)
			x= 0;
		else {
			x= SHIFTRIGHTUP(x); t>>= 1;
		}
	};

	// left down:
	x= SHIFTLEFTDOWN(SquareBoard[s]); t= (unsigned int) 1<<(7-(s&7)+1);
	while (x) {
		a|= x;
		if (t&i)
			x= 0;
		else {
			x= SHIFTLEFTDOWN(x); t<<= 1;
		}
	};
	return a;
}


BitBoard IndexToAFBrightdown (int s, unsigned int i) {
	BitBoard      a, x;
	unsigned int  t;

	a= 0;

	// right down:
	x= SHIFTRIGHTDOWN(SquareBoard[s]); t= (unsigned int) 1<<(7-(s>>3)-1);
	while (x) {
		a|= x;
		if (t&i)
			x= 0;
		else {
			x= SHIFTRIGHTDOWN(x); t>>= 1;
		}
	};

	// left up:
	x= SHIFTLEFTUP(SquareBoard[s]); t= (unsigned int) 1<<(7-(s>>3)+1);
	while (x) {
		a|= x;
		if (t&i)
			x= 0;
		else {
			x= SHIFTLEFTUP(x); t<<= 1;
		}
	};
	return a;
}


void PrintBitBoard (BitBoard b) {
  int i;

  for (i=0; i<64; i++) {
    if ((i & 7)==0) printf("\n");
    if (b & SquareBoard[i])
      printf("1");
    else
      printf("0");
  };
  printf("\n");
}

void delay (void) {
	long i;

	i= 0;
	while (i<555555555) {
		i= i+1;
	}
}

int main (void) {
  unsigned int  i;
  int           s;
  FILE          *f;
  int           n;

  InitBitBoards();

  printf("generating attack tables\n");

  for (s=0; s<64; s++) {
    for (i=0; i<256; i++) {
      AFRhorizontal[s][i]= IndexToAFRhorizontal(s,i);
      AFRvertical[s][i]  = IndexToAFRvertical(s,i);
      AFBrightdown[s][i] = IndexToAFBrightdown(s,i);
      AFBrightup[s][i]   = IndexToAFBrightup(s,i);
    };
  	printf(".");
  };
  printf("ok.\n");

  printf("writing to disk: AFRH   ");
  f= fopen("AFRH","wb");
  if (f) {
    n= fwrite(AFRhorizontal,sizeof(BitBoard),64*256,f);
    if (n<64*256)
      printf("failure.\n");
    else
      printf("ok.\n");
    n= fclose(f);
  }
  else
    printf("failure.\n");

  printf("writing to disk: AFRV   ");
  f= fopen("AFRV","wb");
  if (f) {
    n= fwrite(AFRvertical,sizeof(BitBoard),64*256,f);
    if (n<64*256)
      printf("failure.\n");
    else
      printf("ok.\n");
    n= fclose(f);
  }
  else
    printf("failure.\n");

  printf("writing to disk: AFBRD   ");
  f= fopen("AFBRD","wb");
  if (f) {
    n= fwrite(AFBrightdown,sizeof(BitBoard),64*256,f);
    if (n<64*256)
      printf("failure.\n");
    else
      printf("ok.\n");
    n= fclose(f);
  }
  else
    printf("failure.\n");

  printf("writing to disk: AFBRU   ");
  f= fopen("AFBRU","wb");
  if (f) {
    n= fwrite(AFBrightup,sizeof(BitBoard),64*256,f);
    if (n<64*256)
      printf("failure.\n");
    else
      printf("ok.\n");
    n= fclose(f);
  }
  else
    printf("failure.\n");

  return 0;
}



This page took 0.01 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.