Valid CRC / Chess960 Position generator

[Reinhard Scharnagl]

Hi Chess960 and CRC fans,

here I publish my reference implementation of generating valid positions:

Regards, Reinhard.

Result of the included test program:

first Chess960 positions
(001) bqnbnrkr/pppppppp/8/8/8/8/PPPPPPPP/BQNBNRKR w KQkq - 0 1
(002) bqnnrbkr/pppppppp/8/8/8/8/PPPPPPPP/BQNNRBKR w KQkq - 0 1
(003) bqnnrkrb/pppppppp/8/8/8/8/PPPPPPPP/BQNNRKRB w KQkq - 0 1
(004) qbbnnrkr/pppppppp/8/8/8/8/PPPPPPPP/QBBNNRKR w KQkq - 0 1
(005) qnbbnrkr/pppppppp/8/8/8/8/PPPPPPPP/QNBBNRKR w KQkq - 0 1
(006) qnbnrbkr/pppppppp/8/8/8/8/PPPPPPPP/QNBNRBKR w KQkq - 0 1
(007) qnbnrkrb/pppppppp/8/8/8/8/PPPPPPPP/QNBNRKRB w KQkq - 0 1
(008) qbnnbrkr/pppppppp/8/8/8/8/PPPPPPPP/QBNNBRKR w KQkq - 0 1
(009) qnnbbrkr/pppppppp/8/8/8/8/PPPPPPPP/QNNBBRKR w KQkq - 0 1
(010) qnnrbbkr/pppppppp/8/8/8/8/PPPPPPPP/QNNRBBKR w KQkq - 0 1

first CRC positions
(00001 --) aqbbcnnrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/AQBBCNNRKR w KQkq - 0 1
(00002 ok) qbbacnnrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/QBBACNNRKR w KQkq - 0 1
(00003 --) abbqcnnrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/ABBQCNNRKR w KQkq - 0 1
(00004 ok) qbbcnanrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/QBBCNANRKR w KQkq - 0 1
(00005 ok) abbcnqnrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/ABBCNQNRKR w KQkq - 0 1
(00006 --) qbbcnnrakr/pppppppppp/10/10/10/10/PPPPPPPPPP/QBBCNNRAKR w KQkq - 0 1
(00007 --) abbcnnrqkr/pppppppppp/10/10/10/10/PPPPPPPPPP/ABBCNNRQKR w KQkq - 0 1
(00008 --) qbbcnnrkra/pppppppppp/10/10/10/10/PPPPPPPPPP/QBBCNNRKRA w KQkq - 0 1
(00009 --) abbcnnrkrq/pppppppppp/10/10/10/10/PPPPPPPPPP/ABBCNNRKRQ w KQkq - 0 1
(00010 --) baqbcnnrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BAQBCNNRKR w KQkq - 0 1
(00011 --) bqabcnnrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BQABCNNRKR w KQkq - 0 1
(00012 ok) bbqacnnrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BBQACNNRKR w KQkq - 0 1
(00013 --) bbaqcnnrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BBAQCNNRKR w KQkq - 0 1
(00014 ok) bbqcnanrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BBQCNANRKR w KQkq - 0 1
(00015 ok) bbacnqnrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BBACNQNRKR w KQkq - 0 1
(00016 --) bbqcnnrakr/pppppppppp/10/10/10/10/PPPPPPPPPP/BBQCNNRAKR w KQkq - 0 1
(00017 ok) bbacnnrqkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BBACNNRQKR w KQkq - 0 1
(00018 --) bbqcnnrkra/pppppppppp/10/10/10/10/PPPPPPPPPP/BBQCNNRKRA w KQkq - 0 1
(00019 ok) bbacnnrkrq/pppppppppp/10/10/10/10/PPPPPPPPPP/BBACNNRKRQ w KQkq - 0 1
(00020 --) bacbqnnrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BACBQNNRKR w KQkq - 0 1
(00021 ok) bqcbannrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BQCBANNRKR w KQkq - 0 1
(00022 --) bbcaqnnrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BBCAQNNRKR w KQkq - 0 1
(00023 ok) bbcqannrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BBCQANNRKR w KQkq - 0 1
(00024 ok) bbcnqanrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BBCNQANRKR w KQkq - 0 1
(00025 ok) bbcnaqnrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BBCNAQNRKR w KQkq - 0 1
(00026 ok) bbcnqnrakr/pppppppppp/10/10/10/10/PPPPPPPPPP/BBCNQNRAKR w KQkq - 0 1
(00027 ok) bbcnanrqkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BBCNANRQKR w KQkq - 0 1
(00028 --) bbcnqnrkra/pppppppppp/10/10/10/10/PPPPPPPPPP/BBCNQNRKRA w KQkq - 0 1
(00029 ok) bbcnanrkrq/pppppppppp/10/10/10/10/PPPPPPPPPP/BBCNANRKRQ w KQkq - 0 1
(00030 ok) bacbnnqrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BACBNNQRKR w KQkq - 0 1
(00031 ok) bqcbnnarkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BQCBNNARKR w KQkq - 0 1
(00032 ok) bbcannqrkr/pppppppppp/10/10/10/10/PPPPPPPPPP/BBCANNQRKR w KQkq - 0 1

