Difference between revisions of "Static Exchange Evaluation"

From Chessprogramming wiki
Jump to: navigation, search
(Created page with "'''Home * Search * Move Ordering * Static Exchange Evaluation''' FILE:Kleine Welten IX (Small Worlds IX) MET DP855300.jpg|border|right|thumb| [[Arts#K...")
 
(External Links)
 
(19 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * Static Exchange Evaluation'''
 
'''[[Main Page|Home]] * [[Search]] * [[Move Ordering]] * Static Exchange Evaluation'''
  
[[FILE:Kleine Welten IX (Small Worlds IX) MET DP855300.jpg|border|right|thumb| [[Arts#Kandinsky|Wassily Kandinsky]] - Small Worlds IX <ref>[[Arts#Kandinsky|Wassily Kandinsky]] - [https://commons.wikimedia.org/wiki/File:Kleine_Welten_IX_(Small_Worlds_IX)_MET_DP855300.jpg?uselang=en Small Worlds IX], 1922, [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Art]</ref> ]]
+
[[FILE:Kleine Welten IX (Small Worlds IX) MET DP855300.jpg|border|right|thumb| [[:Category:Wassily  Kandinsky|Wassily Kandinsky]] - Small Worlds IX <ref>[[:Category:Wassily  Kandinsky|Wassily Kandinsky]] - [https://commons.wikimedia.org/wiki/File:Kleine_Welten_IX_(Small_Worlds_IX)_MET_DP855300.jpg?uselang=en Small Worlds IX], 1922, [https://en.wikipedia.org/wiki/Metropolitan_Museum_of_Art Metropolitan Museum of Art]</ref> ]]
  
A '''Static Exchange Evaluation (SEE)''' examines the consequence of a series of exchanges on a single [[Squares|square]] after a given [[Moves|move]], and calculates the likely evaluation change ([[Material|material]]) to be lost or gained, [[Donald Michie]] coined the term [[SOMA#Swapoff|swap-off value]]. A positive static exchange indicates a "winning" move. For example, PxQ will always be a win, since the Pawn side can choose to stop the exchange after its Pawn is recaptured, and still be ahead. Some programs optimize the SEE function to only return a losing or equal/winning flag, since they only use SEE to determine if a move is worth searching and do not need the actual value. SEE is useful in [[Move Ordering|move ordering]], [[Futility Pruning|futility pruning]] and especially in [[Quiescence Search|quiescence search]] in conjunction with [[Delta Pruning|delta pruning]], as well to [[Reductions|reduce]] "bad" [[Captures|captures]] and [[Check|checks]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=40100 Reducing/Pruning Bad Captures (SEE < 0)] by [[Edsel Apostol]], [[CCC]], August 19, 2011</ref> .  
+
A '''Static Exchange Evaluation (SEE)''' examines the consequence of a series of exchanges on a single [[Squares|square]] after a given [[Moves|move]], and calculates the likely evaluation change ([[Material|material]]) to be lost or gained, [[Donald Michie]] coined the term [[SOMA#SwapOff|swap-off value]]. A positive static exchange indicates a "winning" move. For example, PxQ will always be a win, since the Pawn side can choose to stop the exchange after its Pawn is recaptured, and still be ahead. Some programs optimize the SEE function to only return a losing or equal/winning flag, since they only use SEE to determine if a move is worth searching and do not need the actual value. SEE is useful in [[Move Ordering|move ordering]], [[Futility Pruning|futility pruning]] and especially in [[Quiescence Search|quiescence search]] in conjunction with [[Delta Pruning|delta pruning]], as well to [[Reductions|reduce]] "bad" [[Captures|captures]] and [[Check|checks]] <ref>[http://www.talkchess.com/forum/viewtopic.php?t=40100 Reducing/Pruning Bad Captures (SEE < 0)] by [[Edsel Apostol]], [[CCC]], August 19, 2011</ref> .  
  
 
=Implementation=  
 
=Implementation=  
Line 40: Line 40:
 
</pre>
 
</pre>
 
=SOMA=  
 
=SOMA=  
Instead of using a [[Quiescence Search|quiescence search]], some (early) chess programs aimed to determine the material balance of a position by a static analysis of '''all''' possible capture-move sequences. These routines are often referred to as [[SOMA#SOMAALGO|SOMA]] ('''S'''wapping '''O'''ff '''M'''aterial '''A'''nalyzer) <ref>[[Hiroyuki Iida]], [[Makoto Sakuta]], [[Jeff Rollason]] ('''2002'''). ''Computer Shogi''. Artificial Intelligence, Vol. 134, [https://en.wikipedia.org/wiki/Elsevier Elsevier], [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.130.2727 CiteSeerX]</ref> based on the [[SOMA#Swapoff|swap-off algorithm]] used in the one-ply analyzing "paper machine" [[SOMA]] by [https://en.wikipedia.org/wiki/Evolutionary_biologist evolutionary biologist] [[John Maynard Smith]], the '''S'''mith '''O'''ne-'''M'''ove '''A'''nalyzer designed in the early 60s <ref>[[John Maynard Smith]], [[Donald Michie]] ('''1961'''). ''Machines that play games''. [https://en.wikipedia.org/wiki/New_Scientist New Scientist], 12, 367-9. [http://books.google.com/books?id=lo7r0zX_T0sC&lpg=PA369&dq=Machines%20that%20play%20games.%201961%2C%20New%20Scientist%2C%2012&pg=PA367#v=onepage&q&f=false google books]</ref> .
+
Instead of using a [[Quiescence Search|quiescence search]], some (early) chess programs aimed to determine the material balance of a position by a static analysis of '''all''' possible capture-move sequences. These routines are often referred to as [[SOMA#SOMAALGO|SOMA]] ('''S'''wapping '''O'''ff '''M'''aterial '''A'''nalyzer) <ref>[[Hiroyuki Iida]], [[Makoto Sakuta]], [[Jeff Rollason]] ('''2002'''). ''Computer Shogi''. Artificial Intelligence, Vol. 134, [https://en.wikipedia.org/wiki/Elsevier Elsevier], [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.130.2727 CiteSeerX]</ref> based on the [[SOMA#SwapOff|swap-off algorithm]] used in the one-ply analyzing "paper machine" [[SOMA]] by [https://en.wikipedia.org/wiki/Evolutionary_biologist evolutionary biologist] [[John Maynard Smith]], the '''S'''mith '''O'''ne-'''M'''ove '''A'''nalyzer designed in the early 60s <ref>[[John Maynard Smith]], [[Donald Michie]] ('''1961'''). ''Machines that play games''. [https://en.wikipedia.org/wiki/New_Scientist New Scientist], 12, 367-9. [http://books.google.com/books?id=lo7r0zX_T0sC&lpg=PA369&dq=Machines%20that%20play%20games.%201961%2C%20New%20Scientist%2C%2012&pg=PA367#v=onepage&q&f=false google books]</ref> .
  
 
=See also=  
 
=See also=  
Line 74: Line 74:
 
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/645f44f84102e450 MVV/LVA vs SEE move ordering - more test results] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], August 25, 1995
 
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/645f44f84102e450 MVV/LVA vs SEE move ordering - more test results] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], August 25, 1995
 
: [http://groups.google.com/group/rec.games.chess.computer/msg/1951744da404fc33 Re: MVV/LVA vs SEE move ordering - more test results] by [[Brian Sheppard]], [[Computer Chess Forums|rgcc]], August 27, 1995
 
: [http://groups.google.com/group/rec.games.chess.computer/msg/1951744da404fc33 Re: MVV/LVA vs SEE move ordering - more test results] by [[Brian Sheppard]], [[Computer Chess Forums|rgcc]], August 27, 1995
 +
* [https://groups.google.com/d/msg/rec.games.chess.computer/5byhl_6Jmc8/D1QAR146VLIJ MVV/LVA and SEE - what do they mean?] by [[Peter Kappler]], [[Computer Chess Forums|rgcc]], August 28, 1995 » [[MVV-LVA|MVV/LVA]]
 
* [https://www.stmintz.com/ccc/index.php?id=17016 Quiescence vs swapoff] by [[Peter Fendrich]], [[CCC]], April 15, 1998
 
* [https://www.stmintz.com/ccc/index.php?id=17016 Quiescence vs swapoff] by [[Peter Fendrich]], [[CCC]], April 15, 1998
 
* [https://www.stmintz.com/ccc/index.php?id=32703 Question about static exchange evaluation] by Larry Coon, [[CCC]], November 12, 1998
 
* [https://www.stmintz.com/ccc/index.php?id=32703 Question about static exchange evaluation] by Larry Coon, [[CCC]], November 12, 1998
Line 86: Line 87:
 
* [https://www.stmintz.com/ccc/index.php?id=147977 About SEE] by [[Severi Salminen]], [[CCC]], January 04, 2001
 
* [https://www.stmintz.com/ccc/index.php?id=147977 About SEE] by [[Severi Salminen]], [[CCC]], January 04, 2001
 
* [https://www.stmintz.com/ccc/index.php?id=152256 Should an engine using SEE beat another not using it?] by [[Severi Salminen]], [[CCC]], January 27, 2001
 
* [https://www.stmintz.com/ccc/index.php?id=152256 Should an engine using SEE beat another not using it?] by [[Severi Salminen]], [[CCC]], January 27, 2001
* [https://www.stmintz.com/ccc/index.php?id=161209 SEE and possible EXChess bug] by [[Gian-Carlo Pascutto]], [[CCC]], April 01, 2001 » [[EXchess]] <ref>[https://www.stmintz.com/ccc/index.php?id=162704 EXchess v4.02 released] by [[Dan Homan]], [[CCC]], April 10, 2001</ref>
+
* [https://www.stmintz.com/ccc/index.php?id=161209 SEE and possible EXChess bug] by [[Gian-Carlo Pascutto]], [[CCC]], April 01, 2001 » [[EXchess]] <ref>[https://www.stmintz.com/ccc/index.php?id=162704 EXchess v4.02 released] by [[Daniel Homan]], [[CCC]], April 10, 2001</ref>
 
* [https://www.stmintz.com/ccc/index.php?id=179023 Static Exchange Eval (SEE)] by [[Leen Ammeraal]], [[CCC]], July 10, 2001
 
* [https://www.stmintz.com/ccc/index.php?id=179023 Static Exchange Eval (SEE)] by [[Leen Ammeraal]], [[CCC]], July 10, 2001
 
* [https://www.stmintz.com/ccc/index.php?id=178979 Static Exchange Eval] by [[Artem Petakov|Artem Pyatakov]], [[CCC]], August 02, 2001
 
* [https://www.stmintz.com/ccc/index.php?id=178979 Static Exchange Eval] by [[Artem Petakov|Artem Pyatakov]], [[CCC]], August 02, 2001
Line 95: Line 96:
 
* [https://www.stmintz.com/ccc/index.php?id=262577 Static exchange evaluator and 0x88] by Pierre Bokma, [[CCC]], October 30, 2002
 
* [https://www.stmintz.com/ccc/index.php?id=262577 Static exchange evaluator and 0x88] by Pierre Bokma, [[CCC]], October 30, 2002
 
'''2003'''
 
'''2003'''
* [https://www.stmintz.com/ccc/index.php?id=311899 Static Exchange Evaluation (SEE) for pruning in quiescence (?)] by [[Omid David]], [[CCC]], August 19, 2003
+
* [https://www.stmintz.com/ccc/index.php?id=311899 Static Exchange Evaluation (SEE) for pruning in quiescence (?)] by [[Eli David|Omid David]], [[CCC]], August 19, 2003
 
* [https://www.stmintz.com/ccc/index.php?id=330947 table-based SEE or "evaluation in rebel (hanging pieces)"] by [[Martin Fierz]], [[CCC]], November 27, 2003 » [[Hanging Piece]], [[Rebel]]
 
* [https://www.stmintz.com/ccc/index.php?id=330947 table-based SEE or "evaluation in rebel (hanging pieces)"] by [[Martin Fierz]], [[CCC]], November 27, 2003 » [[Hanging Piece]], [[Rebel]]
 
'''2004'''
 
'''2004'''
Line 120: Line 121:
 
==2010 ...==  
 
==2010 ...==  
 
* [http://www.talkchess.com/forum/viewtopic.php?t=31464 SEE Improvement Idea] by [[Mark Lefler]], [[CCC]], January 04, 2010
 
* [http://www.talkchess.com/forum/viewtopic.php?t=31464 SEE Improvement Idea] by [[Mark Lefler]], [[CCC]], January 04, 2010
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=31776 GetSmallestAttacker() in 16x12 board representation] by metax, [[CCC]], January 17, 2010 » [[Piece-Lists]]
 
'''2011'''
 
'''2011'''
 
* [http://www.talkchess.com/forum/viewtopic.php?t=37514 Using SEE to prune in main search] by [[Tom King]], [[CCC]], January 08, 2011 » [[Pruning]], [[Reductions]]
 
* [http://www.talkchess.com/forum/viewtopic.php?t=37514 Using SEE to prune in main search] by [[Tom King]], [[CCC]], January 08, 2011 » [[Pruning]], [[Reductions]]
Line 138: Line 140:
 
* [http://www.talkchess.com/forum/viewtopic.php?t=57548 Magic SEE] by [[Harm Geert Muller]], [[CCC]], September 07, 2015
 
* [http://www.talkchess.com/forum/viewtopic.php?t=57548 Magic SEE] by [[Harm Geert Muller]], [[CCC]], September 07, 2015
 
* [http://www.talkchess.com/forum/viewtopic.php?t=64166 Problems with SEE] by [[Matthew R. Brades]], [[CCC]], June 03, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=64166 Problems with SEE] by [[Matthew R. Brades]], [[CCC]], June 03, 2017
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=64827 Evasion (capture) moves ordering by See] by [[Tamás Kuzmics]], [[CCC]], August 06, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65836 see] by [[Folkert van Heusden]], [[CCC]], November 28, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65836 see] by [[Folkert van Heusden]], [[CCC]], November 28, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65982 Poor man's SEE] by [[Harm Geert Muller]], [[CCC]], December 11, 2017
 
* [http://www.talkchess.com/forum/viewtopic.php?t=65982 Poor man's SEE] by [[Harm Geert Muller]], [[CCC]], December 11, 2017
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=69301 Fast SEE (Ed's lookup revisited)] by [[Harm Geert Muller]], [[CCC]], December 17, 2018 » [[Attack and Defend Maps#EDsLookup|Ed's lookup]]
 +
==2020 ...==
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=72862 SEE versus SEE_GE] by [[Vivien Clauzon]], [[CCC]], January 21, 2020
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=76750 SEE (Static Exchange Evaluation) pruning nodes] by [[Marcel Vanthoor]], [[CCC]], March 01, 2021
 +
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77787 Static exchange evaluation with promotion] by Guido Flohr, [[CCC]], July 23, 2021
 +
* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=78477 Static Exchange Evaluation without bitboards] by Jonathan McDermid, [[CCC]], October 22, 2021
 +
* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79077 Move ordering using SEE] by Christian Dean, [[CCC]], January 08, 2022
 +
* [https://www.talkchess.com/forum3/viewtopic.php?f=7&t=79936 Request for thoughts: SEE "Test Set"] by [[Andrew Grant]], [[CCC]], May 24, 2022
  
 
=External Links=  
 
=External Links=  
 +
* [https://web.archive.org/web/20071027170528/http://www.brucemo.com/compchess/programming/quiescent.htm#SEE SEE] from [https://web.archive.org/web/20071026090003/http://www.brucemo.com/compchess/programming/index.htm Bruce Moreland's Programming Topics] ([https://en.wikipedia.org/wiki/Wayback_Machine Wayback Machine])
 
* [http://mediocrechess.blogspot.com/2007/03/guide-static-exchange-evaluation-see.html Static exchange evaluation (SEE)] from [http://mediocrechess.varten.org/index.html Mediocre Chess] by [[Jonatan Pettersson]]
 
* [http://mediocrechess.blogspot.com/2007/03/guide-static-exchange-evaluation-see.html Static exchange evaluation (SEE)] from [http://mediocrechess.varten.org/index.html Mediocre Chess] by [[Jonatan Pettersson]]
 
* [http://www.chessprogramming.net/computerchess/static-exchange-evaluation-in-chess/ Static Exchange Evaluation in Chess] by [[Steve Maughan]], [http://www.chessprogramming.net/ Chess Programming Blog], July 9, 2013
 
* [http://www.chessprogramming.net/computerchess/static-exchange-evaluation-in-chess/ Static Exchange Evaluation in Chess] by [[Steve Maughan]], [http://www.chessprogramming.net/ Chess Programming Blog], July 9, 2013
 +
* [[:Category:Wolfgang Schmid|Wolfgang Schmid]] - Ringading Dang, [https://play.google.com/store/music/album?id=B4j7q7gplpdq4ibqno2twclf7si&tid=song-Trie7zbkahun3mi7yaz4hynimze&hl=en Special Kick] (2002),  [https://en.wikipedia.org/wiki/YouTube YouTube] Video
 +
: feat.: [[:Category:Joo Kraus|Joo Kraus]], [https://de.wikipedia.org/wiki/Libor_%C5%A0%C3%ADma Libor Shima], [https://de.wikipedia.org/wiki/Peter_W%C3%B6lpl Peter Wölpl], [[:Category:Marco Minnemann|Marco Minnemann]]
 +
: {{#evu:https://www.youtube.com/watch?v=GVGZe69X8K0|alignment=left|valignment=top}}
 +
 +
 +
==Test suites==
 +
* [https://github.com/jdart1/arasan-chess/blob/master/src/unit.cpp unit.cpp by [[Jon Dart]]
 +
* [https://github.com/lithander/Leorik/blob/master/Leorik.Test/see.epd see.epd by [[Thomas Jahn]]
  
 
=References=  
 
=References=  
 
<references />
 
<references />
 
 
'''[[Move Ordering|Up one level]]'''
 
'''[[Move Ordering|Up one level]]'''
 +
[[Category:Wassily Kandinsky]]
 +
[[Category:Joo Kraus]]
 +
[[Category:Wolfgang Schmid]]
 +
[[Category:Marco Minnemann]]

Latest revision as of 09:43, 1 August 2022

Home * Search * Move Ordering * Static Exchange Evaluation

Wassily Kandinsky - Small Worlds IX [1]

A Static Exchange Evaluation (SEE) examines the consequence of a series of exchanges on a single square after a given move, and calculates the likely evaluation change (material) to be lost or gained, Donald Michie coined the term swap-off value. A positive static exchange indicates a "winning" move. For example, PxQ will always be a win, since the Pawn side can choose to stop the exchange after its Pawn is recaptured, and still be ahead. Some programs optimize the SEE function to only return a losing or equal/winning flag, since they only use SEE to determine if a move is worth searching and do not need the actual value. SEE is useful in move ordering, futility pruning and especially in quiescence search in conjunction with delta pruning, as well to reduce "bad" captures and checks [2] .

Implementation

A didactic recursive implementation of SEE is shown below [3] . In most programs, however, an iterative version is used, as demonstrated in SEE - The Swap Algorithm with bitboards. In CCC, Harm Geert Muller deduced an iterative SEE approach directly from Alpha-Beta [4] .

int see(int square, int side)
{
   value = 0;
   piece = get_smallest_attacker(square, side);
   /* skip if the square isn't attacked anymore by this side */
   if ( piece )
   {
      make_capture(piece, square);
      /* Do not consider captures if they lose material, therefor max zero */
      value = max (0, piece_just_captured() -see(square, other(side)) );
      undo_capture(piece, square);
   }
   return value;
}

This uses a trick, equivalent to negamax in tree search, where the loss for the current side is the gain for the opposite side. This can be seen in the expression piece_just_captured() - see(square); which is the value of the piece captured (piece_just_captured()) minus the gain that the opponent might make after the move by recapturing. If that term becomes negative, one would better choose standing pat rather than to capture, which can be done by a conditional assignment, or by a max function with zero as second argument.

Seeing a Capture

To statically evaluate a capture, that particular capture should be forced, because it might not be the lowest attacker that makes the capture, and must not allow the option of standing pat [5] .

int seeCapture(int from, int to, int side)
{
   value = 0;
   piece = board[from];

   make_capture(piece, to);
   value = piece_just_captured() - see(to, other(side));
   undo_capture(piece, to);
   return value;
}

SOMA

Instead of using a quiescence search, some (early) chess programs aimed to determine the material balance of a position by a static analysis of all possible capture-move sequences. These routines are often referred to as SOMA (Swapping Off Material Analyzer) [6] based on the swap-off algorithm used in the one-ply analyzing "paper machine" SOMA by evolutionary biologist John Maynard Smith, the Smith One-Move Analyzer designed in the early 60s [7] .

See also

Swap-off algorithm

Publications

Forum Posts

1990 ...

1995 ...

Re: MVV/LVA vs SEE move ordering - more test results by Brian Sheppard, rgcc, August 27, 1995

2000 ...

2001

Re: I want to SEE by Matthias Gemuh, CCC, December 21, 2001

2002

2003

2004

2005 ...

2007

2008

2009

2010 ...

2011

2013

2014

2015 ...

2020 ...

External Links

feat.: Joo Kraus, Libor Shima, Peter Wölpl, Marco Minnemann


Test suites

References

Up one level