Wikispaces : chessprogramming - items matching description

Algebraic Chess Notation

GerdIsenberg — Mon, 25 Sep 2017 21:28:07 GMT

Home * Chess * Game * Algebraic Chess Notation

Algebraic Chess Notation is a chess notation to record and represent moves of a human readable game notation. It is based on a system developed by Philipp Stamma to notate the target square by algebraic coordinates, and various forms to represent the origin square of the move, either by language dependent piece initials and/or file, rank- or square notation of the from- or origin square. Promotions must be disambiguated by including the promoted piece type, and castling usually has their own symbol strings ('O-O', 'O-O-O'). Some format variations also specify a captured piece, if any, for the purpose to make the notation reversible, and to go backward as easy as forward while re-playing a game.

Chess programs need to convert the list of encoded moves into a sequence of printable strings, or to render them inside a notation window. The move number of the game, starting by '1.' from the initial position, is prefix of the white halfmove, followed by a the black reply, often in a second column of a grid view. If a move notation starts with Black, also after embedded comments or annotations, a trailing ellipsis is used instead of a single dot.

<move> ::= <move number><move descriptor>
<move number> ::= <digit>[<digit>...]{'.' | '...'}

Modern chess programs, and their graphical user interface often support various modes to represent all kinds of game and move notations. Regarding input of moves from a user interface, or reading moves from text files, programs needs to parse strings accordantly.

Pure coordinate notation

Considering the common From-To move encoding inside a chess program, pure coordinate notation is a straight-forward chess notation to use only algebraic From- and To-coordinates. This notation omits any machine redundant piece letters for the moving and/or capturing pieces, and only has to specify the promoted piece as trailing letter in case of promotions.

<move descriptor> ::= <from square><to square>[<promoted to>]
<square>        ::= <file letter><rank number>
<file letter>   ::= 'a'|'b'|'c'|'d'|'e'|'f'|'g'|'h'
<rank number>   ::= '1'|'2'|'3'|'4'|'5'|'6'|'7'|'8'
<promoted to>   ::= 'q'|'r'|'b'|'n'

Pure algebraic coordinate notation was often used in early microcomputer chess programs, sometimes even with capital file letters. Some programs used a hyphen or 'x' delimiter between the coordinate substrings to distinguish quiet moves from captures in move outputs. While not common in human chess notation, pure coordinate notation has the advantage to avoid any ambiguity and is further easy convertible from a move list without the need of retrieving information from internal board representations, (i.e. which pieces occupy which squares). Even castling was often written as E1G1 or E1C1 instead of 'O-O' or 'O-O-O'.

XBoard

Per default, the Chess Engine Communication Protocol requires pure algebraic coordinate notation without from-to delimiters as input and output move format ^[1] .

UCI

The UCI communication protocol requires pure algebraic coordinate notation without from-to delimiters as well. Inside its specification the UCI move format is called "long algebraic notation" ^[2] , which might be considered slightly incorrect concerning leading piece character and dash or hyphen between from- and to coordinates, see LAN definition below.

Output Samples


8080 Chess Display ^[3]		Kempelen move list ^[4]

ICCF numeric notation