21821 valid CRC arrays

Reference implementation:

Code: Select all

//========================================
// Valid CRC / Chess960 Position generator
//========================================
// Reference Implementation, (C) 2005 by
// Reinhard Scharnagl, Munich, Germany
//----------------------------------------
// Correction 2005-Feb-28 (GC-Nearness)
//========================================

#include < string.h>
#include < stdio.h>

#define TXT_LIM 160

static char FenZone[TXT_LIM];

// insert a symbol into FEN-String
// -------------------------------
// color could be:
// col <  0 => not specified
// col == 0 => bright square
// col == 1 => dark square
void PlaceIntoFEN
  (int cntFree, char symbol, int fieldColor)
{
  for (int pos = 0, free = 0; ; ++pos) {
    if (fieldColor < 0 || ((fieldColor ^ pos) & 1)) {
      if (!FenZone[pos] && cntFree == free++) {
        FenZone[pos] = symbol;
        break;
      }
    }
  }
}

// generating of FEN strings
// -------------------------
// nr could be
// nr >= 0 creating Chess960 position (1 ... 960)
// nr <  0 creating CRC position    (1 ... 48000)
const char *GetFen(int nr)
{
  // knight distributions over 5 free squares
  static const int knight_pos[10] = {
     3, // xx--- (binary encoded)
     5, // x-x--
     9, // x--x-
    17, // x---x
     6, // -xx--
    10, // -x-x-
    18, // -x--x
    12, // --xx-
    20, // --x-x
    24  // ---xx
  };

  // clear the working area
  int bit, pos = TXT_LIM;
  while (--pos >= 0) { FenZone[pos] = '\0'; }

  // test whether CRC is requested
  bool isCRC = (nr <= 0);

  if (isCRC) {
    nr = -nr;
    bool q_first = ((nr % 2) != 0);
    nr /= 2;
    PlaceIntoFEN(nr % 5, q_first ? 'q' : 'a', 0);
    nr /= 5;
    PlaceIntoFEN(nr % 5, q_first ? 'a' : 'q', 1);
    nr /= 5;
  }

  PlaceIntoFEN(nr % 4, 'b', 0);
  nr /= 4;
  PlaceIntoFEN(nr % 4, 'b', 1);
  nr /= 4;
  PlaceIntoFEN(nr % 6, isCRC ? 'c' : 'q', -1);
  nr /= 6;
  pos = knight_pos[nr % 10];
  for (bit = 5; --bit >= 0; ) {
    if ((pos & (1 << bit)) != 0)
      PlaceIntoFEN(bit, 'n', -1);
  }

  PlaceIntoFEN(2, 'r', -1);
  PlaceIntoFEN(1, 'k', -1);
  PlaceIntoFEN(0, 'r', -1);

  int width = isCRC ? 10 : 8;
  char *pC = &FenZone[width];
  *pC++ = '/';
  for (pos = width; --pos >= 0; ) {
    *pC++ = 'p';
  }
  for (pos = 4; --pos >= 0; ) {
    *pC++ = '/';
    if (width >= 10) {
      *pC++ = '1';
    }
    *pC++ = (char)('0' + width % 10);
  }
  *pC++ = '/';
  for (pos = width; --pos >= 0; ) {
    *pC++ = 'P';
  }
  *pC++ = '/';
  for (pos = 0; pos < width; ++pos) {
    *pC++ = FenZone[pos] ^ ('a'^'A');
  }
  strcpy(pC, " w KQkq - 0 1");

  return FenZone;
}

