25,161
edits
Changes
Created page with "'''Home * Search * Move Ordering * Last Best Reply''' '''Last Best Reply''' (LBR) is a move ordering heuristic similar to the Countermove Heuristic|Co..."
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * Last Best Reply'''
'''Last Best Reply''' (LBR) is a move ordering heuristic similar to the [[Countermove Heuristic|Countermove heuristic]] but with more specific [[Moves|move]] matching.
''An idea proposed by [[Steven Edwards]]'' <ref>[http://www.talkchess.com/forum/viewtopic.php?t=38556 The LBR move ordering heuristic] by [[Steven Edwards]], [[CCC]], March 26, 2011</ref>. ''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'' <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=401117&t=38556 Testing LBR] by [[Steven Edwards]], [[CCC]], March 27, 2011</ref>.
=The Idea=
At each [[Node|node]] in a search where there is a prior non-null move, the [[Best Move|best move]] for that node is stored along with the prior move in an LBR (Last Best Reply) data store for the [[Ply|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 [[Pieces|moving man]], the [[Captures|captured man]] (if any) and the move special case (e.g., [[En passant|en passant]], [[Promotions|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 [https://en.wikipedia.org/wiki/Binary_tree 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 [[Captures|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=
* [[Best Move]]
* [[Butterfly Boards]]
* [[Countermove Heuristic]]
* [[Killer Heuristic]]
* [[Refutation Move]]
* [[Refutation Table]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=38556 The LBR move ordering heuristic] by [[Steven Edwards]], [[CCC]], March 26, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=44749 Move ordering idea (old and new?)] by [[Dan Homan|Daniel Homan]], [[CCC]], Aug 09, 2012
=References=
<references />
'''[[Move Ordering|Up one Level]]'''
'''Last Best Reply''' (LBR) is a move ordering heuristic similar to the [[Countermove Heuristic|Countermove heuristic]] but with more specific [[Moves|move]] matching.
''An idea proposed by [[Steven Edwards]]'' <ref>[http://www.talkchess.com/forum/viewtopic.php?t=38556 The LBR move ordering heuristic] by [[Steven Edwards]], [[CCC]], March 26, 2011</ref>. ''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'' <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=401117&t=38556 Testing LBR] by [[Steven Edwards]], [[CCC]], March 27, 2011</ref>.
=The Idea=
At each [[Node|node]] in a search where there is a prior non-null move, the [[Best Move|best move]] for that node is stored along with the prior move in an LBR (Last Best Reply) data store for the [[Ply|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 [[Pieces|moving man]], the [[Captures|captured man]] (if any) and the move special case (e.g., [[En passant|en passant]], [[Promotions|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 [https://en.wikipedia.org/wiki/Binary_tree 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 [[Captures|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=
* [[Best Move]]
* [[Butterfly Boards]]
* [[Countermove Heuristic]]
* [[Killer Heuristic]]
* [[Refutation Move]]
* [[Refutation Table]]
=Forum Posts=
* [http://www.talkchess.com/forum/viewtopic.php?t=38556 The LBR move ordering heuristic] by [[Steven Edwards]], [[CCC]], March 26, 2011
* [http://www.talkchess.com/forum/viewtopic.php?t=44749 Move ordering idea (old and new?)] by [[Dan Homan|Daniel Homan]], [[CCC]], Aug 09, 2012
=References=
<references />
'''[[Move Ordering|Up one Level]]'''
