25,161
edits
Changes
Created page with "'''Home * Search * Move Ordering * Relative History Heuristic''' The '''Relative History Heuristic''' was proposed by Mark Winands et al. <ref>Mar..."
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * Relative History Heuristic'''
The '''Relative History Heuristic''' was proposed by [[Mark Winands]] et al. <ref>[[Mark Winands]], [[Erik van der Werf]], [[Jaap van den Herik]], [[Jos Uiterwijk]] ('''2004'''). ''[http://link.springer.com/chapter/10.1007/11674399_18 The Relative History Heuristic]''. [[CG 2004]], [http://erikvanderwerf.tengen.nl/pubdown/relhis.pdf pdf]
</ref> at the [[CG 2004|Computers and Games Conference 2004]] in [https://en.wikipedia.org/wiki/Ramat_Gan Ramat Gan] as improvement of the [[History Heuristic]].
=History Heuristic=
The disadvantage of the history heuristic is that it is biased towards moves that occur more often in a game than others. However, the history heuristic has as implicit assumption that all the legal moves occur roughly with the same frequency in the game (tree). For instance, assume we have a move which is quite successful when applicable (e.g., it then causes a cut-off) but it does not occur so often as a legal move in the game tree. This move will not obtain a high history score and is therefore ranked quite low in the move ordering.
=The Idea=
The idea is to make the history scores (<span style="background-color: #d2d2d2">hhScore</span>) relative to the scores of the [[Butterfly Heuristic|butterfly heuristic]] (<span style="background-color: #d2d2d2">bfScore</span>).
We believe that we can considerably improve the performance of the history heuristic in some games by making it relative instead of absolute: The score used to order the moves (movescore) is given by the following formula:
<pre>
moveScore = hhScore / bfScore;
</pre>
or dependent on the increments:
<pre>
moveScore = (Scale * hhScore) / bfScore;
</pre>
Winands experienced with several increments for <span style="background-color: #d2d2d2">hhScore</span> and <span style="background-color: #d2d2d2">bfScore</span>, namely <span style="background-color: #d2d2d2">{1, depth, depth^2 and 2^depth}</span>. The depth independent increment of 1 seemed to give best results in the game of [[Lines of Action]]. This is how the history [[Array|array]] and butterfly boards may be updated, if a [[Beta-Cutoff|beta-cutoff]] occurs or not (ignoring [[Node Types#PV|PV-Nodes]]):
<pre>
if ( score >= beta ) { // cutoff
if ( isNonCapture (move) )
hhScore[move.from][move.to] += hhIncrement;
...
return score;
} else { // no cutoff
if ( isNonCapture (move) )
bfScore[move.from][move.to] += bfIncrement;
}
</pre>
=Alternatives=
Other approaches of relative history heuristic - proposed by [[Robert Hyatt]], as tried in [[Crafty]] while playing with [[Late Move Reductions]] <ref>[https://www.stmintz.com/ccc/index.php?id=490705 late move reductions] by [[Robert Hyatt]], [[CCC]], March 01, 2006</ref>, and applied by [[Tord Romstad]] in [[Glaurung]] as mentioned by [[Marco Costalba]], the developer of [[Stockfish]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=234691&t=25118&sid=5d8f3f4a0d7f4c59a93e786c21c00072 Re: relative history heuristic] by [[Marco Costalba]], [[CCC]], November 30, 2008</ref> - rely on considering confirmed [[Node Types#CUT|Cut-Nodes]] for updating the counters only. If a [[Fail-High]] occurs, <span style="background-color: #d2d2d2">hhScore</span> is incremented as usual. Additionally, if the move which caused the Cut-Off was not the first one, one has to loop over all previously tried quite moves (still in the move-list), to increment their butterfly penalty scores. A similar idea was proposed by [[Jeff Rollason]], ''Negative Plausibility'' <ref>[http://www.aifactory.co.uk/newsletter/2007_01_neg_plausibility.htm Negative Plausibility] by [[Jeff Rollason]], [[AI Factory]], March 2007</ref> as implemented inside his [[Shogi]] program [https://www.game-ai-forum.org/icga-tournaments/program.php?id=223 Shotest].
<pre>
if ( score >= beta ) { // cutoff
if ( isNonCapture (move) )
hhScore[move.from][move.to] += hhIncrement;
for ( all previous moves m) {
if ( isNonCapture (m) )
bfScore[m.from][m.to] += bfIncrement;
}
...
return score;
}
</pre>
=Peak History Reduction=
A common idea was mentioned by [[Daniel Mehrmann]] in the same LMR-thread <ref>[https://www.stmintz.com/ccc/index.php?id=490779 PHR (Peak History Reduction) idea] by [[Daniel Mehrmann]], [[CCC]], March 01, 2006</ref>, what he called '''Peak History Reduction''' or '''PHR'''. He keeps track of the greatest <span style="background-color: #d2d2d2">hhScore</span>, to consider all other history scores relative to this peak. But that doesn't address the cases, where moves occurred rarely were relative successful.
=See also=
* [[Bobby#StrategicQuiescenceSearch|Bobby's Strategic Quiescence Search]]
* [[History Heuristic]]
* [[Butterfly Heuristic]]
* [[Butterfly Boards]]
* [[Killer Heuristic]]
* [[Countermove Heuristic]]
* [[Late Move Reductions]]
* [[History Leaf Pruning]]
=Publications=
* [[Mark Winands]], [[Erik van der Werf]], [[Jaap van den Herik]], [[Jos Uiterwijk]] ('''2004'''). ''[http://link.springer.com/chapter/10.1007/11674399_18 The Relative History Heuristic]''. [[CG 2004]], [http://erikvanderwerf.tengen.nl/pubdown/relhis.pdf pdf]
=External Links=
* [https://en.wikipedia.org/wiki/Dolby_Laboratories Dolby] - [http://www.letov.ru/SAX-MAFIA.htm SAX-MAFIA] live at [https://en.wikipedia.org/wiki/Smolensk Smolensk] [https://en.wikipedia.org/wiki/Chamber_theatre Chamber Theatre], 2007, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=9GG-LcQZsTs|alignment=left|valignment=top}}
=References=
<references />
'''[[Move Ordering|Up one Level]]'''
The '''Relative History Heuristic''' was proposed by [[Mark Winands]] et al. <ref>[[Mark Winands]], [[Erik van der Werf]], [[Jaap van den Herik]], [[Jos Uiterwijk]] ('''2004'''). ''[http://link.springer.com/chapter/10.1007/11674399_18 The Relative History Heuristic]''. [[CG 2004]], [http://erikvanderwerf.tengen.nl/pubdown/relhis.pdf pdf]
</ref> at the [[CG 2004|Computers and Games Conference 2004]] in [https://en.wikipedia.org/wiki/Ramat_Gan Ramat Gan] as improvement of the [[History Heuristic]].
=History Heuristic=
The disadvantage of the history heuristic is that it is biased towards moves that occur more often in a game than others. However, the history heuristic has as implicit assumption that all the legal moves occur roughly with the same frequency in the game (tree). For instance, assume we have a move which is quite successful when applicable (e.g., it then causes a cut-off) but it does not occur so often as a legal move in the game tree. This move will not obtain a high history score and is therefore ranked quite low in the move ordering.
=The Idea=
The idea is to make the history scores (<span style="background-color: #d2d2d2">hhScore</span>) relative to the scores of the [[Butterfly Heuristic|butterfly heuristic]] (<span style="background-color: #d2d2d2">bfScore</span>).
We believe that we can considerably improve the performance of the history heuristic in some games by making it relative instead of absolute: The score used to order the moves (movescore) is given by the following formula:
<pre>
moveScore = hhScore / bfScore;
</pre>
or dependent on the increments:
<pre>
moveScore = (Scale * hhScore) / bfScore;
</pre>
Winands experienced with several increments for <span style="background-color: #d2d2d2">hhScore</span> and <span style="background-color: #d2d2d2">bfScore</span>, namely <span style="background-color: #d2d2d2">{1, depth, depth^2 and 2^depth}</span>. The depth independent increment of 1 seemed to give best results in the game of [[Lines of Action]]. This is how the history [[Array|array]] and butterfly boards may be updated, if a [[Beta-Cutoff|beta-cutoff]] occurs or not (ignoring [[Node Types#PV|PV-Nodes]]):
<pre>
if ( score >= beta ) { // cutoff
if ( isNonCapture (move) )
hhScore[move.from][move.to] += hhIncrement;
...
return score;
} else { // no cutoff
if ( isNonCapture (move) )
bfScore[move.from][move.to] += bfIncrement;
}
</pre>
=Alternatives=
Other approaches of relative history heuristic - proposed by [[Robert Hyatt]], as tried in [[Crafty]] while playing with [[Late Move Reductions]] <ref>[https://www.stmintz.com/ccc/index.php?id=490705 late move reductions] by [[Robert Hyatt]], [[CCC]], March 01, 2006</ref>, and applied by [[Tord Romstad]] in [[Glaurung]] as mentioned by [[Marco Costalba]], the developer of [[Stockfish]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=234691&t=25118&sid=5d8f3f4a0d7f4c59a93e786c21c00072 Re: relative history heuristic] by [[Marco Costalba]], [[CCC]], November 30, 2008</ref> - rely on considering confirmed [[Node Types#CUT|Cut-Nodes]] for updating the counters only. If a [[Fail-High]] occurs, <span style="background-color: #d2d2d2">hhScore</span> is incremented as usual. Additionally, if the move which caused the Cut-Off was not the first one, one has to loop over all previously tried quite moves (still in the move-list), to increment their butterfly penalty scores. A similar idea was proposed by [[Jeff Rollason]], ''Negative Plausibility'' <ref>[http://www.aifactory.co.uk/newsletter/2007_01_neg_plausibility.htm Negative Plausibility] by [[Jeff Rollason]], [[AI Factory]], March 2007</ref> as implemented inside his [[Shogi]] program [https://www.game-ai-forum.org/icga-tournaments/program.php?id=223 Shotest].
<pre>
if ( score >= beta ) { // cutoff
if ( isNonCapture (move) )
hhScore[move.from][move.to] += hhIncrement;
for ( all previous moves m) {
if ( isNonCapture (m) )
bfScore[m.from][m.to] += bfIncrement;
}
...
return score;
}
</pre>
=Peak History Reduction=
A common idea was mentioned by [[Daniel Mehrmann]] in the same LMR-thread <ref>[https://www.stmintz.com/ccc/index.php?id=490779 PHR (Peak History Reduction) idea] by [[Daniel Mehrmann]], [[CCC]], March 01, 2006</ref>, what he called '''Peak History Reduction''' or '''PHR'''. He keeps track of the greatest <span style="background-color: #d2d2d2">hhScore</span>, to consider all other history scores relative to this peak. But that doesn't address the cases, where moves occurred rarely were relative successful.
=See also=
* [[Bobby#StrategicQuiescenceSearch|Bobby's Strategic Quiescence Search]]
* [[History Heuristic]]
* [[Butterfly Heuristic]]
* [[Butterfly Boards]]
* [[Killer Heuristic]]
* [[Countermove Heuristic]]
* [[Late Move Reductions]]
* [[History Leaf Pruning]]
=Publications=
* [[Mark Winands]], [[Erik van der Werf]], [[Jaap van den Herik]], [[Jos Uiterwijk]] ('''2004'''). ''[http://link.springer.com/chapter/10.1007/11674399_18 The Relative History Heuristic]''. [[CG 2004]], [http://erikvanderwerf.tengen.nl/pubdown/relhis.pdf pdf]
=External Links=
* [https://en.wikipedia.org/wiki/Dolby_Laboratories Dolby] - [http://www.letov.ru/SAX-MAFIA.htm SAX-MAFIA] live at [https://en.wikipedia.org/wiki/Smolensk Smolensk] [https://en.wikipedia.org/wiki/Chamber_theatre Chamber Theatre], 2007, [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=9GG-LcQZsTs|alignment=left|valignment=top}}
=References=
<references />
'''[[Move Ordering|Up one Level]]'''
