25,161
edits
Changes
Created page with "'''Home * Search * Move Ordering * Countermove Heuristic''' File:Static-Dynamic Gradation MET DP-817-001.jpg|border|right|thumb|240px|[[Arts#Klee|Paul..."
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * Countermove Heuristic'''
[[File:Static-Dynamic Gradation MET DP-817-001.jpg|border|right|thumb|240px|[[Arts#Klee|Paul Klee]] - Static-Dynamic Gradation, 1923 <ref>[[Arts#Klee|Paul Klee]] - Static-Dynamic Gradation, 1923, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Ar]</ref>]]
'''Countermove Heuristic''',<br/>
a dynamic move ordering heuristic introduced by [[Jos Uiterwijk]] in 1992, which shows some similarities with the [[Killer Heuristic|killer-]], [[Refutation Table|refutation-]] and [[History Heuristic|history heuristic]] <ref>[[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]</ref> . This heuristic assumes that many moves have a "natural" response, irrespective of the actual position, and is easy to implement either with a 64 * 64 [[Butterfly Boards|butterfly table]] or alternatively a more memory friendly 6 * 64 [[Array|array]] for each [[Side to move|side to move]], indexed by <span style="background-color: #d0d0d0;">[from][to]</span> or by <span style="background-color: #d0d0d0;">[piece][to]</span> <ref>[[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]</ref> of the previous move, containing the counter move. The nature of the countermove heuristic renders it complementary to the killer heuristic, substituting position with same distance to the root with the last move played.
=Update=
This is how the counter move [[Array|array]] is updated, if a [[Beta-Cutoff|beta-cutoff]] occurs:
<pre>
if ( score >= beta ) { // cutoff
if ( isNonCapture (move) )
counterMove[previousMove.from][previousMove.to] = move;
...
return score;
}
</pre>
=Move Score=
While assigning scores to moves for move ordering, a bonus is earned for the move which matches the countermove of the last move played:
<pre>
if ( movelist[i].move == counterMove[previousMove.from][previousMove.to] )
movelist[i].score += counterMoveBonus;
</pre>
=Butterfly Moves=
Independently of Uiterwijk's work, [[Dap Hartmann]] and [[Peter Kouwenhoven]] reported on the similar technique of [[Butterfly Boards|Butterfly board]] moves at [[Advances in Computer Chess 6]], London 1990, being different from the [[Butterfly Heuristic|Butterfly heuristic]] <ref>[[Dap Hartmann]], [[Peter Kouwenhoven]] ('''1991'''). ''Sundry Computer Chess Topics''. [[Advances in Computer Chess 6]]</ref> . Their aim was to safe [[Move Generation|move generation]] by proving only [[Legal Move#LegalityTest|legality]] of a butterfly move. If both [[Transposition Table|transposition-]] and [[Killer Heuristic|killer table]] fail to supply a move, then 1 in 5 times the butterfly board was able to supply a legal killer which saved the complete move generation <ref>[[Paul Lu]] ('''1990'''). ''Report on the Advances in Computer Chess 6 Conference''. [[ICGA Journal#13_3|ICCA Journal, Vol. 13, No. 3]]</ref> .
=See also=
* [[Butterfly Boards]]
* [[Butterfly Heuristic]]
* [[History Heuristic#CMHist|Counter Moves History]]
* [[History Heuristic]]
* [[Killer Heuristic]]
* [[Last Best Reply]]
* [[Refutation Table]]
=Publications=
* [[Dap Hartmann]], [[Peter Kouwenhoven]] ('''1991'''). ''Sundry Computer Chess Topics''. [[Advances in Computer Chess 6]]
* [[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]
* [[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
* [[Eric Thé]] ('''1992'''). ''[http://digitool.library.mcgill.ca/R/?func=dbin-jump-full&object_id=56753&local_base=GEN01-MCG02 An analysis of move ordering on the efficiency of alpha-beta search]''. Master's thesis, [[McGill University]]
* [[Marcel van Kervinck]] ('''2002'''). ''The design and implementation of the Rookie 2.0 Chess Playing Program''. Masters Thesis, [http://alexandria.tue.nl/extra2/afstversl/wsk-i/kervinck2002.pdf pdf]
=Forum Posts=
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=446349 Counter move heuristic] by [[Alvaro Cardoso|Alvaro Jose Povoa Cardoso]], [[CCC]], August 30, 2005
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=38556 The LBR move ordering heuristic] by [[Steven Edwards]], [[CCC]], March 26, 2011 » [[Last Best Reply]]
* [http://www.talkchess.com/forum/viewtopic.php?t=44749 Move ordering idea (old and new?)] by [[Dan Homan|Daniel Homan]], [[CCC]], Aug 09, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=47953&start=2 Re: History pruning / move ordering question] by [[Don Dailey]], [[CCC]], May 10, 2013
: [http://www.talkchess.com/forum/viewtopic.php?t=47953&start=10 Re: History pruning / move ordering question] by [[Joona Kiiski]], [[CCC]], May 12, 2013
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=62676 countermove heuristic] by [[Folkert van Heusden]], [[CCC]], December 31, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=65107 Storing Countermoves by Ply] by [[Jason Fernandez]], [[CCC]], September 08, 2017
=References=
<references />
'''[[Move Ordering|Up one Level]]'''
[[File:Static-Dynamic Gradation MET DP-817-001.jpg|border|right|thumb|240px|[[Arts#Klee|Paul Klee]] - Static-Dynamic Gradation, 1923 <ref>[[Arts#Klee|Paul Klee]] - Static-Dynamic Gradation, 1923, [https://en.wikipedia.org/wiki/Wikimedia_Commons Wikimedia Commons], [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Ar]</ref>]]
'''Countermove Heuristic''',<br/>
a dynamic move ordering heuristic introduced by [[Jos Uiterwijk]] in 1992, which shows some similarities with the [[Killer Heuristic|killer-]], [[Refutation Table|refutation-]] and [[History Heuristic|history heuristic]] <ref>[[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]</ref> . This heuristic assumes that many moves have a "natural" response, irrespective of the actual position, and is easy to implement either with a 64 * 64 [[Butterfly Boards|butterfly table]] or alternatively a more memory friendly 6 * 64 [[Array|array]] for each [[Side to move|side to move]], indexed by <span style="background-color: #d0d0d0;">[from][to]</span> or by <span style="background-color: #d0d0d0;">[piece][to]</span> <ref>[[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]</ref> of the previous move, containing the counter move. The nature of the countermove heuristic renders it complementary to the killer heuristic, substituting position with same distance to the root with the last move played.
=Update=
This is how the counter move [[Array|array]] is updated, if a [[Beta-Cutoff|beta-cutoff]] occurs:
<pre>
if ( score >= beta ) { // cutoff
if ( isNonCapture (move) )
counterMove[previousMove.from][previousMove.to] = move;
...
return score;
}
</pre>
=Move Score=
While assigning scores to moves for move ordering, a bonus is earned for the move which matches the countermove of the last move played:
<pre>
if ( movelist[i].move == counterMove[previousMove.from][previousMove.to] )
movelist[i].score += counterMoveBonus;
</pre>
=Butterfly Moves=
Independently of Uiterwijk's work, [[Dap Hartmann]] and [[Peter Kouwenhoven]] reported on the similar technique of [[Butterfly Boards|Butterfly board]] moves at [[Advances in Computer Chess 6]], London 1990, being different from the [[Butterfly Heuristic|Butterfly heuristic]] <ref>[[Dap Hartmann]], [[Peter Kouwenhoven]] ('''1991'''). ''Sundry Computer Chess Topics''. [[Advances in Computer Chess 6]]</ref> . Their aim was to safe [[Move Generation|move generation]] by proving only [[Legal Move#LegalityTest|legality]] of a butterfly move. If both [[Transposition Table|transposition-]] and [[Killer Heuristic|killer table]] fail to supply a move, then 1 in 5 times the butterfly board was able to supply a legal killer which saved the complete move generation <ref>[[Paul Lu]] ('''1990'''). ''Report on the Advances in Computer Chess 6 Conference''. [[ICGA Journal#13_3|ICCA Journal, Vol. 13, No. 3]]</ref> .
=See also=
* [[Butterfly Boards]]
* [[Butterfly Heuristic]]
* [[History Heuristic#CMHist|Counter Moves History]]
* [[History Heuristic]]
* [[Killer Heuristic]]
* [[Last Best Reply]]
* [[Refutation Table]]
=Publications=
* [[Dap Hartmann]], [[Peter Kouwenhoven]] ('''1991'''). ''Sundry Computer Chess Topics''. [[Advances in Computer Chess 6]]
* [[Jos Uiterwijk]] ('''1992'''). ''The Countermove Heuristic''. [[ICGA Journal#15_1|ICCA Journal, Vol. 15, No. 1]]
* [[Jos Uiterwijk]] ('''1992'''). ''Memory Efficiency in some Heuristics''. [[ICGA Journal#15_2|ICCA Journal, Vol. 15, No. 2]]
* [[Eric Thé]] ('''1992'''). ''[http://digitool.library.mcgill.ca/R/?func=dbin-jump-full&object_id=56753&local_base=GEN01-MCG02 An analysis of move ordering on the efficiency of alpha-beta search]''. Master's thesis, [[McGill University]]
* [[Marcel van Kervinck]] ('''2002'''). ''The design and implementation of the Rookie 2.0 Chess Playing Program''. Masters Thesis, [http://alexandria.tue.nl/extra2/afstversl/wsk-i/kervinck2002.pdf pdf]
=Forum Posts=
==2005 ...==
* [https://www.stmintz.com/ccc/index.php?id=446349 Counter move heuristic] by [[Alvaro Cardoso|Alvaro Jose Povoa Cardoso]], [[CCC]], August 30, 2005
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=38556 The LBR move ordering heuristic] by [[Steven Edwards]], [[CCC]], March 26, 2011 » [[Last Best Reply]]
* [http://www.talkchess.com/forum/viewtopic.php?t=44749 Move ordering idea (old and new?)] by [[Dan Homan|Daniel Homan]], [[CCC]], Aug 09, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=47953&start=2 Re: History pruning / move ordering question] by [[Don Dailey]], [[CCC]], May 10, 2013
: [http://www.talkchess.com/forum/viewtopic.php?t=47953&start=10 Re: History pruning / move ordering question] by [[Joona Kiiski]], [[CCC]], May 12, 2013
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=62676 countermove heuristic] by [[Folkert van Heusden]], [[CCC]], December 31, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=65107 Storing Countermoves by Ply] by [[Jason Fernandez]], [[CCC]], September 08, 2017
=References=
<references />
'''[[Move Ordering|Up one Level]]'''
