Implementing Late Move Reductions

After the unpleasant fixing of the transposition table design flaw I thought it is time to move to something more interesting to actually maybe improve the engine a bit.

I thought that "Late Move Reductions" is worth giving a try.

In a normal Alpha Beta tree you have 3 types of nodes

PV-nodes = nodes that have a score that ends up being inside the alpha beta window. These nodes have all moves searched, and the value returned is exact, which may propagate up to the root.

All-nodes = nodes in which no move's score exceeded alpha. Every move at an All-Node is searched, and the score returned is an upper bound, the exact score might be less.

Cut-nodes = nodes in which a beta cutoff  is performed. The score returned is a lower bound (might be greater) on the exact score of the node.

Statistics show that in Cut Nodes with reasonable move ordering the cut off happens very early, within the first 3 to 4 moves. In "All Nodes" you search every move just to find out no one can improve your situation. Move ordering in All Nodes has no effect so a lot of search time the engine spends in handling the All Nodes. Unfortunatly you don't know that you are searching an All Node until you are done.

Late Move Reduction (LMR) tries to save some of the time here. The idea is that a move that is probably not a Cut Node (you searched the first 4 moves and are still there) and not a PV Node (you searched the probably best 3-4 moves after move ordering and no move was good enough to improve the score you already secured) is most likely an All Node. So the node is searched with a reduced depth to verify that it is really an All Node. This is where the name Late Move Reduction comes from, you reduce the late moves in such a node. If this reduced search reveals that you're guess was wrong you do a research of the moves otherwise you saved a lot of nodes.

However you should not reduce all moves just because they are late in the list. You should not reduce moves that give check, moves that respond to check, captures, promotions ... everything that is interesting or you miss something important.

After implementing this the engine searched a lot deeper but was actually playing weaker than the one without LMR. So I added another restriction that in nodes below a PV node no reduction takes place, as a wrong score here might more likely propagate up to the root. This seemed to do the trick.

I played 10 games of the engine with LMR against the engine without it, and the engine with LMR scored 7:3. One loss of the LMR engine was due to a time control issue where it lost on time in a winning position, so the loss is not a result of LMR. I find this a rather convincing improvement of the engine.

Arena tournament

Rank	Engine	Score	En	En	S-B
1	Engine12	7,0/10	· ·· ·· ·· ··	11===01=11	21,00
2	Engine11	3,0/10	00===10=00	· ·· ·· ·· ··	21,00

10 games played / Tournament is finished

Level: Tournament 40/10

The end of the tournament, the engine with LMR as black will Mate in 2 

8/1p3kp1/3P3p/p1p1B3/P7/RP3qP1/5r2/3R2K1 w - - 0 40