My newest almost bb move generator is wonderful

[Michael Sherwin]

Hey Michael,

This looks interesting. How does it perform in perf tests?

BTW: if you'd like to write it up I'd be happy to publish it as a blog article on chessprogramming.net

Steve

Hi Steve, It's been a long time. I'm working on the perft code now. When I have the perft working I will surely write it up and send it to you!

[Michael Sherwin]

A frustrating 4 hours. I wanted to do something with an array of function pointers similar to something that was done in RomiChess. So I looked in RomiChess to see how it was done. However, Romi is in C and this engine is in C++ so it would not work. I got errors that constantly changed with every change that was tried. So I looked in my ancient C++ primer and it still didn't work. Then I went online to Stack Overflow and found lots of examples but there was always something wrong. I started to hit things (soft things like the arm of my chair), lol. Anyway, I did find an example that was exactly what I was trying to do and it worked! But it was done in a way that I had never seen before. So I thought I'd share it.

typedef void MGt(threadS *, moveU *); // This seems to be another way to declare a prototype.

MGt WPf, WNf, WBf, WRf, WQf, WKf, BPf, BNf, BBf, BRf, BQf, BKf; // This is like creating 12 functions like creating 12 variables.

MGt *MGf[12] = { WPf, WNf, WBf, WRf, WQf, WKf, BPf, BNf, BBf, BRf, BQf, BKf }; // Then create the 12 poiters.

// Then what, specify the actual function code?
void WPf(threadS *t, moveU *m) {}

void WNf(threadS *t, moveU *m) {}

void WBf(threadS *t, moveU *m) {}

void WRf(threadS *t, moveU *m) {}

void WQf(threadS *t, moveU *m) {}

void WKf(threadS *t, moveU *m) {}

void BPf(threadS *t, moveU *m) {}

void BNf(threadS *t, moveU *m) {}

void BBf(threadS *t, moveU *m) {}

void BRf(threadS *t, moveU *m) {}

void BQf(threadS *t, moveU *m) {}

void BKf(threadS *t, moveU *m) {}

// Then actually call the function
MGf[typ](t, &t->moves[t->ply]);

This looked very strange but the longer I looked the more I liked it.

[Michael Sherwin]

As I get further into it I keep having to make minor changes as I discover the needs of the system. I'm making the perft search and creating some simple move generators specifically for perft. I imagine that the move generators for the main search will need to be more versatile. Here is the white knight perft move generator. I'll post one of the sliding pieces when it is complete.

Code: Select all

void Perft(threadS *t, u08 depth) {
  s32 id = t->wtm ? 20 : 40, typ;

  id = t->nxt[id];
  do  {
    typ = t->typ[id];
    MGf[typ](t, id, depth, &t->moves[t->ply]);
    id = t->nxt[id];
  } while(id);
}

// White Knight move generator function - perft version
void WNf(threadS *t, u08 id, u08 depth, moveU *m) {
  u08 i = 1;

  m->fs = t->sqr[id];
  m->typ = WN;
  if (t->inv[id][t->top[id]]) WNBBG(t, id, m->fs, &t->stk[id][t->top[id]]);
  for (i = 1; i <= mvsKN[m->fs][0]; i++) {
    m->ts = mvsKN[m->fs][i];
    m->id = t->brd[m->ts];
    MakeMove(t, m);
    if (depth > 0) Perft(t, depth - 1);
    TakeBack(t, m);
  }
}

So, now the efficiency can be seen more clearly. The call to WNBBG whether it last happened here because the piece was invalidated or happened possibly many moves before takes care of a lot of the details. Therefore, in the move generation phase the board need not be checked for occupancy or edge detection because only valid moves are in mvsKN[64][9].

P.S. I have not been able to test this in the debugger yet because I just finished and it is time for bed. But, I hope it will work!

[Michael Sherwin]

This system will not behave in perft like other systems. The whole idea of this system is to avoid work in the search until it is required in case a cutoff makes that work unnecessary. In perft all nodes (lol, I accidently posted noses) are visited to a certain depth. Therefore all work needs to be done all the time. So I do not expect this system to shine in perft. I do expect it to shine in the normal ab search though! We will see.

[Steve Maughan]

Hi Michael,

(...) I do expect it to shine in the normal ab search though! We will see.

For it to shine in alpha / beta it will need to efficient at validating the hash move as legal and generating captures. Do you think this will be the case?

Cheers,

Steve

[Michael Sherwin]

Hi Michael,

(...) I do expect it to shine in the normal ab search though! We will see.

For it to shine in alpha / beta it will need to efficient at validating the hash move as legal and generating captures. Do you think this will be the case?

Cheers,

Steve

Yes! The full bitboards are maintained for each piece so validating the hash move will be a snap. And capture generation for the sliders would look something like this.

if ((id = t->brd[mvsNW[fs][mvsNW[fs][0]]])) {};

That is all it takes to find a capture along a ray!

[Michael Sherwin]

Well at least I have 'proof of concept' as perft 1 generated the correct 20 moves. The black move generators are still empty functions and I'm out of time for today.

Code: Select all

// A Simple Perft 
void Perft(threadS *t, u08 depth) {
  u08 id = t->wtm ? 19 : 39, typ;

  while (id) {
    id = t->nxt[id];
    typ = t->typ[id];
    MGf[typ](t, id, depth, &t->moves[t->ply]);
  }
}

Code: Select all

void WPf(threadS *t, u08 id, u08 depth, moveS *m) {
  m->fs = t->sqr[id];
  if (t->inv[id][t->top[id]]) WPBBG(t, id, m->fs, &t->stk[id][t->top[id]]);
  for (u08 i = 1; i <= mvsWP[m->fs][0]; i++) {
    m->ts = mvsWP[m->fs][i];
    m->id = t->brd[m->ts];
    m->typ = WPtyp[(m->id)][(m->fs >> 3)]; // Does m->id when in parentheses equate to a truth value or the value of the variable? 
    MakeMove(t, m);                                  // So I might have to change that. Idk, I just can't remember.
    if (depth > 0) Perft(t, depth - 1);
    TakeBack(t, m);
  }
}

Code: Select all

void WNf(threadS *t, u08 id, u08 depth, moveS *m) {
  m->fs = t->sqr[id];
  if (t->inv[id][t->top[id]]) WNBBG(t, id, m->fs, &t->stk[id][t->top[id]]);
  for (u08 i = 1; i <= mvsKN[m->fs][0]; i++) {
    m->ts = mvsKN[m->fs][i];
    m->id = t->brd[m->ts];
    m->typ = (m->id) ? 0 : 1;
    MakeMove(t, m);
    if (depth > 0) Perft(t, depth - 1);
    TakeBack(t, m);
  }
}

Code: Select all

void WBf(threadS *t, u08 id, u08 depth, moveS *m) {
  unsigned char *c = &t->inv[id][t->top[id]];  m->fs = t->sqr[id];
  if (*c) WSBBG(t, id, m->fs, c, &t->stk[id][t->top[id]]);
  for (u08 i = 0; i < 4; i++) {
    for (u08 j = 1; j <= mvsB[i][m->fs]; j++) {
      m->ts = mvsB[m->fs][j];
      m->id = t->brd[m->ts];
      m->typ = (m->id) ? 0 : 1;
      MakeMove(t, m);
      if (depth > 0) Perft(t, depth - 1);
      TakeBack(t, m);
    }
  }
}