Difference between revisions of "Static Exchange Evaluation"
GerdIsenberg (talk | contribs) |
(→External Links) |
||
(9 intermediate revisions by 2 users 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 ...== | ||
* [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 | ||
+ | * [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 | * [[: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.: [ | + | : 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}} | ||
+ | |||
+ | |||
+ | ==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= | ||
Line 157: | Line 169: | ||
'''[[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]] |
Latest revision as of 09:43, 1 August 2022
Home * Search * Move Ordering * Static Exchange Evaluation
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] .
Contents
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
- Negamax
- Futility Pruning
- Delta Pruning
- Guard Heuristic
- Quiescence Search
- MVV-LVA
- Ed's Lookup from Attack and Defend Maps
- SEE - The Swap Algorithm with Bitboards
- SOMA
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
Forum Posts
1990 ...
- efficient algorithm for safety of pieces by Deniz Yuret, rgc, March 18, 1993
- Computer Chess: swap down evaluators vs capture search by Jon Dart, rgc, October 24, 1994
1995 ...
- mvv/lva vs SEE capture ordering test results by Robert Hyatt, rgcc, August 10, 1995
- MVV/LVA vs SEE move ordering - more test results by Robert Hyatt, rgcc, August 25, 1995
- Re: MVV/LVA vs SEE move ordering - more test results by Brian Sheppard, rgcc, August 27, 1995
- MVV/LVA and SEE - what do they mean? by Peter Kappler, rgcc, August 28, 1995 » MVV/LVA
- Quiescence vs swapoff by Peter Fendrich, CCC, April 15, 1998
- Question about static exchange evaluation by Larry Coon, CCC, November 12, 1998
- Help with Static Exchange Evaluator by William Bryant, CCC, July 18, 1999
- SEE for forward pruning in Q. Search by Tom King, CCC, August 04, 1999 » Quiescence Search
- SEE for forward pruning in the Q. search - I'm confused! by Tom King, CCC, August 11, 1999
2000 ...
- Re: Explain SEE (static exchange evaluator)? by Bruce Moreland, CCC, October 25, 2000
- Qsearch problems...(about sorting and SEE) by Severi Salminen, CCC, November 26, 2000 » Quiescence Search
- MVV/LVA or SEE - liability? by Severi Salminen, CCC, November 29, 2000 » MVV-LVA
2001
- About SEE by Severi Salminen, CCC, January 04, 2001
- Should an engine using SEE beat another not using it? by Severi Salminen, CCC, January 27, 2001
- SEE and possible EXChess bug by Gian-Carlo Pascutto, CCC, April 01, 2001 » EXchess [11]
- Static Exchange Eval (SEE) by Leen Ammeraal, CCC, July 10, 2001
- Static Exchange Eval by Artem Pyatakov, CCC, August 02, 2001
- I want to SEE by Matthias Gemuh, CCC, December 21, 2001
- Re: I want to SEE by Matthias Gemuh, CCC, December 21, 2001
2002
- Value of King in SEE by David Rasmussen, CCC, January 07, 2002
- Static exchange evaluator and 0x88 by Pierre Bokma, CCC, October 30, 2002
2003
- Static Exchange Evaluation (SEE) for pruning in quiescence (?) by Omid David, CCC, August 19, 2003
- table-based SEE or "evaluation in rebel (hanging pieces)" by Martin Fierz, CCC, November 27, 2003 » Hanging Piece, Rebel
2004
- A SIMD idea, eg. Piece/Gain of a capture target by Gerd Isenberg, CCC, January 21, 2004
- SEE and FH-% by Renze Steenhuisen, CCC, March 30, 2004
- SEE results by Stuart Cracraft, CCC, August 10, 2004
- SEE and pin detection by Dan Honeycutt, CCC, August 30, 2004 » Pin
- Pin aware SEE by Dan Honeycutt, CCC, October 03, 2004
2005 ...
- Help on how to implement move ordering with a Static Exchange Evaluator by Carlos Magno, CCC, February 09, 2005
- Static Exchange Evaluation Methods by Pradu Kannan, Winboard Forum, March 14, 2005
2007
- SEE with magic bitboards by Pradu Kannan, Winboard Forum, January 24, 2007 » Magic Bitboards
- SEE on non-capture moves in main search by Gary, CCC, March 28, 2007 » Move Ordering
- How good is your SEE? by mjlef, Winboard Forum, April 24, 2007
- Re: Movei added to Crafty vs Rybka comparison data by Edsel Apostol, CCC, June 06, 2007
- SEE algorithm by Robert Pope, CCC, December 02, 2007
2008
- SEE problem by Tord Romstad, CCC, April 13, 2008
- How is SEE used? by Mathieu Pagé, CCC, October 13, 2008
2009
- SEE Observation by Brian Richardson, CCC, August 02, 2009 » Tinker
- SEE algorithm on chessprogramming wiki by Sven Schüle, CCC, December 02, 2009
2010 ...
- SEE Improvement Idea by Mark Lefler, CCC, January 04, 2010
- GetSmallestAttacker() in 16x12 board representation by metax, CCC, January 17, 2010 » Piece-Lists
2011
- Using SEE to prune in main search by Tom King, CCC, January 08, 2011 » Pruning, Reductions
- Simple question about SEE by Andres Valverde, CCC, January 12, 2011
- Implementing SEE by colin, CCC, Aug 12, 2011
- SEE with alpha beta by Onno Garms, CCC, August 14, 2011 » Onno
- Reducing/Pruning Bad Captures (SEE < 0) by Edsel Apostol, CCC, August 19, 2011 » Reductions, Pruning
- question about SEE by Alberto Sanjuan, CCC, September 05, 2011
2013
- SEE by Rasjid Chan, CCC, February 25, 2013
- Static Exchange Evaluation... by Steve Maughan, CCC, July 10, 2013 [12]
- SEE() is slow and SEE() is fast by Steven Edwards, CCC, August 09, 2013
2014
- SEE by Richard Delorme, CCC, February 13, 2014
- SEE logic by Youri Matiounine, CCC, March 08, 2014 » Piece-Square Tables
2015 ...
- SEE Map by Matthew Lai, CCC, July 20, 2015 [13]
- Magic SEE by Harm Geert Muller, CCC, September 07, 2015
- Problems with SEE by Matthew R. Brades, CCC, June 03, 2017
- Evasion (capture) moves ordering by See by Tamás Kuzmics, CCC, August 06, 2017
- see by Folkert van Heusden, CCC, November 28, 2017
- Poor man's SEE by Harm Geert Muller, CCC, December 11, 2017
- Fast SEE (Ed's lookup revisited) by Harm Geert Muller, CCC, December 17, 2018 » Ed's lookup
2020 ...
- SEE versus SEE_GE by Vivien Clauzon, CCC, January 21, 2020
- SEE (Static Exchange Evaluation) pruning nodes by Marcel Vanthoor, CCC, March 01, 2021
- Static exchange evaluation with promotion by Guido Flohr, CCC, July 23, 2021
- Static Exchange Evaluation without bitboards by Jonathan McDermid, CCC, October 22, 2021
- Move ordering using SEE by Christian Dean, CCC, January 08, 2022
- Request for thoughts: SEE "Test Set" by Andrew Grant, CCC, May 24, 2022
External Links
- SEE from Bruce Moreland's Programming Topics (Wayback Machine)
- Static exchange evaluation (SEE) from Mediocre Chess by Jonatan Pettersson
- Static Exchange Evaluation in Chess by Steve Maughan, Chess Programming Blog, July 9, 2013
- Wolfgang Schmid - Ringading Dang, Special Kick (2002), YouTube Video
- feat.: Joo Kraus, Libor Shima, Peter Wölpl, Marco Minnemann
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
- ↑ Wassily Kandinsky - Small Worlds IX, 1922, Metropolitan Museum of Art
- ↑ Reducing/Pruning Bad Captures (SEE < 0) by Edsel Apostol, CCC, August 19, 2011
- ↑ SEE algorithm on chessprogramming wiki by Sven Schüle, CCC, December 02, 2009
- ↑ Re: SEE algorithm on chessprogramming wiki by Harm Geert Muller, CCC, December 20, 2009
- ↑ Re: Simple question about SEE by Harm Geert Muller, CCC, January 12, 2011
- ↑ Hiroyuki Iida, Makoto Sakuta, Jeff Rollason (2002). Computer Shogi. Artificial Intelligence, Vol. 134, Elsevier, CiteSeerX
- ↑ John Maynard Smith, Donald Michie (1961). Machines that play games. New Scientist, 12, 367-9. google books
- ↑ see Swap-off by Helmut Richter
- ↑ Sargon Z80 assembly listing by Dan and Kathe Spracklen, hosted by Andre Adrian, see XCHNG
- ↑ Looking for Alternatives to Quiescence Search by Jeff Rollason, AI Factory, December 2006
- ↑ EXchess v4.02 released by Daniel Homan, CCC, April 10, 2001
- ↑ Static Exchange Evaluation in Chess by Steve Maughan, Chess Programming Blog, July 9, 2013
- ↑ Russell M. Church, Kenneth W. Church (1977). Plans, Goals, and Search Strategies for the Selection of a Move in Chess. Chess Skill in Man and Machine