Move Tables - explain as if I'm five.

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Sven
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Move Tables - explain as if I'm five.

Post by Sven » Mon Nov 05, 2012 11:08 am

Sven Schüle wrote:
ZirconiumX wrote:Any help would be appreciated.
Fix your directions. If NW is +7 (which is +8-1) then SW must be -9 (-8-1) and W must be -1, and so on. I think your init code has that wrong.

EDIT: The following "canonical" definitions might help to avoid this type of bugs:

Code: Select all

int const JumpN  = +8;
int const JumpE  = +1;
int const JumpS  = -JumpN;
int const JumpW  = -JumpE;
int const JumpNW = JumpN+JumpW;
int const JumpNE = JumpN+JumpE;
int const JumpSW = JumpS+JumpW;
int const JumpSE = JumpS+JumpE;
plus always using these constants instead of the hard-coded integers, of course.

Sven
Second problem: your loop conditions.

Code: Select all

      k = j + 7;
      while &#40;k < 64 && k >= 0 && &#40;k&7&#41; != 7&#41; &#123;
(where "!= 7" should be "!= 0" after fixing the directions issue mentioned before) will fail if the square "j" is on file A and "j + 7" has already left the board. Same for all other directions, the above is only the NW example.

EDIT: an additional "if ((k&7) != 0) { ... }" around both the "k = j + 7" and the loop might help.

EDIT2: Still not sure about the loop condition, what happens when you start at j=2 (C1), first you set k=2+7 (B2), then you loop once, then you set k=9+7 (A3) and now the loop stops since "(k&7) != 0" is false, so you do not process A3.


Third problem: handling of your "move_dirs" array. What is the intended meaning of the following?

Code: Select all

move_dirs&#91;NW&#93;&#91;i&#93; = i;
In the loop prior to that statement you use "move_dirs[NW][j]" and "j" is a square number. However, here you use "i" as second array index which is a counter. Seems wrong to me. Same for all other directions as well.

Sven

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Move Tables - explain as if I'm five.

Post by ZirconiumX » Mon Nov 05, 2012 12:51 pm

Sven Schüle, bug finder extraordinaire.

I quickly skimmed your bug list, and mixing in my own issues, I get this:
  • My table generator is slow.
  • It's buggy.
  • It's incorrect.
  • It won't compile.
  • It's hard to read.
  • It needs to be ran twice.
Basically, I need to scrap it and try again.

From what I could make out of Vincent's post, and Gerd's additions, I need to use a 16x16 vector attacks array (for ease of check detection, etc.), an index-based move table (may not be fastest, but it works), a piece list, and a quickboard.

A linked list will not compile for me, but my index-based code will.

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

Sven
Posts: 3826
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Move Tables - explain as if I'm five.

Post by Sven » Mon Nov 05, 2012 2:33 pm

See my inline comments below starting with "=>".
ZirconiumX wrote:
  • My table generator is slow.
    => Not an issue since it only runs at program startup time.
  • It's buggy.
  • It's incorrect.
    => Both can be fixed.
  • It won't compile.
    => That can be fixed, too.
  • It's hard to read.
    => Choose better variable names instead of i, j, k etc., and if you like, try to write one loop instead of eight loops. At least the choice of identifiers already has good potential to increase readability.
  • It needs to be ran twice.
    => Can you explain why? I don't understand that last point.
ZirconiumX wrote:Basically, I need to scrap it and try again.
Whether the second attempt would be successful will also depend on how much you learn from the first attempt. At least I doubt it will if you don't fix the bugs in the first version.

Sven

ZirconiumX
Posts: 1327
Joined: Sun Jul 17, 2011 9:14 am

Re: Move Tables - explain as if I'm five.

Post by ZirconiumX » Mon Nov 05, 2012 4:37 pm

