Move generation for a chess engine is more crucial than I originally thought. Thankfully, it is easy.
Given any location on the board, the valid destinations for a specific piece are always able to be precalculated. That means given an array of long values (BitBoards) you can store all possible moves for a specific piece by creating a 64 element array representing the starting locations, and the bit values in the long storage represent the destinations possible. The great thing about this entire process is that you can quickly check these bit locations against board information to determine blocked moves, capturing moves, and non-capturing moves. The entire process of examining the board comes down to a few bitwise operations. Very nice if you ask me.
I figured I'd demonstrate the process with the knights. During the creation of our chess board, we'll pre-allocate an array representing all of the possible moves a knight can make and then use it during the rest of the process. This array can also be cached and generated statically, which is always another option, especially when we implement the chess board within our web service. The concepts are to take each space on the board, generate all moves given an infinite board space, clamp these into the physical board (validation) and then bitmask them all together to create our final listing of valid moves from that spot.
private static ulong[] GenerateKnightMoves() {
ulong[] moves = new ulong[64];
int[] possibleMoves = new int[8];
ulong bitMask, bit;
for(int i = 0; i < 64; i++) {
bitMask = 0;
possibleMoves[0] = i + 10;
possibleMoves[1] = i + 6;
possibleMoves[2] = i + 17;
possibleMoves[3] = i + 15;
possibleMoves[4] = i - 10;
possibleMoves[5] = i - 6;
possibleMoves[6] = i - 17;
possibleMoves[7] = i - 15;
Remember the knight move validation code I wrote in a previous article. We can reuse that when generating our new possible move bitmask.
for(int j = 0; j < 8; j++) {
if ( possibleMoves[j] < 0 || possibleMoves[j] > 63 ) {
continue;
}
switch(Math.Abs(possibleMoves[j]/8 - i/8)) {
case 1:
if ( Math.Abs(i%8 - possibleMoves[j]%8) != 2 ) {
continue;
}
break;
case 2:
if ( Math.Abs(i%8 - possibleMoves[j]%8) != 1 ) {
continue;
}
break;
default:
continue;
}
We have to get around some C# compiler issues here, but the basic premise is turing our 1, into a destination bit and then OR'ing it together with any previously set bits. I would probably write much of the chess engine in IL since C# has some strange warnings and errors when dealing with bit-shifting ulong values.
bit = 1;
bit <<= possibleMoves[j];
bitMask |= bit;
}
moves[i] = bitMask;
}
return moves;
}
If you want to examine the output from the method we can print a listing of all starting locations and all valid moves. This involves more kludgy bit shifting, but is worth a look anyway. It helps to solidify how the algorithm works and verify that the moves are actually valid with respect to how a human player views the board.
private static void Main(string[] args) {
ulong[] knightMoves = GenerateKnightMoves();
for(ulong i = 0; i < 64; i++) {
Console.Write("Start: {0} to ", ((ChessPiece) i).ToString());
for(int j = 0; j < 64; j++) {
ulong bitMask = 1;
bitMask <<= j;
if ( (knightMoves[i] & bitMask) > 0 ) {
Console.Write("{0} and ", ((ChessPiece) j).ToString());
}
}
Console.WriteLine();
}
}
Now, how can we use this new structure to our advantage? Well, we can start by invalidating moves that just won't work. We need to use another BitBoard for this process. First, we load all of the spaces that are filled by our own pieces. Remember, that you can't move into a spot controlled by your own piece no matter how hard you try. By combining the player controlled spots without our generated moves we can quickly invalidate any impossible moves.
ulong myPieces = ...;
ulong notMyPieces = ~myPieces;
ulong validMoves = allMoves & notMyPieces;
You can clearly see how powerful the new system is at validating moves. Still not sure how much I want to convert over to using these awesome structures, but it clearly makes sense to store certain values in them.