5

This post is a follow up of this one: C++ vs Java Engine move generation performance

My goal here is to improve the performance of my move generator, which finishes perft (start_pos, 6) in 8.5 secs. That's too slow for C++ code (the same Java code runs in 11 secs).

The bottleneck is the check for validity, which in turn tests if the king is in check. This is running for every move, and given that most moves are legal, it's a total waste of time. As pointed out by Student T, we should restricted this test for king in check, pinned pieces and en passant captures.

The king in check or walking to check cases are easy, this post is about pinned pieces code. So, the cpwiki code goes like this:

pinned = 0;
pinner = xrayRookAttacks(occupiedBB, ownPieces, squareOfKing) & opRQ;
while ( pinner ) {
   int sq  = bitScanForward(pinner);
   pinned |= obstructed(sq, squareOfKing) & ownPieces;
   pinner &= pinner - 1;
}

pinner = xrayBishopAttacks(occupiedBB, ownPieces, squareOfKing) & opBQ;
while ( pinner ) {
   int sq  = bitScanForward(pinner);
   pinned |= obstructed(sq, squareOfKing) & ownPieces;
   pinner &= pinner - 1;
}

And here's the code for xrayRookAttacks():

U64 xrayRookAttacks(U64 occ, U64 blockers, enumSquare rookSq) {
   U64 attacks = rookAttacks(occ, rookSq);
   blockers &= attacks;
   return attacks ^ rookAttacks(occ ^ blockers, rookSq);
}

Questions:

a) What is obstructed() doing?

b) After getting the pinned set, how exactly do I use it to test for a valid move?

Thank you all!

4

A: Let's use bishop for our example. xrayBishopAttacks works if we have the following positionenter image description here:

but it doesn't work if you have this:

enter image description here

The f3 knight is not pinned because there is something else behind it. obstructed takes this into consideration.

B: Once you get the pinned pieces, you can just do XAND to check if the piece you want to move is pinned. If it's pinned, you can't move it.

************** EDIT **************

You won't find obstructed() because it's just a pseudocode function. You're expected to implement pinning in obstructed() yourself.

Forget the pseudocode, you should study Stockfish. Goto https://github.com/official-stockfish/Stockfish/blob/master/src/position.cpp

Find bool Position::legal(Move m) const

Check the following:

// A non-king move is legal if and only if it is not pinned or it
// is moving along the ray towards or away from the king.
return   !(pinned_pieces(us) & from)
    ||  aligned(from, to_sq(m), square<KING>(us));

This is exactly what I'm talking about.

  • 1
    The problem is that I coudn't find the code for obstructed(), and regarding point B, what if I move the piece in the direction of the pin? – Fernando Oct 25 '16 at 12:34
  • @Fernando For point B, the function obstructed() is supposed to handle that. Whoever wrote this was lazy to expand it. – SmallChess Oct 25 '16 at 14:16
  • @Fernando EDITED. Please take a look! – SmallChess Oct 25 '16 at 14:22
  • So what obstructed do is to return true if all squares betwen A and B are empty? – Fernando Oct 25 '16 at 16:45
  • 2
    I think I figured it out, obstructed() returns the bitboard value with bits between two given squares. So I'm going to use the 'rectangular lookup' described here chessprogramming.wikispaces.com/Square+Attacked+By#Obstructed. I'll update the post as soon as I solve it. Thanks! – Fernando Oct 25 '16 at 21:23
3

Answering my own question here. I've managed to increase the speed of the move generation code, by implementing the pinnedPices() routine.

The C++ version runs Perft (start_pos, 6) under ~3.5 secs, including hash updates. Here's some Java code for reference (messy indentation, sorry):

//return bitboard of pinned pieces for player side
public static long pinnedBB(Board board, int side, int kingSQ){
    int opp =  side ^ 1;
    long occup = board.bitboards[side] | board.bitboards[opp];
    long pinned = 0L;
    long pinner = xrayRook(board, board.bitboards[side], 
            kingSQ, opp) & (board.bitboards[Board.ROOK | opp] | board.bitboards[Board.QUEEN | opp]);

    while (pinner != 0) {
       int sq  = Long.numberOfTrailingZeros(pinner);
       pinned |= BitBoardGen.rectLookUp[sq][kingSQ] & board.bitboards[side];
       pinner &= pinner - 1;
    }
    pinner = xrayBishop(board, board.bitboards[side], 
        kingSQ, opp) & (board.bitboards[Board.BISHOP | opp] | board.bitboards[Board.QUEEN | opp]);

    while (pinner != 0) {
       int sq  = Long.numberOfTrailingZeros(pinner);
       pinned |= BitBoardGen.rectLookUp[sq][kingSQ] & board.bitboards[side];
       pinner &= pinner - 1;
    }
    return pinned;
}



  public static long xrayBishop(Board board, long blockers, int from, int side){
      int opp = side ^ 1;
      long occup = board.bitboards[side] | board.bitboards[opp];
      long attacks = bishopAttacks(board, occup, from, side);
       blockers &= attacks;
       return attacks ^ bishopAttacks(board, occup ^ blockers, from, side);
 }


  public static long bishopAttacks(Board board, long occup, int from, int side){
    int opp = side ^ 1;
    long enemyOrEmpty = ~board.bitboards[side] & ~board.bitboards[Board.KING | opp];
    long[] up_r = BitBoardGen.BITBOARD_DIRECTIONS[BitBoardGen.IDX_UP_RIGHT];
    long[] up_l = BitBoardGen.BITBOARD_DIRECTIONS[BitBoardGen.IDX_UP_LEFT];
    long[] down_r = BitBoardGen.BITBOARD_DIRECTIONS[BitBoardGen.IDX_DOWN_RIGHT];
    long[] down_l = BitBoardGen.BITBOARD_DIRECTIONS[BitBoardGen.IDX_DOWN_LEFT];

    long upward =  upwardAttackTargetsFrom(from, occup, up_r) | upwardAttackTargetsFrom(from, occup, up_l);
    long downward =  downwardAttackTargetsFrom(from, occup, down_r) | downwardAttackTargetsFrom(from, occup, down_l);
    return upward | downward;
}

The rectLookUp matrix stores the pre-generated bitboards representing the squares between two given squares.

Now, inside moveGen() you only need to test for illegal moves in these situations:

a) ep capture b) pinned piece c) at check d) king move

Everything else will be legal, assuming your pseudo-legal generator is bug-free. You can improve it further for cases 'c' and 'd' (checking only evasive moves for ex).

Hope it helps someone, thanks!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.