Improve Move Ordering for Alpha Beta

The ice engine uses an alpha beta based search, that means if we search possible moves and find one that gives us a position so good, that our opponent will not play the moves that lead to it (because he can reach one that is better for him), we can stop searching further. This is called a cut off (sometimes also called beta cutoff or fail high)

This reduces the search tree. The effective reduction depends on the move order. The earlier I find a move that leads to a "to good to be true" position the more moves I can skip searching. So a simple rule can be formulated that says


Always search the best move first.

This rule is very simple but not 100% accurate, because we don't want to search the best move first, but we want to search a move that gives us a cut off with the least required effort. If the 2nd best move or even the worst move gives us also a cutoff but we only have to search half of the nodes compared to the best move, then we should search this move first obviously.

Always search the move that gives you a cutoff with the least required effort first.

Unfortunately it is not trivial to know it advance what moves give you a cutoff and what is their related effort without searching them. But it is not that bad. In a chess engine various mechanisms exist to help the engine to decide which moves should be searched first.

1. There is the hash move. When a position was searched earlier (with a lower depth) the 1st move that gives you a cutoff was recorded. When this position is searched again with a higher depth, this move is tried first, often it still gives you a cutoff.
2. If you don't have a hash move (you see the position for the first time or last time no move produced a cutoff) or the hash move fails this time, then you look for winning captures. Often they are good.
3. Next you look for equal captures, maybe you get a cutoff here.
4. Then you look for moves that caused a cutoff in similar positions (so called killers). First you have to look whether those killers are legal on the current board and if they are you search them. Good chance for a cutoff with them.
5. Then I try losing captures, most engines search losing captures last and claim that is best for them. I search them before the quiet moves for three reasons. Sometimes a losing capture is not really losing but gives you enough counter play. If it is is really bad than the efforts searching it are small. And last I already have the losing captures generated while generating all captures. When they produce a cutoff I save the generation of all the quiet moves. In average it pays out for me.

Up to this point most engines behave similar (except where they order the losing captures). In 90% of the positions where you get a cutoff, you have got the cutoff with one of the moves above. So when you get here chances are none of the remaining moves will get you a cutoff, nevertheless you can't rely on that. You have to search them and sometimes they surprise you.

So you look for a mechanism to order all the remaining quiet (boring) moves or you decide to search them randomly the way they were generated. Here a lot is tried in different engines but is a bit of black art.

Commonly used is

• Generate the moves in a meaningful order (like casteling moves first, than knight moves, bishop moves, rook moves, queen moves, king moves, pawn moves) and maybe also moves that advance before moves that retreat and just search them in that order
• Use a table for every piece and square (called a piece - square - table) to mark good and bad squares for each piece (like knights get a bad score at the edge and a good score in the center). Search moves first where pieces go from bad squares to good squares. This sounds logic and really helps to order the moves in positions you expect to see on a chess board. Unfortunately in a search tree most of the positions are very strange resulting from a strange sequence of moves and applying a common sense move order must not necessarily help (some state it does, other say it does not)
• Use a technique called history heuristics. Every time in search a move produces a cut off increment a counter for that move (moves searched with higher depth increase the counter more than moves from lower depth searches). Order then your moves according to the value of their counter. This certainly helped when hardware was slow and engines did not search so deeply because the positions in the tree had still some properties in common. Today engines search very deeply and positions after 8 moves of white and a 8 moves of black don't have much in common anymore. So using information from one position in another totally different position must not necessarily be a good thing to do.   

History heuristic is still very commonly used and programmers state it makes their engine stronger. To come up with such a conclusion you must run a lot of games (several 100 at least) against other engines with and without that feature used. Often those games use very short time controls so the testing does not take weeks. Short time controls lead to shallower searches and here history heuristic might help (as it did on slow hardware). So maybe it is still around because the testing framework (with short time controls) of the engine programmers favors it. I tried it at longer time controls and it did not help my engine so I don't use it.

I recently tried the piece square approach. To generate the tables I run longer searches against a lot of positions (more than 1000) and recorded which moves where generated how often, which produced a cut off, which did not and what was the effort required to search them. I also collected information about the pieces that were attacked after that move (if the king was attacked it was a checking move) and about the pieces that were defended by that move. So I generated a database with move heuristics.

The idea was to use the data in that database to generate a rule set or tables to help in the decision process of what move should be tried next.

The data allowed to say something like

A white queen that moves to e7 and attacks a black knight produces a cutoff in 10% of the cases and requires in average 500 nodes to be searched.
A white rook that moves to b5 and gives check produces a cutoff in 90% of the cases and requires in average 5000 nodes to be searched.

So if you encounter a move list that contains only those two moves, the queen move should be search first. (queen move first gives you 5000 nodes in total, rook move first gives you 5050 nodes in total).
but usually the moves lists are longer than 2 moves and it is really difficult to determine a least cost order for the moves even if you have all the data available.

I spent a lot of time with it and I did not find a schema that finally made the engine stronger. It solved some test positions faster but in real play I did not notice a difference.

So for the moment I give up on that idea and go back to a simple ordering schema for the remaining moves. This is maybe not better but as long as it is not worse it helps because it is definitely faster than anything else.