Difference between revisions of "Static Exchange Evaluation"

From Chessprogramming wiki
Jump to: navigation, search
(3 intermediate revisions by the same user not shown)
Line 121: 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 139: 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]]
 
* [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 ...==
 
 
==2020 ...==
 
==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=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
  
 
=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
 
* [[: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.: [https://de.wikipedia.org/wiki/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]]
+
: 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}}
 
: {{#evu:https://www.youtube.com/watch?v=GVGZe69X8K0|alignment=left|valignment=top}}
  
Line 157: Line 160:
 
'''[[Move Ordering|Up one level]]'''
 
'''[[Move Ordering|Up one level]]'''
 
[[Category:Wassily Kandinsky]]
 
[[Category:Wassily Kandinsky]]
 +
[[Category:Joo Kraus]]
 
[[Category:Wolfgang Schmid]]
 
[[Category:Wolfgang Schmid]]
 
[[Category:Marco Minnemann]]
 
[[Category:Marco Minnemann]]

Revision as of 20:14, 2 March 2021

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

References

Up one level