[Guide] Move generation

All the parts of Mediocre up until now have been pretty basic and obvious. Now comes our first big challenge. The move generation algorithm.

This is a huge part of the program and plays a deciding role in the overall speed.

There are a couple of techniques which can be used;

One is only generating a few moves that 'look' good and skip the rest. This is how the human brain works, we look at a position and pick a few good moves to calculate. The problem is it is nearly impossible to make the engine pick the best moves every time, and even if we succeed in the majority of the positions, even a single missed move may lose the game.

Another technique is generating a few moves at a time, calculate them and hope they're so good you don't need to generate the rest. This requires mixing it with the search-algorithm and can get quite messy.

I will go for the third, and easiest approach; generate all moves up front for every reached position.

Pseudo-legal moves: We can divide the moves in a position into pseudo-legal and legal moves.

Pseudo-legal moves are all moves that follows the basic move rules. I.e. the move does not take the piece off the board, or captures own pieces. But it might leave the own king in check, castle while in check or castle over a checked square.

Legal moves are the pseudo-legal moves where the illegal moves have been filtered out.

The reason we make this distinction is because checking if the own king is in check can not be made up front. It takes two steps:

1. Make the move on the board.


2. Check if the square the king is standing on is attacked.

Since we have to actually make the move on the board to see if it's legal, we simply have to generate the pseudo-legal moves first, otherwise we have no moves to check.

We have a choice of leaving the generation at pseudo-legal moves, and then handle the illegal moves in the search by discarding moves if the king gets captured.

Since in-check routines are quite costly, this might save some time, but I find the whole idea a tad silly, capturing the king should not happen, even in the search in my opinion.

So I will generate all pseudo-legal moves and then filter them to get the legal moves to work with.

Deltas: I will be using something called piece deltas to generate the moves for the pieces.

Let's start with an example, the queen delta looks like this:

queen_delta = {-15, -17, 15, 17, -1, -16, 1, 16};

I explained a similar property of the makeMove-method in an earlier post. Here we see the full extent of it.

As illustrated in the diagram to the left the queen's delta is every square next to it, since it can move in all directions. If you take a closer look you will notice that the first position in the queen_delta array represents 'down diagonally to the right'. So add -15 to the original index 52+(-15) and we get the new index 37, as seen in the diagram.

The other positions in the array represents every direction the queen can move (left, right, up, down, diagonally up to the right etc.).

Now let's say we want the queen to move to 'a8'.

The queen follows the line in the diagram, now we need to get the indexes for the squares it passes. So we add the 'up diagonally to the left'-delta (third position in the array, i.e. 15) for each new square.

We get:

'd5' - 52+15 = 67
'c6' - 67+15 = 82
'b7' - 82+15 = 97
'a8' - 97+15 = 112

As you can see we now have a very easy way of generating the squares a queen can move to from a certain position. Just do the same thing with all the deltas until we reach the end of the board with each of them (which will of course be caught by an i & 0x88 check).

The rook delta looks like this:

rook_delta = {-1, -16, 1, 16, 0, 0, 0, 0};

Notice how the last four positions are zeros, that's because the rook can only move in four directions.

And similar for the other pieces.

Sliding and non-sliding pieces: There are two types of pieces, sliding and non-sliding.

Queens, rooks and bishops are sliding. Knights and kings are non-sliding.

The sliding pieces can move numerous squares in a direction, while non-sliding only have one square to move to. This is used to determine wether we should update the delta with the next square (for sliding), or stop after one move is found in a direction (for non-sliding).

Pawns and castling: We now have two trickier moves to handle. Pawn moves and castling.

Pawns are a bit special since they capture diagonally, but can not capture when moving forward. So either we write a separate method for pawns, or make sure we realize it is a pawn when generating the moves for it. We can still use deltas but it gets a bit more complicated.

Castling is a move of it's own and has to be handled separately.

When to stop: Of course not every piece can travel all the way to the edge of the board in every direction. You are bound to run in to a piece now and then.

For ordinary moves we just have to check what piece it runs into, if it is an opponent, the move turns into a capture, and then we have to stop moving in that direction (for sliding pieces). If it is a friendly piece we have to discard that square as moveable and stop generating moves that way.

For castling first we need to make sure castling rights are available for the moving side, but also make sure no pieces are in the way. For legal (as opposed to pseudo-legal) moves we also need to make sure the king is not in check or passes a checked square.

Attacked squares: To be able to check if the king is left in check we need a way to determine if a square is attacked. This can also be useful for other parts of the program and not only for move generation. Like space-evaluation, where the side that attacks the most squares has an advantage in space if material is even.

If this is done wrong it can be very costly, so be careful.

I will make an attack-array in which the program quickly can look up what pieces can attack a certain square from another square.

So let's say I wanted to see if the white king on 'g1' is in check. I would send the index (6) to an isAttacked-method, then go through all squares on the board, and when a piece is found I look in the attack-array to see if it can attack the square from its position.

Let's say we found a bishop on 'b4', the attack-array would quickly state that no piece can attack 'g1' from 'b4', and we know the bishop is not checking the king.

If we found a rook on 'g8' our attack-array would state that it is possible for a rook to attack 'g1' from 'g8', so now we have to check if any pieces are in the way. This is done by traversing the rook's delta towards the king, if we do not run into any pieces on the way, we will eventually end up on the same square as the king and we can conclude the king is in check.

On a sidenote this whole thing could be made another way; let's say we wanted to see if the white king was attacked. Then we could just generate all moves for black (pseudo-legal since it does not matter if black's king is under attack if he can capture the white king), and see if any of the moves is a capture of the white king.

This approach would for sure be easier to implement, but the speed would suffer. We would have to generate all moves (which is quite costly) instead of just doing an extremly fast checkup if the piece has any way of even getting to the square.

I will cover attack-array more thoroughly with examples in later posts.

Conclusion: There is a whole lot of work to be done with this. Let's see if I can put it all together.

Edits:
2006-12-19 - Added the reason for having an attack-array