Infinite Loop when using Extensions

[oriyonay]

Hi there you wonderful humans
Following Finn's reply to my post "The Road to 3000" I've been re-writing my entire negamax search routine. I've come across a weird bug where the search will loop infinitely when extensions are enabled. Extensions/reductions and PVS is written in a similar fashion to Ethereal/Berserk's routine, and are also outlined here:

Code: Select all

// extensions:
    extension = 0;
    if (MOVE_IS_CASTLE(move) || b.is_check() || recapture)
      if (!root) extension = 1;
    new_depth = depth + extension;

    b.make_move(move);

    // reductions:
    R = 1;
    if (depth > 2 && non_pruned_moves > 1) {
      if (!tactical) {
        if (!b.is_check()) R += 2;
        if (!pv) R++;
        if (!improving) R++;
        if (is_killer) R -= 2;
      }
      else R -= pv ? 2 : 1;
      R = std::min(depth - 1, std::max(R, 1));
    }

    // PVS:
    if (pv && non_pruned_moves == 1) {
      score = -negamax(depth - 1, -beta, -alpha, forward_ply + 1);
    }
    else {
      score = -negamax(new_depth - R, -alpha - 1, -alpha, forward_ply + 1);
      if (R != 1 && score > alpha) {
        score = -negamax(new_depth - 1, -alpha - 1, -alpha, forward_ply + 1);
      }
      if ((score > alpha) && (score < beta)) {
        score = -negamax(new_depth - 1, -beta, -alpha, forward_ply + 1);
      }
    }

My hypothesis: when a search has no reduction and has an extension, then new_depth - R = depth and so the search loops infinitely.

What do you think, and how should I go about fixing this? Also, if anyone would be willing to look over my code and review it I would really appreciate it!

Thank you, I hope you're having an incredible day!!
- Ori Yonay

[oriyonay]

For those who may be interested, here's the entire negamax function:

Code: Select all

int negamax(int depth, int alpha, int beta, int forward_ply) {
  // update the UNSAFE bitboard, and a local is_check variable,
  // since it's not updating elsewhere for some reason:
  b.update_move_info_bitboards();
  bool is_check = b.is_check();

  // base case:
  if (depth <= 0 && !is_check) return quiescence(alpha, beta, forward_ply);

  // ensure non-negative depth:
  depth = std::max(depth, 0);

  // if this is a draw, return 0:
  // NOTE: we don't yet count material draws
  if (b.is_repetition() || b.fifty_move_counter >= 100) return 0;

  // every 2048 nodes, communicate with the GUI / check time:
  nodes_evaluated++;
  if (nodes_evaluated % 2048 == 0) communicate();
  if (stop_search) return evaluate();

  // avoid stack overflow:
  if (forward_ply >= MAX_SEARCH_PLY) return is_check ? 0 : evaluate();

  pv_length[forward_ply] = forward_ply;
  bool pv = (alpha != beta - 1);
  bool root = (forward_ply == 0);
  int score = -INF;
  int best_score = -INF;
  int best_move = NULL;
  char tt_flag = TT_ALPHA;

  // look up the position in the TT:
  score = probe_tt(depth, alpha, beta);
  if (b.ply > 0 && !pv && (score != TT_NO_MATCH)) return score;
  score = -INF;

  int eval = evaluate();
  static_evals[forward_ply] = eval;
  bool improving = (!is_check && forward_ply >= 2 && eval > static_evals[forward_ply-2]);

  // NULL MOVE PRUNING GOES HERE

  // generate all possible moves from this position:
  int moves[MAX_POSITION_MOVES];
  int num_moves = b.get_moves(moves);

  // if we're following the principal variation, enable PV scoring:
  if (follow_pv) {
    follow_pv = false;
    for (int i = 0; i < num_moves; i++) {
      if (pv_table[0][forward_ply] == moves[i]) {
        score_pv = true;
        follow_pv = true;
      }
    }
  }

  // score the moves:
  int move_scores[MAX_POSITION_MOVES];
  for (int i = 0; i < num_moves; i++) {
    move_scores[i] = score_move(moves[i]);
  }

  // variables for move selection (selection sort, in main recursive loops):
  int move, move_index;

  // recursively find the best move from here:
  int non_pruned_moves = 0;
  bool tactical;
  bool is_killer;
  bool recapture;
  int extension;
  int new_depth;
  int R;
  for (int i = 0; i < num_moves; i++) {
    // selection sort to find the best move:
    move_index = 0; // contains the index of the best move
    for (int j = 0; j < num_moves; j++) {
      if (move_scores[j] > move_scores[move_index]) {
        move_index = j;
      }
    }

    // once we find the move with the highest score, set its score to -1 so it
    // can't be selected again (essentially marking it as 'seen')
    move = moves[move_index];
    move_scores[move_index] = -1;

    // figure out some things about this move:
    tactical = (MOVE_CAPTURED(move) != NONE) || (MOVE_IS_PROMOTION(move));
    is_killer = (move == killer_moves[0][forward_ply]) ||
                (move == killer_moves[1][forward_ply]);
    recapture = (b.ply) &&
                (MOVE_CAPTURED(b.move_history[b.ply-1]) != NONE) &&
                (MOVE_CAPTURED(move) != NONE) &&
                (MOVE_TO(b.move_history[b.ply-1]) == MOVE_TO(move));

    // FUTURE: PRUNING GOES HERE

    non_pruned_moves++;

    // extensions:
    extension = 0;
    if (MOVE_IS_CASTLE(move) || b.is_check() || recapture)
      if (!root) extension = 1;
    new_depth = depth + extension;

    b.make_move(move);

    // reductions:
    R = 1;
    if (depth > 2 && non_pruned_moves > 1) {
      if (!tactical) {
        if (!b.is_check()) R += 2;
        if (!pv) R++;
        if (!improving) R++;
        if (is_killer) R -= 2;
      }
      else R -= pv ? 2 : 1;
      R = std::min(depth - 1, std::max(R, 1));
    }

    // PVS:
    if (pv && non_pruned_moves == 1) {
      score = -negamax(depth - 1, -beta, -alpha, forward_ply + 1);
    }
    else {
      score = -negamax(new_depth - R, -alpha - 1, -alpha, forward_ply + 1);
      if (R != 1 && score > alpha) {
        score = -negamax(new_depth - 1, -alpha - 1, -alpha, forward_ply + 1);
      }
      if ((score > alpha) && (score < beta)) {
        score = -negamax(new_depth - 1, -beta, -alpha, forward_ply + 1);
      }
    }
    b.undo_move();

    if (score > best_score) {
      best_score = score;
      best_move = move;

      if (score > alpha) {
        // switch the TT flag to indicate storing the exact value of this position,
        // since it's a PV node:
        tt_flag = TT_EXACT;

        // add this move to the history move list, only if it's a quiet move:
        if (MOVE_CAPTURED(move) == NONE) {
          history_moves[MOVE_PIECEMOVED(move)][MOVE_TO(move)] += depth;
        }

        // this is the PV node:
        alpha = score;

        // enter PV move into PV table:
        pv_table[forward_ply][forward_ply] = move;

        // copy move from deeper PV:
        for (int next = forward_ply + 1; next < pv_length[forward_ply + 1]; next++) {
          pv_table[forward_ply][next] = pv_table[forward_ply + 1][next];
        }

        // adjust the PV length table:
        pv_length[forward_ply] = pv_length[forward_ply + 1];

        // fail-hard beta cutoff (node fails high)
        if (score >= beta) {
          // store beta in the transposition table for this position:
          update_tt(depth, beta, move, TT_BETA);

          // add this move to the killer move list, only if it's a quiet move
          if (!tactical && (move != killer_moves[0][b.ply])) {
            killer_moves[1][b.ply] = killer_moves[0][b.ply];
            killer_moves[0][b.ply] = move;
          }

          return beta;
        }
      }
    }
  }

  if (num_moves == 0) return is_check ? -INF + forward_ply : 0;

  // node fails low. store the value in the transposition table first, then exit:
  best_move = pv_table[forward_ply][forward_ply];
  update_tt(depth, alpha, best_move, tt_flag);
  return alpha;
}

