Saving castling states and en passant history

[EricLang]

How do other programmers solve saving castling states and en passant history? I added both to my board structure and update them in my MakeMove() and UnmakeMove().

For Castling I need for example some bytes for the ply of the first rookmove (A + H)
And for enpassant I need an array of 8 records to be able to restore the information.

I thought it had to be done, because when making a few moves and then unmaking them the enpassant information gets lost.
To my surprise I saw in the source code of Crafty (and other programs) that they do not store this information in the board structure. Only a few bits and one EnpassantSquare.
Why is this information stored apart from the board? And where is the information stored then? (I'm a Delphi programmer so cannot read C-code very well).

[gladius]

Castling state is generally stored as 4 bits, one each for white kingside, white queenside, black kingside and black queenside. This way you can update it very quickly with a few masking operations, and restoring it can be done as a simple integer copy.

The code for updating your castle state can basically look like this:

Code: Select all

if (piece == ROOK) {
 CastleFlags &= RookCastleFlagMask[from];
} else if (piece == KING) {
 if (us == WHITE) {
   CastleFlags &= ~(CastleFlagWhiteKing | CastleFlagWhiteQueen);
 } else {
   CastleFlags &= ~(CastleFlagBlackKing | CastleFlagBlackQueen);
 }
}

Where RookCastleFlagMask is initialized to 0xFF, and the starting squares for the rooks have their castling state bit cleared. Something like this:

Code: Select all

RookCastleFlagMask[MakeSquare(RANK_1, FILE_A)] ^= CastleFlagWhiteQueen;
RookCastleFlagMask[MakeSquare(RANK_1, FILE_H)] ^= CastleFlagWhiteKing;
RookCastleFlagMask[MakeSquare(RANK_8, FILE_A)] ^= CastleFlagBlackQueen;
RookCastleFlagMask[MakeSquare(RANK_8, FILE_H)] ^= CastleFlagBlackKing;

En-Passent state can easily be stored as the square where it is possible to perform the en-passent capture. Again, then restoring is done as an integer copy.

I do store this information alongside my board structure.

[EricLang]

Ok I understand that but what if you make the following sequence?

Code: Select all

1. e2-e4 a7-a6
2. e4-e5 d7-d5 // epsquare created = d6
3. c2-c3 ... // epsquare destroyed
3... c7-c6

en now if you unmake all moves back, how do you "remember" to reset the epsquare to d6 when unmaking the move 3. c2-c3?

Same story for castling. How do you know when to restore castlingstates when unmaking moves?

[gladius]

Restoring the state is done by storing the flags, and then copying them back when you unmake the move.

ie.

Code: Select all

MakeMove(UndoInformation &undo)
{
 // store old state
 undo.CastleRights = CastleRights;
 undo.EnPassent = EnPassent;

 // Update castleRights/enPassent as neccesary
 ...
}

UnmakeMove(UndoInformation &undo)
{
 CastleRights = undo.CastleRights;
 EnPassent = undo.EnPassent;

 // No need to update castleRights/enPassent as they are correct
}

[EricLang]

Ok so this undo-information is stored outside of your board structure?
And we need an extra parameter for MakeMove and UnmakeMove.

Something like this?

Code: Select all

MakeMove(Board, Move, UndoInfo);
....

UnmakeMove(Board, Move, UndoInfo);
....

[gladius]

Ah, I see what you mean now. Sorry, I had assumed you only meant storing the current castling rights and en passent state along with my board.

To answer your question, yes, the move undo information is stored seperately.

[hgm]

In my engines the e.p. rights are passed as a parameter to the recursive search routine, and thus disappear automatically if you return from this routine, and the previous incarnation (with its own e.p. rights parameter) becomes active again. MakeMove determines the e.p. rights after the move, and the rights determined by the call to makeMove that performs the actual move played are passed as argument to the root-node Search() call.

Outside the tree (in the game history) I never really undo moves. On an undo command, I simply reset the game, and replay all the moves (except those that needed to be undone). This also guarantees that things like the repetition table and 50-move counter are properly set.

[bob]

How do other programmers solve saving castling states and en passant history? I added both to my board structure and update them in my MakeMove() and UnmakeMove().

For Castling I need for example some bytes for the ply of the first rookmove (A + H)
And for enpassant I need an array of 8 records to be able to restore the information.

I thought it had to be done, because when making a few moves and then unmaking them the enpassant information gets lost.
To my surprise I saw in the source code of Crafty (and other programs) that they do not store this information in the board structure. Only a few bits and one EnpassantSquare.
Why is this information stored apart from the board? And where is the information stored then? (I'm a Delphi programmer so cannot read C-code very well).

I do not quite follow. I pass along two bytes from ply to ply, one is castle-status, which is 4 bits, define whether white/black can castle kingside or queenside. For en passant, I pass a 1-byte square number where an en passant capture is possible because the current side just advanced a pawn two squares, and it passed one or two enemy pawns on either adjacent file.

When I advance to the next ply, I first copy those two bytes to the next ply's copy, then when I call MakeMove() it looks for three possible circumstances:

(1) we advance a pawn two squares, and the enemy has a pawn on our 4th rank on either adjacent file. If this is true, I copy the to-square of the pawn I just moved to the ep_target variable for the next ply. Otherwise I leave it at zero.

(2) we move either rook, I clear the appropriate castle status bit to show that castling to that side is never going to be possible below the move that moved the rook.

(3) we move the king, which instantle sets the appropriate castle status to zero since castling will never be possible below this move in the tree.

As I unmake moves and back up through the tree, the array index (ply) used to access castle/ep status backs up to the old value so that the tree above the move that changed the status is back to the state it was in prior to that move...

Every time I call MakeMove() I clear the EP target for the enemy since either I have to make the EP capture on this ply (if the target is non-zero) or the ep opportunity is lost...

[Harald]

(2) we move either rook, I clear the appropriate castle status bit to show that castling to that side is never going to be possible below the move that moved the rook.

(3) we move the king, which instantle sets the appropriate castle status to zero since castling will never be possible below this move in the tree.

There is one additional strange situation you should handle.
At least if you want your chess engine play right, not fast.
(I think Bob knows this but I speak to you other newbie readers.)

You should clear the castle status for o-o-o or o-o if the opponent captures the rook
on its original place. Otherwise you could have this:

The king stays in the middle watching the carnival around it.
One of the rooks gets captured but the castling rights are still there.
The other rook leaves its place and the castling rights on that side are cleared.
The rook now walks to the other side to take its brother's original place.
Now the knight and the bishop leave their places.
And finally the king decides to castle with the surviving rook.

When you think this is not likely to happen and only cost too much
nanoseconds to prevent it, then wait for the day when you show someone your engine
and that evil person sets up a position and some moves like described above.
You engine may crash or at least disagree with the surrounding GUI.

Harald

[AndrewShort]

How do other programmers solve saving castling states and en passant history? I added both to my board structure and update them in my MakeMove() and UnmakeMove().

For Castling I need for example some bytes for the ply of the first rookmove (A + H)
And for enpassant I need an array of 8 records to be able to restore the information.

I thought it had to be done, because when making a few moves and then unmaking them the enpassant information gets lost.
To my surprise I saw in the source code of Crafty (and other programs) that they do not store this information in the board structure. Only a few bits and one EnpassantSquare.
Why is this information stored apart from the board? And where is the information stored then? (I'm a Delphi programmer so cannot read C-code very well).

I use the move stack to store the en passant square - my move stack contains the move, hash key, en passant square, and piecelist index of a captured piece (only relevant if you use a piecelist). I don't use push/pop, rather the stack is managed at the tail end, which is more efficient. Anyway, the move stack makes UndoMove very efficient, as it contains the info I need to quickly undo a move.

As for castling rights, I do an old trick, which I've been meaning to change, but I never got around to it (I'm sure castling right bit flags would be way more efficient - on my todo list....). That is, I have 2 different piece types for kings (moved, or not moved), and rooks (moved, or not moved). Therefore castling right is not in my move stack, since it's just a piece type. When I undo a move, the pieces that moved get restored, as does castling right.