Tabledriven Move Generation
Home * Board Representation * Move Generation * Table-driven Move Generation
Table-driven Move Generation, is a technique to speed up the common traversal of pieces with their origin (from square) from a piece-list and their potential move target squares by traversing linked lists with pre-calculated moves, which head is indexed by piece-type and origin. There are three control structures to cover the disjoint move abilities for king or knights, pawns, and sliding pieces, while we focus on the latter for the most general case.
GNU Chess
Inspired by Hardware
Table-driven move generation was pioneered by Hans Eric Sandström in 1989 [2] as introduced in GNU Chess Version 1.55 [3] :
New move Generation algorithm: |
Revision: 1989-09-06 |
Author: Hans Eric Sandstroem. |
This algorithm is the result of an attempt to make an hardware move generator, but since I newer had the time and resources to build the hardware I wrote a software version and incorporated that one into gnu chess. This was the best way I could think of sharing this algorithm with the computer chess community. |
If there is anybody out there with the time and resources to build a hardware move generator I will be glad to assist. |
The general idea behind this algorithm is to pre calculate a lot of data. The data that is pre calculated is every possible move for every piece from every square disregarding any other pieces on the board. This pre calculated data is stored in an array … |
Butterfly Tables
The GNU Chess implementation used the natural branches on empty square, and if occupied and the next direction is taken, on own or opponent piece. Piece kind, origin and target square index an array of eight Butterfly boards with 64 Kib in total with 16-bit words while bytes might suffice as next direction or next position squares as well. This is very register but less memory friendly due to the Butterfly layout. Sentinel nodes use the origin square to terminate the do-while loop [4]:
Further Implementations
There are zillions of implementation nuances concerning disjoint move-lists for quiet moves and captures, and space-time tradeoff.
Ferret
The GNU Chess approach was refined by Bruce Moreland, as used in Ferret, and elaborated in his programming topics, for instance for a bishop on d5 [5]:
Diep
Vincent Diepeveen used a similar technique in Diep. He published a move generation skeleton under the GPL [6] in CCC [7] [8] [9] [10]. Vincent’s approach uses the default ones-increment of the list pointer, and adds a further skip-increment to the next direction in case of a block, which is done branch-less by intersection of the increment with a mask for target square empty (0) or not (-1), and was inspiration for the conditional linked list approach, which stresses memory versus a simplified control structure.
Conditional Linked List
To minimize code and to avoid branches on todays super pipelined processors, following recursive data structure of a pre-initialized skip list with two alternative next references might be applied for a prototype of table-driven move generation.
Data Structure
One sliding move node consists of the target square, the bit redundant move itself (might already contain a score based on dedicated piece-square tables concerning move ordering), and an array of two pointers to the next square if any. During traversal, the next array is indexed by the condition whether the target square is empty (0, false) or occupied (1, true), either to arrive the next square on the current ray, or the first square of the next ray-direction if any.
The number of sliding move node structures is determined by the influence quantity of pieces, where bishops have a cardinality of 560, rooks of 896, and queens the sum of 1456, and they are typically declared as array with consecutive nodes and almost always pNext[0] = this + 1. However, despite avoiding conditional branches, this redundancy a little bit pays off since this approach does not require sentinel nodes with one extra indirection to check for an invalid target square for termination, due to storing sentinel values, that is null pointers aka nil.
With following initialization, for instance for a rook on e4:
Control Structure
This data structure simplifies the control structure to generate moves of one sliding piece with only one conditional branch concerning the while loop. To avoid the branch on blocked by own piece, a conditional write taking advantage of write-combining [11] is implemented, storing always, but post-increment the move list pointer by a boolean aka {0,1} condition:
Captures vs Quiet
To generate disjoint sets of captures and quiet moves in different move generation stages, the same conditional linked lists could be traversed, stressing conditional writes in using different conditions for the move-list pointer increment.
However, for capture generation specially in the quiescence search, if one imagines a queen in the late ending, the overhead to visit up to 27 empty squares with conditional stores seems not justified, and one may better rely on branches as demonstrated in Fritz Reul’s blocking Loop, and to scan potential winning capture targets with a vector attack lookup whether they have lines in common with a sliding piece able to move along that line, to only test whether the squares between are empty - not to mention bitboard techniques.
Dense Index List
As proposed by Matthew R. Brades with 64-bit nodes and indices instead of pointer [12], an even denser alternative is to use nodes with two 12-bit indices and target square packed in a 32-bit integer. With appropriate piece-type coding, with bits 2 to 4 masked containing a right shift amount, either 8 for empty squares and 20 for pieces, one may “index” the appropriate next index. Bit 0 and 1 are exclusively set for either white and black pieces.
See also
- 0x88
- Mailbox
- Move Generation in CPW-Engine
- Move Generation in Atlas
- Offset Move Generation
- Vector Attacks
Publications
- Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227, index
Forum Posts
1998 …
- GNU move generation by Jan Willem de Kort, rgcc, March 18, 1998
- Re: 0x88 by Bruce Moreland, January 12, 1999
2000 …
- Pre-calculated move generation by Ujecrh, CCC, June 26, 2000
- Precomputed move information by Sune Fischer, CCC, July 02, 2002
- Diep move generator speeded up by Vincent Diepeveen, CCC, January 01, 2005
- Re: Is it time for another new move generator? by Karlo Bala Jr., CCC, November 11, 2007
- Did someone mention the GNUChess move Generator? by Michael Sherwin, CCC, November 12, 2007
2010 …
- What’s the fastest move generator? by Marcel Fournier, CCC, August 29, 2012
- CPW Move Table compression by Matthew R. Brades, CCC, September 08, 2012
- Move Tables - explain as if I’m five by Matthew R. Brades, CCC, November 04, 2012
Re: Move Tables - explain as if I’m five by Martin Sedlak, CCC, November 04, 2012 Re: Move Tables - explain as if I’m five by Karlo Bala Jr., CCC, November 05, 2012
- Diepeveen’s move generator by Hrvoje Horvatic, CCC, November 18, 2012
Re: Diepeveen’s move generator by Vincent Diepeveen, CCC, November 19, 2012
- Fast table-driven move generation by Syed Fahad, CCC, January 01, 2017
- Re: PieceLists ? by Karlo Bala Jr., CCC, February 17, 2017 » Piece-Lists
- Opinions requested for new move gen idea by Michael Sherwin, CCC, March 03, 2019
External Links
- Move Table move generation from Bruce Moreland’s Programming Topics
- Permission to use code from Random thoughts by Mridul Muralidharan, June 09, 2004
- Skip list from Wikipedia
- Kraftwerk - Ruckzuck, Soest 1970, YouTube Video
lineup: Ralf Hütter, Florian Schneiderr-Esleben, Klaus Dinger
References
- ↑ Alex Bell (1972). Games Playing with Computers. Allen & Unwin, ISBN-13: 978-0080212227, index
- ↑ Re: Move Tables - explain as if I’m five by Karlo Bala Jr., CCC, November 05, 2012
- ↑ GNU’s Bulletin, vol. 1 no. 8 - GNU Project - Free Software Foundation (FSF)
- ↑ GNU’s new move generation algorithm
- ↑ Move Table move generation from Bruce Moreland’s Programming Topics
- ↑ Permission to use code from Random thoughts by Mridul Muralidharan, June 09, 2004
- ↑ Diep move generator speeded up by Vincent Diepeveen, CCC, January 01, 2005
- ↑ Re: What’s the fastest move generator? by Vincent Diepeveen, CCC, August 31, 2012
- ↑ Re: What’s the fastest move generator? by Vincent Diepeveen, CCC, August 30, 2012
- ↑ Re: Diepeveen’s move generator by Vincent Diepeveen, CCC, November 19, 2012
- ↑ Software Optimization Guide for AMD Family 10h and 12h Processors (pdf) see pp. 102 on Conditional Write
- ↑ CPW Move Table compression by Matthew R. Brades, CCC, September 08, 2012