Sven Schüle wrote:See my inline comments below starting with "=>".
ZirconiumX wrote:
  • My table generator is slow.
    => Not an issue since it only runs at program startup time.
    --- I'd like it to be quicker though.
  • It's buggy.
  • It's incorrect.
    => Both can be fixed.
    --- I'd much rather use an elegant initialization routine than one that has loads of obvious holes fixed.
  • It won't compile.
    => That can be fixed, too.
    --- The init code is a nightmare to write - can you think of a better way to make a pointer than casting?
  • It's hard to read.
    => Choose better variable names instead of i, j, k etc., and if you like, try to write one loop instead of eight loops. At least the choice of identifiers already has good potential to increase readability.
    --- I'm unhappy with it anyway, I like to stick to the KISS principle when writing code, and 8 seperate loops looks ugly to my eyes.
  • It needs to be ran twice.
    => Can you explain why? I don't understand that last point.
    --- If you note, the move_dirs array is initialized on the fly. Once it is initialized, the generator needs to re-insert the correct positions in the move table
ZirconiumX wrote:Basically, I need to scrap it and try again.
Whether the second attempt would be successful will also depend on how much you learn from the first attempt. At least I doubt it will if you don't fix the bugs in the first version.
--- Well, keep doubting. I'll find a way through the bugs anyway.


Sven
Inline responses to inline responses.

Matthew:out
Some believe in the almighty dollar.

I believe in the almighty printf statement.

Karlo Bala
Posts: 301
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Move Tables - explain as if I'm five.

Post by Karlo Bala » Mon Nov 05, 2012 6:56 pm

mar wrote:Hi Matthew,

