The LBR move ordering heuristic

[sje]

I can't recall exactly when I came up with the idea of using the LBR heuristic. But it was at one point part of experiments with my old 1987 program Spector back in the pre-Web days. Concerning details, my memory fails me here as it often does.

In any case, I've brought back the technique for application in the new Chess In Lisp toolkit. At present, LBR is used only for the defensive side in the sample matefinder routine where a bonus of a half pawn is added for move ordering. Sometimes it works, and sometimes it doesn't. But in any case, it will be more specific (and so have a better chance at working) than the Countermove heuristic.

People are welcome to check it out for themselves. The constantly evolving CIL toolkit can be found at:

https://public.me.com/chessnotation -> ChessInLisp -> Source

The LBR data store for each ply is organized as an unbalanced binary tree keyed by the prior move's hash. For debugging purposes, the value part of each hash node includes both the last best reply and a clear copy of the prior move in a two element list.

One surprise for me was that the hash tree at a search node can wind up having hundreds of different prior moves, each with a corresponding LBR move (some duplicates here). This is a consequence of the extra specificity of LBR vs Countermove.

Anyone with a Lisp processor can run the code themselves and see what's happening. (The *acs* dbg0 option flag needs to be activated manually for LBR to kick-in.)

Note that any results may (will) be different as more move ordering techniques are added. Also, results will certainly be different for a general move selector vs the existing mate finder.