Difference between revisions of "Countermove Heuristic"

From Chessprogramming wiki
Jump to: navigation, search
(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...")
 
 
(5 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * Countermove Heuristic'''
 
'''[[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>]]  
+
[[File:Static-Dynamic Gradation MET DP-817-001.jpg|border|right|thumb|240px|[[:Category:Paul Klee|Paul Klee]] - Static-Dynamic Gradation, 1923 <ref>[[:Category:Paul 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 Art]</ref>]]  
  
 
'''Countermove Heuristic''',<br/>
 
'''Countermove Heuristic''',<br/>
Line 48: Line 48:
 
==2010 ...==
 
==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=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=44749 Move ordering idea (old and new?)] by [[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=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
 
: [http://www.talkchess.com/forum/viewtopic.php?t=47953&start=10 Re: History pruning / move ordering question] by [[Joona Kiiski]], [[CCC]], May 12, 2013
Line 54: Line 54:
 
* [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=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
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65107 Storing Countermoves by Ply] by [[Jason Fernandez]], [[CCC]], September 08, 2017
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=70217 Depth reduced but ELO increased] by [[Tom King]], [[CCC]], March 16, 2019
 +
==2020 ...==
 +
* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=76255 Problem with counter move heuristic] by John Garrison, [[CCC]], January 08, 2021
  
 
=References=  
 
=References=  
 
<references />
 
<references />
 
 
'''[[Move Ordering|Up one Level]]'''
 
'''[[Move Ordering|Up one Level]]'''
 +
[[Category:Paul Klee]]

Latest revision as of 09:47, 16 February 2022

Home * Search * Move Ordering * Countermove Heuristic

Paul Klee - Static-Dynamic Gradation, 1923 [1]

Countermove Heuristic,
a dynamic move ordering heuristic introduced by Jos Uiterwijk in 1992, which shows some similarities with the killer-, refutation- and history heuristic [2] . 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 table or alternatively a more memory friendly 6 * 64 array for each side to move, indexed by [from][to] or by [piece][to] [3] 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 is updated, if a beta-cutoff occurs:

   if ( score >= beta ) { // cutoff
      if ( isNonCapture (move) )
         counterMove[previousMove.from][previousMove.to] = move;
      ...
      return score;
   }

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:

   if ( movelist[i].move == counterMove[previousMove.from][previousMove.to] )
      movelist[i].score += counterMoveBonus;

Butterfly Moves

Independently of Uiterwijk's work, Dap Hartmann and Peter Kouwenhoven reported on the similar technique of Butterfly board moves at Advances in Computer Chess 6, London 1990, being different from the Butterfly heuristic [4] . Their aim was to safe move generation by proving only legality of a butterfly move. If both transposition- and 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 [5] .

See also

Publications

Forum Posts

2005 ...

2010 ...

Re: History pruning / move ordering question by Joona Kiiski, CCC, May 12, 2013

2015 ...

2020 ...

References

  1. Paul Klee - Static-Dynamic Gradation, 1923, Wikimedia Commons, Metropolitan Museum of Art
  2. Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
  3. Jos Uiterwijk (1992). Memory Efficiency in some Heuristics. ICCA Journal, Vol. 15, No. 2
  4. Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
  5. Paul Lu (1990). Report on the Advances in Computer Chess 6 Conference. ICCA Journal, Vol. 13, No. 3

Up one Level