My newest almost bb move generator is wonderful

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Michael Sherwin
Posts: 3024
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: My newest almost bb move generator is wonderful

Post by Michael Sherwin » Thu Apr 18, 2019 10:32 pm

Steve Maughan wrote:
Thu Apr 18, 2019 9:10 pm
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! :D
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Michael Sherwin
Posts: 3024
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: My newest almost bb move generator is wonderful

Post by Michael Sherwin » Thu Apr 18, 2019 11:55 pm

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. 8-)
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Michael Sherwin
Posts: 3024
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: My newest almost bb move generator is wonderful

Post by Michael Sherwin » Fri Apr 19, 2019 5:01 am

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!
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Michael Sherwin
Posts: 3024
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: My newest almost bb move generator is wonderful

Post by Michael Sherwin » Fri Apr 19, 2019 3:25 pm

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.
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

User avatar
Steve Maughan
Posts: 1059
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Re: My newest almost bb move generator is wonderful

Post by Steve Maughan » Fri Apr 19, 2019 6:12 pm

Hi Michael,
Michael Sherwin wrote:
Fri Apr 19, 2019 3:25 pm
(...) 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
http://www.chessprogramming.net - Maverick Chess Engine

Michael Sherwin
Posts: 3024
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: My newest almost bb move generator is wonderful

Post by Michael Sherwin » Fri Apr 19, 2019 6:24 pm

Steve Maughan wrote:
Fri Apr 19, 2019 6:12 pm
Hi Michael,
Michael Sherwin wrote:
Fri Apr 19, 2019 3:25 pm
(...) 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! :D
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Michael Sherwin
Posts: 3024
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: My newest almost bb move generator is wonderful

Post by Michael Sherwin » Sat Apr 20, 2019 4:45 am

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);
    }
  }
}
I hate if statements. Pawns demand if statements. Therefore I hate pawns.

Post Reply