The language independent ICCF numeric notation as used in Correspondence chess is a numerical pure coordinate notation, giving coordinates by two digits (File '1'-'8) rather than letters ('a'-'h') for the file. In case of promotions a fifth trailing digit is used: '1' for queen, '2' for rook, '3' for bishop and '4' for knight.

Smith notation

The Smith notation designed by Warren D. Smith ^[5] , as used in the Internet Chess Club chess server, encodes moves with from-square, to-square, and to make it reversible, so it is as easy to go backwards in a game as forwards, what piece was captured, if any:

<Smith move descriptor> ::= <from square><to square>[<capture indicator>][<promoted to>]
<capture indicator> ::=  'P' | 'N' | 'B' | 'R' | 'Q'

Long Algebraic Notation (LAN)

Beside the already sufficient and unambiguous pure origin- and target-coordinates, LAN uses a leading redundant, national dependent uppercase piece letter or figurine piece symbol of the moving piece usually other than a pawn, to represent the move, which makes it more human readable and compatible with SAN and desciptive notation. However, for chess programs using pure from-to move encoding, converting the move list to LAN already requires a board representation in sync with the leading moves already played, to lookup the piece on the board.

<LAN move descriptor piece moves> ::= <Piece symbol><from square>['-'|'x']<to square>
<LAN move descriptor pawn moves>  ::= <from square>['-'|'x']<to square>[<promoted to>]
<Piece symbol> ::= 'N' | 'B' | 'R' | 'Q' | 'K'

English symbols Knight, Bishop, Rook, Queen and King.

Aart Bik's Chess for Android, G1 version with LAN representation ^[6]

Standard Algebraic Notation (SAN)

Standard algebraic notation (SAN) is the official notation of the FIDE which must be used in all recognized international competition involving human players ^[7] . Concerning computer chess, SAN is a representation standard for chess moves inside the Portable Game Notation standard using the ASCII Latin alphabet ^[8], and should be supported as default notation by all modern chess programs and their user interfaces ^[9].

Aart Bik's Chess for Android, latest version in SAN mode ^[10]

While otherwise similar to LAN, SAN suppresses redundant information concerning the from-square, while keeping the descriptive letter or symbol of pieces other than a pawn. SAN further suppresses the from-to hyphen, and in some variations also the capture indicator 'x' (or ':').

<SAN move descriptor piece moves>   ::= <Piece symbol>[<from file>|<from rank>|<from square>]['x']<to square>
<SAN move descriptor pawn captures> ::= <from file>[<from rank>] 'x' <to square>[<promoted to>]
<SAN move descriptor pawn push>     ::= <to square>[<promoted to>]

Ambiguities

If the piece is sufficient to unambiguously determine the origin square, the whole from square is omitted. Otherwise, if two (or more) pieces of the same kind can move to the same square, the piece's initial is followed by (in descending order of preference)

file of departure if different
rank of departure if the files are the same but the ranks differ
the complete origin square coordinate otherwise

Captures

Captures are denoted by the lower case letter "x" immediately prior to the destination square. Pawn captures with the omitted piece symbol, include the file letter of the originating square of the capturing pawn prior to the "x" character, even if not required for unambiguousness. Some SAN variations in printed media even omit the target rank if unambiguous, like dxe, which might not be accepted as input format.

En passant

The PGN-Standard does not require En passant captures have any special notation, and is written as if the captured pawn were on the capturing pawn's destination square.FIDE states the redundant move suffix "e.p." optional (after 1 July 2014) ^[11].

In the case of an ‘en passant’ capture, ‘e.p.’ may be appended to the notation.

Pawn promotion

A pawn promotion requires the information about the chosen piece, appended as trailing Piece letter behind the target square. The SAN PGN-Standard requires an equal sign ('=') immediately following the destination square.

Castling

Castling is indicated by the special notations, "O-O" for kingside castling and "O-O-O" for queenside castling. While the FIDE handbook ^[12] uses the digit zero, the SAN PGN-Standard requires the capital letter 'O' for its export format.

Converting Moves

Due to the most compact representation, considering ambiguities concerning the origin square, converting moves with pure from- and to-squares to SAN requires not only an underlying board representation to determine piece initials, but also legal move generation for a subset of moves to the destination square. Pseudo legal, but illegal moves for instance with a Pinned piece must not be considered in ambiguous issues in an export format.

XBoard 2

With the Chess Engine Communication Protocol version 2, one can use the feature command to select SAN as move format for both input and output ^[13] .

Figurine Algebraic Notation (FAN)

Figurine notation uses miniature piece icons instead of single letter piece abbreviations. This enables the moves to be read independent of the language. The Unicode Miscellaneous Symbols set includes all of the symbols necessary for FAN if appropriate fonts were installed on the computer ^[14] . Chess GUIs may alternatively use Scalable Vector Graphics or other scalable 2D Vector Graphics to render the symbols inside their views.

Vector Graphics

IsiChess, notation window with figurine LAN, using 2D Vector Graphics, see sample code

LaTeX

FAN in LaTeX ^[15]

Reading Chess

In an attempt of Computer vision, Henry S. Baird and Ken Thompson used optical character recognition along with various heuristics and applying the rules of chess, to "read" the figurine notation from Informant's Encyclopaedia of Chess Openings with high accuracy and a success rate of 99.995% on approximately one million characters (2850 games, 945 pages) ^[16] .

Publications

Henry S. Baird, Ken Thompson (1990). Reading Chess. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12, No. 6, pdf
Michel Goossens, Frank Mittelbach, Sebastian Rahtz, Denis Roegel, Herbert Voß (2007). The LATEXGraphics Companion. Second Edition, Addison-Wesley, ISBN-13: 978-0-321-50892-8, sample pdf, 10.1 Chess, 10.2 Xiangqi—Chinese Chess ^[17]

Forum Posts

correct SAN notation ? by Andreas Herrmann, CCC, December 19, 2002
Crafty (under winboard) question by Andrei Fortuna, CCC, December 21, 2003 » WinBoard
SAN Move Disambiguation -- looking for test positition by humble programmer, CCC, April 12, 2010 » PGN
Unicode values for chessmen by Steven Edwards, CCC, March 07, 2011
Determining From squares by David Whitten, CCC, December 04, 2011
What world have I been in - castling notation? by Lonnie Cook, CCC, September 13, 2014
SAN test position by Matthew Lai, CCC, September 11, 2016 » SAN
WAC using coordinate notation? by Erin Dame, CCC, September 17, 2017 » Pure coordinate notation, Win at Chess

External Links

Algebraic chess notation from Wikipedia
Desciptive notation from Wikipedia
Punctuation (chess) from Wikipedia
Chess symbols in Unicode from Wikipedia
Standard: Portable Game Notation Specification and Implementation Guide by Steven Edwards - 8.2.3: Movetext SAN (Standard Algebraic Notation)
SAN Kit: Implemented Standards for Chess Move Notation by Steven Edwards
FIDE handbook, Laws of Chess - Appendix C. Algebraic notation

References

^ Chess Engine Communication Protocol: 8. Commands from xboard to the engine
^ The UCI Specification
^ Processor Technology 8080 CHESS User's Manual. pdf, pdf
^ Kempelen Chess from Sierra Online from The Spacious Mind
^ Smith notation
^ Aart's Android Page
^ FIDE handbook, Laws of Chess - Appendix C. Algebraic notation
^ Standard: Portable Game Notation Specification and Implementation Guide by Steven Edwards - 8.2.3: Movetext SAN (Standard Algebraic Notation)
^ SAN Kit: Implemented Standards for Chess Move Notation by Steven Edwards
^ Aart's Android Page
^ FIDE handbook, Laws of Chess - Appendix C. Algebraic notation, C-9
^ FIDE handbook, Laws of Chess - Appendix C. Algebraic notation - C.13 Abbreviations
^ Chess Engine Communication Protocol: 9. Commands from the engine to xboard
^ Unicode values for chessmen by Steven Edwards, CCC, March 07, 2011
^ Michel Goossens, Frank Mittelbach, Sebastian Rahtz, Denis Roegel, Herbert Voß (2007). The LATEXGraphics Companion. Second Edition, Addison-Wesley, ISBN-13: 978-0-321-50892-8, sample pdf, 10.1 Chess, 10.2 Xiangqi—Chinese Chess
^ Henry S. Baird, Ken Thompson (1990). Reading Chess. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 12, No. 6, pdf
^ LaTeX from Wikipedia

What links here?

Page	Date Edited
2D Graphics Board	Sep 23, 2017
Acornsoft Chess	Dec 11, 2016
Algebraic Chess Notation	Sep 25, 2017
Andreas Herrmann	Nov 7, 2014
Andrei Fortuna	Mar 6, 2014
Arena	Mar 16, 2018
Atom Chess	Dec 11, 2016
Captures	Oct 1, 2017
Castling	May 5, 2017
CHEKMO-II	Jan 3, 2018
Cheops (Miller)	Jan 13, 2017
Chess Game	Mar 28, 2017
CPW-Engine_algebraic	May 15, 2011
Dictionary	Aug 24, 2017
En passant	Jan 16, 2018
Encoding Moves	Mar 27, 2016
Entering Moves	Sep 7, 2017
Extended Position Description	Dec 2, 2017
Forsyth-Edwards Notation	Sep 10, 2017
Game Notation	Jan 11, 2018
Graphics Programming	Dec 22, 2017
GUI	Mar 16, 2018
HAL	Jun 14, 2016
Jester US	Sep 15, 2017
Ken Thompson	Sep 8, 2017
Mathematician	Apr 9, 2018
Matthew Lai	Dec 6, 2017
Megachess	Aug 1, 2016
Moves	Feb 19, 2018
Myopic	Nov 11, 2016
Origin Square	Oct 10, 2016
Piece Recognition	Sep 8, 2017
Portable Game Notation	Jan 11, 2018
Promotions	Jun 6, 2017
python-chess	Nov 4, 2017
SolusChess	Apr 21, 2015
Squares	Feb 15, 2015
Test-Positions	Feb 25, 2018
User Interface	Feb 21, 2018
Warren D. Smith	Sep 12, 2015
Win at Chess	Sep 25, 2017

Up one Level

Best Move

GerdIsenberg — Mon, 15 May 2017 18:23:18 GMT

Home * Chess * Moves * Best Move

The Best Move is a Search related issue.

The Best Move in the context of search algorithms like Alpha-Beta or Principal Variation Search, is found at the root or any other confirmed PV-node. It is that move which gained the maximum score, which is exact since it exceeds alpha but is still below beta and therefor not good enough to refute opponent's previous move, which may become his best move and part of the principal variation as well.

Best so far

If an alpha increase occurs, the recently searched move is the best so far and needs to be stored on an explicit or implicit stack, which also might be the triangular PV-Table if available.

TT-Entry

After all remaining moves were searched at a PV-node, the best move found is stored inside the transposition table together with its associated values and flags.

PV-Table

If using a triangular PV-table to collect the principal variation, one has to store the best move (so far) anyway - immediately after an alpha increase occurs, to append the PV of ply + 1, which would otherwise void while searching further.

Cut-Node

At Cut-nodes, if a move fails high, it is not necessarily the best move, but a refutation move, good enough to refute opponents previous move. Since it is the best move found so far, in the context of transposition table, it is often flippant mentioned as best move as well.

All-Node

At All-nodes there is no best move found at all, despite all childs were considered if not pruned. While there is a maximum score in the arithmetical sense, all scores below or equal to alpha are upper bounds and not comparable to determine a best move.

Forum Posts

Best move statistics by Matthew Lai, CCC, September 12, 2016 » Search Statistics
Update Best Score and Best Move by Tamás Kuzmics, CCC, May 10, 2017

What links here?

Page	Date Edited
Alpha-Beta	Jan 28, 2018
Arminius	Aug 5, 2017
Best Move	May 15, 2017
BP	Jan 7, 2016
Brainfish	Oct 8, 2017
Chess 0.5	Nov 20, 2016
Clever & Smart	Jan 20, 2017
Crafty	Jan 28, 2018
Debugging	Jan 20, 2018
Encoding Moves	Mar 27, 2016
Fixafan	Oct 2, 2015
Hash Move	Oct 4, 2017
Houdini	Apr 14, 2018
Internal Iterative Deepening	Feb 5, 2018
Lachex	Jan 7, 2016
Last Best Reply	Jul 6, 2013
MChess	Feb 26, 2018
Move Ordering	Feb 27, 2018
Moves	Feb 19, 2018
Neural MoveMap Heuristic	Sep 24, 2015
Null Move	Aug 9, 2017
Paradise	Nov 19, 2014
Principal variation	Dec 4, 2017
PV-Move	Jan 16, 2013
Queen (engine)	Nov 3, 2014
Refutation Move	May 13, 2013
Refutation Table	Mar 27, 2015
Root	Sep 26, 2016
Score	Apr 14, 2018
Search	Feb 1, 2018
Search Tree	Dec 23, 2016
SmarThink	Feb 2, 2018
The King	Jan 21, 2018
The Turk	Apr 1, 2017
Time Management	Mar 20, 2018
Transposition Table	Apr 19, 2018
Triangular PV-Table	Jun 12, 2017

Up one Level

Captures

GerdIsenberg — Sun, 01 Oct 2017 08:08:41 GMT

Home * Chess * Moves * Captures

Captures are tactical moves changing material balance where an opponent piece is removed from the board as part of the completion of the move. This is either done by moving a piece to a square, which is occupied by the opponent captured piece - or as a special case of pawn takes pawn, en passant.

Winning captures are those with least valuable aggressor of most valuable victim, where even a recapture would win material, and captures of pieces en prise, that is the union of undefended (hanging) pieces, as well as pieces defended inadequately. A static exchange evaluation might be applied to determine a victim is en prise or not. Equal captures are exchanges of equal valued pieces. Winning, as well as equal captures are subject of quiescence search. Some programs extend captures or recaptures under certain conditions, i.e. material becomes close to the root score again.

Capture Generation

With mailbox like square centric board representations, capture generation requires a so called blocker loop, while bitboards rely on attack generation and intersection with the set of opponent pieces.

Six times Take Five

capture	best case	worst case
capturing with the pawn
pxQ	winning queen	pawn for queen
pxR	winning rook	pawn for rook
pxB	winning bishop	pawn for bishop
pxN	winning knight	pawn for knight
pxP	winning pawn	exchanging pawns
capturing with the knight
nxQ	winning queen	knight for queen
nxR	winning rook	winning the exchange
nxB	winning bishop	exchanging minors
nxN	winning knight	exchanging minors
nxP	winning pawn	losing knight for pawn
capturing with the bishop
bxQ	winning queen	bishop for queen
bxR	winning rook	winning the exchange
bxB	winning bishop	exchanging minors
bxN	winning knight	exchanging minors
bxP	winning pawn	losing bishop for pawn
capturing with the rook
rxQ	winning queen	rook for queen
rxR	winning rook	exchanging rooks
rxB	winning bishop	losing exchange
rxN	winning knight	losing exchange
rxP	winning pawn	losing rook for pawn
capturing with the queen
qxQ	winning queen	exchanging queens
qxR	winning rook	losing queen for rook
qxB	winning bishop	losing queen for bishop
qxN	winning knight	losing queen for knight
qxP	winning pawn	losing queen for pawn
capturing with the king, always winning captures
kxQ	winning queen
kxR	winning rook
kxB	winning bishop
kxN	winning knight
kxP	winning pawn

Forum Posts

a question about the definition of winning capture in Rebel(diagrams) by Uri Blass, CCC, January 05, 2003
Reducing/Pruning Bad Captures (SEE < 0) by Edsel Apostol, CCC, August 19, 2011 » Pruning, Reductions, SEE
Sorting Captures by David Cimbalista, CCC, August 03, 2016 » Move Ordering
Ordering Capture Moves by Jason Fernandez, CCC, September 06, 2017 » Move Ordering - Captures

External Links

Capture (disambiguation) from Wikipedia
Al Jarreau - Take Five, live in Ohne Filter, SWR TV, Baden-Baden, Germany, 1994, YouTube Video
feat. Larry Williams, Neil Larsen, Charles “Icarus” Johnson, Andrew Ford, Steve Gadd

What links here?

Page	Date Edited
More Links
Algebraic Chess Notation	Sep 25, 2017
Amundsen	Sep 3, 2013
Amyan	Dec 10, 2013
Andscacs	Jan 16, 2018
Atlas	Nov 5, 2017
Atomic Chess	Nov 26, 2016
Battle Chess	Dec 12, 2016
Belle	Jan 18, 2018
Belzebub	Oct 20, 2015
Bitfoot	Sep 8, 2015
Blockage Detection	Oct 19, 2017
Bobby	Jan 7, 2016
Bobcat	Jun 27, 2017
BootChess	May 16, 2017
Brainless	Jun 24, 2017
Breakthrough (Game)	Aug 11, 2017
BremboCE	Feb 17, 2013
Capture Extensions	Oct 26, 2012
Captures	Oct 1, 2017
Castling rights	Jan 7, 2017
CHEOPS	Apr 18, 2015
Chess 0.5	Nov 20, 2016
Chess Champion Mark V	Sep 7, 2017
Chessmaps Heuristic	Aug 27, 2015
Chezzz	Jan 20, 2013
Crafty	Jan 28, 2018
Crazyhouse	Dec 27, 2017
CXG Sphinx	Jun 23, 2017
Cyrus 68K	Jan 7, 2016
DanaSah	Oct 9, 2017
David J. Wu	Jan 28, 2016
DayDreamer	Aug 22, 2016
Death Chess 5000	Apr 5, 2013
Delta Pruning	Dec 2, 2014
Diablo	May 17, 2016
Dispersion and Distortion	Nov 11, 2017
Dragon FR	Sep 9, 2016
Duck	Dec 12, 2016
Edsel Apostol	Nov 2, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
En passant	Jan 16, 2018
En prise	Oct 11, 2016
Encoding Moves	Mar 27, 2016
Entering Moves	Sep 7, 2017
ESC	Aug 14, 2013
Faile	May 27, 2014
Fidelity	Jan 7, 2016
Fifty-move Rule	Aug 9, 2017
Fixafan	Oct 2, 2015
Freccia	Dec 26, 2017
Freyr	Mar 6, 2014
Futility Pruning	Aug 30, 2017
General Setwise Operations	Feb 25, 2018
Genie	Feb 7, 2016
Golch	Dec 7, 2017
HAL	Jun 14, 2016
Halfmove Clock	Aug 9, 2017
Hanging Piece	Jan 14, 2017
Hannibal	Oct 4, 2017
HaQiKi D	Jul 26, 2017
Incremental Updates	Sep 6, 2017
Influence Quantity of Pieces	Jul 21, 2017
Irreversible Moves	Jan 25, 2014
JikChess	Nov 29, 2015
Joker IT	Sep 16, 2017
Kaissa	Apr 9, 2018
Killer Heuristic	Sep 14, 2017
Killer Move	Feb 16, 2017
Lachex	Jan 7, 2016
Laser	Dec 27, 2017
Last Best Reply	Jul 6, 2013
Late Move Reductions	Sep 25, 2017
Linked List	Oct 11, 2016
Master	Dec 28, 2017
Mater	Apr 26, 2016
Material Hash Table	Apr 3, 2014
Material Tables	May 5, 2017
Maverick	Jan 7, 2016
MessChess	Mar 6, 2014
Middlegame	Sep 6, 2016
MLChess	Jan 17, 2017
Move Generation	Jan 29, 2018
Move List	Jul 19, 2017
Move Ordering	Feb 27, 2018
Moves	Feb 19, 2018
Murka	Nov 11, 2016
MVV-LVA	Oct 26, 2017
MyChess	Dec 25, 2017
Null Move Pruning	Dec 2, 2017
Nullmover	Jul 21, 2013
Paladin	Jan 29, 2017
Papa	Jan 11, 2018
Passed Pawn Extensions	May 11, 2015
Pawn Levers (Bitboards)	Nov 11, 2017
PawnKing	Sep 5, 2014
Peasant	May 21, 2015
Pepito	Nov 27, 2014
Perft Results	Feb 10, 2018
Pharaon	Sep 2, 2017
Piece Drop	Feb 20, 2018
Piece-Lists	Feb 13, 2017
Pieces	Feb 19, 2018
Pieces versus Directions	Oct 6, 2016
Point Value by Regression Analysis	Aug 26, 2017
ProChess IT	Sep 30, 2015
Promotions	Jun 6, 2017
Prophet	Sep 30, 2017
Protector	Oct 12, 2017
Protej	Jul 27, 2014
Pruning	Jan 1, 2018
Pseudo-Legal Move	May 23, 2015
Querg	Dec 11, 2013
Quiescence Search	Aug 19, 2017
Quiet Moves	Mar 4, 2010
Rajah	Sep 12, 2012
Ralph Betza	Mar 12, 2014
Rebel	Feb 25, 2018
RedQueen	Nov 13, 2017
Repetitions	Jan 16, 2018
Reversible Moves	Mar 13, 2010
Rule of the Square	Sep 6, 2014
Search Statistics	Jan 16, 2018
SEE - The Swap Algorithm	Jun 5, 2017
Sensor Chess	Jun 7, 2013
SEX Algorithm	Nov 25, 2014
Sjaak (Glebbeek)	Oct 4, 2017
Skewer	Oct 22, 2014
Sliding Piece Attacks	May 27, 2016
Sliding Pieces	Aug 3, 2017
Smash	May 11, 2016
Spike	Jan 7, 2016
Static Exchange Evaluation	Dec 14, 2017
Strategic Test Suite	Dec 19, 2016
Sungorus	Apr 11, 2014
Syzygy Bases	Apr 19, 2018
Table-driven Move Generation	Feb 19, 2017
Tactical Moves	Sep 22, 2010
Tao	Jan 8, 2016
Target Square	Oct 26, 2017
The King	Jan 21, 2018

Up one Level

Castling

GerdIsenberg — Fri, 05 May 2017 10:03:51 GMT

Home * Chess * Moves * Castling

		Castling is a composite move of King and Rook at the same time. In standard chess it consists of moving a king two squares towards the rook and executing a jump of a rook over the king.
Marina Kalinovsky, Castling, 1961 ^[1]

Rules

The prequisites for doing it are as follows:

the king and the relevant rook must not be moved, considered as castling rights inside a chess position
the king must not be in check
no square between king's start and final square may be controlled by the enemy

Chess960

In Chess960 castling is a move reaching the position just like after standard chess castling, which may be achieved by (a) moving the king to c1 or g1 ant then executing a jump by relevant rook (b) jumping with the rook over a king already placed on c1 or g1 (c) interchanging the positions of king and rook ^[2].

Shogi

A formation achieved after castling is called a castle. This is often contrasted with a castle in the game of Shogi, requiring several moves to complete, but it seems wrong, since chess also has several standard defensive castle formations - like the one after fianchetto of a king's bishop or the one with a knight on g7, often achieved in the Old Benoni. For that reason it might be interesting to use shogi programming concepts of a castle map and an attack map in chess.

Forum Posts

1982

Re: bug in chess program by Bruce C. Wright @ Duke University, net.chess, December 2, 1982
Re: Origin of Castling by Bruce C. Wright @ Duke University, net.chess, December 4, 1982

2000 ...

Castling legality check by mjlef, Winboard Forum, January 04, 2007
Saving castling states and en passant history by Eric Lang, CCC, November 27, 2008 » En passant
0x88 FRC castle questions by Daniel Uranga, Winboard Forum, December 12, 2009 » Chess960

2010 ...

Castling legality check by Stef Luijten, CCC, May 03, 2011
Castling long by Lyudmil Tsvetkov, CCC, August 05, 2013
Castling: A counter-intuitive result by Steven Edwards, CCC, September 03, 2013
Abundance of castling vs en passant rights by Kirill Kryukov, CCC, April 14, 2014 » En passant
Castling Evaluation by Dennis Sceviour, CCC, August 02, 2016 » King Safety

External Links

Castling from Wikipedia
Artificial castling from Wikipedia

References

^ Tableaux Échecs - Chess Paintings
^ 0x88 FRC castle questions by Daniel Uranga, Winboard Forum, December 12, 2009

What links here?

Page	Date Edited
1K ZX Chess	Oct 1, 2015
Acornsoft Chess	Dec 11, 2016
Algebraic Chess Notation	Sep 25, 2017
Atlas	Nov 5, 2017
Atom Chess	Dec 11, 2016
BootChess	May 16, 2017
Brainstorm	Jun 24, 2017
Castling	May 5, 2017
Castling rights	Jan 7, 2017
Charly	Jan 10, 2013
CHEKMO-II	Jan 3, 2018
Chess Position	Sep 10, 2017
Chess960	Sep 27, 2016
ChessLin	May 17, 2017
Color Flipping	May 17, 2017
David Forthoffer	Apr 25, 2016
Dennis Sceviour	Feb 14, 2018
Development	Jan 17, 2018
Diagonal Mirroring	Jun 29, 2013
Dictionary	Aug 24, 2017
DirGolem	Jun 5, 2016
Djinn	Feb 8, 2016
EGA Chess	Nov 30, 2017
En passant	Jan 16, 2018
Encoding Moves	Mar 27, 2016
Ethereal	Mar 20, 2018
Evaluation Overlap	Jul 19, 2016
Evert Glebbeek	Sep 25, 2017
Exacto	Oct 3, 2015
Fianchetto	Feb 18, 2015
Firstchess	Nov 27, 2014
General Setwise Operations	Feb 25, 2018
Genie	Feb 7, 2016
Getting Started	Jan 20, 2014
Halfmove Clock	Aug 9, 2017
iota	Feb 10, 2016
Irreversible Moves	Jan 25, 2014
Jonathan Warkentin	Jun 29, 2014
Kaissa	Apr 9, 2018
King	Feb 26, 2013
King Safety	Feb 14, 2018
Kirill Kryukov	Apr 16, 2014
Lachex	Jan 7, 2016
Lancaster	Aug 30, 2016
Lars Rasmussen	Apr 25, 2016
LarsenVB	Jun 24, 2017
Legal Move	Feb 16, 2017
Little Rook Chess	Sep 1, 2015
Losing Chess	Sep 18, 2017
Lyudmil Tsvetkov	Mar 28, 2018
MANIAC I	Nov 17, 2016
Mark Lefler	Nov 23, 2017
Mark Taylor	Jan 7, 2016
Mate-in-two	Oct 14, 2016
Middlegame	Sep 6, 2016
Mini Chess	Jun 7, 2013
Moves	Feb 19, 2018
MyChess	Dec 25, 2017
Novag Micro Chess	Jan 16, 2013
Opening	Jun 25, 2017
Ostrich	Dec 28, 2017
Pin	Mar 7, 2017
Pseudo-Legal Move	May 23, 2015
Quad-Bitboards	Jan 30, 2017
Quiet Moves	Mar 4, 2010
Reversible Moves	Mar 13, 2010
Robocide	May 11, 2016
Shatranj	Jul 26, 2017
Sito Dekker	Apr 25, 2016
SOMA	Mar 25, 2015
Square Attacked By	Jan 20, 2018
Stef Luijten	Apr 26, 2015
Tempo	Jan 17, 2018
The A.R.B Chess System	May 24, 2016
Toledo	Sep 23, 2017
Turochamp	Dec 14, 2017
Vertical Flipping	Oct 10, 2013
Vice	Mar 8, 2016
William Chase	Jan 21, 2016
Z-Chess	Dec 23, 2017

Up one Level

Copy-Make

GerdIsenberg — Tue, 23 May 2017 13:48:35 GMT

Home * Chess * Position * Copy-Make

While traversing a Search Tree, the Copy-Make approach keeps and updates local copies of certain aspects of a chess position inside an array indexed by ply, which could also be interpreted as explicit, random accessible search stack. It usually refers the irreversible aspects of the position, like ep state, castling rights and the halfmove clock, which can not incrementally updated during unmake move. Some programs even keep reversible stuff inside an array, to avoid incremental update during unmake. Copy-Make is required, if aspects need to be accessed randomly in the current branch from the root (or even starting game position) to the current one.

Copy-Make

// make
memcpy (&position[ply+1].irrvrsAspects, 
        &position[ply  ].irrvrsAspects, 
        sizeof(irrvrsAspects));
ply++;
update (position[ply], move)
...
// unmake
ply--;
// position[ply] is still valid

Stack

The alternative, to maintain those irreversible aspects inside a global structure, would require a stack (LIFO), with push and global update during make, and pop from stack to global structure during unmake, and therefor higher memory bandwidth for copying back and forth.

// make
push (position.irreversibleAspects);
ply++;
update (position, move)
...
// unmake
ply--;
pop (position.irreversibleAspects);
// position is restored from stack

Forum Posts

1995 ...

cheaper search ? by James F. Long, rgcc, April 27, 1997 » Tristram
Re: cheaper search ? by Shaun Press, rgcc, April 28, 1997 » Vanilla Chess, KnightCap
Unmake move v copy the board by Hugh Cumper, CCC, January 24, 1999

2000 ...

The need to unmake move by Mathieu Pagé, CCC, August 19, 2003 » Unmake Move
undo move vs. Position Cloning by BoldReceiver, CCC, September 16, 2009
Re: undo move vs. Position Cloning by Marco Costalba, CCC, September 16, 2009 » Stockfish
Re: undo move vs. Position Cloning by Don Dailey, CCC, September 16, 2009 » Doch
copy/make vs make/unmake test results by Robert Hyatt, CCC, September 19, 2009 » Crafty

2010 ...

Copy Board vs Unmake Move by ChrisJ, OpenChess Forum, September 29, 2010
performance of copy-make by Rein Halbersma, CCC, August 02, 2011
How costly is taking moves back ? by Piotr Lopusiewicz, CCC, April 30, 2013
Saving info before making a move by CDaley11, OpenChess Forum, December 30, 2013
copy/make vs make/unmake by Robert Hyatt, CCC, January 07, 2014
Memory usage in make/unmake vs logic complexity by Matthew Lai, CCC, August 30, 2014

2015 ...

Unifying make/undo and copy-make by Rein Halbersma, CCC, December 21, 2015
Copy-make vs Make/Unmake ? by Mahmoud Uthman, CCC, November 12, 2016

What links here?

Page	Date Edited
Aaron Becker	Jul 22, 2015
Board Representation	Dec 11, 2017
Chess Position	Sep 10, 2017
Copy-Make	May 23, 2017
DayDreamer	Aug 22, 2016
Doch	May 23, 2017
Gromit	Apr 5, 2017
Incremental Updates	Sep 6, 2017
James Swafford	Jan 1, 2018
KnightCap	Nov 6, 2016
LTChess	Mar 30, 2017
Make Move	Mar 2, 2016
Mate-in-two	Oct 14, 2016
Matthew Lai	Dec 6, 2017
Moves	Feb 19, 2018
Nemorino	Dec 21, 2017
Occam	Jan 21, 2016
Paladin	Jan 29, 2017
Pedone	Jan 16, 2018
Rein Halbersma	Dec 22, 2015
Robert Hyatt	Dec 25, 2017
Senpai	Nov 10, 2017
Shaun Press	Sep 24, 2014
Stan Arts	Nov 21, 2014
Tristram	Jan 29, 2014
Unmake Move	Jun 10, 2017
Vadim Demichev	Jul 26, 2013
Vanilla Chess	Jan 13, 2013

Up one Level

CPW-Engine_move(0x88)

Pawel_Koziol — Tue, 30 Dec 2014 19:09:21 GMT

Home * Engines * CPW-Engine * Move(0x88)

Both move_make and move_unmake call the functions fillSq(color, piece, square) and clearSq(square). They are meant to encapsulate all the incremental updates (material and pcsq calues, hash keys etc.) and can be viewed in CPW-Engine_board(0x88). Ideally this will make both make and unmake functions independent from the board representation. Beside that, incremental update code will be rather long, if not necessarily ugly.

Code

#include "stdafx.h"
#include "transposition.h"
 
int move_makeNull() {
    b.stm = !b.stm;
    b.hash ^= zobrist.color;
    b.ply ++;
    if (b.ep != -1) {
        b.hash ^= zobrist.ep[b.ep];
        b.ep = -1;
    }
    return 0;
}
 
int move_unmakeNull(char ep) {
    b.stm = !b.stm;
    b.hash ^= zobrist.color;
    b.ply --;
    if (ep != -1) {
        b.hash ^= zobrist.ep[ep];
        b.ep = ep;
    }
    return 0;
}
 
int move_make(smove move) {
 
    /* switch the side to move */
    b.stm = !b.stm;
    b.hash ^= zobrist.color;
 
    /* a capture or a pawn move clears b.ply */
    b.ply ++;
    if ( (move.piece_from == PAWN) || move_iscapt(move) )
        b.ply = 0;
 
    /* a piece vacates its initial square */
    clearSq(move.from);
 
    /* in case of a capture, the "to" square must be cleared,
       else incrementally updated stuff gets blown up 
    */
    if ( b.pieces[move.to] != PIECE_EMPTY )
       clearSq(move.to);
 
    /* a piece arrives to its destination square */
    fillSq( !b.stm, move.piece_to, move.to );
 
    /* castle flags
        if either a king or a rook leaves its initial square, the side looses its castling-right.
        The same happens if another piece moves to this square (eg.: captures a rook on its initial square)
    */
    switch (move.from) {
    case H1: b.castle &= ~CASTLE_WK; break;
    case E1: b.castle &= ~(CASTLE_WK|CASTLE_WQ); break;
    case A1: b.castle &= ~CASTLE_WQ; break;
    case H8: b.castle &= ~CASTLE_BK; break;
    case E8: b.castle &= ~(CASTLE_BK|CASTLE_BQ); break;
    case A8: b.castle &= ~CASTLE_BQ; break;
    }
    switch (move.to) {
    case H1: b.castle &= ~CASTLE_WK; break;
    case E1: b.castle &= ~(CASTLE_WK|CASTLE_WQ); break;
    case A1: b.castle &= ~CASTLE_WQ; break;
    case H8: b.castle &= ~CASTLE_BK; break;
    case E8: b.castle &= ~(CASTLE_BK|CASTLE_BQ); break;
    case A8: b.castle &= ~CASTLE_BQ; break;
    }
    b.hash ^= zobrist.castling[move.castle];
    b.hash ^= zobrist.castling[b.castle];
 
    /* castle-move
        in communication with the gui a castling move is represented through 
        the king move. (eg.: e1g1 = White castles short) This king move already
        got executed in the code above with the fillSq() and clearSq() command.
        Whats missing now is the relating rook-move.
    */
    if (move.flags & MFLAG_CASTLE) {
        if (move.to == G1) {
            clearSq(H1);
            fillSq(WHITE,ROOK,F1);
        } 
        else if (move.to == C1) {
            clearSq(A1);
            fillSq(WHITE,ROOK,D1);
        }
        else if (move.to == G8) {
            clearSq(H8);
            fillSq(BLACK,ROOK,F8);
        } 
        else if (move.to == C8) {
            clearSq(A8);
            fillSq(BLACK,ROOK,D8);
        }
    }
 
    /* en-passant flag
        First erase the current state of the ep-flag, then set it again 
        in  case there has been a two square pawn move that allows such
        capture. For example, 1.e4 in the initial position will not set
        the en passant flag, because there are no black pawns on d4 and f4.
        This soluion helps with opening book and increases the number of
        transposition table hits.
    */
    if (b.ep != -1) {
        b.hash ^= zobrist.ep[b.ep];
        b.ep = -1;
    }
    if ( (move.piece_from == PAWN) && ( abs(move.from - move.to) == 32 ) &&
         ( pawnRecapture( !b.stm, (move.from + move.to) / 2 ) ) 
       ) {
        b.ep = (move.from + move.to) / 2;
        b.hash ^= zobrist.ep[b.ep];
    }
 
    /* en-passant capture
        if the move is an en-passant capture, the captured pawn has to be removed manually
    */
    if (move.flags & MFLAG_EPCAPTURE) {
        if (!b.stm == WHITE) {
            clearSq(move.to - 16);
        } else {
            clearSq(move.to + 16);
        }
    }
 
    ++b.rep_index;
    b.rep_stack[b.rep_index] = b.hash;
 
    return 0;
}
 
int move_unmake(smove move) {
 
    b.stm = !b.stm;
    b.hash ^= zobrist.color;
 
    b.ply = move.ply;
 
    /* set en passant square */
    if (b.ep != -1) 
        b.hash ^= zobrist.ep[b.ep];
    if (move.ep != -1) 
        b.hash ^= zobrist.ep[move.ep];
    b.ep = move.ep;
 
    clearSq(move.to);
 
    fillSq(b.stm, move.piece_from, move.from);
 
    /* un-capture
        in case of a capture, put the captured piece back
    */
    if ( move_iscapt(move) )
       fillSq(!b.stm, move.piece_cap, move.to );
 
    /* un-castle
        the king has already been moved, now move the rook
    */
    if (move.flags & MFLAG_CASTLE) {
        if (move.to == G1) {
            clearSq(F1);
            fillSq(WHITE,ROOK,H1);
        } 
        else if (move.to == C1) {
            clearSq(D1);
            fillSq(WHITE,ROOK,A1);
        }
        else if (move.to == G8) {
            clearSq(F8);
            fillSq(BLACK,ROOK,H8);
        } 
        else if (move.to == C8) {
            clearSq(D8);
            fillSq(BLACK,ROOK,A8);
        }
    }
 
    /* adjust castling flags */
    b.hash ^= zobrist.castling[move.castle];
    b.hash ^= zobrist.castling[b.castle];
    b.castle = move.castle;
 
    /* en-passant-uncapture
        put the captured pawn back to its initial square
    */
    if (move.flags & MFLAG_EPCAPTURE) {
        if (b.stm == WHITE) {
            fillSq(BLACK,PAWN,move.to - 16);
        } else {
            fillSq(WHITE,PAWN,move.to + 16);
        }
    }
 
    --b.rep_index;
 
    return 0;
}
 
int move_iscapt(smove m) {
    return (m.piece_cap != PIECE_EMPTY);
}
 
int move_isprom(smove m) {
    return (m.piece_from != m.piece_to);
}
 
int move_canSimplify(smove m) {
    if ( m.piece_cap == PAWN ||
         b.PieceMaterial[!b.stm] - e.PIECE_VALUE[m.piece_cap] > e.ENDGAME_MAT )
        return 0;
    else
        return 1;
}
 
// this function returns number of legal moves in the current position
 
int move_countLegal() {
    smove mlist[256];
    int mcount = movegen(mlist, 0xFF);
    int result = 0;
 
    for (int i = 0; i < mcount; i++) {
 
        // try a move...
        move_make( mlist[i] ); 
 
        // ...then increase the counter if it did not leave us in check
        if ( !isAttacked( b.stm, b.KingLoc[!b.stm] ) ) ++result;
 
        move_unmake(mlist[i]);
    }
 
    return result;
}
 
int move_isLegal(smove m) {
    smove movelist[256];
    int movecount = movegen(movelist, 0xFF);
 
    for (int i = 0; i < movecount; i++) {
        if ( movelist[i].from == m.from && 
             movelist[i].to   == m.to ) {
 
                 int result = 1;
 
                 // test if the move in question leaves us in check
 
                 move_make( movelist[i] );
                 if ( isAttacked( b.stm, b.KingLoc[!b.stm] ) ) result = 0;
                 move_unmake( movelist[i] );
 
                 return result;
           }
    }
 
    return 0;
}

What links here?

Page	Date Edited
0x88	Nov 28, 2016
CPW-Engine	Dec 31, 2014
CPW-Engine_move(0x88)	Dec 30, 2014
CPW-Engine_root	Sep 27, 2008

Up one Level

En passant

GerdIsenberg — Tue, 16 Jan 2018 08:34:29 GMT

Home * Chess * Moves * En passant

En passant (from French: "in passing") ^[1] is a special pawn capture move, which is only possible immediately after an opposing pawn tried passing an advanced pawn on the fifth rank (or fourth for black pawns) by a double pawn push. This double pushed pawn can then be captured the same way, as it would only performed a single push - but only as an immediate reply.

This chess rule makes chess programming a bit harder. First, the target square of the en passant capture is not identical with origin of the captured pawn, opposed to all other captures. Second, the double pawn push, which triggered the immediate possibility of an en passant capture, must be part of the chess position. The information required is whether there was a previous pawn push, and if so, at least the file number of that pawn, considered as en passant target square inside the Forsyth-Edwards Notation (FEN), albeit with the redundant rank (3 or 6) as well.

Legality Test

To prove an en passant capture is actually possible, at least the en passant target square should be under attack of an opponent pawn for pseudo legality. Further, for strict legality, the ep capturing pawn should not be absolutely pinned, which additionally requires a horizontal pin test of both involved pawns, which disappear from the same rank.

8/6bb/8/8/R1pP2k1/4P3/P7/K7 b - d3 after d2-d4

The legality test should be best applied in making of the double pawn push, also considering updating Zobist keys to avoid dissimilarity of otherwise repeated positions if the first occurrence happened after a double pawn push with no en passant capture actually possible ^[2] .

En passant bugs

The implementation of the en passant rule often caused subtle bugs. Almost every chess programmer had various issues with it ^[3] , most notable Louis Kessler with his Program Brute Force. Gerd Isenberg had a special en passant experience with IsiChess at Aegon 1994 in the game versus Henk Arnoldus. IsiChess pushed its white pawn from b2 to b4 "between" the two advanced pawns a4 and c4 from Henk, allowing two possible en passant options. Unfortunately IsiChess only generated one - the "wrong" one (an assembly bug due to jc instead if jnz or that like, otherwise it would not have played it), and was immediately lost after Henk played the "right" one ^[4] ^[5] :

[Event "9th AEGON man-comp"]
[Site "The Hague NED"]
[Date "1994.05.02"]
[Round "4"]
[White "IsiChess"]
[Black "Henk Arnoldus"]
[Result "0-1"]
 
1.e4 e6 2.d4 d5 3.Nd2 Nf6 4.e5 Nfd7 5.Bd3 b6 6.Ngf3 Ba6 7.O-O Bxd3
8.cxd3 Be7 9.Nb3 O-O 10.Bd2 Na6 11.Qe2 Qc8 12.Rac1 Qb7 13.Rc2 c5
14.Rfc1 Rfc8 15.dxc5 bxc5 16.Qe3 Nb4 17.Bxb4 Qxb4 18.Nbd2 a5 19.a3 Qb7
20.Kh1 Ra6 21.d4 c4 22.Qc3 a4 23.b4 axb3 24.Nxb3 Rxa3 25.Nfd2 Rb8
26.Rb1 cxb3 27.Rcb2 Bb4 28.Qc1 Bxd2 29.Rxd2 Ra2 30.Rdb2 Rxb2
31.Qxb2 Qb4 32.f4 g6 33.h3 Qc4 34.Rc1 Qd3 35.f5 Qxf5 0-1

2r3k1/1q1nbppp/r3p3/3pP3/pPpP4/P1Q2N2/2RN1PPP/2R4K b - b3 0 23

Forum Posts

1999

en-passant move generation by Larry Griffiths, CCC, February 06, 1999
Unique nodes, en passant and perfect hashing by Andreas Stabel, CCC, November 25, 1999

2000 ...

annoying en passant x-ray by Georg von Zimmermann, CCC, November 30, 2003

2005 ...

Programmer bug hunt challenge by Ed Schröder, CCC, May 04, 2007 » Portable Game Notation

2010 ...

en passant and hash key calculation by Fred Hamilton, CCC, March 21, 2010
Komodo 3 and a minor bug by Jouni Uski, CCC, September 02, 2011
Re: Causes for inconsistent benchmark signatures by Evert Glebbeek, CCC, March 27, 2013 » Forsyth-Edwards Notation
polyglot en passant square by Marco Belli, CCC, September 12, 2013 » Polyglot
ep and castle rights hashing by Natale Galioto, CCC, September 15, 2013 » Castling rights, Repetitions, Transposition Table
Abundance of castling vs en passant rights by Kirill Kryukov, CCC, April 14, 2014 » Castling
En-passant legality test by tetra, OpenChess Forum, August 07, 2014 » Legal Move

2015 ...

En passant bonus by Lyudmil Tsvetkov, CCC, February 10, 2015 » Pawn Structure
Dynamic EP flag by thevinenator, OpenChess Forum, October 02, 2015
Triple Repitition: Is this considered a repitition or not? by Jayakiran Akurathi, CCC, May 07, 2016 » Repetitions
Enpass + Castling for Zorbist hashes by Andrew Grant, CCC, January 06, 2017 » Castling rights, Zobrist Hashing
3-fold repetition and cutechess-cli by Lars Mathiesen, CCC, January 14, 2018 » Repetitions

External Links

References

^ Earliest Occurrences of Chess Terms by Edward Winter
^ en passant and hash key calculation by Fred Hamilton, CCC, March 21, 2010
^ Chrilly Donninger (1999). Computer machen keine Fehler. CSS 2/99, pdf (German)
^ CSVN Downloads Games Aegon Tournaments
^ Aegon 1994 Round 4 (REPOST) by Dap Hartmann, rgc, May 09, 1994

What links here?

Page	Date Edited
1K ZX Chess	Oct 1, 2015
ACM 1978	Dec 23, 2017
Acornsoft Chess	Dec 11, 2016
Algebraic Chess Notation	Sep 25, 2017
AlphaZero	Feb 10, 2018
Andrew Grant	Jan 13, 2018
Atom Chess	Dec 11, 2016
Atomic Chess	Nov 26, 2016
Board Representation	Dec 11, 2017
BootChess	May 16, 2017
Brute Force (Program)	Sep 7, 2017
Butterfly Boards	Jan 27, 2015
Captures	Oct 1, 2017
Castling	May 5, 2017
Castling rights	Jan 7, 2017
Charly	Jan 10, 2013
Check	Feb 1, 2018
CHEKMO-II	Jan 3, 2018
Chess Position	Sep 10, 2017
ChessLin	May 17, 2017
Color Flipping	May 17, 2017
Copy-Make	May 23, 2017
CTG	Aug 22, 2016
Dabbaba	Oct 21, 2014
David Forthoffer	Apr 25, 2016
Deep Pink	Feb 6, 2017
Dictionary	Aug 24, 2017
DirGolem	Jun 5, 2016
Double Check	Apr 4, 2013
EGA Chess	Nov 30, 2017
En passant	Jan 16, 2018
Encoding Moves	Mar 27, 2016
Engine Testing	Feb 1, 2018
Eval Tuning in Deep Thought	Jun 7, 2016
Evert Glebbeek	Sep 25, 2017
Extended Position Description	Dec 2, 2017
Firstchess	Nov 27, 2014
Forsyth-Edwards Notation	Sep 10, 2017
Galahad	Jan 8, 2015
Gaviota Tablebases	Apr 22, 2018
General Setwise Operations	Feb 25, 2018
Genie	Feb 7, 2016
Georg von Zimmermann	May 29, 2017
Harald Lüßen	Mar 20, 2013
Incremental Updates	Sep 6, 2017
iota	Feb 10, 2016
James Swafford	Jan 1, 2018
Jonathan Warkentin	Jun 29, 2014
Kirill Kryukov	Apr 16, 2014
Lars Rasmussen	Apr 25, 2016
Last Best Reply	Jul 6, 2013
Legal Move	Feb 16, 2017
Little Rook Chess	Sep 1, 2015
Lomonosov Tablebases	May 20, 2016
Lyudmil Tsvetkov	Mar 28, 2018
Make Move	Mar 2, 2016
Marco Belli	Jan 6, 2018
Mark Taylor	Jan 7, 2016
Mate-in-two	Oct 14, 2016
Mini Chess	Jun 7, 2013
Move Generation	Jan 29, 2018
Moves	Feb 19, 2018
MyChess	Dec 25, 2017
Nalimov Tablebases	Dec 23, 2016
Paladin	Jan 29, 2017
Pawn Push	Mar 27, 2010
Pawn Pushes (Bitboards)	Apr 5, 2013
Pawn Structure	Oct 2, 2017
Perft	Sep 26, 2017
Perft Results	Feb 10, 2018
Pieces versus Directions	Oct 6, 2016
Pin	Mar 7, 2017
PolyGlot	Jan 17, 2018
Portable Game Notation	Jan 11, 2018
Pseudo-Legal Move	May 23, 2015
Quad-Bitboards	Jan 30, 2017
Quiet Moves	Mar 4, 2010
Repetitions	Jan 16, 2018
Sito Dekker	Apr 25, 2016
Sneaky Pete	Mar 18, 2016
Squares	Feb 15, 2015
Toledo	Sep 23, 2017
Transposition Table	Apr 19, 2018
Unmake Move	Jun 10, 2017
WMCCC 1996	Sep 15, 2016
Z-Chess	Dec 23, 2017
Zobrist Hashing	Jan 22, 2018

Up one Level

Encoding Moves

ecabiac — Sun, 27 Mar 2016 23:30:39 GMT

Information Required

From-To Based

Extended Move Structure

C++ Sample

Various Encodings and Decorations

Home * Chess * Moves * Encoding Moves

Encoding Moves inside a chess program refers to both game records or game notation, and search related generation, make and unmake move to incremental update the board. During generation, moves are stored inside move lists, and best moves or refutation moves failing high inside the search are stored inside the transposition table, Killer slots, PV- or refutation table, and moves, or certain aspects of a move, such as origin square and the target square are used to index butterfly boards for history- or countermove heuristic.

Move encoding in game records and game databases is usually designed to minimize size, while in search efficiency in generating is the main concern, considering board representation and other data structures like attack and defend maps. In general, move encoding either comprehend full information, that is contains involved pieces and square coordinates, or more common, omits the redundant piece information and relies on a adequate board representation to lookup the pieces by square. In Alpha-Beta like search, an important consideration is lazy move generation, to delay acquisition of certain information until it is really needed, which might be never in case of Cut-nodes.

Information Required

From-To Based

The information required to uniquely describe a move is the initial square, also called from-, origin- or departure square, and the target square, also called to- or destination square, and in case of promotions the promoted piece code. While this from-to information is also sufficient for castling in standard chess, due to the otherwise impossible double king step, it might not in Chess960. Therefore and also for efficiency reasons, castles are tagged as "special" moves. Such a move encoding conveniently fits inside a 16-bit word, 6 bits for from-to square each to index a butterfly board, still leaves a nibble for flags for move kind and promoted piece code, for instance this arbitrary flags:

code	promotion	capture	special 1	special 0	kind of move
0	0	0	0	0	quiet moves
1	0	0	0	1	double pawn push
2	0	0	1	0	king castle
3	0	0	1	1	queen castle
4	0	1	0	0	captures
5	0	1	0	1	ep-capture
8	1	0	0	0	knight-promotion
9	1	0	0	1	bishop-promotion
10	1	0	1	0	rook-promotion
11	1	0	1	1	queen-promotion
12	1	1	0	0	knight-promo capture
13	1	1	0	1	bishop-promo capture
14	1	1	1	0	rook-promo capture
15	1	1	1	1	queen-promo capture

Extended Move Structure

The information which piece performs the move and which piece is captured (if any) is implicit given by the from-to squares, with the requirement to lookup the current board before making the move, but in case of captures not after making or before unmaking the move. Some programs use a 32-bit double word as extended move structure at generation time as well for making/unmaking moves, with the upper bits used for a move score scaled by various move ordering techniques for instance dedicated piece-square tables and/or history heuristic, and perhaps two three bit codes for the moving and captured piece (if any) which also implies a kind of MVV-LVA coding. Also the extended move may apply composite indices for incremental update of Zobrist- or BCH keys.

Having the piece codes inside the move structure safes the board lookups during make, and makes storing captured pieces on a ply stack for unmake needless. Of course for space considerations to store moves inside transposition table, Killer slots, PV- or refutation table, the compact 16-bit move structure is still adequate for coordinate and move kind comparison with the lower 16 bits of the extended move structure.

C++ Sample

Rather than using bitfield move structures or classes in C and C++, most programmers rely on scalar integers, such as short and int for 16- or 32-bit words, but implement the composition and extraction while writing and reading various structure elements by explicit shifts and masks, likely encapsulated thought an interface with most likely inlined functions (or macros) to hide the internal representation. Further extended move structures might either embed or inherit this most compact base structure or class, which might already rely the native 32-bit integer type to avoid x86 16-bit optimization issues.

class CMove {
   CMove(unsigned int from, unsigned int to, unsigned int flags) {
      m_Move = ((flags & 0xf)<<12) | ((from & 0x3f)<<6) | (to & 0x3f);
   }
   void operator=(CMove a} {m_Move = a.m_Move;}
 
   unsigned int getTo() const {return m_Move & 0x3f;}
   unsigned int getFrom() const {return (m_Move >> 6) & 0x3f;}
   unsigned int getFlags() const {return (m_Move >> 12) & 0x0f;}
 
   void setTo(unsigned int to) {m_Move &= ~0x3f; m_Move |= to & 0x3f;}
   void setFrom(unsigned int from) {m_Move &= ~0xfc0; m_Move |= (from & 0x3f) << 6;}
   ...
 
   bool isCapture() const {return (m_Move & CAPTURE_FLAG) != 0;}
   ...
 
   unsigned int getButterflyIndex() const {return m_Move & 0x0fff;}
   bool operator==(CMove a) const {return (m_Move & 0xffff) == (a.m_Move & 0xffff);}
   bool operator!=(CMove a) const {return (m_Move & 0xffff) != (a.m_Move & 0xffff);}
 
   unsigned short asShort() const {return (unsigned short) m_Move;}
 
protected:
   unsigned int m_Move; // or short or template type
};

Various Encodings and Decorations

Algebraic Notation

Based on Philipp Stamma's short Algebraic chess notation, a move can be described by the moving piece code and destination square. In case of disambiguating moves if two (or more) identical pieces can move to the same square, the file of departure, or if files are identical as well, the rank or both file and rank are given. A capture move, denoted by the symbol 'x' (takes) does not explicitly specify the captured piece and requires a look to the board as well.

Chess programs usually use algebraic notations concerning the user interface and Portable Game Notation - for appropriate conversion they have to deal with disambiguating source squares, that is need to be aware of all other moves of this piece-kind to the destination square to determine whether the from square needs additional file and/or rank information despite the moving piece.

Direction-Target

Another move encoding alternative motivated by direction wise target square serialization in bitboards is not to use the from-square but target square and direction. While the information is non-ambiguous it needs some effort with ray-lookup and bitscan to determine the from-square.

Check Flag

It might be interesting to determine whether a move gives check in advance during generation time, to possibly score them higher for move ordering, i. e. to don't reduce or even extend them, and also to safe in check detection after make move. However, as mentioned, lazy move generation is required, to delay acquisition of information until it is really needed, which might be never in case of Cut-nodes. Additionally an early determined checking move, even if failing high, usually implies a huge sub-tree due to check extensions, while an early non checking moves likely makes a cheaper cutoff for most futile Cut-nodes. Therefor, determining checking moves in advance is not that recommended for most board-representations.

Move Index

If the generated moves inside a move list are deterministic, one may encode moves as relative list index. Since the maximum number of moves per positions seems 218 ^[1] ^[2] , one byte is enough to index the move. This encoding was used in early game databases.

Two Positions with 218 Moves each		A. Dickins (1968) ^[3]

R6R/3Q4/1Q4Q1/4Q3/2Q4Q/Q4Q2/pp1Q4/kBNN1KB1 w - - 0 1		3Q4/1Q4Q1/4Q3/2Q4R/Q4Q2/3Q4/1Q4Rp/1K1BBNNk w - - 0 1

Move Enumeration

Based on Influence Quantity of Pieces one may enumerate all moves, to specify a unique determined move number with respect to moving piece, from- and to squares, captured piece (if any) and promoted piece inside a 16-bit range.

Pawn Moves

Move Kind	Ranks	Files	Directions	Target Combinations	Cardinality
Pushs	5	8	1	1	40
Promotions	1	8	1	4	32
Double Pushs	1	8	1	1	8
Total Pushs	6	8	1	1+2/3	80
Captures	5	7	2	5	350
Captures & Promotions	1	7	2	4*4 ^[4]	224
En passant	1	7	2	1	14
Total Captures	6	7	2		588
Total Pawns	6		3		668

Piece Moves

Reversible and Captures, Influence Quantity of Pieces times six target combinations for empty and five possible capture targets.

Piece	Influence Quantity	Cardinality
Knight	336	2016
King	420	2520
Bishop	560	3360
Rook	896	5376
Queen	1456	8736
Total	3668	22008

All Moves

Sheet of all moves, considering Castling (but no null move):

Piece	Move Kind	From-To	None	Captures	per Side	Total
Pawn	Promotions	8	32	-	32	64
	Captures & Promotions	14	-	224	224	448
	Double Pushs	8	8	-	8	16
	Pushs	40	40	-	40	80
	Captures	70	-	350	350	700
	En passant	14	-	14	14	28
	Total		80	588	668	1336
King	Castles	2	2	-	2	4
		420	420	2100	2520	5040
	Total		422	2100	2522	5044
Knight		336	336	1680	2016	4032
Bishop		560	560	2800	3360	6720
Rook		896	896	4480	5376	10752
Queen		1456	1456	7280	8736	17472
	Total		3248	16240	19488	38976
Total			3750	18928	22678	45356

Forum Posts

Subject: Maximum Number of Legal Moves by Andrew Shapira, CCC, May 08, 2005
max amount of moves from a position? by Srdja Matovic, CCC, June 10, 2011 » Chess Maxima
Contest: Find Position with the most moves by Charles Roberson, CCC, December 09, 2011
Move encoding by Russell Reagan, CCC, April 21, 2014
Killer and move encoding by Fabio Gobbato, CCC, August 14, 2014 » Killer Heuristic

External Links

Move Representation - Computer Architecture and Languages Laboratory, University of Maribor

References

^ Subject: Maximum Number of Legal Moves by Andrew Shapira, CCC, May 08, 2005
^ max amount of moves from a position? by Srdja Matovic, CCC, June 10, 2011
^ Re: max amount of moves from a position? by Árpád Rusz, CCC, June 11, 2011
^ PxP not possible during promotion, therefore only four capture targets

What links here?

Page	Date Edited
Algebraic Chess Notation	Sep 25, 2017
Andrew Shapira	May 7, 2017
C	Feb 19, 2018
Chess	Jan 21, 2018
Chess Position	Sep 10, 2017
Copy-Make	May 23, 2017
Data	Nov 26, 2017
Encoding Moves	Mar 27, 2016
Fabio Gobbato	Mar 6, 2015
Game Notation	Jan 11, 2018
Incremental Updates	Sep 6, 2017
Influence Quantity of Pieces	Jul 21, 2017
Killer Heuristic	Sep 14, 2017
Killer Move	Feb 16, 2017
Make Move	Mar 2, 2016
MicroChess	Jul 14, 2015
Mini Chess	Jun 7, 2013
Move Generation	Jan 29, 2018
Move List	Jul 19, 2017
Moves	Feb 19, 2018
Napoleon	Jun 25, 2017
Nemorino	Dec 21, 2017
Origin Square	Oct 10, 2016
Othello	Jan 4, 2018
Pawn Pushes (Bitboards)	Apr 5, 2013
Pieces versus Directions	Oct 6, 2016
Promotions	Jun 6, 2017
Scid	Apr 15, 2017
Sliding Pieces	Aug 3, 2017
Target Square	Oct 26, 2017
Unmake Move	Jun 10, 2017
Vice	Mar 8, 2016
Warren D. Smith	Sep 12, 2015

Up one Level

Incremental Updates

GerdIsenberg — Wed, 06 Sep 2017 20:38:03 GMT

Chess Position

Material and Hash keys

Home * Chess * Position * Incremental Updates

Incremental updates keep global or shared structures up to date after making and unmaking moves on the internal board, likely inside a depth-first, alpha-beta like search-algorithm. Incremental update on the same global or shared data ever and ever, will likely keep it in fast cache memory, and saves memory bandwidth compared to a Copy-Make approach, which needs a make-update on the copy as well, but no unmake-update rather than decrementing a ply-index or fetching a pointer.

Chess Position

Incremental updates by make/unmake are obligatory for square centric board arrays like mailbox and 0x88 along with their piece-lists, as well for the classical bitboard board-definition. A move only affects a small fraction of the complete board structure and the update cost is small compared to a copy of the whole board. Also one usually doesn't need an array of boards for random access, but only the current one.

However, there are aspects of a chess position, which can not generally restored from a child-position by unmaking a move, and which therefor need to be restored by either re-playing the whole game record from the root position, or to be memorized inside an array indexed by ply or on a stack (LIFO), most notably ep state, castling rights and the halfmove clock enforcing the fify-move rule. Also, if one doesn't keep a captured piece (if any) inside the move object, one has to memorize those pieces elsewhere as well, to restore the target square of the move about to unmake.

Material and Hash keys

Subject of incremental updates are further data which only change conditionally on certain move types, like material signature, only affected by captures or promotions, or for instance zobrist keys for a pawn hash table, only affected by moving/capturing pawns. Standard zobrist keys for TT purpose and dependent on ep state and castling rights, are slightly more complicated to restore. If stored inside a record anyway to detect repetitions, one has the option to restore the key after unmake from that record.

It is a good idea to compare incremental updated stuff like zobrist keys with its from scratch generated counterparts for debug purposes.

Evaluation

Other global structures or variables as candidates of an incremental update are related to Evaluation, beside the mentioned material (balance), lazy evaluation terms, like the sum of all piece-square values ^[1] ^[2] .

Attack table

Some programs keep Attack and Defend Maps up to date incrementally, which is runtime dependent on the number of squares whose attacks-to are influenced by the move. Due to its size and utilization, copy-make is no issue, but on the fly generation if actually needed.

Publications

John J. Scott (1969). A chess-playing program. Machine Intelligence Vol. 4
Peter W. Frey (1983). The Alpha-Beta Algorithm: Incremental Updating, Well-Behaved Evaluation Functions, and Non-Speculative Forward Pruning. Computer Game-Playing (ed. Max Bramer), pp. 285-289. Ellis Horwood Limited

Forum Posts

2005 ...

Incremental updating for positional evaluation by Steven Edwards, CCC, March 27, 2008
Incremental Zobrist - slow? by Vlad Stamate, CCC, June 20, 2009 » Zobrist Hashing
undo move vs. Position Cloning by BoldReceiver, CCC, September 16, 2009
Re: undo move vs. Position Cloning by Don Dailey, CCC, September 16, 2009 » Doch

2010 ...

Incremental or non-incremental PST evaluation calcs by Mark Pearce, CCC, January 26, 2012 » Piece-Square Tables
copy/make vs make/unmake by Robert Hyatt, CCC, January 07, 2014
Incrementally-updated attack map by Harm Geert Muller, April 21, 2014 » Attack and Defend Maps
Memory usage in make/unmake vs logic complexity by Matthew Lai, CCC, August 30, 2014

2015 ...

Incremental update by Matthew R. Brades, CCC, December 19, 2015

External Links

Search Techniques in REBEL (Lazy Eval) from How Rebel Plays Chess by Ed Schröder » Lazy Evaluation, Rebel
Frumpy - Life Without Pain, All Will Be Changed (1970), YouTube Video

References

^ Search Techniques in REBEL (Lazy Eval) from How Rebel Plays Chess by Ed Schröder
^ Incremental updating for positional evaluation by Steven Edwards, CCC, March 27, 2008

What links here?

Page	Date Edited
Arasan	Apr 8, 2018
Attack and Defend Maps	Nov 5, 2016
BCH Hashing	May 8, 2017
Bebe	Dec 23, 2017
Belle	Jan 18, 2018
Bitboard Board-Definition	Jun 23, 2014
Bitboards	Nov 14, 2017
Board Representation	Dec 11, 2017
Bobby	Jan 7, 2016
Capture Extensions	Oct 26, 2012
Check	Feb 1, 2018
Chess (Program)	Dec 22, 2017
Chess 0.5	Nov 20, 2016
Chess Position	Sep 10, 2017
Chest	Mar 3, 2015
ChipTest	Jun 19, 2016
Color Flipping	May 17, 2017
Connectivity	Mar 6, 2016
Copy-Make	May 23, 2017
Crafty	Jan 28, 2018
Dabbaba	Oct 21, 2014
Diogenes	Jan 8, 2016
Dorpsgek	Apr 2, 2018
El Ajedrecista	Feb 25, 2015
En passant	Jan 16, 2018
Encoding Moves	Mar 27, 2016
Eugen	Jan 7, 2016
Eugenio Castillo Jiménez	Jul 23, 2017
Evaluation function draft	Jul 11, 2014
FCP	Jun 15, 2013
Fortress (Engine)	Oct 19, 2017
Freyr	Mar 6, 2014
General Setwise Operations	Feb 25, 2018
Gibbon	Dec 23, 2014
Gk	Oct 9, 2017
Gromit	Apr 5, 2017
HAL	Jun 14, 2016
Hash Table	Jan 1, 2018
HeavyChess	Feb 14, 2014
Incremental Updates	Sep 6, 2017
Innovation	Jun 12, 2016
IsiChess	Jan 7, 2016
J. Biit	Jan 17, 2017
Joker NL	Sep 15, 2017
King Pattern	Nov 15, 2013
King Safety	Feb 14, 2018
Lachex	Jan 7, 2016
Lazy Evaluation	Sep 1, 2017
Legal Move	Feb 16, 2017
LittleThought	Nov 7, 2016
MadChess	Jul 4, 2017
Make Move	Mar 2, 2016
MANIAC I	Nov 17, 2016
Material Hash Table	Apr 3, 2014
Material Tables	May 5, 2017
Matthew R. Brades	Jun 9, 2017
Mini Chess	Jun 7, 2013
Mobility	Jan 17, 2018
Monsoon	Feb 8, 2015
Moves	Feb 19, 2018
Much	Jun 7, 2016
Occupancy	Sep 19, 2016
Oracle	Sep 4, 2016
Ostrich	Dec 28, 2017
Pandix	Feb 4, 2017
Patzer	Apr 5, 2017
Pawn Hash Table	Feb 1, 2018
Pawn Push	Mar 27, 2010
Piece-Lists	Feb 13, 2017
Piece-Sets	Jun 9, 2017
Piece-Square Tables	Mar 31, 2018
Querg	Dec 11, 2013
ROCE	Jun 6, 2017
Rookie	Jan 7, 2016
Rotated Bitboards	Mar 7, 2017
Rotated Indices	Oct 9, 2017
Scid	Apr 15, 2017
Sierżant	Apr 15, 2014
SnailChess	Nov 26, 2014
SOS	Apr 5, 2017
Spartacus	Oct 17, 2016
Spector	Nov 11, 2016
Square Attacked By	Jan 20, 2018
Stack	Nov 18, 2016
Steven Edwards	Aug 26, 2017
Sunfish	Jan 11, 2018
Sunsetter	Jun 1, 2017
Tao	Jan 8, 2016
Thor's Hammer	Nov 23, 2013
Transposition Table	Apr 19, 2018
Unmake Move	Jun 10, 2017
Vlad Stamate	Dec 31, 2014
Warrior	Feb 23, 2015
Waxman	Aug 18, 2014
Woodpusher	Dec 12, 2016
Y!	Sep 10, 2017
Zappa	Oct 24, 2017
Zobrist Hashing	Jan 22, 2018

Up one Level

Irreversible Moves

GerdIsenberg — Sat, 25 Jan 2014 09:08:54 GMT

Home * Chess * Moves * Irreversible Moves

Irreversible Moves can not be reversed. Thus, they are either captures or pawn moves ^[1]. Making those irreversible moves, resets the halfmove clock inside a position object to zero, concerning the fifty-move rule. Quiet and otherwise reversible moves, which lose the castling rights, that is rook- and king-moves from their initial square, including castling itself, are irreversible in the sense to reverse the same rights - since once a castling right is lost, it is lost forever, and reset the position index to determine repetition of positions. However, those "irreversible" moves don't reset, but increment the halfmove clock ^[2].

External Links

Irreversible (disambiguation) from Wikipedia
Irreversible process from Wikipedia
Point of no return from Wikipedia
Eloy - Point Of No Return, Planets, 1981, YouTube Video

References

^ including promotions
^ Half Move Clock Confusion by HumbleProgrammer, OpenChess Forum, January 10, 2013

What links here?

Page	Date Edited
Chess Position	Sep 10, 2017
Endgame Tablebases	Mar 6, 2018
Fischer-Schneider	Nov 23, 2016
Halfmove Clock	Aug 9, 2017
Irreversible Moves	Jan 25, 2014
Make Move	Mar 2, 2016
Move List	Jul 19, 2017
Moves	Feb 19, 2018
Pawn Push	Mar 27, 2010
Repetitions	Jan 16, 2018
Reversible Moves	Mar 13, 2010
Tactical Moves	Sep 22, 2010

Up one Level

Killer Move

GerdIsenberg — Thu, 16 Feb 2017 16:46:47 GMT

Home * Chess * Moves * Killer Move

See also

Forum Posts

What links here?

The Killer Move is a Move Ordering related issue.

The Killer Move is a quiet move which caused a beta-cutoff in a sibling Cut-node, or any other earlier branch in the tree with the same ply distance to the root. The rule of thumb is to try that move early direct after a possibly available hash move from the transposition table and considering apparently winning captures. This simple but efficient move ordering heuristic is called the Killer Heuristic. Similar to moves from the transposition table , killers may actually save the generation of quiet moves at all if it fails high, but require a legality test.

Forum Posts

Killer moves by Chua Kong Sian, gnu.chess, March 21, 1995
killer moves? by Daniel Shawul, CCC, November 04, 2003
Killer moves? by Mike Robinson, CCC, September 16, 2011
Killer and move encoding by Fabio Gobbato, CCC, August 14, 2014 » Encoding Moves
Effectiveness of killer moves by Alex Ferguson, CCC, August 17, 2014
TTMove legality checking ? & Killers Move Format? by Mahmoud Uthman, CCC, February 08, 2017 » Hash Move

What links here?

Page	Date Edited
Amyan	Dec 10, 2013
Bebe	Dec 23, 2017
Best Move	May 15, 2017
Betsabe	Jul 23, 2017
Brutus	Dec 24, 2016
Chess 0.5	Nov 20, 2016
Clarabit	Nov 3, 2011
Cyrus 68K	Jan 7, 2016
DanaSah	Oct 9, 2017
Diablo	May 17, 2016
DirGolem	Jun 5, 2016
Djinn	Feb 8, 2016
ESC	Aug 14, 2013
Fidelity	Jan 7, 2016
FPGA	Jul 9, 2016
Gibbon	Dec 23, 2014
HAL	Jun 14, 2016
Hash Move	Oct 4, 2017
Horizon	Mar 17, 2013
Killer	Dec 15, 2017
Killer (NL)	Dec 15, 2017
Killer Chess	Jan 8, 2016
Killer Heuristic	Sep 14, 2017
Killer Move	Feb 16, 2017
Kurt	Apr 20, 2014
Legal Move	Feb 16, 2017
Mate Killers	Feb 4, 2017
Maverick	Jan 7, 2016
Move Generation	Jan 29, 2018
Move List	Jul 19, 2017
Move Ordering	Feb 27, 2018
Moves	Feb 19, 2018
Murka	Nov 11, 2016
MyChess	Dec 25, 2017
Null Move	Aug 9, 2017
Pieces versus Directions	Oct 6, 2016
Protector	Oct 12, 2017
Pseudo-Legal Move	May 23, 2015
Purple Haze	Oct 26, 2017
PV-Move	Jan 16, 2013
Querg	Dec 11, 2013
RDChess	May 3, 2013
Refutation Move	May 13, 2013
Search Statistics	Jan 16, 2018
Sensor Chess	Jun 7, 2013
Sinobyl	Jul 3, 2014
Spike	Jan 7, 2016
Square Attacked By	Jan 20, 2018
Terra	Feb 11, 2015
Thor's Hammer	Nov 23, 2013
Threat Move	Sep 10, 2017
Triangular PV-Table	Jun 12, 2017
Waxman	Aug 18, 2014
Winter	Jan 23, 2018

Up one Level

Late Move Reductions

GerdIsenberg — Mon, 25 Sep 2017 21:12:31 GMT

Home * Search * Selectivity * Reductions * Late Move Reductions

		Late Move Reductions (LMR), or its version known as History Pruning and History Reductions ^[1] , save search by reducing moves that are ordered closer to the end of likely fail-low nodes. Typically, most schemes search the first few moves (say 3-4) at full depth, then if no move fails high, many of the remaining moves are reduced in search depth. The technique has been used for many years in various forms, but it became very popular in 2005 after Fruit and Glaurung ^[2] used open source implementations based on the History Heuristic. LMR can often reduce the effective branching factor to less than 2, depending on the reduction conditions.
Samuel Bak - Other Rules ^[3]

Common Conditions

Less Common Conditions

Common Conditions

Most programs do not reduce these types of moves:

Tactical moves (captures and promotions)
Moves while in check
Moves which give check
Moves that cause a search extension
Anytime in a PV-Node in a PVS search
Depth < 3 (sometimes depth < 2)

Less Common Conditions

Less common conditions on moves not to reduce:

Passed Pawn Moves
Killer Moves
Moves threatening the King area
Tactically threatening moves
Moves with good past relative history ^[4]
Any Pawn Moves
Allowing reductions of "bad" captures (SEE < 0)
Moves of a threatened piece to safety (often detected via a Null Move search)

Reduction Depth

Classical implementation reduces by one ply only. Yet modern programs, most notably Stockfish, allow reductions of more than one ply and increase them for later moves. Reduction depth changes according to expected node type (being typically smaller in pv nodes), depth and move number. Here some sample formulas can be viewed:

Senpai reduces by one ply for the first 6 moves and by depth / 3 for remaining moves.
Fruit Reloaded uses formula: uint8( sqrt(double(depth-1)) + sqrt(double(moves-1))); for non-PV nodes. In PV-nodes it reduces by 2/3 of this value.

Re-searches

Classical implementation assumes a re-search at full depth if the reduced depth search returns a score above alpha.

Test Results

Some test results related to LMR can be found on

Late Move Reduction Test Results

Publications

David Levy, David Broughton, Mark Taylor (1989). The SEX Algorithm in Computer Chess. ICCA Journal, Vol. 12, No. 1
Daniel S. Abdi (2013). Analysis of pruned minimax trees. pdf » Alpha-Beta, Null Move Pruning

Forum Posts

2004

Forward pruning and some related techniques by Sergei Markoff, CCC, March 02, 2004

2005 ...

Reductions and null move refutations by Tord Romstad, Winboard Forum, April 18, 2005 » Null Move Pruning
What is History Pruning? by David Dahlem, CCC, July 03, 2005
History based pruning question by Alvaro Jose Povoa Cardoso, CCC, August 26, 2005
About history pruning... by Svein Bjørnar Myrvang, CCC, October 26, 2005
What is "history pruning"? by Vladimir Medvedev, Winboard Forum, November 07, 2005

2006

History pruning by Frank Phillips, CCC, February 27, 2006
late move reductions by Robert Hyatt, CCC, March 01, 2006
Re: late move reductions by Alessandro Scotti, CCC, March 01, 2006 » Kiwi
PHR (Peak History Reduction) idea by Daniel Mehrmann, CCC, March 01, 2006 » Homer, Relative History Heuristic
history pruning/ late move pruning by Tom King, Winboard Programming Forum, March 02, 2006
LMR question by Uri Blass, Winboard Programming Forum, July 13, 2006

2007

LMR in micro-Max by Harm Geert Muller, CCC, April 07, 2007 » Micro-Max
Fruit and History Reductions by Ed Schröder, CCC, July 19, 2007 » Fruit
LMR other conditions by Mark Lefler, CCC, July 23, 2007
Improving history tables by Michael Sherwin, CCC, July 25, 2007
LMR: history or not? by Alessandro Scotti, CCC, December 13, 2007 » Hamsters

2008

Extreme late move reductions? by Gary, CCC, March 05, 2008
LMR? by Martin Giepmans, CCC, April 12, 2008 » Anatoli
Adaptative LMR and TT by Fermin Serrano, CCC, December 23, 2008

2009

About LMR & History reductions by Joona Kiiski, CCC, February 24, 2009
LMR by Robert Hyatt, CCC, March 05, 2009
LMR and 'tactically connected' moves by Harm Geert Muller, CCC, March 10, 2009
LMR revisited by Robert Hyatt, CCC, April 01, 2009
LMR and null move selectivity by Don Dailey, CCC, April 20, 2009
LMR by Bas Hamstra, CCC, September 30, 2009
May I Ask What You Think Of This? by Christopher Conkie, CCC, October 20, 2009
Did people try replacing LMR by pruning by Uri Blass, CCC, December 31, 2009

2010 ...

The problem with LMR in suprtactical positions by Oliver Brausch, CCC, January 05, 2010
Researching if LMR-affected search improves Alpha? by John Merlino, CCC, January 22, 2010
Problems with LMR in late endgames by Luca Hemmerich, CCC, March 01, 2010
LMR algorithm by kenny stanley, CCC, March 15, 2010
LMR Conditions by kenny stanley, CCC, March 23, 2010
LMR at root of search tree - worthwhile? by Tom King, CCC, May 21, 2010
EPR, even better than LMR! by Michael Sherwin, CCC, May 27, 2010
Re: "Automated Discovery of Search Extensions" by Ed Schröder, OpenChess Forum, June 26, 2010
lmr at PV nodes? by Tom King, CCC, July 23, 2010
move count based pruning by Tom King, CCC, September 02, 2010
LMR differences in long vs short games by Jacob Børs Lind, CCC, November 08, 2010
fulitiy + lmr; funny results by Volker Böhm, CCC, December 28, 2010

2011

lmr in PV by Larry Kaufman, CCC, January 03, 2011

2012

Should reduction depend on depth? by Larry Kaufman, CCC, January 14, 2012 » Komodo
Possible LMR improvement using AB_FOOL by Ed Schroder, CCC, April 24, 2012
LMR Research by Matthew R. Brades, CCC, July 02, 2012
Adjustable search pruning depending on time control by Jerry Donald, CCC, December 20, 2012 » Time Management

2013

ROC analysis of Late Move Reductions by Gerard van Ewijk, CCC, March 22, 2013 ^[5]
Is LMR Sound by Henk van den Belt, CCC, May 29, 2013
Is LMR safe within NULL move reduction by Henk van den Belt, CCC, May 30, 2013
LMR at CUT nodes can be arbitrarily bad! by Michel Van den Bergh, CCC, June 20, 2013 » Node Types, Python
How much to reduce ? by Henk van den Belt, CCC, October 03, 2013 » R

2014

Null move and LMR by Laurie Tunnicliffe, CCC, March 12, 2014 » Null Move Pruning
LMR & TT interaction by Natale Galioto, CCC, April 29, 2014 » Transposition Table
A question about Stockfish and LMR or other pruning... by Forrest Hoch, CCC, November 20, 2014

2015 ...

About LMR , again :-) by Daniel Anulliero, CCC, March 01, 2015
LMR tuning by Shawn Chidester, CCC, May 11, 2015
Interpretation of LMR by Alexandru Mosoi, CCC, May 29, 2015
What's Your Engine's Maximum LMR Reduction? by Steve Maughan, CCC, June 08, 2015
New "smoothing" issue by Robert Hyatt, CCC, July 20, 2015
On LMR, and statically predicting moves by Matthew Lai, CCC, August 25, 2015
LMR by another name by Steven Edwards, CCC, September 02, 2015 » Spector
Ratio reduction by Steven Edwards, CCC, September 20, 2015 » Symbolic

