Static_Exchange_Evaluation - peregrineshahin/ChessProgrammingWiki GitHub Wiki

title: Static Exchange Evaluation

Home * Search * Move Ordering * Static Exchange Evaluation

[_MET_DP855300.jpg) 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] .

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] .

Publications

John Maynard Smith, Donald Michie (1961). Machines that play games. New Scientist, 12, 367-9. google books » SOMA
Donald Michie (1966). Game Playing and Game Learning Automata. Advances in Programming and Non-Numerical Computation, Leslie Fox (ed.), pp. 183-200. Oxford, Pergamon. » Includes Appendix: Rules of SOMAC by John Maynard Smith [8]
Donald Michie (1974). On Machine Intelligence. Edinburgh: University Press, ISBN 10: 085224262X, ISBN 13: 9780852242629, abebooks.com, alibris.com, biblio.com
Dan Spracklen, Kathe Spracklen (1978). An Exchange Evaluator for Computer Chess. BYTE, Vol. 3, No. 11 [9]
David Levy (1979). Chess Programming - Before You Begin. Personal Computer World, May 1979
Jeff Rollason (2000). SUPER-SOMA - Solving Tactical Exchanges in Shogi without Tree Searching. Lecture Notes In Computer Science; Vol. 2063, CG 2000, Word preprint[10]
Hiroyuki Iida, Makoto Sakuta, Jeff Rollason (2002). Computer Shogi. Artificial Intelligence, Vol. 134, Elsevier, CiteSeerX
Fritz Reul (2009). New Architectures in Computer Chess, Ph.D. Thesis, Chapter 4, Static Exchange Evaluation, pdf
Fritz Reul (2010). Static Exchange Evaluation with αβ-Approach. ICGA Journal, Vol. 33, No. 1