C++ vs Java Engine move generation performance

Question

I've just finished translating my Java Engine to C++11, expecting great speed improvements in move generation. The code is very straightforward and uses a pre-generate bitboards approach. I also generate only legal moves, ie, inside generateMoves() I check to see if the king is in check.

As a quick test, I ran Perft (6) from the starting position. The Java version finishes the test on ~11 seconds. The C++ version takes ~8.5 seconds (my perft stops at depth 1, and zobrist keys are being updated on makeMove and undoMove).

The same test on Stockfish runs under 1 second.

I was expecting the C++ version to be at least twice as faster as the Java one, and of course, somewhat slower than Stockfish.

After some investigation, it's clear that checking if the king is in check, for every move, is the major bottleneck. What can I do about this? I was trying to understand how to work with pinned pieces (https://chessprogramming.wikispaces.com/Checks+and+Pinned+Pieces+(Bitboards)), but I'm not sure how to follow. For example, what does obstructed() do in the link above?

NOTE: I already compiled it with the -O2 optimization flag.

EDIT: Here is some more details on the code:

Q: How did you generate sliding pieces?

I use the classfical bitboard approach, at program start I generate attack masks for all pieces:

void MoveGen::bishopMoves(Board& board, int side, MoveList& moves){
    int opp = side ^ 1;
    U64 bishops = board.bitboards[Board::BISHOP | side];
    U64 occup = board.bitboards[side] | board.bitboards[opp];
    U64 enemyOrEmpty = ~board.bitboards[side] & ~board.bitboards[Board::KING | opp];

    U64 *up_r = BitBoardGen::BITBOARD_DIRECTIONS[BitBoardGen::IDX_UP_RIGHT];
    U64 *up_l = BitBoardGen::BITBOARD_DIRECTIONS[BitBoardGen::IDX_UP_LEFT];
    U64 *down_r = BitBoardGen::BITBOARD_DIRECTIONS[BitBoardGen::IDX_DOWN_RIGHT];
    U64 *down_l = BitBoardGen::BITBOARD_DIRECTIONS[BitBoardGen::IDX_DOWN_LEFT];

    while (bishops != 0){
        int from = numberOfTrailingZeros(bishops);
        U64 upward =  upwardMoveTargetsFrom(from, occup, up_r, enemyOrEmpty) | upwardMoveTargetsFrom(from, occup, up_l, enemyOrEmpty);
        U64 downward =  downwardMoveTargetsFrom(from, occup, down_r, enemyOrEmpty) | downwardMoveTargetsFrom(from, occup, down_l, enemyOrEmpty);
        add_moves(board, from, upward | downward, Move::NO_FLAGS, moves);
        bishops &= bishops - 1;
    }
}

 //handle blocking
U64 MoveGen::upwardMoveTargetsFrom(int from, U64 occup, U64 dir_mask[], U64 enemyOrEmpty){
    U64 ray = dir_mask[from];
    U64 blocker = occup & ray;

    if (blocker != 0){
        int sq = numberOfTrailingZeros(blocker);
        ray^= dir_mask[sq];
    } 
    return ray & enemyOrEmpty;
}

Q: How did you generate legal moves?

I only generate legal moves, so I check if the king is in check while generating moves. This is probably one of the problems, since most moves don't leave the king in check.

The generateAllMoves code:

MoveList genLegalMoves()
   valid = ()
   moves = getPseudoLegalForAllPieces (may leave the king in check)
   for move in moves
      board.applyMove(move) //its a local makemove, no zorbist involved
      atCheck = isAtCheck()  //dumb code, be more selective here?
      board.removeMove(move)//its a local undomove, no zorbist involved

      if !atCheck:
         valid.add(move)

  atCheck = isAtCheck() //again for castling
  if (! atCheck and canCastleKS)
     valid.add(castleKS)
  if (! atCheck and canCastleQS)
     valid.add(castleQS)
  return valid   

Q: How did you undo your move?

My makeMove is like the following (this is fast):

int makeMove(int move):
    int undo = board.state
    incremental update zobrist key
    update board.board[]
    update board.bitboards
    update board.state
    return undo

void undoMove(int move, int undo):
    board.state = undo
    incremental undo zobrist key
    update board.board[]
    update board.bitboards

And finally, my isAtCheck() code goes like:

boolean isAtCheck(int side):
    locate king square
    get all opponent attacks mask 
    return kingSquare & attacksMask

EDIT 2: I have changed the code to a pseudo-legal generator. The problem now is that I have to go to depth 0 to count only legal moves, and now it's taking ~16 seconds.

Answer 1

Your code looks fine. We can't really give you the exact cause, but we can give you some hints.

Q: How did you generate sliding pieces?

Sliding piece generation is typically the slowest because we need to check the enemy pieces. Stockfish uses magic bitboard, which is also used by Houdini and Komodo.

Q: How did you generate legal moves?

Stockfish always generate pseudo-legal moves and only check when it's necessary.

Q: How did you undo your move?

Stockfish can easily undo a move by zorbrist hashing. Hash value can be updated efficiently.

------------------------ EDIT ------------------------

Your sliding generation and undo look okay to me. I think the bottleneck is your legal move generation. Look at this recent thread:

http://talkchess.com/forum/viewtopic.php?t=61797

How do you ensure legality:
a) by making/unmaking each move and testing whether it leaves the king in check, or
b) by only doing this for the small set of moves that could actually be illegal (king moves, check evasions, ep captures, and moves of pinned pieces), or
c) by doing clever move generation that knows how to avoid generating illegal moves?
Only in case of a) I'd say you should spend effort to improve speed, since that could be done an order of magnitude faster, e.g. like b). Otherwise I'd keep it as it is, provided it is correct Smile

Sven Schule is a respected engine programmer, we should trust his words. Your implementation looks like exactly his point a.

Answer 2

Disclaimer: I can't support my claims with numbers. I don't have your engine to profile. It is mostly gut feelings.

It looks like a performance killer is a castling test.

Testing for canCastle*S (it looks like it is about King and Rook didn't move, and nothing is in between) is way cheaper than testing for King becoming exposed, so swap the tests order. C++ will short-circuit logical and.

BTW, for castling you need to test against inCheck at three squares:

if (canCastleKS && !inCheck(e_file) && !inCheck(f_file) && !inCheck(g_file)) {
    ....
}