2016

late move reduction by Folkert van Heusden, CCC, January 21, 2016
Extensions in the days of LMR? by Martin Fierz, CCC, March 22, 2016 » Extensions
LMR problems by Alvaro Cardoso, CCC, May 16, 2016
Reductions by Harm Geert Muller, CCC, May 22, 2016 » R
Disappointing LMR Results by David Cimbalista, CCC, August 04, 2016
Null Move in LMR by Laurie Tunnicliffe, CCC, August 10, 2016 » Null Move Pruning

2017

LMR and PVS by thevinenator, OpenChess Forum, February 10, 2017 » Principal Variation Search
Late move reductions ? by Mahmoud Uthman, CCC, March 22, 2017
Check extension vs LMR by Harm Geert Muller, CCC, April 04, 2017 » Check Extensions
LMR - [for starters] - [Advance] and [Expert] by Ed Schroder, CCC, May 01, 2017
LMR and killer by Harm Geert Muller, CCC, September 14, 2017 » Killer Heuristic
LMR prescription by Evert Glebbeek, CCC, September 24, 2017

External Links

Late Move Reductions

Late Move Reductions from Wikipedia
An Introduction to Late Move Reductions by Tord Romstad (dead link)
Mediocre Chess: [Guide] Late move reduction (LMR) by Jonatan Pettersson, March 26, 2007 » Mediocre
History Reductions in Pro Deo by Ed Schröder » Pro Deo
LMR advanced from Rebel 13 by Ed Schroder ^[6] » Rebel

