25,161
edits
Changes
Created page with "'''Home * Board Representation * Move Generation * Table-driven Move Generation''' '''Table-driven Move Generation''', is a technique to speed up the co..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Move Generation]] * Table-driven Move Generation'''
'''Table-driven Move Generation''',
is a technique to speed up the common traversal of [[Pieces|pieces]] with their [[Origin Square|origin]] (from square) from a [[Piece-Lists|piece-list]] and their potential [[Target Square|move target squares]] by traversing [[Linked List|linked lists]] with pre-calculated [[Moves|moves]], which head is indexed by [[Pieces#PieceTypeCoding|piece-type]] and origin. There are three control structures to cover the disjoint move abilities for [[King|king]] or [[Knight|knights]], [[Pawn|pawns]], and [[Sliding Pieces|sliding pieces]], while we focus on the latter for the most general case.
=Prologue=
The classical technique in sliding piece move generation with [[Mailbox|square centric board arrays]], is to loop over all [[Direction#RayDirections|ray-directions]], and per ray-direction from the next closest square (if any) to the farthest square of that [[Rays|ray]] until either the target square is occupied by an own piece, or occupied by opponent piece which requires a [[Captures|capture]] generation. The control structure, its code size, number of local and register variables, and conditional branches on ray-termination, that is on piece-code combined with farthest square or off-the board tests, were the driving force in designing efficient board representations like [[0x88]] and [[Mailbox|mailbox]] in conjunction with appropriate piece coding. One example is the [[Gambiet#PieceCoding|piece coding]] in [[Gambiet]] to conditionally branch on several [[Z80]] processor flags, set by only one shift instruction. For a [[8x8 Board|8x8 board]] there was already a proposal by [[Alex Bell]] as used in [[Atlas]] <ref>[[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [https://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227, [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/index.htm index]</ref>, to lookup ray-increments per ray-direction and terminal squares per ray-direction and origin - sample code in [[Cpp|C++]] pseudo code:
<pre>
for (all directions[piece_kind] -> dir) {
delta = delta_table[dir];
lastsq = lastsq_table[dir][fromsq];
if ( fromsq != lastsq ) {
for (tosq = fromsq + delta; board[tosq].isNotPieceOf(side2move); tosq += delta) {
generateMove( fromsq, tosq );
if ( board[tosq].isPiece() || tosq == lastsq )
break; /* next direction after capture or last square */
}
}
}
</pre>
<span id="GNUChess"></span>
=GNU Chess=
==Inspired by Hardware==
Table-driven move generation was pioneered by [[Hans Eric Sandström]] in 1989 <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=490652&t=45846 Re: Move Tables - explain as if I'm five] by [[Karlo Bala Jr.]], [[CCC]], November 05, 2012</ref> as introduced in [[GNU Chess]] Version 1.55 <ref>[http://www.gnu.org/bulletins/bull8.html GNU's Bulletin, vol. 1 no. 8 - GNU Project - Free Software Foundation (FSF)]</ref> :
{| class="wikitable"
|-
| New move Generation algorithm:
Revision: 1989-09-06
Author: Hans Eric Sandstroem.
This algorithm is the result of an attempt to make an [[Move Generation#Hardware|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. [[Pieces#PieceTypeCoding|Piece kind]], [[Origin Square|origin]] and [[Target Square|target square]] index an [[Array|array]] of eight [[Butterfly Boards|Butterfly boards]] with 64 Kib in total with [[Word|16-bit words]] while [[Byte|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. [https://en.wikipedia.org/wiki/Sentinel_node Sentinel nodes] use the origin square to terminate the do-while loop <ref>[http://slackware.dreamhost.com/slackware/slackware-2.1/usr/doc/gnuchess-4.0/MOVE-GEN GNU's new move generation algorithm]</ref>:
<pre>
struct sqdata {
short nextpos;
short nextdir;
};
struct sqdata posdata[8][64][64];
...
struct sqdata *p = posdata[piece_kind][fromsq];
tosq = p[fromsq].nextpos;
do {
if (color[tosq] == neutral) {
linkMove(ply, fromsq, tosq, xside);
tosq = p[tosq].nextpos;
}
else {
if (color[tosq] == xside)
linkMove(ply, fromsq, tosq, xside);
tosq = p[tosq].nextdir;
}
} while (tosq != fromsq);
</pre>
=Further Implementations=
There are zillions of implementation nuances concerning disjoint move-lists for quiet moves and captures, and [[Space-Time Tradeoff|space-time tradeoff]].
<span id="Ferret"></span>
==Ferret==
The [[Table-driven Move Generation#GNUChess|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 <ref>[http://web.archive.org/web/20070715002634/www.brucemo.com/compchess/programming/movetable.htm Move Table move generation] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070607231311/www.brucemo.com/compchess/programming/index.htm Programming Topics]</ref>:
<pre>
typedef struct tagMT {
int square;
struct tagMT * pmtBlocked;
} MT;
MT argmtBD5[] = {
e6, &argmtBD5[3], // Element 0, 1st ray.
d7, &argmtBD5[3],
f8, &argmtBD5[3],
c6, &argmtBD5[3], // Element 3, 2nd ray.
b7, &argmtBD5[6],
a8, &argmtBD5[6],
e4, &argmtBD5[6], // Element 6, 3rd ray.
f3, &argmtBD5[6],
g2, &argmtBD5[6],
h1, NULL, // Element 9, 4th ray.
c4, NULL,
b3, NULL,
a2, NULL,
-1,
};
void genMoves(MT * pmt)
{
for (;;) {
if (IsEmpty(pmt->square)) {
GenMove(pmt->square);
if ((++pmt)->square < 0)
break;
} else {
if (IsEnemy(pmt->square))
GenMove(pmt->square);
if ((pmt = pmt->pmtBlocked) == NULL)
break;
}
}
}
</pre>
<span id="Diep"></span>
==Diep==
[[Vincent Diepeveen]] used a similar technique in [[Diep]]. He published a move generation skeleton under the [[Free Software Foundation#GPL|GPL]] <ref>[http://mridulm.blogspot.de/2004/06/permission-to-use-code-have-to-put-up.html Permission to use code] from [http://mridulm.blogspot.de/ Random thoughts] by [[Mridul Muralidharan]], June 09, 2004</ref> in [[CCC]] <ref>[https://www.stmintz.com/ccc/index.php?id=403656 Diep move generator speeded up] by [[Vincent Diepeveen]], [[CCC]], January 01, 2005</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=480825&t=44939 Re: What's the fastest move generator?] by [[Vincent Diepeveen]], [[CCC]], August 31, 2012</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=480726&t=44939 Re: What's the fastest move generator?] by [[Vincent Diepeveen]], [[CCC]], August 30, 2012</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=493083&t=46056 Re: Diepeveen's move generator] by [[Vincent Diepeveen]], [[CCC]], November 19, 2012</ref>. 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 [[Table-driven Move Generation#ConditionalLinkedList|conditional linked list]] approach, which stresses memory versus a simplified control structure.
<span id="ConditionalLinkedList"></span>
=Conditional Linked List=
To minimize code and to [[Avoiding Branches|avoid branches]] on todays super pipelined processors, following [[Recursion|recursive]] data structure of a pre-initialized [https://en.wikipedia.org/wiki/Skip_list 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|piece-square tables]] concerning [[Move Ordering|move ordering]]), and an [[Array|array]] of two [https://en.wikipedia.org/wiki/Pointer_%28computer_programming%29 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.
<pre>
struct SlidingMoveNode
{
TSquare tosq;
SMove move;
SlidingMoveNode* pNext[2];
};
</pre>
The number of sliding move node structures is determined by the [[Influence Quantity of Pieces|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 <span style="background-color: #dedede;">pNext[0] = this + 1</span>. However, despite avoiding conditional branches, this redundancy a little bit pays off since this approach does not require [https://en.wikipedia.org/wiki/Sentinel_node sentinel nodes] with one extra indirection to check for an invalid target square for termination, due to storing sentinel values, that is [https://en.wikipedia.org/wiki/Pointer_%28computer_programming%29#Null_pointer null pointers] aka nil.
<pre>
SlidingMoveNode slidingMoveTable[1456+896+560]; /* queen, rook, bishop -> 2912 * 16 = 46592 bytes 45.5 Kib */
SlidingMoveNode* slidingMoveHead[3][64];
</pre>
With following initialization, for instance for a rook on e4:
<pre>
slidingMoveHead[rook][e4]
▼ north east south west
┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐─┐-┐ ┌────────┐─┐-┐ ┌────────┐─-┬-┌────────┐
│ e5 │ │ e6 │ │ e7 │ │ e8 │ │ f4 │ │ e3 │ │ d4 │ │ a4 │
├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤g4 ├────────┤e2 ├────────┤c4 ├────────┤
│ Re4e5 │ │ Re4e6 │ │ Re4e7 │ │ Re4e8 │ │ Re4f4 │ h4 │ Re4e3 │ e1 │ Re4d4 │ b4│ Re4a4 │
├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤
│pNext[0]│►│pNext[0]│►│pNext[0]│►│pNext[0]│►─│pNext[0]│►─...│pNext[0]│►─...│pNext[0]│►─..│ NIL │
├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤
│pNext[1]│ │pNext[1]│ │pNext[1]│ │pNext[1]│►─│pNext[1]│ │pNext[1]│ │ NIL │ │ NIL │
└────────┘ └────────┘ └────────┘ └────────┘ └────────┘─┘-┘ └────────┘─┘-┘ └────────┘--┴-└────────┘
▼ ▼ ▼ ▲ ▼ ▲ ▼ ▲
│ │ └───►──────────►───┘ │ │ │ │
│ └───►──────────►──────────►───┘ │ ... ─┘ │ ... ─┘
└───►──────────►──────────►──────────►───┘ └───►─...──┘ └───►─...──┘
</pre>
==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 [[Avoiding Branches#ConditionalWrite|conditional write]] taking advantage of [https://en.wikipedia.org/wiki/Write-combining write-combining] <ref>[http://support.amd.com/us/Processor_TechDocs/40546.pdf Software Optimization Guide for AMD Family 10h and 12h Processors] (pdf) see pp. 102 on Conditional Write</ref> is implemented, storing always, but post-increment the [[Move List|move list]] pointer by a boolean aka {0,1} condition:
<pre>
pMoveNode = slidingMoveHead[slidingPiece_kind_012][fromSq];
do {
tosq = pMoveNode->tosq;
*pMoveList = pMoveNode->move;
pMoveList += board[tosq].isNotPieceOf( side2move );
pMoveNode = pMoveNode->pNext[ board[tosq].isPiece() ];
} while ( pMoveNode );
</pre>
==Captures vs Quiet==
To generate disjoint sets of [[Captures|captures]] and [[Quiet Moves|quiet moves]] in different move generation stages, the same conditional linked lists could be traversed, stressing [[Avoiding Branches#ConditionalWrite|conditional writes]] in using different conditions for the move-list pointer increment.
<pre>
/* Captures */
pMoveNode = slidingMoveHead[slidingPiece_kind_012][fromSq];
do {
tosq = pMoveNode->tosq;
*pMoveList = capture( pMoveNode->move, board[tosq]);
pMoveList += board[tosq].isPieceOf( side2move ^ 1 );
pMoveNode = pMoveNode->pNext[ board[tosq].isPiece() ];
} while ( pMoveNode );
/* none Captures */
pMoveNode = slidingMoveHead[slidingPiece_kind_012][fromSq];
do {
tosq = pMoveNode->tosq;
*pMoveList = pMoveNode->move;
pMoveList += board[tosq].isPiece() ^ 1; /* isEmpty */
pMoveNode = pMoveNode->pNext[ board[tosq].isPiece() ];
} while ( pMoveNode );
</pre>
However, for capture generation specially in the [[Quiescence Search|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|Fritz Reul's]] [[Vector Attacks#NewArchitecture|blocking Loop]], and to scan potential winning capture targets with a [[Vector Attacks|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 [[Bitboards|bitboard]] techniques.
==Dense Index List==
As proposed by [[Matthew R. Brades]] with 64-bit nodes and indices instead of pointer <ref>[http://www.talkchess.com/forum/viewtopic.php?t=45042 CPW Move Table compression] by [[Matthew R. Brades]], [[CCC]], September 08, 2012</ref>, 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.
<pre>
// U32 as struct SlidingMoveNode {int next1 : 12; int next0 : 12; int tosq : 8; /* low byte */ };
U32 slidingMoveTable[1456+896+560]; /* queen, rook, bishop -> 2912 * 4 = 11648 bytes */
U32 slidingMoveHead[3][64];
/* five least significant piece code bits from board:
01000 empty
10101 white piece
10110 black piece */
node = slidingMoveHead[slidingPiece_kind_012][fromSq];
do {
node = slidingMoveTable[node];
tosq = node & 0x3f;
piece = board[tosq];
*pMoveList = fromaspects | tosq;
pMoveList += (piece & side2moveBit) == 0;
node = (node >> (piece & 0x1c)) & 0x0fff;
} while ( node );
</pre>
=See also=
* [[0x88]]
* [[Mailbox]]
* [[CPW-Engine_movegen(0x88)|Move Generation in CPW-Engine]]
* [[Atlas#MoveGeneration|Move Generation in Atlas]]
* [[10x12 Board#OffsetMG|Offset Move Generation]]
* [[Vector Attacks]]
=Publications=
* [[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [https://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227, [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/index.htm index]
=Forum Posts=
==1998 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7292bfb78152b40b GNU move generation] by [[Jan Willem de Kort]], [[Computer Chess Forums|rgcc]], March 18, 1998
* [https://www.stmintz.com/ccc/index.php?id=39133 Re: 0x88] by [[Bruce Moreland]], January 12, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=116593 Pre-calculated move generation] by Ujecrh, [[CCC]], June 26, 2000
* [https://www.stmintz.com/ccc/index.php?id=238333 Precomputed move information] by [[Sune Fischer]], [[CCC]], July 02, 2002
* [https://www.stmintz.com/ccc/index.php?id=403656 Diep move generator speeded up] by [[Vincent Diepeveen]], [[CCC]], January 01, 2005
* [http://www.talkchess.com/forum/viewtopic.php?t=17790&start=4 Re: Is it time for another new move generator?] by [[Karlo Bala Jr.]], [[CCC]], November 11, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=17820 Did someone mention the GNUChess move Generator?] by [[Michael Sherwin]], [[CCC]], November 12, 2007
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=44939 What's the fastest move generator?] by Marcel Fournier, [[CCC]], August 29, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=45042 CPW Move Table compression] by [[Matthew R. Brades]], [[CCC]], September 08, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=45846 Move Tables - explain as if I'm five] by [[Matthew R. Brades]], [[CCC]], November 04, 2012
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=490492&t=45846 Re: Move Tables - explain as if I'm five] by [[Martin Sedlak]], [[CCC]], November 04, 2012
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=490652&t=45846 Re: Move Tables - explain as if I'm five] by [[Karlo Bala Jr.]], [[CCC]], November 05, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46056 Diepeveen's move generator] by Hrvoje Horvatic, [[CCC]], November 18, 2012
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=493083&t=46056 Re: Diepeveen's move generator] by [[Vincent Diepeveen]], [[CCC]], November 19, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=62686 Fast table-driven move generation] by [[Syed Fahad]], [[CCC]], January 01, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63126&start=40 Re: PieceLists ?] by [[Karlo Bala Jr.]], [[CCC]], February 17, 2017 » [[Piece-Lists]]
=External Links=
* [http://web.archive.org/web/20070715002634/www.brucemo.com/compchess/programming/movetable.htm Move Table move generation] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070607231311/www.brucemo.com/compchess/programming/index.htm Programming Topics]
* [http://mridulm.blogspot.de/2004/06/permission-to-use-code-have-to-put-up.html Permission to use code] from [http://mridulm.blogspot.de/ Random thoughts] by [[Mridul Muralidharan]], June 09, 2004
* [https://en.wikipedia.org/wiki/Skip_list Skip list from Wikipedia]
* [https://en.wikipedia.org/wiki/Kraftwerk Kraftwerk] - [http://de.wikipedia.org/wiki/Ruck_Zuck_%28Begriffskl%C3%A4rung%29 Ruckzuck] (1970), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=JbK1GulvSDQ|alignment=left|valignment=top}}
=References=
<references />
'''[[Move Generation|Up one level]]'''
'''Table-driven Move Generation''',
is a technique to speed up the common traversal of [[Pieces|pieces]] with their [[Origin Square|origin]] (from square) from a [[Piece-Lists|piece-list]] and their potential [[Target Square|move target squares]] by traversing [[Linked List|linked lists]] with pre-calculated [[Moves|moves]], which head is indexed by [[Pieces#PieceTypeCoding|piece-type]] and origin. There are three control structures to cover the disjoint move abilities for [[King|king]] or [[Knight|knights]], [[Pawn|pawns]], and [[Sliding Pieces|sliding pieces]], while we focus on the latter for the most general case.
=Prologue=
The classical technique in sliding piece move generation with [[Mailbox|square centric board arrays]], is to loop over all [[Direction#RayDirections|ray-directions]], and per ray-direction from the next closest square (if any) to the farthest square of that [[Rays|ray]] until either the target square is occupied by an own piece, or occupied by opponent piece which requires a [[Captures|capture]] generation. The control structure, its code size, number of local and register variables, and conditional branches on ray-termination, that is on piece-code combined with farthest square or off-the board tests, were the driving force in designing efficient board representations like [[0x88]] and [[Mailbox|mailbox]] in conjunction with appropriate piece coding. One example is the [[Gambiet#PieceCoding|piece coding]] in [[Gambiet]] to conditionally branch on several [[Z80]] processor flags, set by only one shift instruction. For a [[8x8 Board|8x8 board]] there was already a proposal by [[Alex Bell]] as used in [[Atlas]] <ref>[[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [https://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227, [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/index.htm index]</ref>, to lookup ray-increments per ray-direction and terminal squares per ray-direction and origin - sample code in [[Cpp|C++]] pseudo code:
<pre>
for (all directions[piece_kind] -> dir) {
delta = delta_table[dir];
lastsq = lastsq_table[dir][fromsq];
if ( fromsq != lastsq ) {
for (tosq = fromsq + delta; board[tosq].isNotPieceOf(side2move); tosq += delta) {
generateMove( fromsq, tosq );
if ( board[tosq].isPiece() || tosq == lastsq )
break; /* next direction after capture or last square */
}
}
}
</pre>
<span id="GNUChess"></span>
=GNU Chess=
==Inspired by Hardware==
Table-driven move generation was pioneered by [[Hans Eric Sandström]] in 1989 <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=490652&t=45846 Re: Move Tables - explain as if I'm five] by [[Karlo Bala Jr.]], [[CCC]], November 05, 2012</ref> as introduced in [[GNU Chess]] Version 1.55 <ref>[http://www.gnu.org/bulletins/bull8.html GNU's Bulletin, vol. 1 no. 8 - GNU Project - Free Software Foundation (FSF)]</ref> :
{| class="wikitable"
|-
| New move Generation algorithm:
Revision: 1989-09-06
Author: Hans Eric Sandstroem.
This algorithm is the result of an attempt to make an [[Move Generation#Hardware|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. [[Pieces#PieceTypeCoding|Piece kind]], [[Origin Square|origin]] and [[Target Square|target square]] index an [[Array|array]] of eight [[Butterfly Boards|Butterfly boards]] with 64 Kib in total with [[Word|16-bit words]] while [[Byte|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. [https://en.wikipedia.org/wiki/Sentinel_node Sentinel nodes] use the origin square to terminate the do-while loop <ref>[http://slackware.dreamhost.com/slackware/slackware-2.1/usr/doc/gnuchess-4.0/MOVE-GEN GNU's new move generation algorithm]</ref>:
<pre>
struct sqdata {
short nextpos;
short nextdir;
};
struct sqdata posdata[8][64][64];
...
struct sqdata *p = posdata[piece_kind][fromsq];
tosq = p[fromsq].nextpos;
do {
if (color[tosq] == neutral) {
linkMove(ply, fromsq, tosq, xside);
tosq = p[tosq].nextpos;
}
else {
if (color[tosq] == xside)
linkMove(ply, fromsq, tosq, xside);
tosq = p[tosq].nextdir;
}
} while (tosq != fromsq);
</pre>
=Further Implementations=
There are zillions of implementation nuances concerning disjoint move-lists for quiet moves and captures, and [[Space-Time Tradeoff|space-time tradeoff]].
<span id="Ferret"></span>
==Ferret==
The [[Table-driven Move Generation#GNUChess|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 <ref>[http://web.archive.org/web/20070715002634/www.brucemo.com/compchess/programming/movetable.htm Move Table move generation] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070607231311/www.brucemo.com/compchess/programming/index.htm Programming Topics]</ref>:
<pre>
typedef struct tagMT {
int square;
struct tagMT * pmtBlocked;
} MT;
MT argmtBD5[] = {
e6, &argmtBD5[3], // Element 0, 1st ray.
d7, &argmtBD5[3],
f8, &argmtBD5[3],
c6, &argmtBD5[3], // Element 3, 2nd ray.
b7, &argmtBD5[6],
a8, &argmtBD5[6],
e4, &argmtBD5[6], // Element 6, 3rd ray.
f3, &argmtBD5[6],
g2, &argmtBD5[6],
h1, NULL, // Element 9, 4th ray.
c4, NULL,
b3, NULL,
a2, NULL,
-1,
};
void genMoves(MT * pmt)
{
for (;;) {
if (IsEmpty(pmt->square)) {
GenMove(pmt->square);
if ((++pmt)->square < 0)
break;
} else {
if (IsEnemy(pmt->square))
GenMove(pmt->square);
if ((pmt = pmt->pmtBlocked) == NULL)
break;
}
}
}
</pre>
<span id="Diep"></span>
==Diep==
[[Vincent Diepeveen]] used a similar technique in [[Diep]]. He published a move generation skeleton under the [[Free Software Foundation#GPL|GPL]] <ref>[http://mridulm.blogspot.de/2004/06/permission-to-use-code-have-to-put-up.html Permission to use code] from [http://mridulm.blogspot.de/ Random thoughts] by [[Mridul Muralidharan]], June 09, 2004</ref> in [[CCC]] <ref>[https://www.stmintz.com/ccc/index.php?id=403656 Diep move generator speeded up] by [[Vincent Diepeveen]], [[CCC]], January 01, 2005</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=480825&t=44939 Re: What's the fastest move generator?] by [[Vincent Diepeveen]], [[CCC]], August 31, 2012</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=480726&t=44939 Re: What's the fastest move generator?] by [[Vincent Diepeveen]], [[CCC]], August 30, 2012</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=493083&t=46056 Re: Diepeveen's move generator] by [[Vincent Diepeveen]], [[CCC]], November 19, 2012</ref>. 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 [[Table-driven Move Generation#ConditionalLinkedList|conditional linked list]] approach, which stresses memory versus a simplified control structure.
<span id="ConditionalLinkedList"></span>
=Conditional Linked List=
To minimize code and to [[Avoiding Branches|avoid branches]] on todays super pipelined processors, following [[Recursion|recursive]] data structure of a pre-initialized [https://en.wikipedia.org/wiki/Skip_list 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|piece-square tables]] concerning [[Move Ordering|move ordering]]), and an [[Array|array]] of two [https://en.wikipedia.org/wiki/Pointer_%28computer_programming%29 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.
<pre>
struct SlidingMoveNode
{
TSquare tosq;
SMove move;
SlidingMoveNode* pNext[2];
};
</pre>
The number of sliding move node structures is determined by the [[Influence Quantity of Pieces|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 <span style="background-color: #dedede;">pNext[0] = this + 1</span>. However, despite avoiding conditional branches, this redundancy a little bit pays off since this approach does not require [https://en.wikipedia.org/wiki/Sentinel_node sentinel nodes] with one extra indirection to check for an invalid target square for termination, due to storing sentinel values, that is [https://en.wikipedia.org/wiki/Pointer_%28computer_programming%29#Null_pointer null pointers] aka nil.
<pre>
SlidingMoveNode slidingMoveTable[1456+896+560]; /* queen, rook, bishop -> 2912 * 16 = 46592 bytes 45.5 Kib */
SlidingMoveNode* slidingMoveHead[3][64];
</pre>
With following initialization, for instance for a rook on e4:
<pre>
slidingMoveHead[rook][e4]
▼ north east south west
┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐─┐-┐ ┌────────┐─┐-┐ ┌────────┐─-┬-┌────────┐
│ e5 │ │ e6 │ │ e7 │ │ e8 │ │ f4 │ │ e3 │ │ d4 │ │ a4 │
├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤g4 ├────────┤e2 ├────────┤c4 ├────────┤
│ Re4e5 │ │ Re4e6 │ │ Re4e7 │ │ Re4e8 │ │ Re4f4 │ h4 │ Re4e3 │ e1 │ Re4d4 │ b4│ Re4a4 │
├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤
│pNext[0]│►│pNext[0]│►│pNext[0]│►│pNext[0]│►─│pNext[0]│►─...│pNext[0]│►─...│pNext[0]│►─..│ NIL │
├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤ ├────────┤
│pNext[1]│ │pNext[1]│ │pNext[1]│ │pNext[1]│►─│pNext[1]│ │pNext[1]│ │ NIL │ │ NIL │
└────────┘ └────────┘ └────────┘ └────────┘ └────────┘─┘-┘ └────────┘─┘-┘ └────────┘--┴-└────────┘
▼ ▼ ▼ ▲ ▼ ▲ ▼ ▲
│ │ └───►──────────►───┘ │ │ │ │
│ └───►──────────►──────────►───┘ │ ... ─┘ │ ... ─┘
└───►──────────►──────────►──────────►───┘ └───►─...──┘ └───►─...──┘
</pre>
==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 [[Avoiding Branches#ConditionalWrite|conditional write]] taking advantage of [https://en.wikipedia.org/wiki/Write-combining write-combining] <ref>[http://support.amd.com/us/Processor_TechDocs/40546.pdf Software Optimization Guide for AMD Family 10h and 12h Processors] (pdf) see pp. 102 on Conditional Write</ref> is implemented, storing always, but post-increment the [[Move List|move list]] pointer by a boolean aka {0,1} condition:
<pre>
pMoveNode = slidingMoveHead[slidingPiece_kind_012][fromSq];
do {
tosq = pMoveNode->tosq;
*pMoveList = pMoveNode->move;
pMoveList += board[tosq].isNotPieceOf( side2move );
pMoveNode = pMoveNode->pNext[ board[tosq].isPiece() ];
} while ( pMoveNode );
</pre>
==Captures vs Quiet==
To generate disjoint sets of [[Captures|captures]] and [[Quiet Moves|quiet moves]] in different move generation stages, the same conditional linked lists could be traversed, stressing [[Avoiding Branches#ConditionalWrite|conditional writes]] in using different conditions for the move-list pointer increment.
<pre>
/* Captures */
pMoveNode = slidingMoveHead[slidingPiece_kind_012][fromSq];
do {
tosq = pMoveNode->tosq;
*pMoveList = capture( pMoveNode->move, board[tosq]);
pMoveList += board[tosq].isPieceOf( side2move ^ 1 );
pMoveNode = pMoveNode->pNext[ board[tosq].isPiece() ];
} while ( pMoveNode );
/* none Captures */
pMoveNode = slidingMoveHead[slidingPiece_kind_012][fromSq];
do {
tosq = pMoveNode->tosq;
*pMoveList = pMoveNode->move;
pMoveList += board[tosq].isPiece() ^ 1; /* isEmpty */
pMoveNode = pMoveNode->pNext[ board[tosq].isPiece() ];
} while ( pMoveNode );
</pre>
However, for capture generation specially in the [[Quiescence Search|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|Fritz Reul's]] [[Vector Attacks#NewArchitecture|blocking Loop]], and to scan potential winning capture targets with a [[Vector Attacks|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 [[Bitboards|bitboard]] techniques.
==Dense Index List==
As proposed by [[Matthew R. Brades]] with 64-bit nodes and indices instead of pointer <ref>[http://www.talkchess.com/forum/viewtopic.php?t=45042 CPW Move Table compression] by [[Matthew R. Brades]], [[CCC]], September 08, 2012</ref>, 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.
<pre>
// U32 as struct SlidingMoveNode {int next1 : 12; int next0 : 12; int tosq : 8; /* low byte */ };
U32 slidingMoveTable[1456+896+560]; /* queen, rook, bishop -> 2912 * 4 = 11648 bytes */
U32 slidingMoveHead[3][64];
/* five least significant piece code bits from board:
01000 empty
10101 white piece
10110 black piece */
node = slidingMoveHead[slidingPiece_kind_012][fromSq];
do {
node = slidingMoveTable[node];
tosq = node & 0x3f;
piece = board[tosq];
*pMoveList = fromaspects | tosq;
pMoveList += (piece & side2moveBit) == 0;
node = (node >> (piece & 0x1c)) & 0x0fff;
} while ( node );
</pre>
=See also=
* [[0x88]]
* [[Mailbox]]
* [[CPW-Engine_movegen(0x88)|Move Generation in CPW-Engine]]
* [[Atlas#MoveGeneration|Move Generation in Atlas]]
* [[10x12 Board#OffsetMG|Offset Move Generation]]
* [[Vector Attacks]]
=Publications=
* [[Alex Bell]] ('''1972'''). ''[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/overview.htm Games Playing with Computers]''. [https://en.wikipedia.org/wiki/Allen_%26_Unwin Allen & Unwin], ISBN-13: 978-0080212227, [http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/index.htm index]
=Forum Posts=
==1998 ...==
* [http://groups.google.com/group/rec.games.chess.computer/browse_frm/thread/7292bfb78152b40b GNU move generation] by [[Jan Willem de Kort]], [[Computer Chess Forums|rgcc]], March 18, 1998
* [https://www.stmintz.com/ccc/index.php?id=39133 Re: 0x88] by [[Bruce Moreland]], January 12, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=116593 Pre-calculated move generation] by Ujecrh, [[CCC]], June 26, 2000
* [https://www.stmintz.com/ccc/index.php?id=238333 Precomputed move information] by [[Sune Fischer]], [[CCC]], July 02, 2002
* [https://www.stmintz.com/ccc/index.php?id=403656 Diep move generator speeded up] by [[Vincent Diepeveen]], [[CCC]], January 01, 2005
* [http://www.talkchess.com/forum/viewtopic.php?t=17790&start=4 Re: Is it time for another new move generator?] by [[Karlo Bala Jr.]], [[CCC]], November 11, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=17820 Did someone mention the GNUChess move Generator?] by [[Michael Sherwin]], [[CCC]], November 12, 2007
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=44939 What's the fastest move generator?] by Marcel Fournier, [[CCC]], August 29, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=45042 CPW Move Table compression] by [[Matthew R. Brades]], [[CCC]], September 08, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=45846 Move Tables - explain as if I'm five] by [[Matthew R. Brades]], [[CCC]], November 04, 2012
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=490492&t=45846 Re: Move Tables - explain as if I'm five] by [[Martin Sedlak]], [[CCC]], November 04, 2012
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=490652&t=45846 Re: Move Tables - explain as if I'm five] by [[Karlo Bala Jr.]], [[CCC]], November 05, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=46056 Diepeveen's move generator] by Hrvoje Horvatic, [[CCC]], November 18, 2012
: [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=493083&t=46056 Re: Diepeveen's move generator] by [[Vincent Diepeveen]], [[CCC]], November 19, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=62686 Fast table-driven move generation] by [[Syed Fahad]], [[CCC]], January 01, 2017
* [http://www.talkchess.com/forum/viewtopic.php?t=63126&start=40 Re: PieceLists ?] by [[Karlo Bala Jr.]], [[CCC]], February 17, 2017 » [[Piece-Lists]]
=External Links=
* [http://web.archive.org/web/20070715002634/www.brucemo.com/compchess/programming/movetable.htm Move Table move generation] from [[Bruce Moreland|Bruce Moreland's]] [http://web.archive.org/web/20070607231311/www.brucemo.com/compchess/programming/index.htm Programming Topics]
* [http://mridulm.blogspot.de/2004/06/permission-to-use-code-have-to-put-up.html Permission to use code] from [http://mridulm.blogspot.de/ Random thoughts] by [[Mridul Muralidharan]], June 09, 2004
* [https://en.wikipedia.org/wiki/Skip_list Skip list from Wikipedia]
* [https://en.wikipedia.org/wiki/Kraftwerk Kraftwerk] - [http://de.wikipedia.org/wiki/Ruck_Zuck_%28Begriffskl%C3%A4rung%29 Ruckzuck] (1970), [https://en.wikipedia.org/wiki/YouTube YouTube] Video
: {{#evu:https://www.youtube.com/watch?v=JbK1GulvSDQ|alignment=left|valignment=top}}
=References=
<references />
'''[[Move Generation|Up one level]]'''
