Writing a chess engine 5: moves generation (part 1)

You have chosen a board representation: now it's time to write the move generation function, maybe the most difficult task and main source of bugs (with makemove function); obviously the way to generate moves is different according to the board representation you have chosen.

We can distinguish two kind of move generator:

1. legal moves generator
2. pseudo legal moves generator

For us a move is legal when, after you play it, your king isn't in check. So a "legal moves generator" generates only legal moves; a "pseudo legal moves generator" generates all moves available. Why? Speed! To control if a move is a legal move is a "time consuming" task; so it is a good idea to delay this control until the move is played effectively. A pseudo legal moves generator generates moves as fast is possible, later in "make move function" we control if a move is a legal one; if it is legal we go ahead, if it isn't legal we must "undo" the move and try another move. We will write a pseudo legal moves generator. So why i'm talking about a legal moves generator? Because there are situation in which is more simple to write a legal generator! If your king is in check you can only:

1. move your king out of check
2. capture the attacking piece (only for single check)
3. if the attacking piece is a sliding piece (bishop, rook, queen) you can move a piece of yours between king and the opponent piece

It is more simple and more fast to write a legal "check escaping"moves generator and not to make legality test in "makemove" instead using the pseudo-legal generator and to have a lot of "failed legality test" and "undo". Strong chess engines have at least two kind of moves generator:

• a pseudo-legal generator
• a "check evasion generator"

I suggest to write first a pseudo-legal moves generator and to debug it; then when your chess engine is finished and "bug free" you can improve it writing a "check evasion generator". You'll be able to use pseudo-legal moves generator to debug the legal one and you'll know that if there is a bug, it is coming from legal generator.

We know that a chess programs consider chess moves as a game tree. In theory, they examine all moves, then all counter-moves to those moves, then all moves countering them, and so on, where each individual move by one player is called a "ply". This evaluation continues until it reaches a final "leaf" position which is evaluated. We will talk later about search, but now you must know only that it is possible (indeed it is favorable) that a chess engines doesn't examine all moves to find a good one. To help a chess engine to do this it is very, very important to ordering them in some way; from the most dangerous to the less dangerous.

In the early day of "Computer Chess" computers were not so powerful to generate and search all moves at every ply; so old chess engines used a "selective generator" that generated only some moves to search. Today this kind of moves generator are used by shogi engine or by go engine. Today we have the power to generate and search all moves: but as you know there is the possibility that a chess engines doesn't examine all moves to find a good one. It is a waste of time to generate all moves just to find out that the first one is the only that we need. There are various strategies about how many moves a (pseudo-legal) moves generator can generate. We can distinguish:

1. All-moves generator: this function generates and stores every moves available.
2. "Capture / no capture" moves generator: We can use 2 functions, one generates only capture moves (more dangerous and more interesting) and the second one generates only no capture moves. First we generate only capture and if we can't find an interesting move we generate the rest of moves available.
3. Incremental moves generator: after that our opponent plays his moves we must generate all moves available from scratch, but often a good numbers of moves available are identical to the move generated before. So it can be useful to write an incremental move generator that remebers moves generated before and generates only moves that now is possible to do.

To write an all-moves is simpler than to write a "capture / no capture". To write a "capture / no capture" is simpler than to write an incremental generator. You must pay attention that according to your board representation, writing a "capture / no capture" or an incremental can be useless. For array-based board i think that an all moves is a good choice, for bitboard based "capture/no capture" is a best choice (it is more simple to generate only capture move or non capture). I think incremental is an optimum, but i never used this kind of generator (Fruit uses this). The only way is to test every generator and to chose the best (you can think that it is obvious, but believe me a lot of people don't do test)!

I suggest to write a simple all-moves pseudo legal generator and a capture only pseudo legal generator (useful in quiescence search, we will talk about quiescence later):

1. there are simple to write and debug
2. you can always use them to debug a more sophisticated generator
3. believe me: more speed in moves generator is good, but it isn't the way to have a more strong engine; search, pruning and evaluation are more important.

Many of you have mailed me to say thank you about this column. Thank you too! But there's a better way to say "Thanks" by adding a link to this blog in your blog/website!

(to be continued...)