GNU move generation
J.W.J.de.Kort
Hi friends!
At the moment i'am investigating the different methodes used to genarate
a list of possible moves. It seems to me that their are (at least) five
different methodes to do this;
1. postbox
2. 0x88
3. bitboards
4. rotated bitboards
5. gnu chess type
nr 1, 2, 3 and 4 have been covered in this newsgroup extensively in the
past, but i do not recall even having read something about the gnu chess
methode. I have a 'feeling' about how this might operate but i would
really appreciate some help on this part from some of you experts out
there. This methode seems to be better then the other systems mentioned.
I studied the gnu source and some people claim that this nethode could
be made more efficient to yield a speed five time as high as the gnu
source. Could some one please gives some hints on this issue?
Regards and many thanks in advance
Jan Willem
Peter W. Gillgasch
[ 100 % technical content warning. ]
J.W.J.de.Kort <J.W.J....@rechten.rug.nl> wrote:
> Hi friends!
>
> At the moment i'am investigating the different methodes used to genarate
> a list of possible moves. It seems to me that their are (at least) five
> different methodes to do this;
>
> 1. postbox
> 2. 0x88
> 3. bitboards
> 4. rotated bitboards
> 5. gnu chess type
>
>
> nr 1, 2, 3 and 4 have been covered in this newsgroup extensively in the
> past, but i do not recall even having read something about the gnu chess
> methode. I have a 'feeling' about how this might operate but i would
> really appreciate some help on this part from some of you experts out
> there. This methode seems to be better then the other systems mentioned.
Well I will not comment on efficiency issues, I doubt that it is
"better" in any sense, but I strongly encourage you to toy with this.
Maybe you will find something that others overlooked.
The general idea is this. For each piece class / square combination (I
ignore pawns, because they are a bit different) you have an array of
this structure:
typedef struct {
int mNextSquare; /* you could try shorts or chars as well */
int mNextDirection;
} MoveGenS;
so you have
MoveGenS gMoveGeneratorV [8][64][64];
(you will map the black pawn to [6][] and the white pawn to [7][]).
Before the program really uses this insanely huge table you run a
routine that precomputes mNextSquare and mNextDirection in a way that
allows the following:
Assume you want to generate moves for a non pawn piece of colour C,
piece class P located at square X.
const MoveGenS * const myMoveGenP = gMoveGeneratorV[P][X];
Now you you want to generate the sequence of "to" squares that are
pseudo-legal with the following code:
unsigned int myToSquare = myMoveGenP[X]->mNextSquare;
do {
unsigned int myBoardData;
myBoardData = gBoard[myToSquare];
if (myBoardData == kEmpty) {
/* now you found a target square and you do something
* with that. Code omitted.
*
* Since the ray is not blocked you step via mNextSquare
* to the next square.
*
* THE KEY IDEA: When you precalculate this data
* structure, you make sure that mNextSquare == mNextDir
* if the "to" square "falls off" the board. For non
* raying pieces mNextSquare == mNextDir as well.
*/
myToSquare = myMoveGenP[myToSquare]->mNextSquare;
} else {
if (IS_OPPONENT_PIECE(C,myBoardData)) {
/* here you can handle the capture case
* Code omitted.
*/
}
/*
* THE KEY IDEA: The ray is blocked, so you want
* to continue at the next square of the next
* ray you have not looked at. Note that you
* have precomputed the data in such a way
* that you are guaranteed to stay "on board".
*/
myToSquare = myMoveGenP[myToSquare]->mNextDir;
}
/* the gMoveGeneratorV vector has been precomputed in
* such a way that after you stepped through all possible
* squares you end up on your home square. When this happens,
* you are done.
*/
} while (myToSquare != X);
So for a rook on E4 the array looks like this:
Square index mNextSquare mNextDir
E4 E5 F4
E5 E6 F4
E6 E7 F4
E7 E8 F4
E8 F4 E3
F4 G4 E3
G4 H4 E3
H4 E3 E3
E3 E2 D4
E2 E1 D4
E1 D4 D4
D4 C4 E4
C4 B4 E4
B4 A4 E4
A4 E4 E4
The other elements are never being referenced, so you should
stuff an "impossible square" into that, for the sake of debugging.
> I studied the gnu source and some people claim that this nethode could
> be made more efficient to yield a speed five time as high as the gnu
> source. Could some one please gives some hints on this issue?
Sorry. I don't know how this is possible, but don't let this scare you
off. Possibly one could win big time by thinking about how to compress
the data in such a way that only the elements that are used are stored
sequentially as in the table above, since the table above essentially is
also the order in which the data will be referenced. That would be
significantly quicker, but I never tried. Maybe Bruce can jump into this
thread, since his program is with the exceptions of GNU and DarkThought
V1 the only program that is known for using this method. Bruce ?
-- Peter
We love to do the things we hate...
bruce moreland
>nr 1, 2, 3 and 4 have been covered in this newsgroup extensively in the
>past, but i do not recall even having read something about the gnu chess
>methode. I have a 'feeling' about how this might operate but i would
>really appreciate some help on this part from some of you experts out
>there. This methode seems to be better then the other systems mentioned.
> I studied the gnu source and some people claim that this nethode could
>be made more efficient to yield a speed five time as high as the gnu
>source. Could some one please gives some hints on this issue?
The idea is that you do your vector stuff once, at program startup.
When you want to see what a bishop on d4 can do, you traverse a linked
list. Each node on the list contains a pointer to the square you are
going to move to, a pointer to the next node in the list if the square
was empty, and a pointer to the next node in the list if the square
had something on it.
So, assume that the bishop is the only thing on the board. It might
try to go to e5, f6, g7, h8, c5, b6, a7, c3, b2, a1, e3, f2, g1, in
that order, going through the "next" link each time.
If there is something on e5, you'll follow the "blocked" link and go
straight to the c5 element.
This allows you to make a move generation a very tight loop.
A disadvantage is that you access a lot of memory, since you are
accessing pointers rather than adding a constant value to an offset.
I have used this in Ferret for years, it works fine. I don't know or
care if it is the best way, if I found a better way and completely
ripped my proram apart to implement it, I would probably only get a
couple of percent speedup.
bruce
bruce moreland
On Wed, 18 Mar 1998 16:57:49 +0100, gil...@ilk.de (Peter W. Gillgasch)
wrote:
>typedef struct {
>
> int mNextSquare; /* you could try shorts or chars as well */
> int mNextDirection;
>
>} MoveGenS;
>
>so you have
>
>MoveGenS gMoveGeneratorV [8][64][64];
>
>(you will map the black pawn to [6][] and the white pawn to [7][]).
>
>Before the program really uses this insanely huge table you run a
>routine that precomputes mNextSquare and mNextDirection in a way that
>allows the following:
>
>Assume you want to generate moves for a non pawn piece of colour C,
>piece class P located at square X.
>
>const MoveGenS * const myMoveGenP = gMoveGeneratorV[P][X];
Last time I looked at Gnu, it didn't work like this. It had something
like 4608 of those structs you are calling "MoveGenS", and another
array that was maybe 64 * 7 (wp, bp, n, b, r, q, k) of pointers into
that array. So the whole mess is less than 40K.
Less than 20K if you use 16-bit pointers or indexes or whatever.
I've been tweaking with this a lot, until now my table really is huge,
it is over 400K.
bruce
Edward Screven
bruce moreland wrote:
> On Wed, 18 Mar 1998 16:57:49 +0100, gil...@ilk.de (Peter W. Gillgasch)
> wrote:
>
> >typedef struct {
> >
> > int mNextSquare; /* you could try shorts or chars as well */
> > int mNextDirection;
> >
> >} MoveGenS;
> >
> >so you have
> >
> >MoveGenS gMoveGeneratorV [8][64][64];
>
> Last time I looked at Gnu, it didn't work like this. It had something
> like 4608 of those structs you are calling "MoveGenS", and another
> array that was maybe 64 * 7 (wp, bp, n, b, r, q, k) of pointers into
> that array. So the whole mess is less than 40K.
i use a variant of the gnu scheme for non-capturing piece moves. instead
of storing a struct pair <nextsq,nextdir>, i store a single 32 bit value
into which i encode everything i need to construct a move value, in
addition to an offset to the next direction. because of the way the bit
fields are layed out, i can get the "to-square", "move", and
"next-direction" components with a single bit-and or shift. ("to-sq" is a
subset of "move".)
i use different mechanisms for pawn moves and capturing piece moves.
- edward