Reverse move generation

[oreopoulos]

I was searching for any code to do reverse move generation (before trying to do it on my own), but i found nothing.

I am not looking that for any engine. Just to create a simple chess tree, so the basic use is just for any position generate possible "parent" positions.

Can anyone point me in any direction?

[hgm]

It isn't really much different from normal non-capture generation. It is just that any move you generate could also be an 'uncapture', which leaves any of the opponent's captured pieces on the square you just evacuated, rather than leaving it empty.

For special moves 6th-rank Pawns can move diagonally to 5th rank if the square in front of them is empty, under creation of an opponent Pawn on the e.p. square, but then the next retro-move must push that created Pawn back two squares.

Uncastlings also need special treatment.

[oreopoulos]

First of all thx for your answer.

I "know" how to do it. I just think its a waste of time to re-invent the wheel , so any tested code will save a lot of time. The only think i will have to do is transfer the code to the language i will be writing the code to (probably javascript - nodejs).

There so many move generators out there, but not a single one doing retro stuff

[hgm]

Well, it is so trivial that porting it to another language / board representation would always be far more work than writing it from scratch.

[Sven]

There so many move generators out there, but not a single one doing retro stuff

Endgame tablebase generators are often using retro move generation.

[oreopoulos]

Endgame tablebase generators are often using retro move generation.

i havent seen any open source code tb generators.

[hgm]

