An annoying problem with pvs

Mike Sherwin · Post by **Mike Sherwin** » Sun Feb 28, 2021 8:07 pm

// in the iteration function at the beginning
memset(pvs, 0, sizeof(pvs));
pvl[ply] = ply;

// after each iteration
    PrintBest(bestMove, d);
    
// in PrintBest
if (d == 0) {
    printf("move %s\n", xbmove);
  }
  else {
    printf("%i %i %i %i", d, bestMove.score, (clock() - begin) / 10, nodes);
    for (i = 0; i < pvl[0]; i++) {
      if (pvs[0][i].fs == 0 && pvs[0][i].ts == 0) break;
      xbmove[0] = 'a' + (pvs[0][i].fs & 7);
      xbmove[1] = '1' + (pvs[0][i].fs >> 3);
      xbmove[2] = 'a' + (pvs[0][i].ts & 7);
      xbmove[3] = '1' + (pvs[0][i].ts >> 3);
      xbmove[4] = '\0';
      if (pvs[0][i].type == Wn || pvs[0][i].type == Bn) xbmove[4] = 'n';
      if (pvs[0][i].type == Wb || pvs[0][i].type == Bb) xbmove[4] = 'b';
      if (pvs[0][i].type == Wr || pvs[0][i].type == Br) xbmove[4] = 'r';
      if (pvs[0][i].type == Wq || pvs[0][i].type == Bq) xbmove[4] = 'q';
      printf("  %s", xbmove);
    }
    printf("\n");
  }
  fflush(stdout);

// in SearchRoot() after each move
    if (mov->score > alpha) {
      alpha = mov->score;
      bestMove = *mov;
      pvs[ply][ply] = *mov;
      for (j = ply + 1; j < pvl[ply + 1]; j++)pvs[ply][j] = pvs[ply + 1][j];
      pvl[ply] = pvl[ply + 1];
    }
    
// in Search() at the beginning
   pvl[ply] = ply;  
   
// in Search() after each move 
    if (mov->score > alpha) {
      alpha = mov->score;
      pvs[ply][ply] = *mov;
      for (j = ply + 1; j < pvl[ply + 1]; j++) pvs[ply][j] = pvs[ply + 1][j];
      pvl[ply] = pvl[ply + 1];
    }

For the first search there is no pv except for pvs[0][0].
FEN: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1

Bricabrac:
1 00:00 20 20 +0.50 b1c3
2 00:00 85 85 0.00 b1c3
3 00:00 618 618 +0.50 b1c3
4 00:00 4k 4k 0.00 b1c3
5 00:00 23k 23k +0.50 b1c3
6 00:00 155k 15,529k 0.00 b1c3
7 00:00 940k 13,422k +0.40 e2e4
8 00:00 5,717k 10,394k +0.10 e2e4
9 00:01 26,270k 13,335k +0.40 e2e4
10 00:19 213,102k 10,768k +0.10 e2e4

Then if I undo that move and search again.

FEN: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1

Bricabrac:
1 00:00 20 20 +0.50 b1c3
2 00:00 85 85 0.00 b1c3
3 00:00 618 618 +0.50 b1c3 d7d5 d2d4
4 00:00 4k 4k 0.00 b1c3 d7d5 d2d4 b8c6
5 00:00 23k 23k +0.50 b1c3 d7d5 g1f3 b8c6 d2d4
6 00:00 155k 15,529k 0.00 b1c3 d7d5 g1f3 b8c6 d2d4 g8f6
7 00:00 940k 13,422k +0.40 e2e4 b8c6 g1f3 d7d5 e4d5 d8d5 d2d4
8 00:00 5,717k 10,394k +0.10 e2e4 e7e5 b1c3 b8c6 g1f3 f8c5 d2d3 g8f6
9 00:01 26,270k 13,335k +0.40 e2e4 b8c6 b1c3 g8f6 d2d4 d7d5 e4e5 f6e4 g1e2
10 00:19 213,102k 10,763k +0.10 e2e4 e7e5 b1c3 g8f6 g1f3 f8d6 d2d4 e5d4 f3d4 e8g8

