Last Best Reply

From Chessprogramming wiki
Revision as of 14:02, 22 January 2019 by GerdIsenberg (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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

  1. Instead of the prior move, both the prior move and the move before it are used for the first match operation.
  2. Instead of the prior move, the move two plies earlier is used.
  3. LBR operations are skipped if the reply move is a capture or promotion.
  4. 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

References

Up one Level