Difference between revisions of "Static Exchange Evaluation"

From Chessprogramming wiki
Jump to: navigation, search
(One intermediate revision by the same user not shown)
Line 149: Line 149:
 
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=77787 Static exchange evaluation with promotion] by Guido Flohr, [[CCC]], July 23, 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=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
  
 
=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])
+
* [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

Revision as of 16:18, 15 January 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

References

Up one level