Ply two is missing a move but it works. Does pvs[][] and pvl[] need primed in some way? Does anyone know why it would not work the first time but then works the second time?

hgm · Post by **hgm** » Sun Feb 28, 2021 9:10 pm

I think you should only update the PV for scores between alpha and beta.

Mike Sherwin · Post by **Mike Sherwin** » Sun Feb 28, 2021 9:37 pm

hgm wrote: ↑Sun Feb 28, 2021 9:10 pm I think you should only update the PV for scores between alpha and beta.

Thanks HGM, but I check for beta cut first and return beta before checking the score against alpha. I'll double check though. I'll just post the entire search.

Code: Select all

Move Bricabrac(Thread* t) {
  u64 n;
  s32 d, i;
  Move bestMove = { 0 }, lastBest;

  memset(pvs, 0, sizeof(pvs));

  pvl[ply] = ply;

  nodes = 0;

  begin = clock();
  end = begin + st;
  ply = 0;
  bestMove.score = -INF;

  n = GenMoves(t, &move[0]);

  for (d = 1; d <= sd; d++) {

    if (!xboard) {
      printf("\nBegin Depth %i\n", d);
    }

    lastBest = bestMove;

    bestMove = RootSearch(t, &move[0], -INF, INF, d, n);

    pvl[0] = d;

    if (clock() > end) {
      bestMove = lastBest;
      break;
    }

    SortRoot(t, move, n);

    PrintBest(bestMove, d);

  }

  bricabrac = MOVE;

  return bestMove;
}

void PrintBest(Move bestMove, s32 d) {
  s32 i;
  char xbmove[5];
  xbmove[0] = 'a' + (bestMove.fs & 7);
  xbmove[1] = '1' + (bestMove.fs >> 3);
  xbmove[2] = 'a' + (bestMove.ts & 7);
  xbmove[3] = '1' + (bestMove.ts >> 3);
  xbmove[4] = '\0';
  if (bestMove.type == Wn || bestMove.type == Bn) xbmove[4] = 'n';
  if (bestMove.type == Wb || bestMove.type == Bb) xbmove[4] = 'b';
  if (bestMove.type == Wr || bestMove.type == Br) xbmove[4] = 'r';
  if (bestMove.type == Wq || bestMove.type == Bq) xbmove[4] = 'q';
  if (d == 0) {
    printf("move %s\n", xbmove);
  }
  else {
    printf("%i %i %i %i", d, bestMove.score, (clock() - begin) / 10, nodes);
    for (i = 0; i < pvl[0]; i++) {
      if (pvs[0][i].fs == 0 && pvs[0][i].ts == 0) break;
      xbmove[0] = 'a' + (pvs[0][i].fs & 7);
      xbmove[1] = '1' + (pvs[0][i].fs >> 3);
      xbmove[2] = 'a' + (pvs[0][i].ts & 7);
      xbmove[3] = '1' + (pvs[0][i].ts >> 3);
      xbmove[4] = '\0';
      if (pvs[0][i].type == Wn || pvs[0][i].type == Bn) xbmove[4] = 'n';
      if (pvs[0][i].type == Wb || pvs[0][i].type == Bb) xbmove[4] = 'b';
      if (pvs[0][i].type == Wr || pvs[0][i].type == Br) xbmove[4] = 'r';
      if (pvs[0][i].type == Wq || pvs[0][i].type == Bq) xbmove[4] = 'q';
      printf("  %s", xbmove);
    }
    printf("\n");
  }
  fflush(stdout);
}


