TalkChess.com

[Sven Schüle]

Hi Richard,

within AttackedByDark()/AttackedByLight() you are using an uncommon algorithm: you are going through all enemy piece lists, trying to find attacks from enemy pieces to the target square. The most common algorithm is different in that you start at the target square and watch out for enemy attacks in all directions from there, by assuming a "super piece" on the target square and taking all "outgoing" attacks of that super piece as "incoming" to the target square. That will save quite a lot of unnecessary work.

For knights and king this is not immediately obvious with your mailbox board (and in fact you might even take a hybrid approach by searching for knight and king attacks the way you do it now) but for sliders and pawns it should be a significant improvement to start at the target square since the effort for that is never bigger than the effort to find "outgoing" attacks for one queen and one pawn.

Testing for attacks to the target square of a castling rook (F1, D1, F8, D8) might even be done a tiny bit cheaper by writing specialized functions. For instance, for F1 you would only need these:
- attack by black queen or bishop on diagonals A6-E2 or G2-H3
- attack by black queen or rook on file F
- attack by black knight on D2/E3/G3/H2
- attack by black pawn on E2/G2
- attack by black king on G2 (everything else would already have been an illegal position before)
I don't know how big the speedup will be, if any, considering that castling availability is statistically rare so this code is rarely used. But at least it should be somehow measureable as long as AttackedByDark() etc. are very expensive operations.


A minor issue: MovePieceOnList(): in my opinion this function is missing a "break" for the "board.pceLst[index] == fromsq" case (fromsq should be unique in the piece list)


When making a move, you always check for "enemy king in check" immediately. This can be improved significantly by asking if the move you just made might really have been illegal. With normal pseudo-legal move generation, it is possible to restrict the set of potentially illegal moves like this:

1) check evasions,
2) king moves (including castles),
3) ep captures,
4) moves of pinned pieces (or weaker: moves of potentially pinned pieces).

Only these need the expensive "enemy king in check" test, other moves are legal unless you do something very extraordinary in move generation (which I am sure you don't do after looking into the code you posted). I made this proposal (which I did not invent, of course!) recently in a different thread opened by Folkert van Heusden.

In another recent thread I mentioned that checking for attacks to E1/E8 twice per color within castling move generation can be avoided, i.e. reduced to doing it only once per color, e.g. by introducing some "wereAttacksToE8Tested" flag. When maintaining an inCheck flag which is set at the top of each node (you'll do this anyway in regular search so why not in perft?), the whole "attacks to E1/E8" check can be skipped and replaced by testing the inCheck flag before generating castle moves.


As my last point, your piece list handling looks expensive to me. For instance, RemoveFromPieceList() loops through the list until it finds the slot to be removed. What if you spend a bit more of memory and store the piece list index for each square? This lets you find the right slot for Remove() immediately. Restoring a captured piece's square in the piece list when unmaking a capture move can be improved the same way if you additionally store the piece list index of the captured piece together with other "undo move" related information, like the captured piece type. You can then reinsert the square into the right slot by moving back the square that is currently in that slot beyond the current end of the list (where it came from, since you are unmaking a capture move where you had moved the square from the "end" position to the now empty slot!).

I don't know how much of a speed improvement you will get by implementing that last point about piece lists, which is also the reason why I mention it at the bottom of my post.

Sven