Misc

Wolfgang Schmid - The Latest Kick, Bix Jazzclub Stuttgart, Summer 2010, YouTube Video

References

^ History Reductions in Pro Deo by Ed Schröder
^ An Introduction to Late Move Reductions by Tord Romstad
^ Chess in the Art of Samuel Bak, Center for Holocaust & Genocide Studies, University of Minnesota
^ Mark Winands, Erik van der Werf, Jaap van den Herik, and Jos Uiterwijk (2006). The Relative History Heuristic. Computers and Games, Lecture Notes in Computer Science (LNCS 3846) (eds. Jaap van den Herik, Yngvi Björnsson, and Nathan S. Netanyahu), pp. 262-272. pdf
^ Receiver operating characteristic (ROC) from Wikipedia
^ LMR - [for starters] - [Advance] and [Expert] by Ed Schroder, CCC, May 01, 2017

What links here?

Page	Date Edited
Alessandro Scotti	Feb 27, 2014
AliBaba	Aug 17, 2014
Alpha-Beta	Jan 28, 2018
Alvaro Cardoso	Jan 12, 2018
Amoeba	Mar 19, 2018
Amundsen	Sep 3, 2013
Amyan	Dec 10, 2013
Anatoli	Oct 22, 2014
Andscacs	Jan 16, 2018
Artificial Intelligence	Apr 9, 2018
Atlas (ESP)	Jan 28, 2018
Bagatur	Sep 10, 2016
Bas Hamstra	Feb 4, 2018
Betsabe	Jul 23, 2017
Bison	Sep 29, 2016
Bobcat	Jun 27, 2017
Booot	Jan 22, 2018
Brainless	Jun 24, 2017
Branching Factor	Jun 28, 2017
Bright	Oct 25, 2016
Butterfly Boards	Jan 27, 2015
Butterfly Heuristic	May 6, 2016
Capture Extensions	Oct 26, 2012
Carballo	Oct 2, 2016
Check Extensions	Apr 19, 2018
Cheese	Feb 17, 2018
Cheng	Jul 30, 2017
Chepla	May 10, 2013
chess22k	Apr 23, 2018
ChessBrainVB	Jun 24, 2017
ChessV	Jan 21, 2018
Christopher Conkie	May 17, 2016
Cinnamon	Sep 23, 2017
Clarabit	Nov 3, 2011
Clubfoot	Sep 8, 2015
Coiled	Mar 12, 2017
Counter	Nov 13, 2017
CPW history	Jan 1, 2015
Crafty	Jan 28, 2018
CuckooChess	Jan 17, 2017
Cupcake	May 19, 2016
CXG Sphinx	Jun 23, 2017
Cyrus 68K	Jan 7, 2016
DanaSah	Oct 9, 2017
Daniel Anulliero	Oct 3, 2017
Daniel Mehrmann	Dec 13, 2015
Daniel Shawul	Jan 28, 2018
DayDreamer	Aug 22, 2016
Defenchess	Mar 18, 2018
Delfi	Jan 7, 2016
Demolito	Mar 1, 2018
Depth	Feb 25, 2018
Depth Reduction R	Oct 4, 2017
Deuterium	Jun 23, 2014
Dictionary	Aug 24, 2017
Dimitri	Aug 22, 2017
DisasterArea	Mar 27, 2017
DiscoCheck	Jun 23, 2017
Donna	Aug 17, 2017
Dorky	Oct 10, 2016
Dorpsgek	Apr 2, 2018
Encoding Moves	Mar 27, 2016
Engine Testing	Feb 1, 2018
Ethereal	Mar 20, 2018
Eveann	Apr 3, 2017
Evert Glebbeek	Sep 25, 2017
Exacto	Oct 3, 2015
Extensions	Apr 19, 2018
Fail-High Reductions	Mar 6, 2014
FCP	Jun 15, 2013
Fermin Serrano	Nov 27, 2015
Fischerle	Aug 21, 2017
Flux	Jan 12, 2016
Folkert van Heusden	Nov 24, 2017
Frank Phillips	Sep 26, 2016
Fridolin	Jun 27, 2017
Fruit	Sep 27, 2016
Futility Pruning	Aug 30, 2017
Galjoen	Mar 19, 2018
Garbochess	Sep 23, 2017
Garbochess-JS	Sep 23, 2017
Gary Linscott	Jan 16, 2018
Gaviota	Jan 21, 2018
Ghost	Feb 2, 2018
Gibbon	Dec 23, 2014
Ginkgo	Jul 13, 2016
Glass	May 24, 2017
Glaurung	Mar 14, 2017
Go	Jan 24, 2018
Gogobello	Jul 30, 2017
GopherCheck	Feb 3, 2017
Hakkapeliitta	Apr 26, 2016
Hamsters	Apr 11, 2014
HaQiKi D	Jul 26, 2017
Harm Geert Muller	Mar 31, 2018
History Heuristic	Jul 19, 2017
History Leaf Pruning	Apr 15, 2013
Home	Jul 2, 2018
Homer	Dec 23, 2013
Horizon	Mar 17, 2013
iCE	Jan 4, 2016
Ifrit	Feb 7, 2016
ISA	Apr 2, 2018
JFresh	Mar 2, 2016
JikChess	Nov 29, 2015
John Merlino	Feb 26, 2015
Killer Heuristic	Sep 14, 2017
KingSlayer	Oct 17, 2016
Kiwi	Sep 2, 2016
Komodo	Mar 6, 2018
Larry Kaufman	Jan 28, 2018
Laser	Dec 27, 2017
Late Move Reduction Test Results	Sep 25, 2017
Late Move Reductions	Sep 25, 2017
Laurie Tunnicliffe	Jun 13, 2017
Little Wing	Oct 26, 2017
LittleThought	Nov 7, 2016
Lozza	Apr 18, 2018
Luca Hemmerich	Jun 19, 2017
MadChess	Jul 4, 2017
Mark Lefler	Nov 23, 2017
Martin Fierz	Apr 26, 2018
Marvin	Feb 10, 2018
Matthew R. Brades	Jun 9, 2017
Mediocre	Feb 27, 2015
Micro-Max	Aug 7, 2017
Murka	Nov 11, 2016
Napoleon	Jun 25, 2017
Naum	Nov 23, 2017
Nebula	Feb 7, 2015
Nemorino	Dec 21, 2017
Nirvanachess	Sep 30, 2017
Node Types	Oct 22, 2017
NoraGrace	Nov 23, 2014
Null Move Pruning	Dec 2, 2017
Obender	Apr 17, 2016
Octochess	Aug 15, 2017
OliThink	May 19, 2017
Oliver Brausch	May 19, 2017
Orion	Oct 15, 2017
Paladin	Jan 29, 2017
Parity Pruning	Jan 14, 2013
Path-Dependency	Oct 16, 2017
Pawny	Jun 17, 2015
Phalanx	May 2, 2016
Philidor	Jan 7, 2016
Plisk	Dec 31, 2014
Prédateur	Nov 11, 2016
Principal Variation Search	Oct 22, 2017
ProbCut	Mar 25, 2016
Protector	Oct 12, 2017
Pruning	Jan 1, 2018
PV Extensions	May 4, 2013
Python	Jan 31, 2018
RattateChess	Dec 2, 2014
Reductions	Nov 1, 2017
Relative History Heuristic	Jun 8, 2015
Rhetoric	Nov 15, 2017
Robert Hyatt	Dec 25, 2017
Robocide	May 11, 2016
Rodent	Jan 11, 2018
RomiChess	Jan 2, 2018
RuyDos	Feb 17, 2018
Rybka	Mar 27, 2017
Sayuri	Oct 1, 2017
Schooner	Feb 2, 2018
Search Instability	May 5, 2017
Selectivity	Jan 12, 2018
Senpai	Nov 10, 2017
SEX Algorithm	Nov 25, 2014
Shawn Chidester	Aug 9, 2016
Shield	May 17, 2017
Simplex	Mar 6, 2016
Sjaak (Glebbeek)	Oct 4, 2017
Sloppy	Sep 17, 2016
Soldat	Aug 20, 2017
Spark	Oct 19, 2017
Spector	Nov 11, 2016
Spike	Jan 7, 2016
Stockfish	Apr 7, 2018
Symbolic	May 8, 2017
Tactics	Jan 12, 2018
Teki	Mar 29, 2018
Texel	Oct 9, 2017
The Baron	Jan 8, 2018
The Turk (TR)	Apr 1, 2017
Tigran	Aug 16, 2015
Time Management	Mar 20, 2018
Tom King	Aug 19, 2017
tomitankChess	Dec 8, 2017
Tord Romstad	Dec 9, 2017
Tornado	Dec 14, 2017
TRACE	Feb 14, 2013
Transposition Table	Apr 19, 2018
Tucano	Dec 16, 2017
Tunguska	Sep 16, 2017
UCT	Jan 22, 2018
Uncertainty Cut-Offs	Jul 21, 2015
Vadim Demichev	Jul 26, 2013
Vajolet	Jan 25, 2018
Vladimir Medvedev	Jul 22, 2016
Volker Böhm	Jan 7, 2016
Wasp	Nov 24, 2017
WildCat	Nov 11, 2016
Wing	Oct 26, 2017
Winter	Jan 23, 2018
WyldChess	Mar 10, 2018
Xiphos	Apr 22, 2018
Ziggy IS	Sep 6, 2015
Zochova	Nov 9, 2014
Zurichess	Mar 12, 2018