Not sure whether it helps, I believe the table idea comes from old GNUChess, some scandinavian guy (I think - don't remember) described it as he wanted to build a hardware movegenerator.
The (naive) idea behind it (as I understand it - [shameless plug] I implemented it in Heretic - an experimental engine to play Capablanca chess), is that you have a table for each piece type.
You store indices to next square to examine, for sliders you also store index to skip to the next ray.
So whenever you encounter a blocked square you either generate a capture and skip or ignore it and skip (or use next for non-sliders). For empty square you simply go to next square in chain.
In case you would be interested, the actual implementation (tables.cpp and tables.h) is here: http://www.mediafire.com/download.php?ohxab35ckj84dsy (no guarantee that the implementation is very clean and readable)
I'm sure Vincent came up with something much better though.
Hope it helps.

Martin
Back then it was a real invention.
This file contains a description of GNU's new move generation algoritm.
Copyright (C) 1989 Free Software Foundation, Inc.

This file is part of CHESS.

CHESS is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY. No author or distributor accepts responsibility to anyone for the consequences of using it or for whether it serves any particular purpose or works at all, unless he says so in writing. Refer to the CHESS General Public License for full details.

Everyone is granted permission to copy, modify and redistribute CHESS, but only under the conditions described in the CHESS General Public License. A copy of this license is supposed to have been given to you along with CHESS so you can know your rights and responsibilities. It should be in a file named COPYING. Among other things, the copyright notice and this notice must be preserved on all copies.

New move Generation algoritm:

Revision: 1989-09-06

Author: Hans Eric Sandstroem.

This algortim 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 gnuchess. 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 rescources to build a hardware move generator I will be glad to assist.

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 == neutral) {
LinkMove(ply,sq,u,xside);
u = p.nextpos;
}
else {
if (color == xside) LinkMove(ply,sq,u,xside);
u = p.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.


Initialisation:

/*
C source for GNU CHESS

Revision: 1990-09-30

Modified by Daryl Baker for use in MS WINDOWS environment

Copyright (C) 1986, 1987, 1988, 1989, 1990 Free Software Foundation, Inc.
Copyright (c) 1988, 1989, 1990 John Stanback

This file is part of CHESS.

CHESS is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY. No author or distributor accepts responsibility to anyone for
the consequences of using it or for whether it serves any particular
purpose or works at all, unless he says so in writing. Refer to the CHESS
General Public License for full details.

Everyone is granted permission to copy, modify and redistribute CHESS, but
only under the conditions described in the CHESS General Public License.
A copy of this license is supposed to have been given to you along with
CHESS so you can know your rights and responsibilities. It should be in a
file named COPYING. Among other things, the copyright notice and this
notice must be preserved on all copies.
*/

#define NOATOM
#define NOCLIPBOARD
#define NOCREATESTRUCT
#define NOFONT
#define NOREGION
#define NOSOUND
#define NOWH
#define NOWINOFFSETS
#define NOCOMM
#define NOKANJI

#include <windows.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#include "gnuchess.h"
#include "defs.h"

extern HWND hStats;

/*extern short distdata[64][64], taxidata[64][64];*/
extern short far *distdata, far *taxidata;

extern FILE *hashfile;
extern short stage, stage2, Developed[2];
extern short ChkFlag[maxdepth], CptrFlag[maxdepth], PawnThreat[maxdepth];
extern short Pscore[maxdepth], Tscore[maxdepth];
extern short rehash;

/* extern struct hashval hashcode[2][7][64]; */
extern struct hashval far *hashcode;
extern unsigned char far * history;

void
Initialize_dist (void)
{
register short a, b, d, di;

for (a = 0; a < 64; a++)
for (b = 0; b < 64; b++)
{
d = abs (column (a) - column (b));
di = abs (row (a) - row (b));
/*
taxidata[a] = d + di;
distdata[a] = (d > di ? d : di);
*/
*(taxidata+a*64+b) = d + di;
*(distdata+a*64+b) = (d > di ? d : di);

}
}

static short _based(_segname("_CODE")) Stboard[64] =
{rook, knight, bishop, queen, king, bishop, knight, rook,
pawn, pawn, pawn, pawn, pawn, pawn, pawn, pawn,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
pawn, pawn, pawn, pawn, pawn, pawn, pawn, pawn,
rook, knight, bishop, queen, king, bishop, knight, rook};

static short _based(_segname("_CODE")) Stcolor[64] =
{white, white, white, white, white, white, white, white,
white, white, white, white, white, white, white, white,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
black, black, black, black, black, black, black, black,
black, black, black, black, black, black, black, black};

extern short board[64], color[64];

/*extern unsigned char nextpos[8][64][64];*/
/*extern unsigned char nextdir[8][64][64];*/
extern unsigned char far * nextpos;
extern unsigned char far * nextdir;
/*
ptype is used to separate white and black pawns, like this;
ptyp = ptype[side][piece]
piece can be used directly in nextpos/nextdir when generating moves
for pieces that are not black pawns.
*/
static short _based(_segname("_CODE")) ptype[2][8] =
{
no_piece, pawn, knight, bishop, rook, queen, king, no_piece,
no_piece, bpawn, knight, bishop, rook, queen, king, no_piece};

static short _based(_segname("_CODE")) direc[8][8] =
{
0, 0, 0, 0, 0, 0, 0, 0,
10, 9, 11, 0, 0, 0, 0, 0,
8, -8, 12, -12, 19, -19, 21, -21,
9, 11, -9, -11, 0, 0, 0, 0,
1, 10, -1, -10, 0, 0, 0, 0,
1, 10, -1, -10, 9, 11, -9, -11,
1, 10, -1, -10, 9, 11, -9, -11,
-10, -9, -11, 0, 0, 0, 0, 0};

static short _based(_segname("_CODE")) max_steps[8] =
{0, 2, 1, 7, 7, 7, 1, 2};

static short _based(_segname("_CODE")) nunmap[120] =
{
-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, 8, 9, 10, 11, 12, 13, 14, 15, -1,
-1, 16, 17, 18, 19, 20, 21, 22, 23, -1,
-1, 24, 25, 26, 27, 28, 29, 30, 31, -1,
-1, 32, 33, 34, 35, 36, 37, 38, 39, -1,
-1, 40, 41, 42, 43, 44, 45, 46, 47, -1,
-1, 48, 49, 50, 51, 52, 53, 54, 55, -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};


void
Initialize_moves (void)

/*
This procedure pre-calculates all moves for every piece from every square.
This data is stored in nextpos/nextdir and used later in the move generation
routines.
*/

{
short ptyp, po, p0, d, di, s, delta;
unsigned char far *ppos, far *pdir;
short dest[8][8];
short steps[8];
short sorted[8];

for (ptyp = 0; ptyp < 8; ptyp++)
for (po = 0; po < 64; po++)
for (p0 = 0; p0 < 64; p0++)
{
*(nextpos+ptyp*64*64+po*64+p0) = (unsigned char) po;
*(nextdir+ptyp*64*64+po*64+p0) = (unsigned char) po;
}
for (ptyp = 1; ptyp < 8; ptyp++)
for (po = 21; po < 99; po++)
if (nunmap[po] >= 0)
{
ppos = nextpos+ptyp*64*64+nunmap[po]*64;
pdir = nextdir+ptyp*64*64+nunmap[po]*64;
/* dest is a function of direction and steps */
for (d = 0; d < 8; d++)
{
dest[d][0] = nunmap[po];
delta = direc[ptyp][d];
if (delta != 0)
{
p0 = po;
for (s = 0; s < max_steps[ptyp]; s++)
{
p0 = p0 + delta;
/*
break if (off board) or
(pawns only move two steps from home square)
*/
if (nunmap[p0] < 0 || (ptyp == pawn || ptyp == bpawn)
&& s > 0 && (d > 0 || Stboard[nunmap[po]] != pawn))
break;
else
dest[d][s] = nunmap[p0];
}
}
else
s = 0;

/*
sort dest in number of steps order
currently no sort is done due to compability with
the move generation order in old gnu chess
*/
steps[d] = s;
for (di = d; s > 0 && di > 0; di--)
if (steps[sorted[di - 1]] == 0) /* should be: < s */
sorted[di] = sorted[di - 1];
else
break;
sorted[di] = d;
}

/*
update nextpos/nextdir,
pawns have two threads (capture and no capture)
*/
p0 = nunmap[po];
if (ptyp == pawn || ptyp == bpawn)
{
for (s = 0; s < steps[0]; s++)
{
ppos[p0] = (unsigned char) dest[0][s];
p0 = dest[0][s];
}
p0 = nunmap[po];
for (d = 1; d < 3; d++)
{
pdir[p0] = (unsigned char) dest[d][0];
p0 = dest[d][0];
}
}
else
{
pdir[p0] = (unsigned char) dest[sorted[0]][0];
for (d = 0; d < 8; d++)
for (s = 0; s < steps[sorted[d]]; s++)
{
ppos[p0] = (unsigned char) dest[sorted[d]][s];
p0 = dest[sorted[d]][s];
if (d < 7)
pdir[p0] = (unsigned char) dest[sorted[d + 1]][0];
/* else is already initialized */
}
}
}
}
Best Regards,
Karlo Balla Jr.

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Move Tables - explain as if I'm five.

Post by Gerd Isenberg » Mon Nov 05, 2012 7:38 pm

Karlo Bala wrote: Back then it was a real invention.
New move Generation algoritm:
Revision: 1989-09-06
Author: Hans Eric Sandstroem.

This algortim 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 gnuchess. 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 rescources to build a hardware move generator I will be glad to assist.

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:
snip
C source for GNU CHESS
Revision: 1990-09-30
Copyright (c) 1988, 1989, 1990 John Stanback
Thanks for sharing. For some reason I thought the table driven move-generator was contributed to John Stanback. It was invented by Hans Eric Sandström, interesting.

Karlo Bala
Posts: 301
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Move Tables - explain as if I'm five.

Post by Karlo Bala » Mon Nov 05, 2012 9:42 pm

Gerd Isenberg wrote:
Thanks for sharing. For some reason I thought the table driven move-generator was contributed to John Stanback. It was invented by Hans Eric Sandström, interesting.
On "Tim Mann's Chess Pages", people can find all old versions of gnuchess. http://www.tim-mann.org/gnuchess.html
Best Regards,
Karlo Balla Jr.

Karlo Bala
Posts: 301
Joined: Wed Mar 22, 2006 9:17 am
Location: Novi Sad, Serbia

Re: Move Tables - explain as if I'm five.

Post by Karlo Bala » Mon Nov 05, 2012 9:52 pm

Gerd Isenberg wrote:
Thanks for sharing. For some reason I thought the table driven move-generator was contributed to John Stanback. It was invented by Hans Eric Sandström, interesting.
Another interesting thing was repetition detection. Does anybody know how it works?

Code: Select all

inline void
repetition &#40;short int *cnt&#41;

/*
  Check for draw by threefold repetition.
*/

&#123;
  short i, c, f, t;
  short b&#91;64&#93;;
  unsigned short m;

  *cnt = c = 0;
  if &#40;GameCnt > Game50 + 3&#41;
    &#123;
#ifdef NOMEMSET
      for &#40;i = 0; i < 64; b&#91;i++&#93; = 0&#41; ;
#else
      memset (&#40;char *) b, 0, sizeof &#40;b&#41;);
#endif /* NOMEMSET */
      for &#40;i = GameCnt; i > Game50; i--)
        &#123;
          m = GameList&#91;i&#93;.gmove;
          f = m >> 8;
          t = m & 0xFF;
          if (++b&#91;f&#93; == 0&#41;
            c--;
          else
            c++;
          if (--b&#91;t&#93; == 0&#41;
            c--;
          else
            c++;
          if &#40;c == 0&#41;
            (*cnt&#41;++;
        &#125;
    &#125;
&#125;

Best Regards,
Karlo Balla Jr.

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Move Tables - explain as if I'm five.

Post by Gerd Isenberg » Tue Nov 06, 2012 7:27 am

Karlo Bala wrote:
Gerd Isenberg wrote:
Thanks for sharing. For some reason I thought the table driven move-generator was contributed to John Stanback. It was invented by Hans Eric Sandström, interesting.
Another interesting thing was repetition detection. Does anybody know how it works?

Code: Select all

inline void
repetition &#40;short int *cnt&#41;

/*
  Check for draw by threefold repetition.
*/

&#123;
  short i, c, f, t;
  short b&#91;64&#93;;
  unsigned short m;

  *cnt = c = 0;
  if &#40;GameCnt > Game50 + 3&#41;
    &#123;
#ifdef NOMEMSET
      for &#40;i = 0; i < 64; b&#91;i++&#93; = 0&#41; ;
#else
      memset (&#40;char *) b, 0, sizeof &#40;b&#41;);
#endif /* NOMEMSET */
      for &#40;i = GameCnt; i > Game50; i--)
        &#123;
          m = GameList&#91;i&#93;.gmove;
          f = m >> 8;
          t = m & 0xFF;
          if (++b&#91;f&#93; == 0&#41;
            c--;
          else
            c++;
          if (--b&#91;t&#93; == 0&#41;
            c--;
          else
            c++;
          if &#40;c == 0&#41;
            (*cnt&#41;++;
        &#125;
    &#125;
&#125;

Nice! A counter array for 64 squares (b) initialized with zero. As long there are reversible moves along the game recored, from-coordinates increment its counter[sq], to-coordinates decrement counter[sq]. An accumulated counter is decremented each time a from-counter becomes zero, incremented otherwise, and vice versa for the to-square. Each time the accumulated counter becomes zero, that is all square counters are balanced, a repetition of moves is detected. A similar approach with a chain-list instead of a byte 64 array was proposed by Vladan Vu&#269;kovi&#263; and &#272;or&#273;e Vidanovi&#263; in 2004. These approaches do not consider all repetitions of positions, i.e. where two rooks of each side exchange their places.

User avatar
hgm
Posts: 23713
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Move Tables - explain as if I'm five.

Post by hgm » Tue Nov 06, 2012 8:34 am

Just the opposite, right? They do detect false repetitions when you exchange two unequal pieces, as they only consider square occupancy, and thus implicitly consider all pieces equal. This could be fixed by not incrementing the square counters by 1, but by a piece-type-dependent number. This would require storing of the piece type in the move list, however.

Post Reply