2

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.

  • 1
    In addition to -O2, you need -DNDEBUG to turn off those asserts. – Pete Becker Oct 23 '16 at 9:49
  • Already did, I only have those 2 asserts, so no change in performance. – Fernando Oct 24 '16 at 2:07
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.

  • Thanks, I've update the post with more info. I commented the isAtCheck() routine, the time went down to 6 secs, so I should improve on that. What do you mean by undo a move by zobrist hashing? – Fernando Oct 23 '16 at 16:54
  • @Fernando Updated. Please take a look. – SmallChess Oct 24 '16 at 4:39
  • That´s it, if I disable the legality checks it runs perft (6) in 2 secs, Can you help me to implement pinned pieces detection? I didn't understand the cpwiki code for that. – Fernando Oct 24 '16 at 12:30
  • @Fernando I think we should start a new question for it. Do you want to accept my answer and we can discuss with a new question? Other people can join too. – SmallChess Oct 24 '16 at 12:33
  • Here it is: chess.stackexchange.com/questions/15714/… Thanks! – Fernando Oct 24 '16 at 13:31
1

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)) {
    ....
}
  • This makes no sense because checking for castling is really just checking for the bitboard on the f1,g1,f8,g8,a8,b8,b1,c1 squares. This can be done quickly with bitboard AND. Furthermore, there're lots of positions this check is not even needed because 1: already castled 2: some pieces in the squares between. – SmallChess Oct 24 '16 at 5:07
  • @StudentT The positions where the check is not needed is exactly what I am talking about. OTOH I am not really sure that bitboard AND is cheap. OP said (and I have no reason to doubt it) that the bottleneck is in atCheck. – user58697 Oct 24 '16 at 5:14
  • In my answer, I also believed consistently checking for the king positions is a slowdown. However, I'm not sure it's related to castling. It's more to do that it's called for every move, even moves that can't possibly be illegal. – SmallChess Oct 24 '16 at 5:16
  • It´s not the castle test. The problem is checking for validity after every move, which in turn check for 'king in check' condition. – Fernando Oct 24 '16 at 12:26

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.