[oriyonay]

Never mind - I fixed it. Simple bug in check detection... I'd still love any feedback on the code if anyone is willing to offer some though!

[Bo Persson]

I don't get all the implications of your reduction code, so you might already indirectly do this.

However, I found an odd position with two kings, two queens, and just a few pawns remaining that crashed at ply 94(!). Out of stack space, obviously, when both sides succeeded in extending the search.

A quick fix was to just limit the total number of extensions in a search to twice the intended depth.

Code: Select all

         if (CheckEvation && Ply < 2 * Iteration)
            ++SearchExtension;

Most sane search paths never hit the limit

[hgm]

Extensions are risky. Fairy-Max only has check extension. This is safe in orthodox Chess, as mutual perpetual checks are impossible there. But in variants with Xiangqi Cannons or Nightriders, these are possible, and make Fairy-Max crash by stack overflow. Recognizing repetitions (and score those without further search) helped to prevent this. It would still be problematic if very long non-repetitive sequences of moves exist, which all trigger extensions.

[Jakob Progsch]

At one point I thought doing check extensions when there is only a single legal follow up would be safe to extend by two. Since any repetition would be caught by the repetition draw code. Turns out there are sequences of 50+ non-repeating moves with a queen chasing a king around the board. And those can have many transpositions. Strictly speaking those were not infinite but practically close to it. In some cases this could lead to my engine not even finishing the first search in the iterative deepening loop within time control.

So my extensions got more and more conservative. Only extend checks in main search (instead of QS), never double extend etc.

I now limit extensions to 50% of the "target depth" to keep it somewhat in check. Annoyingly that seems to make it play slightly worse but also avoids the issue of it occasionally just failing to produce a plausible move at all due to these (quasi-)infinite loop problems.

[Henk]

Extension is a not reduction. So maybe you can rewrite your code. All non extensions getting reduced.
Advantage is that with reductions only you never can get an infinite loop.

[j.t.]

Just check if the current height of your tree is at the maximum depth (127 or something like that) and return a draw value in that case. If your engine has stack overflows anyway, then you have some big data that you create with each new search call, which you may want to avoid anyway for performance reasons. Or an unusually small stack size.