Well, there is one on my website. ( http://home.hccnet.nl/h.g.muller/EGTB.html ) A more recent source is in the fairygen package ( http://hgm.nubati.net/fairygen.zip ). A more symplistic one (not making use of any symmetry, and therefore good for asymmetric pieces, and arbitrary board formats like 10x8) was never released, but will post it here. (It only does 3 vs 1 where none of the pieces can cause a mate on its own, but for the move generation that would not be relevant.)

Code: Select all

/***************************************************************************/
/* EGT generator to determine mating potential for 3 men vs bare King.     */
/*                                                                         */
/* The generator does not make any symmetry assumption.                    */
/* It uses some simplifications that would not work for a general-purpose  */
/* EGT generator:                                                          */
/* - Black has a bare royal piece, which is non-divergent, so that all its */
/*   moves can both go to empty and occupied (will be opponent!) squares.  */
/* - None of the white pieces has mating potential by itself, so that any  */
/*   capture of an unprotected piece automatically draws.                  */
/*                                                                         */
/*                                                  H.G. Muller, (c) 2011  */
/***************************************************************************/

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

typedef int int_ptr;

#define BWIDTH 8
#define BSIZE  BWIDTH*8
#define STRIDE3 BSIZE
#define STRIDE2 &#40;STRIDE3*BSIZE + BSIZE&#41;
#define STRIDE1 &#40;STRIDE2*BSIZE + BSIZE&#41;
#define b &#40;board + 2*BSIZE + BWIDTH&#41;
#define SEC &#40;1./CLOCKS_PER_SEC&#41;

/*
 *  Some macros to define often-used control constructs
 */

// loop through all moves of given piece. capts indicates which captures will be accepted

#define FOR_ALL_MOVES&#40;movelist, from, index, capts&#41; \
  &#123; int r, f;                                       \
    for&#40;r=movelist; f=flags&#91;r&#93;; r++) &#123;              \
      int v=steps&#91;r&#93;, to=from, nwind=index;         \
      while&#40;b&#91;to+=v&#93; <= capts&#41; &#123;                    \
        nwind += isteps&#91;r&#93;;                         \

#define NEXT_MOVE               \
        if&#40;b&#91;to&#93; || f&4&#41; break; \
      &#125;                         \
    &#125;                           \
  &#125;

// scan through tablebase and update 0x88 board in lockstep

#define SCAN&#40;p, index, start, stride&#41;                              \
  for&#40;nr&#91;p&#93;=0, index=start; nr&#91;p&#93;<BSIZE; nr&#91;p&#93;++, index+=stride&#41; &#123; \
    pos&#91;p&#93; = Ox88&#91;nr&#91;p&#93;&#93;;                                          \
    if&#40;b&#91;pos&#91;p&#93;&#93;) continue; /* skip broken positions */            \
    b&#91;pos&#91;p&#93;&#93; = p+1;

#define NEXT&#40;p&#41;    \
    b&#91;pos&#91;p&#93;&#93; = 0; \
  &#125;

/*
 *  Global variables&#58; board & piece-list, move-gen and auxiliary tables
 */

unsigned int Ox88&#91;BSIZE&#93;;             // raster-scan square nr to 0x88 square nr translation table
unsigned char board&#91;6*BSIZE + BWIDTH&#93;; // raw 0x88 board with generous guard band
int pos&#91;4&#93;; // piece locations on 0x88 board; piece 3 = black King, 2 = white King, 0 & 1 other white men
int nr&#91;4&#93;;  // piece locations as raster-scan number;
int first&#91;4&#93;, firstCapts&#91;4&#93;; // indicate first entry in move table for each piece.
int N, wcnt, todo;
unsigned char *EGT, *map;
signed char steps&#91;128&#93;, flags&#91;128&#93;;
int isteps&#91;128&#93;, cnt&#91;256&#93;, ptr;

// char array&#91;1500000000&#93;;

// sample piece descriptions&#58; &#40;mode, delta_x, delta_y&#41; triples, where mode 4=leaper, 2=non-capt, 1=capt
int king&#91;&#93;   = &#123;7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,1,0, 7,-1,0, 7,0,1, 7,0,-1, 0&#125;;
int knight&#91;&#93; = &#123;7,2,1, 7,2,-1, 7,-2,-1, 7,-2,1, 7,1,2, 7,-1,2, 7,1,-2, 7,-1,-2, 0&#125;;
int zebra&#91;&#93;  = &#123;7,2,3, 7,2,-3, 7,-2,-3, 7,-2,3, 7,3,2, 7,-3,2, 7,3,-2, 7,-3,-2, 0&#125;;
int camel&#91;&#93;  = &#123;7,3,1, 7,3,-1, 7,-3,-1, 7,-3,1, 7,1,3, 7,-1,3, 7,1,-3, 7,-1,-3, 0&#125;;
int bishop&#91;&#93; = &#123;3,1,1, 3,1,-1, 3,-1,-1, 3,-1,1, 0&#125;;
int wazir&#91;&#93;  = &#123;7,1,0, 7,-1,0, 7,0,1, 7,0,-1, 0&#125;;
int ferz&#91;&#93;   = &#123;7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 0&#125;;
int silver&#91;&#93; = &#123;7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,0,1, 0&#125;;
int copper&#91;&#93; = &#123;7,1,1, 7,-1,1, 7,0,1, 7,0,-1, 0&#125;;
int omni&#91;&#93;   = &#123;5,1,1, 5,1,-1, 5,-1,-1, 5,-1,1, 6,1,0, 6,-1,0, 6,0,1, 6,0,-1, 0&#125;;
int lang&#91;&#93;   = &#123;7,2,2, 7,2,-2, 7,-2,2, 7,-2,-2, 7,3,3, 7,3,-3, 7,-3,3, 7,-3,-3, 0&#125;;
int phoenix&#91;&#93;= &#123;7,1,0, 7,-1,0, 7,0,1, 7,0,-1, 7,2,2, 7,2,-2, 7,-2,2, 7,-2,-2, 0&#125;;
int alibaba&#91;&#93;= &#123;7,2,0, 7,-2,0, 7,0,2, 7,0,-2, 7,2,2, 7,2,-2, 7,-2,2, 7,-2,-2, 0&#125;;
int unicorn&#91;&#93;= &#123;7,1,0, 7,-1,0, 7,0,1, 7,0,-1, 7,2,1, 7,2,-1, 7,-2,-1, 7,-2,1, 7,1,2, 7,-1,2, 7,1,-2, 7,-1,-2, 0&#125;;
int elephant&#91;&#93; = &#123;7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,2,2, 7,2,-2, 7,-2,2, 7,-2,-2, 0&#125;;
int fibnif&#91;&#93;   = &#123;7,1,1, 7,1,-1, 7,-1,-1, 7,-1,1, 7,1,2, 7,-1,2, 7,1,-2, 7,-1,-2, 0&#125;;
int admiral&#91;&#93;= &#123;3,1,1, 3,1,-1, 3,-1,-1, 3,-1,1, 3,2,0, 3,0,2, 3,0,-2, 3,-2,0, 6,1,0, 6,-1,0, 6,0,1, 6,0,-1, 0&#125;;

/*
 *  Initialization stuff
 */

// routines to prepare move-gen tables from the piece descriptors.
// each piece has two tables; one used for retrograde moving &#40;so contains only non-captures&#41;,
// one for forward moving. Both the 0x88 board step and EGT index step are tabulated in each.
// To allow for asymmetric pieces, the retro table flips the sign, so it can be used with the same generator.
// The forward table is used for black king escapes, and for determining black-king locations that are
// attacked by the white pieces &#40;by generating captures of the latter on empty squares with black-king stride&#41;.

int Fill&#40;int sgn, int mode, int *desc, int stride&#41;
&#123;
  int i, res = ptr;
  for&#40;i=0; desc&#91;i&#93;; i+=3&#41; &#123;
    if&#40;!&#40;desc&#91;i&#93; & mode&#41;) continue; // skip directions we cannot capture in;
    steps&#91;ptr&#93; = sgn*&#40;2*BWIDTH*desc&#91;i+1&#93; + desc&#91;i+2&#93;);
    isteps&#91;ptr&#93; = sgn*&#40;BWIDTH*desc&#91;i+1&#93; + desc&#91;i+2&#93;)*stride;
    flags&#91;ptr++&#93; = desc&#91;i&#93;;
  &#125;
  flags&#91;ptr++&#93; = 0;
  return res;
&#125;

int AddPiece&#40;int nr, signed int *desc, int stride&#41;
&#123;
  first&#91;nr&#93;      = Fill&#40;-1, 2, desc, stride&#41;; // unmoves, so flip sign, and non-capts only
  firstCapts&#91;nr&#93; = Fill&#40; 1, 1, desc, 1&#41;;      // captures only
&#125;

static Init&#40;int *desc1, int *desc2, int *desc3, int *desc4, void *mem&#41;
&#123;
  int i, j;

  // create empty 0x88 board with large guard band
  for&#40;i=0; i<6*BSIZE+BWIDTH; i++) board&#91;i&#93; = 5; // guards
  for&#40;i=0; i<BSIZE; i++) b&#91;Ox88&#91;i&#93; = &#40;i/BWIDTH&#41;*BWIDTH + i&#93; = 0;
  for&#40;i=0; i<256; i++) cnt&#91;i&#93; = 0; // reset stats

  // load move-generator tables
  AddPiece&#40;0, desc1, STRIDE1&#41;; // N
  AddPiece&#40;1, desc2, STRIDE2&#41;; // B
  AddPiece&#40;2, desc3, STRIDE3&#41;; // K
  AddPiece&#40;3, desc4, 1&#41;;       // K

  // allocate and cache-align main storage
  EGT = &#40;unsigned char*) mem;
  if&#40;!EGT&#41;
    EGT = &#40;unsigned char*) (&#40;int_ptr&#41;malloc&#40;j = BSIZE*STRIDE1+64&#41; + 63 & ~&#40;int_ptr&#41;63&#41;;
  printf&#40;"allocate %d bytes at %x\n", j, &#40;int&#41; EGT&#41;;
&#125;

/*
 *  routines for retrograde generation through 3-ply tree &#40;2 unmoves followed by 1 move&#41;
 */


static int Escape&#40;int sq, int index&#41;
&#123; // try black King moves &#40;assumed to be valid as both capts and non-capts!)
  FOR_ALL_MOVES&#40;firstCapts&#91;3&#93;, sq, index, 3&#41;
    if&#40;!&#40;EGT&#91;nwind&#93; & 1&#41;) return 1;
  NEXT_MOVE
  return 0;
&#125;

static void RetroBlack&#40;int index, int kpos&#41;
&#123;
  // don't bother to move black king; the move it blocks on verify went to the now won position
  FOR_ALL_MOVES&#40;first&#91;3&#93;, kpos, index, 0&#41;
    if&#40;!Escape&#40;to, nwind&#41;) &#123;
      EGT&#91;nwind&#93; |= N+2;
      cnt&#91;N+2&#93;++; todo += 3; // takes 3 visits to treat!
    &#125;
  NEXT_MOVE
&#125;

static void RetroWhite&#40;int p, int index, int kpos&#41;
&#123;
  b&#91;kpos&#93; = 4;   // place black King on board to prevent white unmoving to broken position
  b&#91;pos&#91;p&#93;&#93; = 0; // start making white unmove by removing piece from 0x88 board
  FOR_ALL_MOVES&#40;first&#91;p&#93;, pos&#91;p&#93;, index, 0&#41;
    if&#40;!&#40;EGT&#91;nwind&#93; & 1&#41;) &#123;    // parent was not yet marked as won
      EGT&#91;nwind&#93; |= 1;         // mark it
      b&#91;to&#93; = p+1;             // complete white unmove on 0x88 board
      RetroBlack&#40;nwind, kpos&#41;; // check if this closes last escape of parents &#40;making them lost&#41;
      b&#91;to&#93; = 0;
      cnt&#91;N+1&#93;++;
    &#125;
  NEXT_MOVE
  b&#91;pos&#91;p&#93;&#93; = p+1;
  b&#91;kpos&#93; = 0;
  todo--;
&#125;

static void IterStart31&#40;)
&#123;
  int i1, i2, i3, k, p;
  SCAN&#40;1, i1, 0, STRIDE2&#41;
    SCAN&#40;2, i2, i1, STRIDE3&#41;
      SCAN&#40;0, i3, i2, STRIDE1&#41;
        // at this point the board goes through all white constellations,
        // while i3 is the corresponding white contribution to the index

        // mark checks in current black chunk, by making all possible white capture steps
        for&#40;p=0; p<3; p++) &#123;
          FOR_ALL_MOVES&#40;firstCapts&#91;p&#93;, pos&#91;p&#93;, i3+nr&#91;p&#93;, 2&#41; // allow capt of own piece 0 & 1 and non-capts
            cnt&#91;1&#93; += !b&#91;to&#93; & !EGT&#91;nwind&#93;; // do not count broken or doubles
            EGT&#91;nwind&#93; = 1;
          NEXT_MOVE
        &#125;
        // label checkmates in the chunk where we just marked all captures
        for&#40;k=0; k<BSIZE; k++) &#123; // when not in check, or broken position, no testing needed
          if&#40;EGT&#91;i3+k&#93; && !b&#91;Ox88&#91;k&#93;&#93; && !Escape&#40;Ox88&#91;k&#93;, i3+k&#41; ) EGT&#91;i3+k&#93; = 3, cnt&#91;2&#93;++, todo += 3;
        &#125;
      NEXT&#40;0&#41;
    NEXT&#40;2&#41;
  NEXT&#40;1&#41;
&#125;

void *Build31&#40;desc1, desc2, desc3, desc4, verbose, mem&#41;
int *desc1, *desc2, *desc3, *desc4; // piece descriptions
int verbose; // flag to enable printing
void *mem;   // memory area to build EGT in &#40;if NULL the memory is allocated&#41;
// returns start of end-game table &#40;which can be different from mem, because of alignment to cache-line boundaries&#41;
&#123;
  int i1, i2, i3, k, p;
  clock_t t;

  Init&#40;desc1, desc2, desc3, desc4, mem&#41;; // initialize auxiliary tables
  if&#40;!EGT&#41; return &#40;void*) EGT;           // allocation failed, abort

  N=2;         // double of iteration count
  todo = 0; t = clock&#40;);
  IterStart31&#40;); // detrmine checkmates, first half &#40;piece-0 moves&#41; of iteration 1

  if&#40;verbose&#41; printf&#40;"        mated    mate\nKing captures %d\nmates %7d         (%5.2f sec&#41;\n",
                       cnt&#91;1&#93;, cnt&#91;2&#93;, &#40;clock&#40;)-t&#41;*SEC&#41;;
  while&#40;todo&#41; &#123; // plain iteration; cache unfriendly!

    // treat unmoves of white pieces 1 and 2 &#40;plus black unmoves & verification&#41;, two iterations
    SCAN&#40;0, i1, 0, STRIDE1&#41;
      SCAN&#40;1, i2, i1, STRIDE2&#41;
        SCAN&#40;2, i3, i2, STRIDE3&#41;
          for&#40;k=0; k<BSIZE; k++)
            if&#40;&#40;EGT&#91;i3+k&#93; & ~1&#41; == N&#41; /* broken won't ever match! */
              for&#40;p=0; p<3; p++) RetroWhite&#40;p, i3+k, Ox88&#91;k&#93;);
        NEXT&#40;2&#41;
      NEXT&#40;1&#41;
    NEXT&#40;0&#41;

    if&#40;verbose&#41; printf&#40;"in-%-2d %7d %7d (%5.2f sec&#41;\n", N/2, cnt&#91;N+2&#93;, cnt&#91;N+1&#93;, &#40;clock&#40;)-t&#41;*SEC&#41;;
    N += 2;
    if&#40;N>253&#41; break;
  &#125;
  return &#40;void*) EGT;
&#125;

PrintStats&#40;)
&#123;
  int i, wtot=0, btot=0, wsum=0, bsum=0;
  double tot;
  tot = BSIZE;
  tot = 100./&#40;tot*&#40;tot-1&#41;*&#40;tot-2&#41;*&#40;tot-3&#41;);
  for&#40;i=0; i<254; i+=2&#41; wtot+=cnt&#91;i+1&#93;, btot+=cnt&#91;i+2&#93;, wsum+=i*cnt&#91;i+1&#93;, bsum+=i*cnt&#91;i+2&#93;;
  printf&#40;"won&#58;  %9d (%5.1f%%)\nlost&#58; %9d (%5.1f%%)\navg&#58;  %9.1f moves\n",
          wtot, wtot*tot, btot, btot*tot, bsum*0.5/btot&#41;;
&#125;

main&#40;)
&#123;
  Build31&#40;knight, bishop, king, king, 1, NULL&#41;; // NBKK
  PrintStats&#40;);
&#125;

[kbhearn]

robbobases or syzygy off the top of my head have publicly available generators.

[oreopoulos]

Thx a lot!!!

Its very kind of you

[sje]

Back in 1994 when I was doing the tablebases, I wrote a retrograde move generator; however, it did not handle en passant or castling moves.

The code is very much like a prograde (regular) move generator, except that it takes an extra parameter: the chessman (if any) to be uncaptured. Also, pawns move backward and pieces can reverse promote.

It may be easier to write a retrograde generator from scratch than to adapt one from existing code.