Home * Search * Move Ordering * Static Exchange Evaluation
wassily-kandinsky_dreissig.jpg

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 [1] .
Wassily Kandinsky - Dreißig [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


Publications


Forum Posts

1990 ...

1995 ...

2000 ...

2005 ...

2010 ...


External Links


References

  1. ^ Reducing/Pruning Bad Captures (SEE < 0) by Edsel Apostol, CCC, August 19, 2011
  2. ^ Wassily Kandinsky - Dreißig - Art Print
  3. ^ SEE algorithm on chessprogramming wiki by Sven Schüle, CCC, December 02, 2009
  4. ^ Re: SEE algorithm on chessprogramming wiki by Harm Geert Muller, CCC, December 20, 2009
  5. ^ Re: Simple question about SEE by Harm Geert Muller, CCC, January 12, 2011
  6. ^ Hiroyuki Iida, Makoto Sakuta, Jeff Rollason (2002). Computer Shogi. Artificial Intelligence, Vol. 134, Elsevier, CiteSeerX
  7. ^ John Maynard Smith, Donald Michie (1961). Machines that play games. New Scientist, 12, 367-9. google books
  8. ^ see Swap-off by Helmut Richter
  9. ^ Sargon Z80 assembly listing by Dan and Kathe Spracklen, hosted by Andre Adrian, see XCHNG
  10. ^ Looking for Alternatives to Quiescence Search by Jeff Rollason, AI Factory, December 2006
  11. ^ EXchess v4.02 released by Dan Homan, CCC, April 10, 2001
  12. ^ Static Exchange Evaluation in Chess by Steve Maughan, Chess Programming Blog, July 9, 2013

What links here?


Up one level