0x88 Sqaure attack detection

[Richard Allbert]

Hi,

I have been writing a 0x88 move generation scheme over the past few weeks. I read that one of the advantages was the speed up for 'In check' detection.

I made an array[256] that sets the correct piece bits depending on the delta between squares, and add 128 to make all -ve deltas +ve.

So far, I have only a skeleton for the function, because of an efficiency problem.

Code: Select all

int sq_attacked(int sq)
{
    //---assign opposing side
    int oside = 1 - ourside;

   //---integers
    register int i, tdet;
    register const int delta = -sq + 128;
 if (oside == WHITE)
 {
  for( i = 0;i < 64; ++i)
  {
   if (ISWHITE(game_board[board_index[i]]))
   {       
      if (attackarray[board_index[i]+delta] & game_board[board_index[i]])
      {
      /*
       we've found a possible attack
     */
            //------one square pieces fist-----------//
       if (ISPAWN(game_board[board_index[i]]) ||
            ISKNIGHT(game_board[board_index[i]]) ||
             ISKING(game_board[board_index[i]]) )
            {
              return TRUE;
            }
     
...............


etc etc...... and now the next part should deal with pieces not adjacent to sq.

For example, sq = H8 and there is a wBishop on A1.

if (attackarray[board_index[i]+delta] & game_board[board_index[i]])

will be true, but the function needs to check B2, C3, D4 etc. to see if the diagonal is empty.

How is this done efficiently? The problem, as I see it, is that the function doesn't 'know' that this is a diagonal - to do this, I tried a structure with

Code: Select all

typedef struct lookupdelta {
   int d, int diff
};



where 'd' is the difference (H8-A1) and diff is the ray direction to loop from to check the diagonal. The structure is pre-computed when the program boots.

This all seems a bit slow to me?

Am I missing a simple solution?

For reference,

Code: Select all

#define  ISEMPTY(sq)  ((sq)&1)
#define  ISPIECE(sq)  ((sq)&2)
#define  ISWHITE(sq)  ((sq)&4)
#define  ISBLACK(sq)  ((sq)&8)
#define  ISSLIDE(sq)  ((sq)&16)
#define  ISPAWN(sq)   ((sq)&32)
#define  ISKNIGHT(sq) ((sq)&64)
#define  ISKING(sq)   ((sq)&128)
#define  ISBISHOP(sq) ((sq)&256)
#define  ISROOK(sq)   ((sq)&512)
#define  ISQUEEN(sq)  ((sq)&1024)
#define  OFFBOARD(sq) ((sq)&0x88)

const int board_index[64] = {
    0,1,2,3,4,5,6,7,
    16,17,18,19,20,21,22,23,
    32,33,34,35,36,37,38,39,
    48,49,50,51,52,53,54,55,
    64,65,66,67,68,69,70,71,
    80,81,82,83,84,85,86,87,
    96,97,98,99,100,101,102,103,
    112,113,114,115,116,117,118,119
                       };


Thanks,

Richard


[Dann Corbit]

Use piece lists.

You should never, never, never see:

Code: Select all

for (i = 0; i < 64; i++)
{
    /* do stuff */
}


in any chess code other than perhaps an initialization routine.

If you are going to hunt over every square on the board to find things or to do things, it will not matter what scheme you choose -- all of them are going to be bad.

I would recommend separate piece lists by piece type and color.
Even make one for the king [despite the fact that there is always exactly one kind], and you will see new wonders for you "InCheck()" routine.

[Alessandro Scotti]

Hi Richard,
you need to store two informations in your attack array: the attack mask, which you already do, and the attack direction.
In this small piece of code (from an engine I'm writing):

Code: Select all

bool Position::is_square_attacked( int sq, int side ) const
{
    for( const Piece * p = BY_SIDE( side ); p->sq != 0; p = NEXT_BY_SIDE(p) ) {
        int piece = board[ p->sq ];
        int index = ATTACK_INDEX( p->sq, sq );

        if( Attacks[index].mask & AttackMask[piece] ) {
            int inc = Attacks[index].inc;
            int dst = sq - inc;

            if( IS_SLIDER(piece) ) {
                while( board[dst] == EMPTY ) {
                    dst -= inc;
                }
            }
           
            if( p->sq == dst ) {
                return true;
            }
        }
    }

    return false;
}


you will find this idea as well as Dann suggestion of keeping a piece list.

[Richard Allbert]

Hi,

Thanks for the help;

Just a note Dann - I do keep a piece list in my existing engine, but haven't arrived at introducing one in the version I'm writing now... I have only written the move generator and various parsing functions.

Richard

[Anonymous]

0x88 attack detection has two parts:

1) Look up the bit mask. You take a delta between from and to squares, which might be negative of course, and you look at that location in an array of (probaby) bytes, and do a bitwise-AND test against the piece that you think might be doing the attacking.

For example, if you are going from e4 to d5 the delta is 17. To deal with negative numbers you probably add 128 to this to get 145. In element 145 in the array will be something like bfwpawn | bfbishop | bfqueen | bfking.

So you do this test first, and if it fails, there can't possibly be an attack, because there is no way to get there from here.

If the test succeeds, you are done if you are checking a non-sliding piece, meaning anything other than a bishop, rook, or queen.

2) Traverse the ray. If the test succeeds, and you have a sliding piece, you have to look at the squares between the source and the destination.

You do this by using your delta value to look up in another array, which tells you how to get from the source to the destination a step at a time.

For example, from d4 to f6, the delta is is 34. You add 128 to this, to account for negative numbers, to get 162. In element 162 of the array you will find a 17, which is amount you add each time to step along the ray.

We're talking a dozen lines of code here -- look in Gerbil.

bruce

[Richard Allbert]

Hi,

Thanks.

Yes; I made an array[256] of structures which contain the bits, and the corresponding ray delta. The function looks up array[i].bits and then traverses the ray using array[i].delta.

One question...

As described above, I have defined the pieces with quite a range of different bits, so I can retrieve information using a macro. e.g

Code: Select all

#define  ISSLIDE(sq)  ((sq)&16)
#define  ISQUEEN(sq)  ((sq)&1024)


It seems the correct thing to do for asking if a piece is a sliding piece, but in terms of speed, is it faster to write

Code: Select all

if ( game_board[i] == QUEEN ) {..}


rather than use the

Code: Select all

ISQUEEN(game_board[i])

macro?

Thanks,

Richard

[Gerd Isenberg]

Hi,

Thanks.

Yes; I made an array[256] of structures which contain the bits, and the corresponding ray delta. The function looks up array[i].bits and then traverses the ray using array[i].delta.

One question...

As described above, I have defined the pieces with quite a range of different bits, so I can retrieve information using a macro. e.g

Code: Select all

#define  ISSLIDE(sq)  ((sq)&16)
#define  ISQUEEN(sq)  ((sq)&1024)


It seems the correct thing to do for asking if a piece is a sliding piece, but in terms of speed, is it faster to write

Code: Select all

if ( game_board[i] == QUEEN ) {..}


rather than use the

Code: Select all

ISQUEEN(game_board[i])

macro?

Thanks,

Richard

Hi Richard,
no there should be no difference - if a compiler optimize both cases equal, what should be most likely true:

Code: Select all

; assuming int gameboard and sq in ebx:
test   [gameboard + 4*ebx],  1024
jnz   isQueen


...
or
...

Code: Select all

cmp [gameboard + 4*ebx],  QUEEN
je    isQueen


X86 has a TEST regmem32, imm32 instruction, which performs a bitwise "and" without changing regmem32, but setting the zero flag if the temporary "and"-result becomes zero. The compare instruction CMP regmem32, imm32 is about the same speed. Like TEST, CMP only sets flags but internally performs a substraction.

Gerd