Up one level

Legal Move

GerdIsenberg — Thu, 16 Feb 2017 16:47:59 GMT

Home * Chess * Moves * Legal Move

		A Legal Move is a pseudo-legal move which does not leave its own king in check. If not in check, most programs delay the legality test to the child node, after incremental updates attack and defend maps or an explicit square attacked test direct after make move. Earlier programs were even more "lazy", to determine illegal moves after an illegal king capture, while many programs consider absolutely pinned pieces in move generation and also for evaluation purpose, or even perform a strictly legal generation to demand searching legal positions. If in check, most programs apply a special move generator to omit the majority of illegal moves.
Marina Kalinovsky, The King can never be Captured ^[1]

Legality Test

Beside the pseudo-legal condition which might already be sufficient for a subset of chess programs, there are several conditions to test, dependent whether the king is in check or not.

Not in Check

The moving piece is not absolutely pinned on its move direction
En passant requires special horizontal pin test of both involved pawns, which disappear from the same rank
While castling, rook is not pinned horizontally in Chess960

King in Check

Double Check

Only king moves to non attacked squares, sliding check x-rays the king

Single Check

Capture of checking piece. The capturing piece is not absolutely pinned
King moves to non attacked squares, sliding check x-rays the king
Interposing moves in case of distant sliding check. The moving piece is not absolutely pinned.

Forum Posts

Question about testing legality of moves by ambrooks1, Winboard Forum, February 07, 2014
En-passant legality test by tetra, OpenChess Forum, August 07, 2014 » En passant
TTMove legality checking ? & Killers Move Format? by Mahmoud Uthman, CCC, February 08, 2017 » Hash Move, Killer Move

References

^ Marina Kalinovsky, Portfolio, Drawings, Page 1

What links here?

Page	Date Edited
Abyss	Aug 5, 2017
Algebraic Chess Notation	Sep 25, 2017
Berkeley Chess Microprocessor	May 22, 2013
Check	Feb 1, 2018
Checks and Pinned Pieces (Bitboards)	Aug 14, 2013
CHEOPS	Apr 18, 2015
Chess Game	Mar 28, 2017
Chest	Mar 3, 2015
Countermove Heuristic	Oct 1, 2017
DirGolem	Jun 5, 2016
Double Check	Apr 4, 2013
En passant	Jan 16, 2018
Entering Moves	Sep 7, 2017
Eval Tuning in Deep Thought	Jun 7, 2016
Fifty-move Rule	Aug 9, 2017
Freedom	Dec 28, 2017
Genie	Feb 7, 2016
Gibbon	Dec 23, 2014
GiuChess	May 8, 2017
Giuliano Ippoliti	Feb 22, 2014
Hash Move	Oct 4, 2017
Interior Node Recognizer	Mar 12, 2018
Jan Eric Larsson	Dec 11, 2013
Killer Move	Feb 16, 2017
Legal Move	Feb 16, 2017
Mark Bromley	Oct 12, 2016
Mate at a Glance	Sep 24, 2014
Mate-in-two	Oct 14, 2016
Mobility	Jan 17, 2018
Move Generation	Jan 29, 2018
Moves	Feb 19, 2018
Mr. Turk	Feb 21, 2015
One Reply Extensions	Dec 31, 2014
Pawn Push	Mar 27, 2010
Perft	Sep 26, 2017
Pieces versus Directions	Oct 6, 2016
Pin	Mar 7, 2017
Pseudo-Legal Move	May 23, 2015
Purple Haze	Oct 26, 2017
RDChess	May 3, 2013
Retrograde Analysis	Mar 21, 2017
Ryan Rifkin	Oct 12, 2016
Spector	Nov 11, 2016
Square Attacked By	Jan 20, 2018
Stalemate	Feb 21, 2018
Terminal Node	Nov 17, 2012
Warlord	Apr 15, 2014
Stockfish : home	Feb 2, 2014

Up one Level

Make Move

GerdIsenberg — Wed, 02 Mar 2016 16:46:50 GMT

Home * Chess * Moves * Make Move

Make Move is a function inside a chess program to update the internal chess position and its board representation as well as associated or dependent state variables and data by a move made on the internal board, such as zobrist keys to index the transposition table. That usually happens inside the Search algorithm, where the move acts like an edge connecting two nodes of a search tree, a parent and a child node. Dependent on the design of the data structures and the used search algorithms there are different approaches with respect to randomly accessing aspects of nodes and restoring the position while unmaking the move.

Operations

The general arithmetical and/or bitwise-logical operations to convert a node to its child are either reversible (even for irreversible moves), by inverse (e.g. addition and subtraction) or own inverse (exclusive or) operations, or are irreversible, for instance a sequence of addition and conjunction (add, and) of move aspects, to update ep state, castling rights and the halfmove clock.

Update

Aspects of a position altered by reversible operations may be kept in global structures, shared by all nodes of the tree, for instance square centric mailbox board arrays or bitboard board-definition, and require incremental updates by make and unmake. Irreversible aspects of the position, which can not generally restored from a child-position by unmaking a move, need to be restored by either re-playing the whole game record from the root position (too slow), or to be memorized inside an array indexed by ply or on a stack (LIFO), most notably ep state, castling rights and the halfmove clock enforcing the fifty-move rule.

All those aspects of a position, no matter if reversible by unmake or not, which may need random access in a branch of moves from the root (or initial position of the game) to the current position inside a certain implementation of a search algorithm, require an array of those aspects, indexed by ply, and updated by a Copy-Make approach.

Forum Posts

doing undoing by Fritz Reul, CCC, May 14, 2007
performance of copy-make by Rein Halbersma, CCC, August 02, 2011
Saving info before making a move by CDaley11, OpenChess Forum, December 30, 2013

What links here?

Page	Date Edited
Aaron Becker	Jul 22, 2015
Alpha-Beta	Jan 28, 2018
Anechka	Mar 20, 2014
Attack and Defend Maps	Nov 5, 2016
Bebe	Dec 23, 2017
Belle	Jan 18, 2018
Bitboard Board-Definition	Jun 23, 2014
Bitboards	Nov 14, 2017
Board Representation	Dec 11, 2017
Carballo	Oct 2, 2016
Castling rights	Jan 7, 2017
Checkmate	Apr 13, 2018
Cilkchess	Jan 21, 2016
Color Flipping	May 17, 2017
Copy-Make	May 23, 2017
Dabbaba	Oct 21, 2014
DayDreamer	Aug 22, 2016
El Ajedrecista	Feb 25, 2015
En passant	Jan 16, 2018
Encoding Moves	Mar 27, 2016
Entering Moves	Sep 7, 2017
Eugen	Jan 7, 2016
Eugenio Castillo Jiménez	Jul 23, 2017
Evaluation function draft	Jul 11, 2014
Extensions	Apr 19, 2018
FPGA	Jul 9, 2016
Fritz Reul	Nov 28, 2016
General Setwise Operations	Feb 25, 2018
Gk	Oct 9, 2017
Incremental Updates	Sep 6, 2017
Innovation	Jun 12, 2016
Irreversible Moves	Jan 25, 2014
Iteration	May 5, 2017
Jonathan Warkentin	Jun 29, 2014
King Pattern	Nov 15, 2013
Komodo	Mar 6, 2018
Legal Move	Feb 16, 2017
Linked List	Oct 11, 2016
LTChess	Mar 30, 2017
Make Move	Mar 2, 2016
MANIAC I	Nov 17, 2016
Mate-in-two	Oct 14, 2016
Mater	Apr 26, 2016
MBChess	Sep 29, 2012
Mini Chess	Jun 7, 2013
Minimax	Dec 29, 2017
Move Generation	Jan 29, 2018
Move List	Jul 19, 2017
Moves	Feb 19, 2018
Negamax	Sep 11, 2015
Nibble	Jan 25, 2015
Nodes per second	Feb 28, 2018
Oracle	Sep 4, 2016
Othello	Jan 4, 2018
Pawn Push	Mar 27, 2010
Perft	Sep 26, 2017
Piece-Lists	Feb 13, 2017
Piece-Square Tables	Mar 31, 2018
Pieces versus Directions	Oct 6, 2016
Pigeon	Nov 2, 2016
python-chess	Nov 4, 2017
Quad-Bitboards	Jan 30, 2017
Querg	Dec 11, 2013
Rabbit	Oct 5, 2014
Razoring	Oct 5, 2015
Reverse Futility Pruning	Jun 2, 2017
Reversible Moves	Mar 13, 2010
ROCE	Jun 6, 2017
Rotated Bitboards	Mar 7, 2017
Rotated Indices	Oct 9, 2017
Search	Feb 1, 2018
Side to move	Oct 29, 2017
Sidonia	May 19, 2016
Stack	Nov 18, 2016
Sunfish	Jan 11, 2018
Target Square	Oct 26, 2017
Teki	Mar 29, 2018
Transposition Table	Apr 19, 2018
Unmake Move	Jun 10, 2017
Vice	Mar 8, 2016
Winglet to include	Apr 25, 2015
Woodpusher	Dec 12, 2016
Zobrist Hashing	Jan 22, 2018

Up one Level

Move Generation

GerdIsenberg — Mon, 29 Jan 2018 08:17:10 GMT

Home * Board Representation * Move Generation

		Generation of moves is a basic part of a chess engine with many variations concerning a generator or an iterator to loop over moves inside the search routine. The implementation heavily depends on the board representation, and it can be generalized into two types, pseudo-legal and legal move generation.
Blast Generation ^[1]

Legality

Pseudo-legal

In Pseudo-legal move generation pieces obey their normal rules of movement, but they're not checked beforehand to see if they'll leave the king in check. It is left up to the move-making function to test the move, or it is even possible to let the king remain in check and only test for the capture of the king on the next move.

Legal

In Legal move generation, as the name implies, only legal moves are generated, which means extra time must be spent to make sure the king isn't going to be left or placed in check after each move. Pins are the main difficulty, particularly when en passant is involved.

Special Generators

Most programs use special move generators for the quiescence search, sometimes supplemented by one for getting out of check. These special cases can be made more efficient than generating and testing each possible move to fit specific criteria. For example, if the king is in check, the only possible legal moves are to capture the attacking piece, block the attacker if it is a "ray" piece, or move the king to safety. Special generators for the quiescence search might want to generate checks in addition to captures and promotions. They can use the fact that a knight or bishop must start off on the same color square as the opponent king if they are to attack it. And rooks can only generate at most 2 checking moves...to the squares with the rook's column and the king's row or the king's column and the rooks row.

Similar tricks can be used for generating possible moves out of check, which must be by the king, capturing the opponent's checking piece, or blocking its attack if it is a ray piece. When in double check, only king moves are permitted.

Chunk move generation

With move ordering in mind, chess programs, while traversing pieces and their move-target sets once, store and buffer generated moves inside one or two move lists (i.e. for tactical and quiet moves), which is convenient for book-keeping and assigning scores based on MVV-LVA, SEE, history, piece square table etc., to later perform a selection sort before actually making the move.

Staged move generation

Some programs do not generate all moves at once, but do it in several stages (i.e. hash move first, then captures, then killer moves, then all the rest in a chunk) on the premise that if one of the early moves causes a cutoff, then we may save on the effort of generating the rest of the moves ^[2].

Debugging

It is important to ensure that the move generator works properly. Although this could be tested by playing many games, a better approach is to write a Perft function. This function recursively generates moves for the current position and all children up to a certain depth, and by counting all the leaf nodes, it can be compared to a table of values to test its accuracy.

Publications

1950 ...

Dietrich Prinz (1952). Robot Chess. Research, Vol. 6, reprinted 1988 in Computer Chess Compendium

1970 ...

Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227
Gerard Zieliński (1976). Arrays for Programming Chess. Kybernetes, Vol. 5, No. 2
Ozalp Babaoglu (1977). Hardware implementation of the legal move generation and relative ordering functions for the game of chess. Master's thesis, University of California, Berkeley
Peter W. Frey (1977). An Introduction to Computer Chess. Chess Skill in Man and Machine pp. 54-81

1980 ...

