Search algorithm

Chess programs divide the task of deciding which move to play in two parts: a static evaluation function that is applied to the current position, and a search algorithm that recursively tries all moves in the current position and returns the static score after a certain number of moves have been player. The best move is simply the move that leads to the best position.

These two topics, search and static evaluation, are normally dicussed separately.

Basic search

I use a standard fail-soft alpha-beta search algorithm, the workings of which is discussed in detail on several sites (try wikipedia).

There are a few details worth mentioning:

Only the first (best, see below) move is searched with a normal window. All other moves are searched with a minimal window. I believe this is referred to as "principle variation search".
I generate all moves up front and sort them (using libc's qsort. Actually, I keep track of the "expected best" move and search that before sorting the other moves, so that I can avoid the sort if I get an immediate cut-off.
If the side to move is in check, the search is extended by one ply.
Moves that are not expected to be good have their search depth reduced. This is known as "late move reduction" and greatly reduces the search time.
Moves that are expected to be bad but "fail high" are re-searched immediately with a normal window and no reductions.

Quiescence search

Before calling the static evaluation, we call the quiescence search: this resolves all winning captures and promotions. I don't consider losing captures (even if there might be something to gain from them, that's likely not something that would be picked up by the quiescence search) or checks (mainly because I don't have a check-generating move generator).

Move ordering

Move ordering is very important. It can be shown quite easily that the alpha-beta algorithm operates most efficiently if we always examine the best move in each position first.

That's a problem, because if we knew what the best move was, we wouldn't have to do the search at all.

Although we don't know the best move in the current position, we can nevertheless try to make a good guess for the best move. That way, we can sort moves that are likely to create a cutoff near the top of the move list. In a sense, we're trying to combine the strength of Shannon type B programs (look only at plausible moves) with the strength of type A programs (it's hard or impossible to give general guidelines for what good moves are, so we really need to look at all of them). There are various ways to guess what a good move might be:

Winning captures are likely to be good. Our program in principle searches every move in a given position, most of which are sufficiently daft that they can be refuted by capturing a hanging piece immediately afterwards.
If we searched this position before (which we probably have in an iterative deepening framework), then the best move from the previous search is probably a good bet for our best move here, or at least a reasonable guess.
Say that, in a certain position, we examined the move a3 and it was refuted by NxQf3, then we can probably refute a4 by the same move - in fact, we can probably refute most moves by this move. So if, in a "sibling-node" (a node at the same depth in the search tree) a certain move (called a "killer move") was found to be good, we should probably try it in this position as well.
A slight modification to this idea is to record moves that have historically been good responses to an opponent's move are searched first. This is known as the "counter move" heuristic.
Along similar lines, some moves may be good follow-ups to our last move and so we should search these early as well. I haven't seen this idea discussed anywhere, for all I know it's a new idea. I'll call it the "combo move" until I can come up with something better. We don't expect a large gain from this because at a given search depth combo moves are probably killer moves as well.
More general than that, if a particular move has historically been good, we can again try it first. This is called the "history heuristic".
If we have nothing else to go on, we can at least try a move that develops a piece or moves it to a better square before a random other move.

The history heuristic, the counter move heuristic and the combo move heuristic can be thought of as generalisations of the killer move that work on different levels in the search tree. In a sense, they're a way for killer moves to filter through to other parts of the tree. Note that the idea behind many of these moves is not that we look for moves that are good for us per se, but rather we look for moves that will quickly weed out obvious blunders by the opponent one ply earlier. My move ordering scheme looks like this:

The move from the hash table is tried before all other moves (if it exists in the current position; normally it does, but there is a slight possibility that the entry in the hash table is actually from another position that hashes to the same value; I'm sure that if I ignore this it'll bite me at an awkward moment).
If there is no move available from the hash table, we do a very shallow search of the current position to get a "best move" to try first. This is known as "internal iterative deepening". This is surprisingly cheap, because we can make good use of the transposition table if we need to re-examine this node later (since this move will now be searched first, we'll always do that).
The mate killer is tried next. This is a normal killer move, but it resulted in a mate score before - so it might do so again here. This is rare in practice, but it speeds up the search in positions where there is a mate threat.
Next, I examine winning captures and promotions. A winning capture is a capture that ends up winning material. It's not normally enough to simply try to take the most valuable piece with the least valued attacker (known as "most valued victim/least valued attacker", abbreviated MVV/LVA). The trick, then is to evaluate a capture, at least approximately, without playing out the entire capture sequence. This is called "static exchange evaluation" (abbreviated SEE). More on that later. For now, let's just say we search winning captures immediately after the hash move and the mate killer.
Normal killer moves. I keep two slots for killer moves: if a new killer is found, the one in the first slot is bumped down to second place and the new killer takes its place. This is so we don't forget killer moves too quickly, which is important, especially at greater depth in the tree. I have experimented with three rather than two killer moves, but it doesn't seem to make a lot of difference. With this move ordering scheme, killers should not be captures or promotion moves. The reason is obvious: those moves will be sorted high in the list anyway. Best use the valuable killer slots for other moves then. Should the killers be sorted before or after the winning captures? I imagine people do different things here; I've found that my search was faster if I sorted the killers after the winning captures, probably because we end up refuting obvious blunders faster.
Normal killers from two plies lower in the search tree. The idea behind this is that sometimes the player may use delaying tactics. This doesn't actually do much - if this move does turn out to be good, it becomes a killer move at this search depth anyway, but it helps a little bit.
The combo move is tried on the same level as the delayed killer moves. The benefit is normally small, but it seems that it help cut down the size of the search tree a little bit with little overhead.
The counter move to the previous move of the opponent (if there is one). This heuristic doesn't seem to be very popular, it's not discussed much. I noticed a fairly small effect on search time, so I kept it - but it doesn't seem like a spectacular improvement. Probably for the same reason that the killer moves from two ply lower down don't do much.
Normal moves, sorted according to the expected improvement to our position based on the piece square tables. This helps quite a bit and is very clearly much better than random ordering.
Losing captures. Captures where we would expect to lose material.

The history heuristic is a curious beast. There are a lot of articles saying how great this historical heuristic is, and there are several claims that it actually doesn't work at all.

In my experience, it certainly doesn't help one bit in its original form (any move causing a cut-off gets registered in the history table), and in fact seems to do more harm than good. It appears that it performs very badly alongside extensions and reductions: situations where it might have helped don't arise so often because the moves where it helped have been reduced anyway. Jazz has code for the history heuristic (disabled), Sjaak does not.

So far so good, but how do we actually sort the moves? One possibility is to build up a sorted list by insertion sort as we're scoring the possible moves. I was too lazy to do something like that, so I just use the standard quicksort to sort the movelist after I scored all the moves. This can actually be quite expensive and I'd like to get rid of it if possible. I only call quicksort after trying the hash move, so there is a chance that I never get to call it at all (if the hash move causes a cut-off), but still I'd like to eliminate it entirely. For now, it results in code that works and is tolerably fast, so it's not a big priority to eliminate it yet.

Extensions/reductions

As explained above, I like to think of looking for a cutoff as refuting bad moves by the opponent (as opposed to looking for good moves for the player who is to move). It is important in this sense to recognise "delaying tactics" that try to push the refutation across the search horizon. For this reason, some moves need to be searched to a greater depth: the search is extended rather than reduced. However, this needs to be done with some care.

Checks are an obvious choise for extension, since they can very easily be used as a delaying tactic. Alternatively, we might extend checks just in case we have something to gain by them, but this is less common. I extend the search depth by one ply if the side to move is in check. This could perhaps be limited in some way, e.g. don't extend checks unless we're close to the search horizon.

Null move

The idea behind trying a null move is to let the side who has just played a move move again. If doing so does not improve their position, then our own position is very strong, no matter what we do. Any reasonable move will fail high, so we may as well cut this branch off before spending any more time on it.

There are situations where a null move should be avoided, however. Being in check is an obvious one. Being in a position with zugzwang is another: in such a position, there is no "reasonable move" that will fail high.

The first of these conditions is easy to detect, the latter one not so much. In Jazz, I skip the null-move if there are very few pieces on the board and if there are no sliders (which can make a "waiting" or "tempo" move). In Sjaak, I skip the null-move if there are fewer than 4 piece types for the side to move.

If the null move does not fail high but is refuted, that means that the other player has some sort of threat and we can use this information to improve the search: we can withdraw a piece that is en-prise, or avoid a threatened mate.