Last Best Reply
Home * Search * Move Ordering * Last Best Reply
Last Best Reply (LBR) is a move ordering heuristic similar to the Countermove heuristic but with more specific move matching.
An idea proposed by Steven Edwards [1]. 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. Note that any results may (will) be different as more move ordering techniques are added [2].
The Idea
At each node in a search where there is a prior non-null move, the best move for that node is stored along with the prior move in an LBR (Last Best Reply) data store for the ply of the node. At move ordering time in all nodes, there are a first and a possible second move match operation. For the first match operation, the LBR data store for the current ply is examined for a match of the current prior move. If a match of the LBR stored prior move is made, then a second match operation is performed. In the second match operation, the generated moves at the node are scanned for a match with the LBR stored reply for the prior move. If this second match exists, the corresponding generated move is given a move ordering bonus so that it might be considered early in the move scan for the current node.
Unlike the Countermove heuristic, the LBR approach also uses the moving man, the captured man (if any) and the move special case (e.g., en passant, promotion) for matching purposes. This means a less frequent match but a more appropriate match when one is made.
Implementation
One way of implementing the LBR data store is by means of a binary tree with each node having a hash of the prior move as a key and having the node's value being the reply move.
Variants
- Instead of the prior move, both the prior move and the move before it are used for the first match operation.
- Instead of the prior move, the move two plies earlier is used.
- LBR operations are skipped if the reply move is a capture or promotion.
- Instead of an LBR data store at each ply, there are only two LBR data stores (one for each color) for an entire search.
See also
Forum Posts
- The LBR move ordering heuristic by Steven Edwards, CCC, March 26, 2011
- Move ordering idea (old and new?) by Daniel Homan, CCC, Aug 09, 2012
References
- ↑ The LBR move ordering heuristic by Steven Edwards, CCC, March 26, 2011
- ↑ Testing LBR by Steven Edwards, CCC, March 27, 2011