Quickly vaidating chess moves, a mixture of performance and ingenuity. [Edit: 6:45 Oct 5th]
Validating a chess move you need the source location and the destination location. That way you can do some basic boundary checks. We'll assume that your source and destination fall in a specific and validated range on the board. For a 0 offset array this would be 0-63 and for a 1 offset this would be 1-64.
int cloc = 20; int dloc = 30;
if ( cloc >= 0 && cloc <= 63 && dloc >= 0 && dloc <= 63 ) {
// Valid offsets, let's go to work
}
Now we need to label specific offsets. The easiest way to label a bunch of the offsets into the array is to use an enumeration.
public enum ChessPiece {
/*
BoardPositions
*/
A1 = 0x00, B1 = 0x01, C1 = 0x02, D1 = 0x03, E1 = 0x04, F1 = 0x05, G1 = 0x06, H1 = 0x07,
A2 = 0x08, B2 = 0x09, C2 = 0x0A, D2 = 0x0B, E2 = 0x0C, F2 = 0x0D, G2 = 0x0E, H2 = 0x0F,
A3 = 0x10, B3 = 0x11, C3 = 0x12, D3 = 0x13, E3 = 0x14, F3 = 0x15, G3 = 0x16, H3 = 0x17,
A4 = 0x18, B4 = 0x19, C4 = 0x1A, D4 = 0x1B, E4 = 0x1C, F4 = 0x1D, G4 = 0x1E, H4 = 0x1F,
A5 = 0x20, B5 = 0x21, C5 = 0x22, D5 = 0x23, E5 = 0x24, F5 = 0x25, G5 = 0x26, H5 = 0x27,
A6 = 0x28, B6 = 0x29, C6 = 0x2A, D6 = 0x2B, E6 = 0x2C, F6 = 0x2D, G6 = 0x2E, H6 = 0x2F,
A7 = 0x30, B7 = 0x31, C7 = 0x32, D7 = 0x33, E7 = 0x34, F7 = 0x35, G7 = 0x36, H7 = 0x37,
A8 = 0x38, B8 = 0x39, C8 = 0x3A, D8 = 0x3B, E8 = 0x3C, F8 = 0x3D, G8 = 0x3E, H8 = 0x3F,
BoardBits = 0x3F,
}
Ignore the BoardBits for now. We use that to pack the enumeration which isn't important for validating a particular move. What is important is that we have now labelled each of the offsets so that we can use them to perform checks. When working with white pawns for instance, we might write code that ensures the pawn only moves one square, that it moves in the correct direction, that it doesn't try to capture a piece illegally, etc...
if ( dloc - cloc == 8 ) { /* We are moving forward 1 */ }
if ( dloc - cloc == 16 && cloc >= A2 && cloc <= H2 ) { /* We are moving forward 2 */ }
// For ingenuity, we can assume the piece to be behind a particular row as well
if ( dloc - cloc == 16 && cloc < A3 ) { /* This is a small perf increase, but not a full consistency check */ }
Pawns are allowed to capture as well, but I haven't shown you how we learn about the target location, so I can't demonstrate that. Instead we'll move on to the rook, which for non chess players, moves vertically or horizontally in a straight line around the board. The key here is to quickly recognize if it is moving in a straight line. We can easily do that using integer division and modulus.
if ( cloc/8 == dloc/8 ) { /* the same rank or horizontal row */ }
if ( cloc%8 == dloc%8 ) { /* the same file or vertical column */ }
Knights are interesting as well. They can legally move to 8 positions on the board from their current location, jumping any pieces along the way. If we reduce the problem to basic mathematics again we can write another basic check to find out if a move is valid. The concept here is to recognize that subtracting the destination from the starting location is going to result in a specific number. Let's take the sample move E3->F5:
E3 == 0x14 or 20
F5 == 0x25 or 37
Diff = F5 - E3 = 17
D5 == 0x23 or 35
Diff = D5 - E3 = 15
The old knight algorithm in this post was drastically flawed. A first attempt at providing a linear array approach to chess moves. In any case, refactoring the existent algorithm simply added too much overhead (see the comments). Changing the algorithm is actually much more efficient to take advantage of rank and file checks instead of relying on linear offsets. The new algorithm ensures the destination is 1 or 2 files away. Depending on the file distance, it then determines a maximum rank distance.
switch(Math.Abs(dloc/8 - cloc/8)) {
case 1:
if ( Math.Abs(cloc%8 - dloc%8) != 2 ) {
return false;
}
break;
case 2:
if ( Math.Abs(cloc%8 - dloc%8) != 1 ) {
return false;
}
break;
default:
return false;
}
Diagonals are a bit harder to handle, and they are required for the King, Bishop, and Queen pieces. We can always find the rank difference through division, since we used this process to make sure the rook stayed in the same rank. Modulus arithmetic can give you the change in file. If the rank and file changes are identical then we are moving along a diagonal.
if ( Math.Abs(cloc/8 - dloc/8) == Math.Abs(cloc%8 - dloc%8) ) { /* We may have a diagonal */ }
Mainstream chess engines probably have some extremely interesting checks, but these seem to be good enough for most general scenarios. Takes a bit more to add in en-passant, pawn promotion, and castling, but they are also easy boundary checks. King check conditions are a bit more difficult. You have to cycle through all available pieces and see if they threaten the King. This check can be run through the above equations given the location of the opposite King as the destination. If the move is valid then the King is probably in check.
The above checks have to be fast, because you don't only make them once as a result of a move. You wind up making them once for the move, and then many times for check validation, and further many more times for check-mate validation. Chess is definitely a difficult problem to solve, but a fairly easy environment to create. Here I'm focusing on the environment, while before I've focused a bit on the problem Quick introduction to the Zobrist Hash with real examples. We'll never rewrite Deep Blue, but then again, some of the lower ratings on Chessmaster can kick my butt and there isn't any reason I can't at least code a bit of Chess AI capable of giving me and hopefully some others a challenge.