Bitboards and inCheck

[Andreas Guettinger]

Happy 2007 to everybody.

I have a question to the use of bitboards to check whether one side is in check. I currently use some code like that:

Code: Select all

bool inCheck(const Position& poos, bool side, int square = -1);

bool inCheck(const Position& ppos, bool side, int square)
{
   register Bitboard attackers, all_attacks;
   all_attacks = 0;

   if (side == WHITE) {
      if (square < 0) square = ppos.WhiteKing;
      attackers = Attacks::BishopAttacks(ppos.occupied, square);
      all_attacks = attackers & ppos.BlackBishops;
      all_attacks |= attackers & ppos.BlackQueens;
   
      attackers = Attacks::RookAttacks(ppos.occupied, square);
      all_attacks |= attackers & ppos.BlackRooks;
      all_attacks |= attackers & ppos.BlackQueens;
      
      all_attacks |= knight_attacks[square] & ppos.BlackKnights;
      all_attacks |= wpawn_attacks[square] & ppos.BlackPawns;
      all_attacks |= king_attacks[square] & set_mask[ppos.BlackKing];
   }
   else {
      if (square < 0) square = ppos.BlackKing;
      attackers = Attacks::BishopAttacks(ppos.occupied, square);
      all_attacks = attackers & ppos.WhiteBishops;
      all_attacks |= attackers & ppos.WhiteQueens;
   
      attackers = Attacks::RookAttacks(ppos.occupied, square);
      all_attacks |= attackers & ppos.WhiteRooks;
      all_attacks |= attackers & ppos.WhiteQueens;
      
      all_attacks |= knight_attacks[square] & ppos.WhiteKnights;
      all_attacks |= bpawn_attacks[square] & ppos.WhitePawns;
      all_attacks |= king_attacks[square] & set_mask[ppos.WhiteKing];
   }

   return (all_attacks) ? true : false;
   
}


This looks expensive and the function is a bit to big for my taste to inline. Will the compiler inline the whole code or only the side relevant part? Is there something fundamentally better to test if the king is in check?
I use this function to check whether the king is in check or to see if a square is attacked, therefore the optional variable int square. I know that I could remove the if(square < 0) line if I would make separate functions, but I doubt if it's worth it.

[Tord Romstad]

This looks expensive and the function is a bit to big for my taste to inline. Will the compiler inline the whole code or only the side relevant part? Is there something fundamentally better to test if the king is in check?

Good question - I have also had difficulties with this. For deciding whether the position is check, I have developed a method which is somewhat ugly, but probably faster than yours:

After generating moves, directly before the loop that selects and searches each move, I compute a bitboard of all "discovered check candidates" for the side to move. This bitboard is passed as a parameter to my do_move() function. With the help of this bitboard, I compute a bitboard of all checking pieces after the move has been made, and store this bitboard in a slot in the position object.

Tord

[Sven Schüle]

Hi Andreas,

what about having more but smaller functions, like in this example:

Code: Select all

/* header file */
bool inCheck(const Position& ppos, bool side);
bool isAttacked(const Position& ppos, bool side, int square);
bool isWhiteAttacked(const Position& ppos, int square);
bool isBlackAttacked(const Position& ppos, int square);

inline bool inCheck(const Position& ppos, bool side)
{
   return (side == WHITE) ?
      isWhiteAttacked(ppos, ppos.WhiteKing) :
      isBlackAttacked(ppos, ppos.BlackKing);
}

inline bool isAttacked(const Position& ppos, bool side, int square)
{
   return (side == WHITE) ?
      isWhiteAttacked(ppos, square) :
      isBlackAttacked(ppos, square);
}

/* implementation file */

bool isWhiteAttacked(const Position& ppos, int square)
{
   register Bitboard all_attacks;

   all_attacks  = Attacks::BishopAttacks(ppos.occupied, square) & (ppos.BlackBishops | ppos.BlackQueens);
   all_attacks |= Attacks::RookAttacks(ppos.occupied, square) & (ppos.BlackRooks | ppos.BlackQueens);
   all_attacks |= knight_attacks[square] & ppos.BlackKnights;
   all_attacks |= wpawn_attacks[square] & ppos.BlackPawns;
   all_attacks |= king_attacks[square] & set_mask[ppos.BlackKing];

   return (all_attacks) ? true : false;
}

bool isBlackAttacked(const Position& ppos, int square)
{
   register Bitboard all_attacks;

   all_attacks  = Attacks::BishopAttacks(ppos.occupied, square) & (ppos.WhiteBishops | ppos.WhiteQueens);
   all_attacks |= Attacks::RookAttacks(ppos.occupied, square) & (ppos.WhiteRooks | ppos.WhiteQueens);
   all_attacks |= knight_attacks[square] & ppos.WhiteKnights;
   all_attacks |= bpawn_attacks[square] & ppos.WhitePawns;
   all_attacks |= king_attacks[square] & set_mask[ppos.WhiteKing];

   return (all_attacks) ? true : false;
}


I hope to have transformed your original code into functionally equivalent code. I tried to make the fundamental code itself shorter, perhaps it is even slightly faster (I did not try it, of course).