Joe Condon, Ken Thompson (1982). Belle Chess Hardware, Advances in Computer Chess 3, Reprinted (1988) in Computer Chess Compendium
Greg Bakker, Jim Jonkman, Jonathan Schaeffer, Tom Schultz (1982). VLSI Implementation of a Chess Legal Move Generator. EE755S-1, University of Waterloo ^[3]
Jonathan Schaeffer, Patrick A.D. Powell, Jim Jonkman (1983). A VLSI legal move generator for the game of chess. in Randal Bryant (eds.) Third Caltech Conference on Very Large Scale Integration
Carl Ebeling, Andrew James Palay (1984). The Design and Implementation of a VLSI Chess Move Generator. Proceedings of the 11th Annual International Symposium on Computer Architecture. IEEE and ACM.
Stuart Cracraft (1984). Bitmap move generation in Chess. ICCA Journal, Vol. 7, No. 3
Burton Wendroff (1985). Attack Detection and Move Generation on the X-MP/48. ICCA Journal, Vol. 8, No. 2
Carl Ebeling (1986). All the Right Moves: A VLSI Architecture for Chess. Ph.D. thesis, Carnegie Mellon University, MIT Press, Cambridge, MA. ISBN 0-262-05035-8.
Feng-hsiung Hsu (1986). Two designs of functional units for VLSI based chess machines. Carnegie Mellon University, Computer Science Department. Paper 1566.
Feng-hsiung Hsu (1987). A Two-Million Moves/Sec CMOS Single-Chip Chess Move Generator. IEEE J. of Solid-state Circuits, Vol. 22, No. 5, pp. 841-846.

1990 ...

James Testa, Alvin M. Despain (1990). A CMOS VLSI chess microprocessor. University of California, Berkeley, IEEE Custom Integrated Circuit Conference
Chun Ye (1992). Experiments in Selective Search Extensions. MSc. thesis, Department of Computing Science, University of Alberta, pdf
Yi-Fan Ke, Tai-Ming Parng (1996). Parallel Move Generation System for Computer Chess. IEICE Transactions on Information and Systems, April, 1996, pp. 290-296
Ernst A. Heinz (1997). How DarkThought Plays Chess. ICCA Journal, Vol. 20, No. 3
Robert Hyatt (1999). Rotated Bitmaps, a New Twist on an Old Idea. ICCA Journal, Vol. 22, No. 4
Feng-hsiung Hsu (1999). IBM’s Deep Blue Chess Grandmaster Chips. pdf

2000 ...

Reijer Grimbergen, Hitoshi Matsubara (2001). Plausible Move Generation in Two-Player Complete Information Games Using Static Evaluation. Transactions of the Japanese Society for Artificial Intelligence, Vol.16, pp. 55-62. pdf
Marc Boulé (2002). An FPGA Move Generator for the Game of Chess. Masters thesis, McGill University, (Supervisor: Zeljko Zilic, Co-Supervisor: Monty Newborn), pdf
Marc Boulé, Zeljko Zilic (2002). An FPGA Move Generator for the Game of Chess. McGill University, pdf » FPGA
Marc Boulé, Zeljko Zilic (2002). An FPGA Move Generator for the Game of Chess. ICGA Journal, Vol. 25, No. 2, pdf
Reijer Grimbergen (2007). Using Bitboards for Move Generation in Shogi. ICGA Journal, Vol. 30, No. 1, pdf, was topic of the 11th Game Programming Workshop
Fritz Reul (2009). New Architectures in Computer Chess, Ph.D. Thesis, pdf

2010 ...

Adrien Couetoux, Olivier Teytaud, Hassen Doghmen (2012). Learning a Move-Generator for Upper Confidence Trees. ICS 2012, Hualien, Taiwan, December 2012 » Learning, UCT

Forum Posts

1990 ...

move generators in computer chess by Deniz Yuret, rgcc, October 11, 1994
Re: move generators in computer chess, Tricky bit tricks by Marcel van Kervinck, rgcc, October 20, 1994 » Traversing Subsets of a Set
bitboard move generation by Robert Hyatt, rgc, October 25, 1994
move generators in computer chess by Joël Rivat, rgc, October 26, 1994
bitboard move generator by Joël Rivat, rgc, November 13, 1994
Speed of Move Generator by Valavan Manohararajah, rgcc, August 15, 1995
Move generator design choices by Martin Borriss, rgcc, April 26, 1996
Sane numbers by Martin Borriss, rgcc, June 26, 1996
GNU move generation by Jan Willem de Kort, rgcc, March 18, 1998 » GNU Chess

2000 ...

