Moderators: hgm, Rebel, chrisw
Gerd to the rescue...Gerd Isenberg wrote:I just found some more code of Vincent's generator in Mridul Muralidharan's Random thought blog:
http://mridulm.blogspot.de/2004/06/perm ... ut-up.html
I have a slightly improved version, which i made in 2005, i'll post it here some hours from now.Gerd Isenberg wrote:I just found some more code of Vincent's generator in Mridul Muralidharan's Random thought blog:
http://mridulm.blogspot.de/2004/06/perm ... ut-up.html
What's this for focking nonsense.ZirconiumX wrote:A discussion in the Olympus ICS came up about this.
The result was we thought that it was useless, because he didn't explain how the arrays worked, jus gave code which we weren't even sure worked.
If it did work, and VD would tell us how it worked, then we would use it hands down, because it seems quick.
Matthew:out
Had you considered shipping me an e-mail?Hrvoje Horvatic wrote:Gerd to the rescue...Gerd Isenberg wrote:I just found some more code of Vincent's generator in Mridul Muralidharan's Random thought blog:
http://mridulm.blogspot.de/2004/06/perm ... ut-up.html
I'v looked at the code, and it looks usable... many parts of a complete move generator are missing, but it seems that most important parts are there, procedure for initialization of arrays (table), and a two procedures for using those arrays for generating moves... I might be more lucky than Matthew...
I'll report results later...
You really should ship an email you know.Hrvoje Horvatic wrote:I'm puzzled about the speed of square-oriented vs bitboard-based move generators... I've checked existing open source programs and the best result I got was from cpw (0x88 based), which was about 20-25% slower than crafty (baseline bitboard engine with magic-based slider attacks)... I've checked both sources, and they seem to do the same thing, both are intel-compiled, so at first blush my crude comparison seems legit...
The rumor has it that Diepeveen's table-based move generator is THE move generator, and that it beats "beancounters" easily, because it's cache optimized...
Has anyone actually tried to do a comparison? a real comparison? Instead of just arguing? I would have done it, but don't have a complete source code, only some small patches left in a forum by Vincent here and there... which I couldn't turn into a working move generator...
hmmmm? anybody?
Code: Select all
/*
Gnu public license here.
See copy of it at FSF (free software foundation)
*/
const int
nunmap[144] = {
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, 0, 1, 2, 3, 4, 5, 6, 7, -1, -1,
-1, -1, 8, 9, 10, 11, 12, 13, 14, 15, -1, -1,
-1, -1, 16, 17, 18, 19, 20, 21, 22, 23, -1, -1,
-1, -1, 24, 25, 26, 27, 28, 29, 30, 31, -1, -1,
-1, -1, 32, 33, 34, 35, 36, 37, 38, 39, -1, -1,
-1, -1, 40, 41, 42, 43, 44, 45, 46, 47, -1, -1,
-1, -1, 48, 49, 50, 51, 52, 53, 54, 55, -1, -1,
-1, -1, 56, 57, 58, 59, 60, 61, 62, 63, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
-1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1
};
int
color[64], // having 0 = white, 1 = black, 2 = neutral
board[64], // having 0 = empty, pawn=1,knight=2,bishop=3,rook=4,queen=5,king=6
snelbord[64], // for white same as board[64], for black same as white but with a +8 for each piece
// like whitepawn = 1, blackpawn = 9
gentable[3][64][128], //* 24k loper, toren, dame *
iskippos[64][64], /* l t d */
ipiecepos[7][64][32], /* 0 = witte pion, 1 = zwarte pion, 2 = knight ... 6 = koning */
ipawndir[2][64][4]; /* slagzetten */
void QuickFullMoveList(int side,struct Move *EP) {
/* Generate semi-legal moves in fast manner
*/
int to,xside,*psq,sq,*t;
xside = side^1;
to = EP->zet&63;
if( board[to] == pawn ) { /* for enpassant */
int from = (EP->zet>>6)&63;
if( to-from == 16 || from-to == 16 ) {
int f,*w,u;
f = (to+from)>>1;
w = ipawndir[xside][f];
u = *w++;
if( color[u] == side && board[u] == pawn ) {
genindex->score = 1000;
QuickLink((u<<6)|f|move_captures|move_enpassant);
}
if( (u=*w) != 128 && color[u] == side && board[u] == pawn ) {
genindex->score = 1000;
QuickLink((u<<6)|f|move_captures|move_enpassant);
}
}
}
if( !castld[side] ) {
int u = PieceList[side][0];
if( quickcastle(side,u,u+2) ) {
genindex->score = 0;
QuickLink((u<<6)|(u+2)|move_castles);
}
if( quickcastle(side,u,u-2) ) {
genindex->score = 0;
QuickLink((u<<6)|(u-2)|move_castles);
}
}
t = cancapside[side];
psq = &quickpiecelist[side][12]; /* Q R B */
while( (sq=*psq++) != 128 ) {
int SRsq = (sq<<6);
int piece = board[sq];
int *s,*v,*w,u;
s = andscan[0];
v = ipiecepos[piece][sq];
w = iskippos[sq];
u = *v++;
do {
int p1=snelbord[u],sh=w[u];
v += (s[p1]&sh);
if( ((p1-1)>>3) != side ) {
genindex->score = pvals[p1];
QuickLink(SRsq|u|t[p1]);
}
} while( (u=*v++) != 128 );
}
psq = &quickpiecelist[side][26]; /* pawns */
while( (sq=*psq++) != 128 ) {
int SRsq = (sq<<6);
int u,*v,*w;
v = ipiecepos[side][sq];
w = ipawndir[side][sq];
u = *v++;
if( row(u) != 0 && row(u) != 7 ) {
if( color[u] == neutral) {
genindex->score = 0;
QuickLink(SRsq|u);
if( (u=*v) != 128 && color[u] == neutral ) { /* indien u == sq dan false */
genindex->score = 0;
QuickLink(SRsq|u);
}
}
u = *w++;
if( color[u] == xside ) { /* ppos bevat geen 100, maar sq. */
genindex->score = pvals[snelbord[u]];
QuickLink(SRsq|u|move_captures);
}
if( (u=*w) != 128 && color[u] == xside ) { /* zelf ben je per definitie side */
genindex->score = pvals[snelbord[u]];
QuickLink(SRsq|u|move_captures);
}
}
else {
if( color[u] == neutral) {
genindex->score = pvals[queen];
QuickLink(SRsq|u|move_pqueen);
genindex->score = 0;
QuickLink(SRsq|u|move_pknight);
genindex->score = 0;
QuickLink(SRsq|u|move_prook);
genindex->score = 0;
QuickLink(SRsq|u|move_pbishop);
}
u = *w++;
if( color[u] == xside) {/* captures */
genindex->score = pvals[queen];
QuickLink(SRsq|u|move_captures|move_pqueen);
genindex->score = 0;
QuickLink(SRsq|u|move_captures|move_pknight);
genindex->score = 0;
QuickLink(SRsq|u|move_captures|move_prook);
genindex->score = 0;
QuickLink(SRsq|u|move_captures|move_pbishop);
}
if( (u=*w) != 128 && color[u] == xside) {
genindex->score = pvals[queen];
QuickLink(SRsq|u|move_captures|move_pqueen);
genindex->score = 0;
QuickLink(SRsq|u|move_captures|move_pknight);
genindex->score = 0;
QuickLink(SRsq|u|move_captures|move_prook);
genindex->score = 0;
QuickLink(SRsq|u|move_captures|move_pbishop);
}
}
}
psq = quickpiecelist[side]; /* K N */
while( (sq=*psq++) != 128 ) {
int SRsq = (sq<<6);
int piece = board[sq];
int u,*v;
v = ipiecepos[piece][sq];
u = *v++;
do {
int p1 = snelbord[u];
if( ((p1-1)>>3) != side ) {
genindex->score = pvals[p1];
QuickLink(SRsq|u|t[p1]);
}
} while( (u=*v++) != 128 );
}
} /* End QuickFullMoveList() */
void InitGens(void) {
/* vul tabellen voor een 8x8 bord */
int
paardspring[8] = {15,-15,17,-17,6,-6,10,-10},
koningvlucht[8] = {7,-7,9,-9,8,-8,1,-1},
alldirec[3][8] = { /* delta richtingen op een 8x8 bord */
{7,-7,9,-9,0,0,0,0},
{8,-8,1,-1,0,0,0,0},
{7,-7,9,-9,8,-8,1,-1}
},
nsq,sq,flag,i,j,next_sq,rij,piece,np,lijn,m,ms,c,t,old_sq,
skipm[16],
rij8[2] = {7,0},
rij2[2] = {1,6},
slalinks[2] = {7,-9},
slarechts[2] = {9,-7},
veuren[2] = {8,-8},
/* 12x12 bord delta-coordinaten */
numberpiece[3] = {bishop,rook,queen},
numberfields[3] = {4,4,8},
direc[3][10] = { /* richtingen op een 12x12 bord */
{11,-11,13,-13,0,0,0,0,0,0}, /* loper */
{12,-12,1 ,-1 ,0,0,0,0,0,0}, /* toren */
{11,-11,13,-13,12,-12,1 ,-1,0,0} /* dame */
},
vlucht[8] = {11,-11,13,-13,12,-12,1 ,-1}, /* koning */
spring[8] = {23,-23,25,-25,10,-10,14,-14};/* paard */
for( sq = 0 ; sq < 64 ; sq++ )
for( m = 0 ; m < 64 ; m++ )
iskippos[sq][m] = 0;
for( i = 0 ; i < 7 ; i++ ) /* default value */
for( sq = 0 ; sq < 64 ; sq++ )
for( m = 0 ; m < 32 ; m++ )
ipiecepos[i][sq][m] = 128;
/* pionnen */
for( sq = 0 ; sq < 64 ; sq++ ) {
lijn = sq&7;
rij = sq/8;
nsq = 26 + rij*12 + lijn;
for( c = white ; c <= black ; c++ ) { /* pion: wit en zwart */
if( rij == rij8[c] )
ipawndir[c][sq][0] = 128;
else {
m = 0;
if( lijn != 7 ) {
ipawndir[c][sq][m] = (sq+slarechts[c]);
m++;
}
if( lijn != 0 ) {
ipawndir[c][sq][m] = (sq+slalinks[c]);
m++;
}
ipawndir[c][sq][m] = 128;
m = 0;
ipiecepos[c][sq][m] = (sq+veuren[c]);
m++;
if( rij == rij2[c] )
ipiecepos[c][sq][m] = (sq+2*veuren[c]);
}
}
m = 0;
old_sq = sq;
for( i = 0; i < 8; i++ ) {/* paard */
t = nsq+spring[i];
if( nunmap[t] >= 0 ) {
ipiecepos[knight][sq][m] = nunmap[t];
m++;
old_sq = nunmap[t];
}
}
ipiecepos[knight][sq][m] = 128;
m = 0;
old_sq = sq;
for( i = 0; i < 8; i++ ) { /* koning */
t = nsq+vlucht[i];
if( nunmap[t] >= 0 ) {
ipiecepos[king][sq][m] = nunmap[t];
m++;
old_sq = nunmap[t];
}
}
ipiecepos[king][sq][m] = 128;
for( np = 0 ; np < 3 ; np++ ) { /* loper,toren,dame */
piece = numberpiece[np];
m = 0;
ms = 0;
flag = 0;
j = 0;
while( nunmap[nsq+direc[np][j]] == -1 )
j++;
for( i = 0; i < numberfields[np]; i++ ) { /* voor alle richtingen */
int sqdone=0;
t = nsq;
t = t+direc[np][i];
j = i+1;
while( nunmap[nsq+direc[np][j]] == -1 )
j++;
next_sq = nunmap[nsq+direc[np][j]];
while( nunmap[t] != -1 ) {
sqdone++;
ipiecepos[piece][sq][m] = nunmap[t];
m++;
t = t+direc[np][i];
flag = 1;
}
if( sqdone >= 2 && np <= 1 ) {
/* alleen als er bij from-to daarna nog velden af
* te gaan zijn dan is het interessant. Anders 0.
* Dame hoeft niet want toren,loper al gedaan */
int my12sq/*,yesdeze=false*/;
/* begonnen met nsq (12x12) + delta (direc[np][i])
* */
my12sq = nsq+direc[np][i];
do {
/* 8x8 bord opslaan */
sqdone--;
my12sq += direc[np][i];
} while( sqdone >= 2 );
}
if( flag ) {
flag = 0;
skipm[ms] = m;
ms++;
}
}
ipiecepos[piece][sq][m] = 128;
m = 0;
ms = 0;
t = ipiecepos[piece][sq][m];
if( np == 2 ) { /* skippos alleen voor de dame vullen dat is genoeg */
do {
iskippos[sq][t] = (skipm[ms]-m)-1;
m++;
t = ipiecepos[piece][sq][m];
if( m == skipm[ms] )
ms++;
} while( t != 128 );
}
}
}
}
Code: Select all
s = andscan[0];
v = ipiecepos[piece][sq];
w = iskippos[sq];
u = *v++;
do {
int p1=snelbord[u],sh=w[u];
v += (s[p1]&sh);
genindex->zet = SRsq|u|t[p1];
genindex += lm[p1];
} while( (u=*v++) != 128 );
Code: Select all
int u,*v;
v = ipiecepos[piece][sq];
u = *v++;
do {
int p1 = snelbord[u];
genindex->zet = SRsq|u|t[p1];
genindex += lm[p1];
} while( (u=*v++) != 128 );
Code: Select all
int
linkmask[2][16] = {
{ 1,0,0,0,0,0,0,0, /* white is 1 when move is legal to piece in question */
0,1,1,1,1,1,1,0 /* black pieces are 8 + piece, so pawn = 1 ==> bpawn = 8+1 = 9 */
},
{ 1,1,1,1,1,1,1,0, /* black is 1 when move is legal */
0,0,0,0,0,0,0,0
}
};
lm = linkmask[side];
Yes, I would think if someone were interested in the Diep move generator, sending you an emaildiep wrote:Had you considered shipping me an e-mail?