Some prefer having few large functions. Personally I tend to write more smaller functions, which sometimes may also have the advantage of getting more inlining. It depends on taste and compiler somehow.

In my example you also avoid the small overhead of the "square" parameter defaulting to -1 when your inCheck() function is called for the purpose of detecting checks.

Regards,
Sven

[Gerd Isenberg]

I have a question to the use of bitboards to check whether one side is in check. ...

I determine checks in advance during legal movegen and have two bits inside my move-structure to determine whether the move was direct check, discovered check or both. So only after position setup at the root i use a similar function than your's.

Cheers,
Gerd

[Pradu]

A (much) faster inCheck() function should return as soon as one (or more) attackers are found.
Andrew

Not necessarily, most of the time inCheck will return false.

[Andreas Guettinger]

....

Some prefer having few large functions. Personally I tend to write more smaller functions, which sometimes may also have the advantage of getting more inlining. It depends on taste and compiler somehow.

In my example you also avoid the small overhead of the "square" parameter defaulting to -1 when your inCheck() function is called for the purpose of detecting checks.

Regards,
Sven

Thanks, Sven. Indeed this code looks more readable than my large function. Since I code in C++, I should use more such small inline wrapper functions. I will try it when I get home tonight.

regards
Andy

[Sven Schüle]

A (much) faster inCheck() function should return as soon as one (or more) attackers are found.
Andrew

Not necessarily, most of the time inCheck will return false.

Hi Pradu,

you're right for inCheck() as far as it is really used for check detection.

But the problem is different, so I think Andrew is also right partially: the isXAttacked() functions as well as Christian's original inCheck() function are reused for detection of arbitrary attacks, and there they are slow because it is quite likely that a given square is attacked by any piece of a given colour (10%? 20%? 40%? does anybody have figures about it?). Having the king in check seems to be a special case which is much less likely to occur.

So perhaps a better implementation, when following this approach at all, might be to rename the two isXAttacked() into isXInCheck() and then to have two more functions isXAttacked() with additional "if (all_attackers) return" statements, hoping that this will be faster for normal attack detection.

I'm pretty sure Christian will find out

Sven

[Grant Osborne]

Hi Andreas

What happens after your inCheck() function returns true? Do you then generate check evasions in a separate checkEvasions() function?

I accepted the fact that I have to 'build' a queens attackboard from the kings position each time, so IF inCheck() is not going to return FALSE I save the attackboard. This is then used to see if a piece can interpose the checker in checkEvasions() and saves time by not having to recalculate it. Also, instead of returning TRUE, my inCheck() returns a value representing the type of checker e.g. 1 for non-slider, 2 for slider; and passes this as an argument to checkEvasions().

Grant

[H.G.Muller]

I don't use bitboards in my engine, but I see that the problems w.r.t. check detection are about the same. How efficiently you can solve it depends on if you want to know if your move puts yourself in check (for the purpose of legal move generation), or if you want to know if your move checks the opponent's King.

In the former case King moves pose the biggest problem. You are more or less forced to an approach as presented above: scanning the board in all directions from which a check can possibly come. (In my 0x88 approach I scan the board for Pawns, and the piece list for other pieces.) Moves with other pieces than King can only put yourself in check if the piece was pinned (or with an e.p. capture). I don't determine that on a per-move basis (since each pinned piece might have many moves), but 'in bulk' before the move generation starts. Only enemy Sliders can pin my pieces, so I only have to scan the part of the piece list containing those Sliders.

The opponent can be checked only by the moving piece, or as a discovered check by one of your Sliders (or, again, e.p. capture). As you know what piece just moved, the former test should be very quick. The other again only requires tests on Sliders, and is very similar to the pin test. With bitboards you might want to generate all attacks through a single piece, (you might have a separate 'HalfAttacks' table for that), to intersect the set with enemy Sliders, and do some further investigation if you find such a properly aligned Slider. (Which will happen only rarely, so it will not be too critical how you handle that case. Most likely you would peel off the Sliders one-by-one, and intersect the attacks of each of them with the pseudo-attacks from the King square to get the blocking pieces. A bitboard with the blockers could inform you that a piece might deliver discovered check through a very simple test on a per-move basis.)

[smcracraft]

My function to determine whether a square is attacked by
side is:

Code: Select all

  return ((pg->p[side][pawn] & MoveArray[ptype[side ^ 1]][tsq]) ||
          (Knight[tsq] & pg->p[side][knight]) ||
          (Bmagic (tsq ^ 63, pg->Occupied) &
           (pg->p[side][bishop] | pg->p[side][queen]))
          || (Rmagic (tsq ^ 63, pg->Occupied) &
              (pg->p[side][rook] | pg->p[side][queen]))
          || (King[tsq] & pg->p[side][king]));


I think it is fairly efficient and seems to be the natural way
to do this kind of task with bitboards. This is not to say that
others don't do it far more efficiently, etc.

There is also a version that uses my own bitboard attack
generation for sliding piece attacks but since it is somewhat
slower than magic, I have the latter enabled by default in
the program.

Stuart