// check if FEN is valid for CRC
// -----------------------------
bool IsValidCRC(const char *pFen)
{
  // to be avoided GC position
  static const char *gcArray = "rnbqckabnr";
  // pawn covering pieces (like a rook)
  static const char *covNear = "rcqk";
  // pawn covering pieces (like a bishop)
  static const char *covDiag = "baqk";
  // pawn covering pieces (like a knight)
  static const char *covDist = "nac";

  int size = (int)(strchr(pFen, '/') - pFen);
  int diff = 0;
  for (int n = size; --n >= 0; ) {
    // different to GC?
    if (pFen[n] != gcArray[n]) {
      ++diff;
    }
    // unprotected pawns?
    if (strchr(covNear, pFen[n]))
      continue;
    if ((n+1) < size && strchr(covDiag, pFen[n+1]))
      continue;
    if ((n-1) >=   0 && strchr(covDiag, pFen[n-1]))
      continue;
    if ((n+2) < size && strchr(covDist, pFen[n+2]))
      continue;
    if ((n-2) >=   0 && strchr(covDist, pFen[n-2]))
      continue;
    return false;
  }
  // GC-near position?
  if (diff < 3 && size == (int)strlen(gcArray)) {
    return false;
  }

  return true;
}

// test output
// -----------
int main(void)
{
  puts("\nfirst Chess960 positions");
  for (int nrFRC = 0; ++nrFRC <= 10; ) {
    printf("(%03d) %s\n",
      nrFRC, GetFen(nrFRC));
  }

  puts("\nfirst CRC positions");
  int cntValid = 0;
  for (int nrCRC = 0; ++nrCRC <= 48000; ) {
    const char *pFEN = GetFen(-nrCRC);
    bool valid = IsValidCRC(pFEN);
    if (nrCRC <= 32) {
      printf("(%05d %s) %s\n",
        nrCRC, valid ? "ok" : "--", pFEN);
    }
    if (valid) {
      ++cntValid;
    }
  }

  printf("\n%d valid CRC arrays\n", cntValid);

  return 0;
}


[Jaime Benito de Valle]

Hi Reinhard,

It's quite nice from you to post these pieces of code; I'm sure some people will find them useful. I'd like to add my own implementation for generating a fen for FRC.
It's maybe a bit messy, but quite compact. Just call it with a number between 0-959 with something like:

printf("FEN: %s\n", GenerateRandomFEN(0));

... to generate the first FEN position, which will probably be different from the first one of other people.

---------------------------------------------------------

char* GenerateRandomFEN(int i)
{
#define scanc(x) {while (f[c] != ' ') c++; while (n>0) if (f[++c] == ' ') n--;f[c] = x;}

int n, c, knights[10][2] = {0,0,0,1,0,2,0,3,1,0,1,1,1,2,2,0,2,1,3,0};
char f[9]=" ";
static char fen[45]="";

n = i % 4; i /= 4; f[n*2]='b';
n = i % 4; i /= 4; f[n*2+1]='b';
n = i % 6; i /= 6; c = 0; scanc('q');
n = knights[i][0]; c=0; scanc('n');
n = knights[i][1]; scanc('n');
c=0; scanc('r'); c=0; scanc('k'); c=0; scanc('r');

sprintf(fen,"%s",f);
sprintf(fen,"%s/pppppppp/8/8/8/8/PPPPPPPP/%s w KQkq -", fen, ToUpper(f));
return &fen[0];
}

[Reinhard Scharnagl]

Hello Jaime,

as far as I can see, your code will work equivalent for 8x8 FRC/Chess960.

Nevertheless I hope for my code to be readable also for non C/C++ enthusiasts - may be some few comment lines could help a little for that.

One reason which lead me to publish those code snippets has been to enable a unic number to position relation for every programmer as an act of standardisation. The other reason has been to show that generating 10x8 CRC positions could be done using nearly the same source slightly extended.

Reinhard.