=Programming=
==Board Representation=====TSCP===
[[TSCP]] uses two 64 element arrays, containing empty square plus [[Pieces#PieceTypeCoding|pure piece code]], and empty square plus piece color code <ref>[https://jim.sh/svn/jim/vendor/microwindows/current/src/demos/tuxchess/data.c TSCP - data.c]</ref>:.
<pre>
However, when generating moves, TSCP converts the board data into a bigger array [[10x12 Board]].
===FirstChess===
[[FirstChess]] uses two 64 integer arrays, for all tasks, including move generating.
</pre>
===Banksia===
[[Banksia]] uses only one vector from C++ standard library <ref>https://github.com/nguyenpham/Banksia/blob/master/src/base/base.h Banksia - base.h</ref>:
<pre>
}
</pre>
==Move Generators==
===Straightforward===
Based on the given cell and the size of the board, programs can calculate if the target cells are out of the board.
In below code [[Banksia]] generates moves for a Rook at position pos:
<pre>
case PieceType::rook: // both queen and rook here
{
int col = getColumn(pos);
for (int y=pos - 1; y >= pos - col; y--) { /* go left */
gen_addMove(moves, pos, y, captureOnly);
if (!isEmpty(y)) {
break;
}
}
for (int y=pos + 1; y < pos - col + 8; y++) { /* go right */
gen_addMove(moves, pos, y, captureOnly);
if (!isEmpty(y)) {
break;
}
}
for (int y=pos - 8; y >= 0; y -= 8) { /* go up */
gen_addMove(moves, pos, y, captureOnly);
if (!isEmpty(y)) {
break;
}
}
for (int y=pos + 8; y < 64; y += 8) { /* go down */
gen_addMove(moves, pos, y, captureOnly);
if (!isEmpty(y)) {
break;
}
}
break;
}
</pre>
==Precalculate data==
Some programs pre-calculate data for each cell and extract it when generating moves. That method is well-known mentioned by [[Hans Eric Sandstroem]] in [[GNU Chess]] version 4.0 document, 6 Sep 1989:
<pre>
The general idea behind this algoritm 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 that looks like
this:
struct sqdata {
short nextpos;
short nextdir;
};
struct sqdata posdata[8][64][64];
/* posdata[piecetype][fromsquare][destinationsquare] */
example:
the first move for a queen at e8 is stored at;
posdata[queen][e8][e8].nextpos
suppose this is e7 and e7 is occupied then the next move
will be found in;
posdata[queen][e8][e7].nextdir
To handle the differeces between white and black pawns (they move in
opposite directions) an array ptype has been introduced:
static const short ptype[2][8] = {
no_piece,pawn,knight,bishop,rook,queen,king,no_piece,
no_piece,bpawn,knight,bishop,rook,queen,king,no_piece};
^^^^^
And it is used like this:
piecetype = ptype[side][piece]
When generating moves for pieces that are not black pawns, piece
can be used directly in posdata. As in the example above.
Thus the only thing one has to do when generating the moves
is to check for collisions with other pieces.
the move generation to do this looks like this: (for non pawns)
p = posdata[piece][sq];
u = p[sq].nextpos;
do {
if (color[u] == neutral) {
LinkMove(ply,sq,u,xside);
u = p[u].nextpos;
}
else {
if (color[u] == xside) LinkMove(ply,sq,u,xside);
u = p[u].nextdir;
}
} while (u != sq);
- I`nt this just beautiful!
The array posdata is initialized in the routine Initialize_moves.
This routine is called just once and it works so no time has been spent
on the structure of this code. GenMoves and CaptureList generates the
moves but the routines ataks, BRscan, Sqatakd, KingScan and trapped
also relies on the move generation algoritm so they have also been
rewritten.
</pre>
=Alternatives=
As a lone board representation, the 8x8 board has some efficiency issues with [[Move Generation|move generation]] related to off the board test. Therefore more common are approaches dealing with that, that is [[10x12 Board|10x12 board]] with surrounding ranks and files, and [[Vector Attacks]] with its cheap test and unique square difference property with respect to [[Distance|distance]] and [[Direction|direction]] <ref>[[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, ''2 Non-Bitboard Architectures''</ref>. In ''Games Playing with Computers'', 1972 <ref>[http://www.chilton-computing.org.uk/acl/literature/books/gamesplaying/p003.htm Chapter 3: Board Games - 3.1 CHESS] from [[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</ref> , [[Alex Bell]] introduced an array of 65 squares, where the purpose of square 65 (always empty) is to detect pawns capturing outside the board by a table driven move generator.
=See also=
* [[Bitboards]]
: [[Square Mapping Considerations]]
* [[Table-driven Move Generation]]
* [[Vector Attacks]]
: [[0x88]]