Fast BB move generation by Bas Hamstra, CCC, May 08, 2000
move_generation + hash by Georg von Zimmermann, CCC, May 28, 2000
Pre-calculated move generation by Ujecrh, CCC, June 26, 2000
Move generation question for the big boys by Sune Fischer, CCC, September 15, 2001
Precomputed move information by Sune Fischer, CCC, July 02, 2002
Natural move generation with bitboards (was Re:significant math) by Alessandro Damiani, CCC, November 20, 2002
Strength question by Bruce Moreland, CCC, January 05, 2003
Which open source chess program has the fastest move generator? by Dennis Breuker, CCC, April 25, 2003
Improvements in BF makes my MoveGen suck =( by Albert Bertilsson, CCC, June 26, 2003 » Branching Factor
Speed improvement in split move generation by Federico Corigliano, CCC, August 16, 2003
Move Generation Speed by Dan Honeycutt, Winboard Forum, October 21, 2004

2005 ...

Is it time for another new move generator? by Michael Sherwin, CCC, November 11, 2007
Did someone mention the GNUChess move Generator? by Michael Sherwin, CCC, November 12, 2007 » GNU Chess
Move generator by kongsian, CCC, April 12, 2008
Bitboards / move generation on larger boards by Gregory Strong, CCC, January 09, 2009
Move generation: staged vs all-at-once by Steven Edwards, CCC, April 30, 2009
Re: Move generation: staged vs all-at-once by Lance Perkins, CCC, April 30, 2009

2010 ...

Assembly move generation in Freccia by Stefano Gemma, CCC, July 26, 2011

2012

move generation speed by Folkert van Heusden, Winboard Forum, January 03, 2012
Is there such a thing as branchless move generation? by John Hamlen, CCC, June 07, 2012 » DirGolem, GPU
hyper threading and move generation by Gabor Buella, CCC, August 01, 2012
What's the fastest move generator? by Marcel Fournier, CCC, August 29, 2012
Re: Question About CPP-C#, Performance, and Square Representation by Erik Madsen, CCC, October 03, 2012 » MadChess ^[4] ^[5]
Plausible move generator by Jorge Garcia, CCC, November 09, 2012
Diepeveen's move generator by Hrvoje Horvatic, CCC, November 18, 2012 » Table-driven Move Generation

2014

Just another movegen by Syed Fahad, CCC, November 14, 2014
How to call the Satana move generation by Stefano Gemma, CCC, November 17, 2014 » Satana
Black/White symmetry in move generation by Jeffery A Esposito, CCC, November 25, 2014 » Color Flipping
Symmetric move generation using bitboards by Lasse Hansen, CCC, December 20, 2014
Reverse move generation by Kostas Oreopoulos, December 30, 2014 » Retrograde Analysis

2015 ...

On bitboard legal move generation by Lasse Hansen, CCC, February 09, 2015
Questions about chess programming from a newbie by Matt Palmer, CCC, April 18, 2015
Caching generated moves list in recursive searches by Rein Halbersma, CCC, May 10, 2015

2016

speed up your engine part 4 by Laurie Tunnicliffe, CCC, August 03, 2016 » Staged move generation
Performance diff between legal / illegal move generator by Mahmoud Uthman, CCC, October 22, 2016

2017

Most efficient way to generate legal king moves? by notachessplayer, OpenChess Forum, February 04, 2017
Back to the basics, generating moves on gpu in parallel... by Srdja Matovic, CCC, March 05, 2017 » GPU
Fastest pawn quiet move generation I was able to come with by Daniel José Queraltó, CCC, June 10, 2017 » Duff's Device
History heuristic and quiet move generation by Daniel José Queraltó, CCC, July 16, 2017 » History Heuristic
Skipping duplicat moves by Harm Geert Muller, CCC, December 03, 2017

External Links

Chapter 3: Board Games - 3.1 CHESS from Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227
Description of 0x88 method from Bruce Moreland's Programming Topics
Move Table move generation from Bruce Moreland's Programming Topics
How Zarkov Plays Chess by John Stanback
Monsoon/Typhoon Homepage by Scott Gasch, covers 0x88 move generation
generate.c by Scott Gasch
Description of Rotated Bitboards by Robert Hyatt
Buzz - A Winboard Chess Playing Program by Pradu Kannan - Source of magic Move Generator
Chess Programming Part III: Move Generation by François-Dominic Laramée, gamedev.net, July 2000
Chess Move Generator - Computer Architecture and Languages Laboratory, University of Maribor
Engine - Hispanic Chess Engines | The move generator by Pedro Castro
Generator (computer programming) from Wikipedia

References

^ electric driven air compressor in the machine hall of Zollern II/IV Colliery, Dortmund Bövinghausen, Germany - part of The Industrial Heritage Trail, Photo by Gerd Isenberg, September 18, 2016
^ Move generation: staged vs all-at-once by Steven Edwards, CCC, April 30, 2009
^ 1983 | Waking up to change in Chris Redmond and Simon the Troll (1998). Water Under the Bridge. University of Waterloo » VLSI Move Generation
^ yield - MSDN C# Reference
^ Behind the scenes of the C# yield keyword | Struggles by Lars Corneliussen, June 9, 2008

What links here?

Page	Date Edited
0x88	Nov 28, 2016
10x12 Board	Feb 19, 2018
8x8 Board	Aug 29, 2017
Abyss	Aug 5, 2017
Advance	Jan 7, 2016
Alaric	Mar 4, 2014
Albert Bertilsson	Jun 6, 2017
Algebraic Chess Notation	Sep 25, 2017
AltiVec	Jun 7, 2016
Amoeba	Mar 19, 2018
Anechka	Mar 20, 2014
Ankan Banerjee	Aug 26, 2017
Arion	Nov 28, 2014
Atlas	Nov 5, 2017
Attack and Defend Maps	Nov 5, 2016
Bas Hamstra	Feb 4, 2018
Beaches	Jun 10, 2017
Bebe	Dec 23, 2017
BELCT 2001	Apr 4, 2017
Belle	Jan 18, 2018
Beowulf	May 5, 2017
Berkeley Chess Microprocessor	May 22, 2013
Betsabe	Jul 23, 2017
Bitboard Serialization	Dec 24, 2014
Bitboards	Nov 14, 2017
Bitfoot	Sep 8, 2015
BlackBishop	Nov 7, 2014
Board Representation	Dec 11, 2017
Bobby	Jan 7, 2016
BP	Jan 7, 2016
Branching Factor	Jun 28, 2017
Bruja	Feb 3, 2015
Brutus	Dec 24, 2016
CAPS	Dec 23, 2017
Capture (program)	Jan 8, 2016
Captures	Oct 1, 2017
Carballo	Oct 2, 2016
Check	Feb 1, 2018
Checkmate	Apr 13, 2018
Checks and Pinned Pieces (Bitboards)	Aug 14, 2013
Cheiron	Jan 7, 2016
Chenard	Sep 5, 2015
Cheng	Jul 30, 2017
CHEOPS	Apr 18, 2015
Cheops (Miller)	Jan 13, 2017
Chess 0.5	Nov 20, 2016
Chess Brain	Jun 25, 2017
chess4j	Jan 1, 2018
ChessBase (Database)	Feb 26, 2018
Chest	Mar 3, 2015
ChipTest	Jun 19, 2016
Coiled	Mar 12, 2017
Color Flipping	May 17, 2017
Conqueror	Apr 20, 2015
Constellation	Oct 2, 2016
Counter	Nov 13, 2017
Countermove Heuristic	Oct 1, 2017
Crafty	Jan 28, 2018
Cupcake	May 19, 2016
Daniel José Queraltó	Dec 31, 2017
Darmenios	Jan 7, 2016
David J. Wu	Jan 28, 2016
David Kittinger	Dec 27, 2017
DayDreamer	Aug 22, 2016
Delphil	Sep 17, 2016
Deniz Yuret	Aug 9, 2016
Diablo	May 17, 2016
DirGolem	Jun 5, 2016
Discovered Attack	Nov 8, 2010
Djinn	Feb 8, 2016
Dorky	Oct 10, 2016
Double Check	Apr 4, 2013
Dumb	Mar 10, 2018
Encoding Moves	Mar 27, 2016
Engine Testing	Feb 1, 2018
EXchess	Jan 21, 2018
Eye Movements	Jul 22, 2015
Fairy-Max	Feb 19, 2018
FCP	Jun 15, 2013
Federico Andrés Corigliano	Feb 13, 2014
Fencer	Jan 20, 2013
Ferret	Jan 7, 2016
Fixafan	Oct 2, 2015
Floyd	Sep 11, 2016
Folkert van Heusden	Nov 24, 2017
FPGA	Jul 9, 2016
Freccia	Dec 26, 2017
Freedom	Dec 28, 2017
Fridel Fainshtein	Oct 8, 2014
Galjoen	Mar 19, 2018
Gambiet	Jan 8, 2016
Garbochess	Sep 23, 2017
Genie	Feb 7, 2016
Georg von Zimmermann	May 29, 2017
George Baylor	Sep 22, 2014
Gerard Zielinski	Sep 25, 2014
Gibbon	Dec 23, 2014
Gideon	Feb 26, 2018
GiuChess	May 8, 2017
Gk	Oct 9, 2017
Glass	May 24, 2017
GNU Chess	Jan 21, 2018
Gogobello	Jul 30, 2017
Golem	May 18, 2017
GPU	Dec 16, 2017
GullChess	Jun 27, 2017
Hannibal	Oct 4, 2017
Hash Move	Oct 4, 2017
History Heuristic	Jul 19, 2017
HiTech	Mar 31, 2018
Holmes	Apr 24, 2014
Ifrit	Feb 7, 2016
Initial Position Summary	Nov 21, 2012
Interior Node Recognizer	Mar 12, 2018
Iteration	May 5, 2017
Joker IT	Sep 16, 2017
Jonathan Schaeffer	Jan 29, 2018
Kanguruh	Jan 13, 2013
Killer (NL)	Dec 15, 2017
Killer Move	Feb 16, 2017
Knowledge	Jul 22, 2017
Lachex	Jan 7, 2016
Lance Perkins	Nov 10, 2011
Lasse Hansen	Sep 1, 2015
Laurie Tunnicliffe	Jun 13, 2017
LCZero	Apr 18, 2018
Legal Move	Feb 16, 2017
Leonid Liberman	May 23, 2015
Little Wing	Oct 26, 2017
LittleThought	Nov 7, 2016
Loop (Program)	Mar 14, 2017
MadChess	Jul 4, 2017
Marc Boulé	Feb 17, 2015
Marek Strejczek	Jan 24, 2014
Mark Bromley	Oct 12, 2016
Mate-in-two	Oct 14, 2016
Mater	Apr 26, 2016
MBChess	Sep 29, 2012
Michael Gherrity	May 8, 2015
Michael Sherwin	Dec 18, 2017
MicroChess	Jul 14, 2015
Mini Chess	Jun 7, 2013
Minimax (program)	Dec 27, 2013
Move Generation	Jan 29, 2018
Move List	Jul 19, 2017
Move Ordering	Feb 27, 2018
Movei	Jan 7, 2016
Moves	Feb 19, 2018
Much	Jun 7, 2016
Murka	Nov 11, 2016
MVV-LVA	Oct 26, 2017
MyChess	Dec 25, 2017
NagaSkaki	Oct 28, 2017
Napoleon	Jun 25, 2017
Nesik	Jan 24, 2014
Niklas Fiekas	Sep 17, 2017
NoraGrace	Nov 23, 2014
Novag Micro Chess	Jan 16, 2013
NSS	Jul 14, 2015
Numpty chess	Oct 21, 2014
OliThink	May 19, 2017
One Reply Extensions	Dec 31, 2014
Origin Square	Oct 10, 2016
Ostrich	Dec 28, 2017
Othello	Jan 4, 2018
Ozalp Babaoglu	Oct 5, 2013
Patzer	Apr 5, 2017
Pedone	Jan 16, 2018
Pedro Castro	Apr 19, 2016
Perft	Sep 26, 2017
Perft Results	Feb 10, 2018
Perft(10) 20 draft 9 Positions	Nov 21, 2012
Perft(10) 400 draft 8 Positions	Nov 21, 2012
Perft(11) 20 draft 10 Positions	Nov 21, 2012
Perft(11) 400 draft 9 Positions	Nov 21, 2012
Perft(12) 20 draft 11 Positions	Nov 21, 2012
Perft(12) 400 draft 10 Positions	Nov 21, 2012
Perft(13) 20 draft 12 Positions	Nov 21, 2012
Perft(13) 400 draft 11 Positions	Nov 21, 2012
Piece-Lists	Feb 13, 2017
Pieces	Feb 19, 2018
Pieces versus Directions	Oct 6, 2016
Pigeon	Nov 2, 2016
Pin	Mar 7, 2017
Pioneer	Dec 23, 2017
Plisk	Dec 31, 2014
Praetorian	Feb 21, 2015
Promotions	Jun 6, 2017
Proscha	May 20, 2015
Protector	Oct 12, 2017
Pseudo-Legal Move	May 23, 2015
Pulse	Aug 14, 2017
Purple Haze	Oct 26, 2017
python-chess	Nov 4, 2017
Quazar	Oct 29, 2015
Querg	Dec 11, 2013
Raffaela	Apr 22, 2017
Rajah	Sep 12, 2012
Razoring	Oct 5, 2015
RDChess	May 3, 2013
Retrograde Analysis	Mar 21, 2017
ROCE	Jun 6, 2017
Rodin	Feb 7, 2016
Rotated Bitboards	Mar 7, 2017
RumbleMinze	Apr 13, 2014
Ryan Rifkin	Oct 12, 2016
Rybka	Mar 27, 2017
SAL	Dec 7, 2017
Schach (US)	Jul 21, 2016
Scidlet	May 31, 2014
SD Chess	Dec 22, 2017
Search	Feb 1, 2018
Searcher	Sep 26, 2016
SEE	Jan 14, 2013
Sensor Chess	Jun 7, 2013
Sharper	Jun 6, 2017
Shrike	Dec 30, 2012
Sidonia	May 19, 2016
Sierżant	Apr 15, 2014
Sliding Piece Attacks	May 27, 2016
Sliding Pieces	Aug 3, 2017
Sloppy	Sep 17, 2016
Small Potato	Feb 14, 2014
SnailChess	Nov 26, 2014
Snitch	Apr 7, 2016
Spartacus	Oct 17, 2016
Spector	Nov 11, 2016
Spike	Jan 7, 2016
Square Attacked By	Jan 20, 2018
Stalemate	Feb 21, 2018
Steven Edwards	Aug 26, 2017
Stuart Cracraft	May 19, 2017
Sune Fischer	Apr 7, 2014
Sunsetter	Jun 1, 2017
Super Constellation	Oct 1, 2016
Superpawn	Mar 9, 2015
Syzygy Bases	Apr 19, 2018
Table-driven Move Generation	Feb 19, 2017
Tao	Jan 8, 2016
Target Square	Oct 26, 2017
Teerapong Tovirat	Oct 21, 2014
Teki	Mar 29, 2018
Terra	Feb 11, 2015
The King	Jan 21, 2018
The switch Approach	Nov 5, 2010
Thor's Hammer	Nov 23, 2013
Thread	Apr 22, 2018
Tinker	Aug 29, 2015
Tiny Chess 86	Dec 24, 2017
UCT	Jan 22, 2018
University of Waterloo	Jan 29, 2018
Vajolet	Jan 25, 2018
Vanilla Chess	Jan 13, 2013
Vector Attacks	Dec 15, 2017
Vice	Mar 8, 2016
Warp	Nov 26, 2017
Winglet to include	Apr 25, 2015
Woodpusher	Dec 12, 2016
Workshop Chess and Mathematics	Mar 5, 2015
Yaakov HaCohen-Kerner	Aug 23, 2014
Zevra	Mar 12, 2018
Zurichess	Mar 12, 2018

Up one level

Move Ordering

GerdIsenberg — Tue, 27 Feb 2018 10:33:36 GMT

Home * Search * Move Ordering

For the alpha-beta algorithm to perform well, the best moves need to be searched first. This is especially true for PV-nodes and expected Cut-nodes. The goal is to become close to the minimal tree. On the other hand - at Cut-nodes - the best move is not always the cheapest refutation, see for instance enhanced transposition cutoff. Most important inside an iterative deepening framework is to try the principal variation of the previous iteration as the leftmost path for the next iteration, which might be applied by an explicit triangular PV-table or implicit by the transposition table.

Standard techniques

Following techniques are common in finding a good first move

PV-Move from the principal variation of the previous Iteration
Hash Move - stored move from Transposition Table, if available
Internal Iterative Deepening - if no hash move is available, likely only at PV-Nodes

Captures

For captures (if any), a simple, but quite efficient heuristic is (re)capturing the last moved piece with the least valuable attacker. Otherwise following heuristics may used, concerning the order of captures:

MVV-LVA - Most Valuable Victim - Least Valuable Aggressor
Static Exchange Evaluation abbreviated as SEE

Non-Captures

Killer Heuristic ^[1]
History Heuristic ^[2]
Relative History Heuristic ^[3]
Dedicated Piece-Square Tables only for move ordering ^[4]

Less common techniques

These techniques are well known theoretically for non-captures, but not all programmers use them:

Using Neural Networks

Move ordering (as well as Time Management) is an interesting application of Neural Networks, as introduced by Kieran Greer et al. and Levente Kocsis et al.

Typical move ordering

After move generation with assigned move-scores, chess programs usually don't sort the whole move list, but perform a selection sort each time a move is fetched. Exceptions are the Root and further PV-Nodes with some distance to the horizon, where one may apply additional effort to score and sort moves. For performance reasons, a lot of programs try to save the move generation of captures or non-captures at expected Cut-Nodes, but try the hash-move or killer first, if they are proved legal in this position.

A typical move ordering consists as follows:

PV-move of the principal variation from the previous iteration of an iterative deepening framework for the leftmost path, often implicitly done by 2.
Hash move from hash tables
Winning captures/promotions
Equal captures/promotions
Killer moves (non capture), often with mate killers first
Non-captures sorted by history heuristic and that like
Losing captures (* but see below

*) Depending on the implementation, the board representation, whether and where SEE is used, the extension policy (recapture extensions) and other stuff - many programmers favor losing captures before other none-captures - directly behind the killers. They are kind of forced, and one possibly has to deal with all kind of tactical motives and interactions, one may not consider in move ordering. Such as pins, batteries, discovered attacks and overloaded defenders. Otherwise, obviously losing captures are likely refuted cheaply. But if a losing capture fails high for some reason, we have saved the effort to generate, and more importantly to search other non-captures at all.

Node Type Considerations

Move ordering and scoring effort might be controlled by expected Node Types.

PV-nodes

At PV-nodes move ordering is very important, since the best alpha-increase as early as possible makes further search cheaper, due to narrower windows in Alpha-Beta, while in PVS later but better moves require re-searches of the null window scout.

Cut-nodes

Move ordering is crucial at expected and confirmed Cut-nodes, since it is important to fail-high as early as possible, as best with the first move, as in greater than 90% of all fail-high nodes. However, in situations where multiple moves may cut, e.g. with huge material advantage, we like it as cheap as possible, but not necessarily a huge subtree with f.i. due to check extensions.

All-nodes

At confirmed ALL-nodes with null windows, move ordering didn't care that much. Since we don't know in advance (otherwise we wouldn't search at all), and expected All-nodes may become Cut-nodes, move ordering is an issue as well, but usually with less effort for late moves.

Depth and Ply Considerations

Move ordering effort might be controlled by considering draft and/or plies from root. The closer the root, the farther the horizon, the more effort might be justified to score and sort moves.

Root Node Considerations

Despite trying the best move and principal variation from previous iteration first, iterative deepening offers another ressource to order the remaining moves at the root - their subtree size which could be easily determined. As already mentioned by Ingo Althöfer in an 1992 ICCA Journal correspondence ^[9] inspired by Jos Uiterwijk's Countermove Heuristic article ^[10], based on the soundness of following rule of thumb,

The longer it takes to refute a move, the higher is its chance to become best move in the next iteration

the old idea is to use the search time or subtree size of the depth-n iteration to reorder the direct successors of the root before the depth-(n+1) iteration. Some programs use the evaluation to initially score the moves, to adjust them by their subtree size in subsequent iterations.

An idea to apply randomness and/or bonuses, i.e. developing bonus, or penalties to move scores at the root by an oracle approach, was proposed by Ronald de Man - without any changes in alpha-beta search or leaf evaluation, and without any problems with the transposition table ^[11] ^[12].

Ordering in Quiescence

In the quiescence search, captures are often approximated, for speed. For example, PxQ need not have a SEE performed on it, since it is clearly a winning capture, where RxB might have the SEE done, to see if it is a winning or possibly losing capture if the bishop is protected.

Publications

1977 ...

Selim Akl, Monroe Newborn (1977). The Principal Continuation and the Killer Heuristic.1977 ACM Annual Conference Proceedings
Ozalp Babaoglu (1977). Hardware implementation of the legal move generation and relative ordering functions for the game of chess. Master's thesis, University of California, Berkeley

1980 ...

Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
Prakash Bettadapur (1986). Influence of Ordering on Capture Search. ICCA Journal, Vol. 9, No. 4
Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3

1990 ...

Dap Hartmann, Peter Kouwenhoven (1991). Sundry Computer Chess Topics. Advances in Computer Chess 6
Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
Jos Uiterwijk (1992). Memory Efficiency in some Heuristics. ICCA Journal, Vol. 15, No. 2
Ingo Althöfer (1992). Move Ordering by Time Ordering. Correspondence, ICCA Journal, Vol. 15, No. 2
Eric Thé (1992). An analysis of move ordering on the efficiency of alpha-beta search. Master's thesis, McGill University, advisor Monroe Newborn » Fixafan
Yi-Fan Ke, Tai-Ming Parng (1993). The Guard Heuristic: Legal Move Ordering with Forward Game-Tree Pruning. ICCA Journal, Vol. 16, No. 2
Mei-En Chen, Yo-Ping Huang (1995). Guard heuristic by dynamic fuzzy reasoning model for Chinese chess. Proceedings of ISUMA-NAFIPS '95
Kieran Greer, Piyush Ojha, David A. Bell (1999). A Pattern-Oriented Approach to Move Ordering: the Chessmaps Heuristic. ICCA Journal, Vol. 22, No. 1

2000 ...

Kieran Greer (2000). Computer chess move-ordering schemes using move influence. Artificial Intelligence, Vol. 120, No. 2
Levente Kocsis, Jos Uiterwijk, Jaap van den Herik (2001). Move Ordering using Neural Networks. IEA/AIE 2001, LNCS 2070
Levente Kocsis, Jos Uiterwijk, Eric Postma, Jaap van den Herik (2002). The Neural MoveMap Heuristic in Chess. CG 2002
Yoshinori Higashiuchi, Reijer Grimbergen (2005). Enhancing Search Efficiency by Using Move Categorization Based on Game Progress in Amazons. pdf
Mark Winands, Erik van der Werf, Jaap van den Herik, Jos Uiterwijk (2006). The Relative History Heuristic. CG 2004, pdf
Jeff Rollason (2006). Driving search with Plausibility analysis: Looking at the right moves. AI Factory, Winter 2006
Jeff Rollason (2007). Negative Plausibility. AI Factory, Spring 2007 » Relative History Heuristic
Rémi Coulom (2007). Computing Elo Ratings of Move Patterns in the Game of Go. ICGA Journal, Vol. 30, No. 4, CGW 2007, pdf ^[13]
Timothy Furtak, Michael Buro (2009). Minimum Proof Graphs and Fastest-Cut-First Search Heuristics. IJCAI 2009, pdf ^[14]

2010 ...

David J. Wu (2011). Move Ranking and Evaluation in the Game of Arimaa. B.Sc. thesis, Harvard College, Cambridge, Massachusetts, pdf » Arimaa
David J. Wu (2015). Designing a Winning Arimaa Program. ICGA Journal, Vol. 38, No. 1

Forum Posts

1996 ...

Pawn Structure "Holes" and Move Ordering by Daniel A. Thies, rgcc, February 12, 1996 » Pawn Structure, Holes
computer chess "oracle" ideas... by Robert Hyatt, rgcc, April 1, 1997
Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 3, 1997
Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 7, 1997
Measure of moveorder quality by Ralf Elvsén, CCC, September 04, 1999
Fast way to sort moves in movelist ? by Stefan Plenkner, CCC, October 14, 1999

2000 ...

Move ordering? by Severi Salminen, CCC, April 28, 2000
Better subject title: Move ordering by Tom Kerrigan, CCC. May 31, 2000
Move ordering ideas by Matt McKnight, CCC, March 08, 2001
Dynamic move ordering for capture/promotions? by Scott Gasch, CCC, April 02, 2001
root search ordening by Jan Willem de Kort, CCC, May 02, 2001
Move ordering at root of search by Tom King, CCC, May 07, 2001
A SIMD idea, eg. Piece/Gain of a capture target by Gerd Isenberg, CCC, January 21, 2004 » SSE2
move ordering and node count by Martin Fierz, CCC, March 29, 2004
Move ordering at root by Renze Steenhuisen, CCC, April 04, 2004
Fail-high on first move stat (86%) by Michael Henderson, CCC, July 29, 2004 » Fail-High

2005 ...

Move ordering at different (Knuth) node types by Tom Likens, Winboard Forum, February 21, 2006 » Node Types
SEE on non-capture moves in main search by Gary, CCC, March 28, 2007 » Static Exchange Evaluation
caps->noncaps vs. goodcaps->noncaps->badcaps by James Swafford, CCC, July 18, 2007
Move ordering: Delaying moves on the history phase by Miguel A. Ballicora, CCC, May 13, 2008
Re: Move ordering: Delaying moves on the history phase by Lance Perkins, CCC, May 14, 2008
Order of implementing things by cyberfish, CCC, October 10, 2008

2010 ...

root move ordering by Edward Yu, CCC, June 02, 2010
Move ordering improvements by Howard E, Open Chess Programming Forum, September 26, 2010

2011

out of check move ordering by Don Dailey, CCC, March 12, 2011 » Check
The LBR move ordering heuristic by Steven Edwards, CCC, March 26, 2011 » Last Best Reply
Move ordering by PST by Onno Garms, CCC, April 16, 2011 » Piece-Square Tables, History Heuristic, Onno
Move ordering question by Stef Luijten, CCC, June 11, 2011
Root node search in Stockfish by Onno Garms, CCC, June 12, 2011 » Stockfish, Root
Improve Move Ordering for Alpha Beta by Thomas Petzke, mACE Chess, August 11, 2011

2012

Minimax/ Alpha beta pruning Move Ordering? by Felix, Stack Overflow, January 18, 2012
Move ordering idea (old and new?) by Daniel Homan, CCC, Aug 09, 2012 » Countermove Heuristic
How effective is move ordering from TT? by Bill Henry, CCC, August 09, 2012 » Transposition Table
Relationship between move ordering and pruning by Don Dailey, OpenChess Forum, December 17, 2012 » Pruning
Move Ordering? by Thomas Kolarik, CCC, December 28, 2012

2013

Killer and History: Increased Node Count by Cheney Nattress, CCC, January 15, 2013
Root move order (again) by Alberto Sanjuan, CCC, March 21, 2013
History pruning / move ordering question by Jerry Donald, CCC, May 10, 2013
Move ordering contest by Ed Schroder, CCC, May 26, 2013
An idea for move ordering at the root by Steven Edwards, CCC, June 09, 2013
MoveOrdering++ by Henk van den Belt, CCC, August 16, 2013
How do you get a "Best first move" near the leaves by Henk van den Belt, CCC, December 05, 2013

2014

Idea of different history by Daniel José Queraltó, CCC, April 14, 2014 » History Heuristic
Effectiveness of killer moves by Alex Ferguson, CCC, August 17, 2014
Solving a fail low situation at the root by Alberto Sanjuan, CCC, November 03, 2014 » Aspiration Windows, Fail-Low, Root

2015 ...

Idea #8430: Optimizing move ordering, very slowly by Steven Edwards, CCC, April 06, 2015
Move ordering for cheapest refutation by Matthew Lai, CCC, August 09, 2015
Bonus for "null move SEE" by Matthew Lai, CCC, August 23, 2015
Q: Move ordering, checks by Harm Geert Muller, CCC, September 02, 2015
Ordering of Root moves and search instability ! by Mahmoud Uthman, CCC, October 26, 2015 » Search Instability

2016

Sorting Captures by David Cimbalista, CCC, August 03, 2016
New killer idea by Alexandru Mosoi, CCC, August 28, 2016
Starting with move ordering by Luis Babboni, CCC, August 28, 2016
Best move statistics by Matthew Lai, CCC, September 12, 2016
Searching worse moves first by Matthew Lai, CCC, September 14, 2016
move ordering especially ordering&searching of root move by Mahmoud Uthman, CCC, December 21, 2016

2017

Move ordering ? by Mahmoud Uthman, CCC, January 15, 2017
Move ordering ? by Mahmoud Uthman, CCC, February 04, 2017
Sorting losing captures ? by Mahmoud Uthman, CCC, February 25, 2017
Move ordering statistics by Sander Maassen vd Brink, CCC, February 26, 2017
speed up or avoiding move sorting by Alexandru Mosoi, CCC, March 19, 2017 » Zurichess
Testing for Move Ordering Improvements by Cheney Nattress, CCC, March 25, 2017 » Engine Testing, Search Statistics
Sorting algorithms by Fermin Serrano, CCC, April 22, 2017
What is causing this problem? by Michael Sherwin, CCC, August 16, 2017 » RomiChess
Ordering Capture Moves by Jason Fernandez, CCC, September 06, 2017 » Move Ordering - Captures
Marginal hash move by Harm Geert Muller, CCC, September 16, 2017
Unordered moves phenomenon by Alvaro Cardoso, CCC, October 03, 2017
Move ordering by Matthew R. Brades, CCC, November 09, 2017

2018

Simple quiet move sorting by Andrew Grant, CCC, January 13, 2018
[Discussion] - Measuring move ordering by Ed Schroder, CCC, February 24, 2018

External Links

Move Ordering in Rebel by Ed Schröder
Hiromi Uehara, The Trio Project, feat. Anthony Jackson & Simon Phillips - Move, (2012), YouTube Video

References

^ Selim Akl, Monroe Newborn (1977). The Principal Continuation and the Killer Heuristic.1977 ACM Annual Conference Proceedings
^ Jonathan Schaeffer (1983). The History Heuristic. ICCA Journal, Vol. 6, No. 3
^ Mark Winands, Erik van der Werf, Jaap van den Herik, Jos Uiterwijk (2006). The Relative History Heuristic. CG 2004, pdf
^ Move Ordering in Rebel by Ed Schröder, also available as pdf
^ Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
^ Dap Hartmann (1988). Butterfly Boards. ICCA Journal, Vol. 11, Nos. 2/3
^ Levente Kocsis, Jos Uiterwijk, Jaap van den Herik (2001). Move Ordering using Neural Networks. IEA/AIE 2001, LNCS 2070
^ Levente Kocsis, Jos Uiterwijk, Eric Postma, Jaap van den Herik (2002). The Neural MoveMap Heuristic in Chess. CG 2002
^ Ingo Althöfer (1992). Move Ordering by Time Ordering. Correspondence, ICCA Journal, Vol. 15, No. 2
^ Jos Uiterwijk (1992). The Countermove Heuristic. ICCA Journal, Vol. 15, No. 1
^ Re: random play by Ronald de Man, rgcc, November 28, 1996
^ Re: computer chess "oracle" ideas... by Ronald de Man, rgcc, April 7, 1997, see also Re: mate threat extension/null move by Don Beal, CCC, October 04, 2004 » Mate Threat Extensions, Null Move and WAC booster
^ Bradley–Terry model from Wikipedia
^ Re: Move ordering for cheapest refutation by Mikko Aarnos, CCC, August 10, 2015

What links here?

Page	Date Edited
Abyss	Aug 5, 2017
AI Factory	Dec 26, 2015
AICE	Nov 29, 2017
Alarm	Jun 7, 2017
Alberto Sanjuan	Nov 3, 2014
Aldebaran	Feb 10, 2013
Alexandru Mosoi	Jan 8, 2018
Algorithms	May 5, 2017
Alpha-Beta	Jan 28, 2018
Alvaro Cardoso	Jan 12, 2018
Amundsen	Sep 3, 2013
Amyan	Dec 10, 2013
Andrea Zinno	May 19, 2017
Andrew Grant	Jan 13, 2018
Andscacs	Jan 16, 2018
Arasan	Apr 8, 2018
Atomystica	Oct 2, 2014
Awesome	Nov 19, 2015
Bebe	Dec 23, 2017
Belzebub	Oct 20, 2015
Berkeley Chess Microprocessor	May 22, 2013
Beta-Cutoff	Oct 22, 2017
Betsabe	Jul 23, 2017
BigLion	Sep 28, 2016
Bison	Sep 29, 2016
Bitboard Serialization	Dec 24, 2014
Brainless	Jun 24, 2017
Branching Factor	Jun 28, 2017
Butterfly Boards	Jan 27, 2015
Butterfly Heuristic	May 6, 2016
Captures	Oct 1, 2017
Carballo	Oct 2, 2016
Check	Feb 1, 2018
Cheese	Feb 17, 2018
Cheiron	Jan 7, 2016
Chenard	Sep 5, 2015
Cheng	Jul 30, 2017
chess22k	Apr 23, 2018
ChessBrainVB	Jun 24, 2017
Chessmaps Heuristic	Aug 27, 2015
ChessV	Jan 21, 2018
Chezzz	Jan 20, 2013
Chump	Jan 31, 2016
Coiled	Mar 12, 2017
Color Flipping	May 17, 2017
Counter	Nov 13, 2017
Countermove Heuristic	Oct 1, 2017
Crafty	Jan 28, 2018
Dan Homan	Oct 19, 2016
DanaSah	Oct 9, 2017
DarkThought	Jul 3, 2018
Darmenios	Jan 7, 2016
David J. Wu	Jan 28, 2016
Debugging	Jan 20, 2018
Defenchess	Mar 18, 2018
Demolito	Mar 1, 2018
Diablo	May 17, 2016
DirGolem	Jun 5, 2016
Discovered Attack	Nov 8, 2010
Djinn	Feb 8, 2016
Dolphin	Nov 28, 2014
Don Dailey	Dec 7, 2016
Dorpsgek	Apr 2, 2018
DrunkenMaster	Nov 1, 2016
Duck	Dec 12, 2016
Dumb	Mar 10, 2018
Elephant	Sep 19, 2016
Encoding Moves	Mar 27, 2016
Engine Testing	Feb 1, 2018
Eric Thé	Oct 2, 2015
ESC	Aug 14, 2013
Ethereal	Mar 20, 2018
Eveann	Apr 3, 2017
Exacto	Oct 3, 2015
Eye Movements	Jul 22, 2015
Fail-High	Oct 22, 2017
Fail-Low	Jun 23, 2017
Faile	May 27, 2014
Falcon	Sep 2, 2016
Ferret	Jan 7, 2016
Firstchess	Nov 27, 2014
Fixafan	Oct 2, 2015
Floyd	Sep 11, 2016
Francesca	Jan 7, 2016
Freyr	Mar 6, 2014
Garbochess	Sep 23, 2017
Garbochess-JS	Sep 23, 2017
Gary Linscott	Jan 16, 2018
Gibbon	Dec 23, 2014
Gk	Oct 9, 2017
Gogobello	Jul 30, 2017
Golch	Dec 7, 2017
GopherCheck	Feb 3, 2017
Guard Heuristic	Nov 18, 2015
Hagrid	Apr 12, 2016
HAL	Jun 14, 2016
HaQiKi D	Jul 26, 2017
Hash Move	Oct 4, 2017
History Heuristic	Jul 19, 2017
Holes	Oct 16, 2017
Horizon	Mar 17, 2013
ICGA Journal	Dec 21, 2017
Ifrit	Feb 7, 2016
Ingo Althöfer	May 4, 2017
Internal Iterative Deepening	Feb 5, 2018
ISA	Apr 2, 2018
Iteration	May 5, 2017
Iterative Deepening	Jun 23, 2017
James Swafford	Jan 1, 2018
Jan Renze Steenhuisen	Sep 10, 2017
Jeff Rollason	Dec 23, 2016
JikChess	Nov 29, 2015
Kaissa	Apr 9, 2018
Kholin	Jan 3, 2018
Killer Heuristic	Sep 14, 2017
Killer Move	Feb 16, 2017
KnockOut	Sep 20, 2016
Knowledge	Jul 22, 2017
Kurt	Apr 20, 2014
Lance Perkins	Nov 10, 2011
Laser	Dec 27, 2017
Last Best Reply	Jul 6, 2013
Late Move Reductions	Sep 25, 2017
Lazy SMP	Jan 4, 2018
LittleThought	Nov 7, 2016
LTChess	Mar 30, 2017
Martin Fierz	Apr 26, 2018
Marvin	Feb 10, 2018
Master	Dec 28, 2017
Mate Killers	Feb 4, 2017
Mater	Apr 26, 2016
Matt McKnight	Oct 10, 2016
Matthew Lai	Dec 6, 2017
Maverick	Jan 7, 2016
MChess	Feb 26, 2018
MessChess	Mar 6, 2014
Miguel A. Ballicora	Jun 19, 2017
Mini Chess	Jun 7, 2013
Morgoth	Nov 30, 2014
Move Generation	Jan 29, 2018
Move List	Jul 19, 2017
Move Ordering	Feb 27, 2018
Movei	Jan 7, 2016
Moves	Feb 19, 2018
Murka	Nov 11, 2016
Muse	May 17, 2016
MVV-LVA	Oct 26, 2017
MyChess	Dec 25, 2017
Napoleon	Jun 25, 2017
NegaScout	Jul 6, 2016
Nemorino	Dec 21, 2017
Neural MoveMap Heuristic	Sep 24, 2015
Neural Networks	Mar 12, 2018
Nirvanachess	Sep 30, 2017
Node Types	Oct 22, 2017
Null Move Pruning	Dec 2, 2017
Nullmover	Jul 21, 2013
Obender	Apr 17, 2016
OliThink	May 19, 2017
Onno	Jul 19, 2013
Onno Garms	Jul 19, 2013
Oracle	Sep 4, 2016
Ostrich	Dec 28, 2017
Othello	Jan 4, 2018
Paladin	Jan 29, 2017
Path-Dependency	Oct 16, 2017
Patzer	Apr 5, 2017
PawnKing	Sep 5, 2014
Pawny	Jun 17, 2015
Peasant	May 21, 2015
Pepito	Nov 27, 2014
Pharaon	Sep 2, 2017
Piece-Lists	Feb 13, 2017
Piece-Square Tables	Mar 31, 2018
PolarChess	May 15, 2017
Principal variation	Dec 4, 2017
Principal Variation Search	Oct 22, 2017
ProChess IT	Sep 30, 2015
Proof-number search	Jan 22, 2018
Prophet	Sep 30, 2017
Protector	Oct 12, 2017
Pruning	Jan 1, 2018
PV-Move	Jan 16, 2013
RDChess	May 3, 2013
Rebel	Feb 25, 2018
Recursion	Nov 18, 2017
RedQueen	Nov 13, 2017
Refutation Move	May 13, 2013
Refutation Table	Mar 27, 2015
Relative History Heuristic	Jun 8, 2015
Richard Vida	Aug 11, 2013
Robocide	May 11, 2016
ROCE	Jun 6, 2017
Rodin	Feb 7, 2016
RomiChess	Jan 2, 2018
Rookie	Jan 7, 2016
Root	Sep 26, 2016
RuyDos	Feb 17, 2018
Sayuri	Oct 1, 2017
Schach (US)	Jul 21, 2016
Scidlet	May 31, 2014
Scout	Jan 28, 2018
Search	Feb 1, 2018
Search Explosion	Mar 30, 2017
Search Instability	May 5, 2017
Search Statistics	Jan 16, 2018
Search Tree	Dec 23, 2016
Sensor Chess	Jun 7, 2013
Severi Salminen	May 7, 2015
SharpChess	Jun 6, 2017
Sharper	Jun 6, 2017
Shield	May 17, 2017
Sierżant	Apr 15, 2014
Sinobyl	Jul 3, 2014
Sjaak (Glebbeek)	Oct 4, 2017
Sjeng	Aug 17, 2017
Sloppy	Sep 17, 2016
Slow Chess	May 17, 2016
SmarThink	Feb 2, 2018
Smash	May 11, 2016
Snitch	Apr 7, 2016
Spector	Nov 11, 2016
Spike	Jan 7, 2016
SSE2	Feb 27, 2018
Static Exchange Evaluation	Dec 14, 2017
Stef Luijten	Apr 26, 2015
Steven Edwards	Aug 26, 2017
Stockfish	Apr 7, 2018
Table-driven Move Generation	Feb 19, 2017
Tai-Ming Parng	May 23, 2016
TDChess	Jan 10, 2013
Teki	Mar 29, 2018
Terra	Feb 11, 2015
The King	Jan 21, 2018
The Turk	Apr 1, 2017
The Turk (TR)	Apr 1, 2017
Thomas Kolarik	Aug 26, 2016
Threat Move	Sep 10, 2017
Tom King	Aug 19, 2017
Tom Likens	Mar 7, 2017
Touch	Dec 12, 2016
Transposition Table	Apr 19, 2018
Tunguska	Sep 16, 2017
Turning Point	Apr 6, 2012
Vadim Demichev	Jul 26, 2013
Vajolet	Jan 25, 2018
Valavan Manohararajah	May 4, 2017
Vice	Mar 8, 2016
Wasp	Nov 24, 2017
WildCat	Nov 11, 2016
Wing	Oct 26, 2017
Winglet to include	Apr 25, 2015
Winter	Jan 23, 2018
Witz	Nov 14, 2017
WyldChess	Mar 10, 2018
Xiphos	Apr 22, 2018
Xpdnt	Sep 13, 2015
Yi-Fan Ke	Feb 16, 2015
ZChess	Jan 8, 2016
Zeus RU	Jun 6, 2015
Zurichess	Mar 12, 2018

Up one level

Moves

GerdIsenberg — Tue, 20 Feb 2018 07:44:02 GMT

Home * Chess * Moves

		In Chess terminology or game notation, a Move (or full move) implies a piece movement of both sides, white and black, e.g. 1. d4 Nf6. To relax this ambiguity, the term Half-move is used, also donated as one ply, to make sure that it is only the piece movement of one single side. However, in the context of chess programming, if not stated otherwise, the term Move refers the piece movement of one side, thus a half-move. In the context of search, a Move is the edge, connecting two Nodes, which represent two consecutive chess positions inside one path of the search tree.
Irving Amen, Chess Move, 1977 ^[1]

Encoding and Generating

Type of Moves

Quiet Moves

Quiet Moves
Pawn Push
Castling
Null Move, even if invalid in Chess

Altering Material

Tactical moves
Captures
En passant capture
Promotions
Piece Drop in various Chess variants

Tactical Properties

Reversibility

Involved Squares

Encoding and Generating

Notation

Adjunct Moves

Those moves are determined by search and are matter of move ordering:

Make and Unmake

Publications

Alex Bell, N. Jacobi (1979). How to read, make and store chess moves. The Computer Journal Vol. 22, No. 1, 71-75
Barak Oshri, Nishith Khandwala (2015). Predicting Moves in Chess using Convolutional Neural Networks. pdf ^[2] » Deep Learning, Neural Networks

External Links

Betza notation and XBoard » Chess Variants, XBoard
NHØP & Joe Pass - Move, Jazzhus Slukefter, Tivoli, Copenhagen, 1982, YouTube Video

References

What links here?

Page	Date Edited
Acornsoft Chess	Dec 11, 2016
Algebraic Chess Notation	Sep 25, 2017
Alpha-Beta	Jan 28, 2018
Atom Chess	Dec 11, 2016
Attack and Defend Maps	Nov 5, 2016
Auto232	Feb 25, 2018
Awesome	Nov 19, 2015
Battle Chess	Dec 12, 2016
Best Move	May 15, 2017
Beta-Cutoff	Oct 22, 2017
Bitboard Board-Definition	Jun 23, 2014
Board Representation	Dec 11, 2017
Bobby	Jan 7, 2016
Bookup	Feb 4, 2018
BP	Jan 7, 2016
Branching Factor	Jun 28, 2017
Butterfly Boards	Jan 27, 2015
CAPS	Dec 23, 2017
Captures	Oct 1, 2017
Castling	May 5, 2017
Checks and Pinned Pieces (Bitboards)	Aug 14, 2013
Cheops (Miller)	Jan 13, 2017
Chess	Jan 21, 2018
Chess Game	Mar 28, 2017
Chess Position	Sep 10, 2017
ChessX	Feb 26, 2015
Color	Mar 12, 2014
Combination	Oct 25, 2016
Constellation	Oct 2, 2016
CTG	Aug 22, 2016
Data	Nov 26, 2017
Databases	Mar 18, 2018
Debugging	Jan 20, 2018
Dedicated Chess Computers	Feb 20, 2018
Dictionary	Aug 24, 2017
Diego Rasskin-Gutman	Jan 19, 2014
Direction	Oct 6, 2016
Distance	Sep 25, 2015
Double Attack	Oct 22, 2014
El Ajedrecista	Feb 25, 2015
En passant	Jan 16, 2018
Encoding Moves	Mar 27, 2016
Entering Moves	Sep 7, 2017
Evaluation function draft	Jul 11, 2014
Eye Movements	Jul 22, 2015
Ferdinand Mosca	Jul 28, 2017
Fifty-move Rule	Aug 9, 2017
Fill Algorithms	Nov 6, 2013
Freccia	Dec 26, 2017
Game Notation	Jan 11, 2018
General Setwise Operations	Feb 25, 2018
Gideon	Feb 26, 2018
Hash Move	Oct 4, 2017
Incremental Updates	Sep 6, 2017
Influence Quantity of Pieces	Jul 21, 2017
Interception	May 21, 2011
Irreversible Moves	Jan 25, 2014
Jacques Pitrat	Aug 7, 2015
John L. Jerz	Jul 15, 2013
KC Chess	Jan 28, 2012
Killer Move	Feb 16, 2017
King	Feb 26, 2013
Knowledge	Jul 22, 2017
Last Best Reply	Jul 6, 2013
Late Move Reductions	Sep 25, 2017
Legal Move	Feb 16, 2017
Linked List	Oct 11, 2016
Logging	Jan 20, 2018
Losing Chess	Sep 18, 2017
Make Move	Mar 2, 2016
Manhattan-Distance	May 19, 2014
Mate Killers	Feb 4, 2017
Mater	Apr 26, 2016
Michael Hartisch	Aug 11, 2017
Mini Chess	Jun 7, 2013
Minimax	Dec 29, 2017
Mobility	Jan 17, 2018
Move Generation	Jan 29, 2018
Move List	Jul 19, 2017
Move Ordering	Feb 27, 2018
Moves	Feb 19, 2018
Negamax	Sep 11, 2015
Neural MoveMap Heuristic	Sep 24, 2015
Node	Jul 20, 2015
Nodes per second	Feb 28, 2018
Null Move	Aug 9, 2017
Null Move Observation	Dec 30, 2015
Null Window	Nov 8, 2016
Octavius	Dec 7, 2017
Oracle	Sep 4, 2016
Origin Square	Oct 10, 2016
Path-Dependency	Oct 16, 2017
Pawn Push	Mar 27, 2010
Peasant	May 21, 2015
Piece Drop	Feb 20, 2018
Piece-Square Tables	Mar 31, 2018
Pieces versus Directions	Oct 6, 2016
Ply	Jan 27, 2014
Promotions	Jun 6, 2017
Pseudo-Legal Move	May 23, 2015
PV-Move	Jan 16, 2013
Quiet Moves	Mar 4, 2010
Recursion	Nov 18, 2017
Refutation Move	May 13, 2013
Reinforcement Learning	Feb 12, 2018
Repetitions	Jan 16, 2018
Retrograde Analysis	Mar 21, 2017
Reversible Moves	Mar 13, 2010
Ronald de Man	Nov 20, 2017
Sacrifice	Aug 10, 2017
Scid	Apr 15, 2017
Search	Feb 1, 2018
Search Tree	Dec 23, 2016
Sensory 9	Jan 8, 2016
Sensory Board	Mar 1, 2018
SEX Algorithm	Nov 25, 2014
Sfinks	Dec 25, 2017
SOMA	Mar 25, 2015
Square Attacked By	Jan 20, 2018
Squares	Feb 15, 2015
Static Exchange Evaluation	Dec 14, 2017
Super Constellation	Oct 1, 2016
Symbolic	May 8, 2017
Table-driven Move Generation	Feb 19, 2017
Tactical Moves	Sep 22, 2010
Tai-Ming Parng	May 23, 2016
Target Square	Oct 26, 2017
Temporal Difference Learning	Feb 20, 2018
The Fox	Feb 27, 2017
Threat Move	Sep 10, 2017
Trajectory	Jan 3, 2015
Transposition	Jun 8, 2015
Transposition Table	Apr 19, 2018
Turochamp	Dec 14, 2017
Unmake Move	Jun 10, 2017
Vector Attacks	Dec 15, 2017
William Fink	Dec 25, 2017
Winter	Jan 23, 2018
Xadreco	Jul 23, 2017
Yi-Fan Ke	Feb 16, 2015
Zobrist Hashing	Jan 22, 2018
Zwischenzug	Jan 15, 2014

Up one Level

Null Move

GerdIsenberg — Wed, 09 Aug 2017 18:11:50 GMT

Home * Chess * Moves * Null Move

See also

Forum Posts

What links here?

A null move or passing move is invalid in Chess. Nevertheless, chess programs often apply a null move inside their search algorithm for various reasons and applications:

Forum Posts

Null move in PV by Harm Geert Muller, CCC, July 18, 2012 » Principal Variation
tt move vs null move by Erin Dame, CCC, May 27, 2017 » Hash Move
Fifty move counter and Null move by Tamás Kuzmics, CCC, August 09, 2017 » Fifty-move Rule, Null Move Pruning

What links here?

Page	Date Edited
B*	Nov 27, 2017
CAPS	Dec 23, 2017
Check	Feb 1, 2018
Color Flipping	May 17, 2017
Delicate Brute	Jun 7, 2016
Double Null Move	May 8, 2015
Engine Testing	Feb 1, 2018
Erin Dame	Dec 2, 2017
Eugen	Jan 7, 2016
Hash Move	Oct 4, 2017
Horizon	Mar 17, 2013
Knowledge	Jul 22, 2017
LChess	Jan 7, 2016
List (Program)	Jan 7, 2016
Mate Threat Extensions	Apr 14, 2012
Mater	Apr 26, 2016
Merlin	Jan 20, 2018
Moves	Feb 19, 2018
Node Types	Oct 22, 2017
Null Move	Aug 9, 2017
Null Move Observation	Dec 30, 2015
Null Move Pruning	Dec 2, 2017
Null Move Reductions	Jun 22, 2015
Onno	Jul 19, 2013
Phoenix	May 8, 2017
Principal variation	Dec 4, 2017
Quiescence Search	Aug 19, 2017
Quiet Moves	Mar 4, 2010
Reverse Futility Pruning	Jun 2, 2017
Side to move	Oct 29, 2017
Thomas Thomsen	Mar 25, 2015
Threat Move	Sep 10, 2017
Triangulation	Apr 4, 2013
Woodpusher	Dec 12, 2016
Ziggurat	Oct 9, 2017
Zzzzzz	May 14, 2016

Up one Level

Pawn Push

GerdIsenberg — Sat, 27 Mar 2010 09:07:30 GMT

Home * Chess * Moves * Pawn Push

A Pawn Push is a quiet, irreversible move of a pawn one single step forward, or optionally but only from its initial rank, two steps forward. The condition for a pseudo-legal pawn push is that its target square ahead, the stop square, is empty, while the origin square is obviously occupied by the pawn of the side to move.

Promotion

A push from the seventh (second) rank is a promotion.

Double Push

The double pawn push from the initial rank requires both squares ahead empty. Making a double push is a precondition to set the en passant target square in the obtained position, as specified by initial Forsyth-Edwards Notation (FEN) unconditionally, where todays programs are instructed to set en passant target square if the en passant would be pseudo-legal (an opponent pawn left or right) or even better strictly legal ^[1], also considering updating Zobist keys during make move to avoid dissimilarity of otherwise repeated positions if the first occurrence happened after a double pawn push with no en passant capture actually possible ^[2].

External Links

Pawn Movement from Wikipedia

References

^ Re: Arasan test suite update by Steven Edwards, CCC, September 19, 2008
^ en passant and hash key calculation by Fred Hamilton, CCC, March 21, 2010

What links here?

Page	Date Edited
Blockage Detection	Oct 19, 2017
Breakthrough (Game)	Aug 11, 2017
Butterfly Boards	Jan 27, 2015
ChessLin	May 17, 2017
DirGolem	Jun 5, 2016
Dispersion and Distortion	Nov 11, 2017
En passant	Jan 16, 2018
Encoding Moves	Mar 27, 2016
Fifty-move Rule	Aug 9, 2017
Halfmove Clock	Aug 9, 2017
Irreversible Moves	Jan 25, 2014
Late Move Reductions	Sep 25, 2017
MANIAC I	Nov 17, 2016
Mate-in-two	Oct 14, 2016
Moves	Feb 19, 2018
Passed Pawn Extensions	May 11, 2015
Pawn Levers (Bitboards)	Nov 11, 2017
Pawn Push	Mar 27, 2010
Pawn Pushes (Bitboards)	Apr 5, 2013
Pieces versus Directions	Oct 6, 2016
Promotion Square	Aug 15, 2011
Promotions	Jun 6, 2017
Quiet Moves	Mar 4, 2010
Repetitions	Jan 16, 2018
Reversible Moves	Mar 13, 2010
Rule of the Square	Sep 6, 2014
Shatranj	Jul 26, 2017
Square Attacked By	Jan 20, 2018
Square Control	Sep 15, 2016
Stop Square	Jul 2, 2013
Syzygy Bases	Apr 19, 2018
The A.R.B Chess System	May 24, 2016
Tornado	Dec 14, 2017
Transposition	Jun 8, 2015

Up one Level

Pawn Pushes (Bitboards)

GerdIsenberg — Fri, 05 Apr 2013 22:01:38 GMT

Home * Board Representation * Bitboards * Pawn Pattern and Properties * Pawn Pushes

		Bitboards imply to determine pawn push target squares, or equivalently their stop squares set-wise, while pawn pushes of a single pawn are the domain of mailbox-approaches. To generate the single-step targets for all pawns requires vertical shift by one rank and intersection with the set of empty squares. The resulting set might be shifted one more time for the double pushes by further intersection with empty squares on the fourth (white) or fifth (black) double push target ranks. Since double pushing triggers determination of en passant target square, it makes sense to serialize both sets separately for different move encoding.
Chimpanzee pushing 1. d4 ^[1] ^[2]

Push per Side

Keeping different but most efficient code for both white and black pawns. The code snippets rely on shifting bitboards, specially by one step only.

U64 wSinglePushTargets(U64 wpawns, U64 empty) {
   return nortOne(wpawns) & empty;
}
 
U64 wDblPushTargets(U64 wpawns, U64 empty) {
   const U64 rank4 = C64(0x00000000FF000000);
   U64 singlePushs = wSinglePushTargets(wpawns, empty);
   return nortOne(singlePushs) & empty & rank4;
}
 
U64 bSinglePushTargets(U64 bpawns, U64 empty) {
   return soutOne(bpawns) & empty;
}
 
U64 bDoublePushTargets(U64 bpawns, U64 empty) {
   const U64 rank5 = C64(0x000000FF00000000);
   U64 singlePushs = bSinglePushTargets(bpawns, empty);
   return soutOne(singlePushs) & empty & rank5;
}

Pawns able to Push

To get the set of source squares of pawns able to push is about intersection of pawns with the shifted empty squares in opposite direction:

U64 wPawnsAble2Push(U64 wpawns, U64 empty) {
   return soutOne(empty) & wpawns;
}
 
U64 wPawnsAble2DblPush(U64 wpawns, U64 empty) {
   const U64 rank4 = C64(0x00000000FF000000);
   U64 emptyRank3 = soutOne(empty & rank4) & empty;
   return wPawnsAble2Push(wpawns, emptyRank3);
}

and similar for black.

Generalized Push

One may rely on the generalized shift for one color parametrized pawn push routine. Since pawns don't occur on the first or eighth rank, one may either safe the wrap-ands ...

enum { white, black };
 
U64 singlePushTargets(U64 pawns, U64 empty, int color) {
    return rotateLeft( pawns, 8 - (color << 4) ) & empty;;
}

... or make the "white" north-shift unconditionally but to conditionally shift back south two ranks by color*16:

U64 singlePushTargets(U64 pawns, U64 empty, int color) {
    return ( (pawns << 8) >> (color << 4) ) & empty;
}

Forum Posts

How to Shift Left (by) a Negative Number?? by Steve Maughan, CCC, April 05, 2013

References

What links here?

Page	Date Edited
DirGolem	Jun 5, 2016
Double Attack	Oct 22, 2014
General Setwise Operations	Feb 25, 2018
Pawn Levers (Bitboards)	Nov 11, 2017
Pawn Pattern and Properties	Nov 11, 2017
Pawn Push	Mar 27, 2010
Pawn Pushes (Bitboards)	Apr 5, 2013
Pawn Spans	Jul 22, 2010
Pieces versus Directions	Oct 6, 2016
Steve Maughan	Jan 31, 2018

Up one Level

Wikispaces : chessprogramming - items matching description

Algebraic Chess Notation

Table of Contents

Pure coordinate notation

XBoard

UCI

Output Samples

ICCF numeric notation

Smith notation

Long Algebraic Notation (LAN)

Standard Algebraic Notation (SAN)

Ambiguities

Captures

En passant

Pawn promotion

Castling

Converting Moves

XBoard 2

Figurine Algebraic Notation (FAN)

Vector Graphics

LaTeX

Reading Chess

See also

Publications

Forum Posts

External Links

References

What links here?

Best Move

Table of Contents

Best so far

TT-Entry

PV-Table

Cut-Node

All-Node

See also

Forum Posts

What links here?

Captures

Table of Contents

Capture Generation

Six times Take Five

See also

Forum Posts

External Links

What links here?

Castling

Table of Contents

Rules

Chess960

Shogi

See also

Forum Posts

1982

2000 ...

2010 ...

External Links

References

What links here?

Copy-Make

Table of Contents

Copy-Make

Stack

See also

Forum Posts

1995 ...

2000 ...

2010 ...

2015 ...

What links here?

CPW-Engine_move(0x88)

Code

What links here?

En passant

Table of Contents

Legality Test

En passant bugs

See also

Forum Posts

1999