Move RootSearch(Thread* t, Move* m, s32 alpha, s32 beta, s32 depth, u64 n) {
  s32 mi, j;
  Move* mov;
  Move bestMove = { 0 };

  bestMove.score = -INF;

  for (mi = 0; mi < n; mi++) {
    mov = m + mi;
    MakeMove(t, mov);
    mov->score = -Search(t, m + n, -beta, -alpha, depth - 1);
    TakeBack(t, mov);
    if (mov->score == ILLEGAL) continue;
    if (mov->score > alpha) {
      alpha = mov->score;
      bestMove = *mov;
      pvs[ply][ply] = *mov;
      for (j = ply + 1; j < pvl[ply + 1]; j++)pvs[ply][j] = pvs[ply + 1][j];
      pvl[ply] = pvl[ply + 1];
    }
    if (clock() > end) break;
  }
  return bestMove;
}  

s32 Search(Thread* t, Move* m, s32 alpha, s32 beta, s32 depth) {
  s32 mi, j, count = 0;
  u64 n;
  Move* mov;

  if (depth == 0) return Qsearch(t, m, alpha, beta);

  if (clock() > end) return alpha;

  pvl[ply] = ply;

  n = GenMoves(t, m);

  if (!n) return -ILLEGAL;

 if (depth > 2) {
    for (mi = 0; mi < n; mi++) {
      mov = m + mi;
      MakeMove(t, mov);
      mov->score = -Qsearch(t, m + n, -beta - 1000, -alpha + 100);
      TakeBack(t, mov);
    }
  }

  for (mi = 0; mi < n; mi++) {
    Sort(t, m, mi, n);
    mov = m + mi;
    MakeMove(t, mov);
    nodes++;
    mov->score = -Search(t, m + n, -beta, -alpha, depth - 1);
    TakeBack(t, mov);
    if (mov->score == ILLEGAL) continue;
    if (mov->score >= beta) return beta;
    count++;
    if (mov->score > alpha) {
      alpha = mov->score;
      pvs[ply][ply] = *mov;
      for (j = ply + 1; j < pvl[ply + 1]; j++) pvs[ply][j] = pvs[ply + 1][j];
      pvl[ply] = pvl[ply + 1];
    }
  }
  if (!count) {
    if (InCheck[wtm](t, king[wtm])) {
      return -(MATE - ply);
    }
    else return STALEMATE;
  }
  return alpha;
}

Mike Sherwin · Post by **Mike Sherwin** » Mon Mar 01, 2021 4:36 am

I made a kludge that fixed the problem.

After

memset(pvs, 0, sizeof(pvs));

I added

for (i = 1; i < 100; i++) pvl(i) = i; // () = square brackets, lol

to prime pvl[ply] with lengths. At least for now it works! And on the very first search after loading.

FEN: rnbqkbnr/pppppppp/8/8/4P3/8/PPPP1PPP/RNBQKBNR b KQkq e3 0 1

Bricabrac:
1 00:00 20 20 +0.50 b1c3
2 00:00 85 85 0.00 b1c3 d7d5
3 00:00 618 618 +0.50 b1c3 d7d5 d2d4
4 00:00 4k 4k 0.00 b1c3 d7d5 d2d4 b8c6
5 00:00 23k 23k +0.50 b1c3 d7d5 g1f3 b8c6 d2d4
6 00:00 155k 15,529k 0.00 b1c3 d7d5 g1f3 b8c6 d2d4 g8f6
7 00:00 940k 13,422k +0.40 e2e4 b8c6 g1f3 d7d5 e4d5 d8d5 d2d4
8 00:00 5,717k 10,394k +0.10 e2e4 e7e5 b1c3 b8c6 g1f3 f8c5 d2d3 g8f6
9 00:01 26,270k 13,268k +0.40 e2e4 b8c6 b1c3 g8f6 d2d4 d7d5 e4e5 f6e4 g1e2
10 00:19 213,102k 10,741k +0.10 e2e4 e7e5 b1c3 g8f6 g1f3 f8d6 d2d4 e5d4 f3d4 e8g8

An annoying problem with pvs

An annoying problem with pvs

Re: An annoying problem with pvs

Re: An annoying problem with pvs

Re: An annoying problem with pvs