Search readability

[Henk]

Code of search method does not fit on the screen. I tried to use more high level subroutines with unclear names and large parameter lists but that was a failure for you have to look up all the time.

Current lines of code for search is about 190.

[brtzsnr]

My main search function has 200 lines too. Recursive functions are very hard to split, especially when you have such a large state per call (alpha, beta, score, depth, moves, lmr / nmp flags, in check, best score, best move, etc).

But of course, I do my best to simplify the code all the time, even if it's only a couple of lines. This recent commit [1] cut 4 lines from the search function. It's very important to maintain a mental model of the engine and with chess engines it's easy to have an exploding complexity.

https://bitbucket.org/zurichess/zuriche ... 267c6f8fff

[Henk]

If code maintainability gets worse and worse then end of project is near.
So it should or must have highest priority.

[Sven]

Code of search method does not fit on the screen. I tried to use more high level subroutines with unclear names and large parameter lists but that was a failure for you have to look up all the time.

Current lines of code for search is about 190.

This is a well-known problem. Many engines have huge and monolithic search functions. There are various approaches to deal with it, e.g.:

- Keep a clear structure and use lots of comments. Examples: Stockfish, Crafty.

- Use various different search functions for specific purposes where each function is much smaller. Problem: code duplication. Advantage: you can understand each function separately (hopefully).

- Use subroutines for some common parts. I have done this in some my engines. Example: a family of "expand subtree of move" subroutines (or one with several parameters) that cover just makeMove(), the recursive search call, and unmakeMove(), and return the score from the recursive call. And another subroutine that does the typical "if (score >= beta) DO_THE_CUTOFF ...; if (score > bestScore) bestScore = score;" bookkeeping stuff, and returns a boolean indicating whether a beta cutoff has been detected. Also everything that checks for one of several possible draw situations could be combined in one function.

The last one is a possible way to keep the search function, or all of the different search functions, slightly shorter in terms of "lines of code". But it is not clear whether this actually helps to keep the whole search code simple and easy to understand so I do not explicitly encourage everyone to follow this approach (nor do I want to discourage anyone to do so, of course!). So maybe the two other approaches are best.

With null move, LMR, futility pruning, PVS, and possibly other search features the problem becomes more urgent but even without that it is not trivial to keep search functions easy to read.

If you feel your (search) code has become very hard to maintain then consider a rewrite. Many people have successfully done so before.

[jdart]

I dunno. There are static analysis tools that will measure function complexity and tell you to break up big routines. On the other hand, complexity is not a sign of problems necessarily. I have worked on commercial systems that were huge and complex by every measure.

--Jon

[Henk]

I remember I had to develop a component to test a generic library written by others. Only after two months they admitted that it was not possible to use the library for that component. For functionality was not there.

So each time they told me I had to use this or that functionality or I should re-use another component.

Perhaps Russian politics. At least they were Russian.

Also the one who gave me that task knew in advance that it would probably fail. But he could not proof that they were lying. Still don't understand why he did not fire me in the first week when there is no appropriate work.

Though it might have been that it was all a misunderstanding.

So never trust generic libraries or tools. Usually it is all crap unless there are very many users.

[Joost Buijs]

So never trust generic libraries or tools. Usually it is all crap unless there are very many users.

Henk, I fully agree with you on this, I try to avoid libraries written by others as the plague.
Most open source stuff you'll find on the internet is very messy and buggy with maybe a few exceptions.

[Evert]

In my more recent endeavours the search looks like this:

Code: Select all

int search(game_t *game, int alpha, int beta, int draft, int ply)
{
   assert(game);
   assert(beta > alpha);

   /* Truncate the principle variation at this depth here, otherwise we may
    * end up with rubbish at the end of the PV.
    */
   truncate_principle_variation(game, ply);

   /* The very first thing we do is to check if this position has occurred
    * three times in the game tree, or whether no irreversible move has
    * been played in 50 moves (100 ply). Either of these conditions means
    * we should flag a draw and return immediately.
    * During the search, we simply score positions as a draw if they have
    * occurred at least once before. From the top level, we don't claim a
    * draw until three repetitions have been made.
    */
   if (ply > 0) {
      if (legal_draw(game) || position_repeated_once(game))
         return 0;
   }

   /* Check whether our search time for this move has expired */
   check_clock();
   if (abort_search) return 0;

   /* Check whether we're looking for a checkmate.
    * If so, prune branches that are worse than the best mate found so far
    * (mate distance pruning).
    */
   alpha = max(alpha, -CHECKMATE + ply);
   beta  = min(beta,   CHECKMATE - ply - 1);
   if (alpha >= beta)
      return alpha;

   if &#40;draft <= 0 || ply > MAX_SEARCH_DEPTH&#41;
      return qsearch&#40;game, alpha, beta, draft, ply&#41;;

   /* Look up this position in the transposition table */
   move_t hash_move = 0;
   int    hash_score_upper = 0;
   int    hash_score_lower = 0;
   int    hash_depth_upper = 0;
   int    hash_depth_lower = 0;
   bool   have_hash = retrieve_table&#40;game->transposition_table, game->board.hash, &hash_depth_lower, &hash_score_lower, &hash_depth_upper, &hash_score_upper, &hash_move&#41;;
   game->hash_found += have_hash;

   /* Internal iterative deepening */
   if (!have_hash && alpha != beta-1 && draft > 1&#41; &#123;
      search&#40;game, alpha, beta, draft-1, ply&#41;;
      have_hash = retrieve_table&#40;game->transposition_table, game->board.hash, &hash_depth_lower, &hash_score_lower, &hash_depth_upper, &hash_score_upper, &hash_move&#41;;
   &#125;

   if &#40;have_hash && game->board.fifty_counter < 80&#41; &#123;
      if &#40;hash_depth_lower>0&#41; hash_score_lower = score_from_hashtable&#40;hash_score_lower, ply&#41;;
      if &#40;hash_depth_upper>0&#41; hash_score_upper = score_from_hashtable&#40;hash_score_upper, ply&#41;;

      if (&#40;hash_depth_lower >= draft || is_mate_score&#40;hash_score_lower&#41;) && hash_depth_lower>0 && hash_score_lower >= beta&#41; &#123;
         game->hash_cut++;
         return hash_score_lower;
      &#125;

      if (&#40;hash_depth_upper >= draft || is_mate_score&#40;hash_score_upper&#41;) && hash_depth_upper>0 && hash_score_upper <= alpha&#41; &#123;
         game->hash_cut++;
         return hash_score_upper;
      &#125;

      if &#40;hash_score_upper == hash_score_lower && alpha != beta-1 && hash_depth_upper>0 && &#40;hash_depth_upper >= draft || is_mate_score&#40;hash_score_upper&#41;)) &#123;
         game->hash_cut++;
         return hash_score_upper;
      &#125;
   &#125;

   /* First try a null-move.
    * This serves a double-purpose&#58; it is also used as a check-detection.
    */
   bool check = game->board.check;
   int static_score = &#40;check&#41; ? -CHECKMATE
                              &#58; evaluate&#40;game&#41;;

   move_t prev_move = game->moves_played ?  game->move_list&#91;game->moves_played-1&#93; &#58; 0;
   bool avoid_null = beta > alpha+1 ||
                     check ||
                     draft < 4 ||
                     prev_move == 0 ||
                     zugzwang_threat&#40;&game->board&#41; ||
                     static_score < beta ||
                     is_mate_score&#40;beta&#41;;
   if (!avoid_null&#41; &#123;
      int r = 2 + draft / 4;
      int score;
      play_null_move&#40;game&#41;;
      game->clock.nodes_searched++;
      score = -search&#40;game, -beta, -&#40;beta-1&#41;, draft - 1 - r, ply+1&#41;;
      takeback_null_move&#40;game&#41;;
      if &#40;score >= beta && !is_mate_score&#40;score&#41; && !abort_search&#41;
         return score;
   &#125;

   /* Futility pruning */
   if (!check && draft == 1 && (&#40;static_score + 700&#41; < alpha || &#40;static_score - 700&#41; > beta&#41; && !is_mate_score&#40;alpha&#41;)
      return static_score;

   /* Generate moves - not needed in the root, where it was already done by
    * the iterative deepening loop.
    * If the other side is in check, we return a -ILLEGAL score which is
    * caught one level up to mark the preceding move as illegal.
    */
   movelist_t *movelist = game->movelist + ply;
   bool legal = true;
   if &#40;ply == 0&#41;
      rewind_movelist&#40;movelist&#41;;
   else
      legal = movegen&#40;movelist, &game->board&#41;;
   if (!legal&#41; return -ILLEGAL;

   int legal_moves = movelist->num_moves;

   /* Score the moves */
   score_moves&#40;game, movelist, ply, hash_move&#41;;

   /* Search the first move */
   int score = -CHECKMATE;
   move_t move = 0;
   while &#40;legal_moves&#41; &#123;
      move = next_move&#40;movelist&#41;;
      game->best_move&#91;ply&#93; = move;
      playmove&#40;game, move&#41;;
      game->clock.nodes_searched++;
      game->board.check = in_check&#40;&game->board, game->board.side_to_move&#41;;
      int e = draft <= 1 && game->board.check && see&#40;&game->board, move&#41; > 0;
      score = -search&#40;game, -beta, -alpha, draft-1 + e, ply+1&#41;;
      takeback&#40;game&#41;;

      if &#40;score == ILLEGAL&#41; &#123;
         legal_moves--;
         continue;
      &#125;
      break;
   &#125;

   /* If there are no legal moves, the game is over */
   if &#40;legal_moves == 0&#41; &#123;
      score = &#40;check || game->stale_win&#41; ? (-CHECKMATE + ply&#41; &#58; STALEMATE;
      return score;
   &#125;

   if &#40;score > alpha&#41; &#123;           /* New best line found */
      alpha = score;

      adjust_history_score&#40;game, move, draft * draft&#41;;

      /* Update and store principle variation */
      backup_principle_variation&#40;game, ply, move&#41;;
   &#125;

   /* Search remaining moves; we know there is at least one legal move at
    * this point, so don't bother tracking those anymore.
    */
   move_t best_move = move;
   int moves_searched = 1;
   int best_score = score;
   while &#40;alpha < beta && movelist->cur_move < movelist->num_moves&#41; &#123;
      move = next_move&#40;movelist&#41;;

      /* Futility pruning */
      if &#40;draft == 1 && !check && !is_mate_score&#40;beta&#41; && static_score < beta&#41; &#123;
         /* Losing captures */
         if &#40;is_capture_move&#40;&game->board, move&#41; && get_move_score&#40;movelist&#41; < 1000&#41; continue;
      &#125;

      playmove&#40;game, move&#41;;
      game->clock.nodes_searched++;

      int e = get_extension&#40;move, get_move_score&#40;movelist&#41;);
      int r = &#40;e == 0&#41; ? get_reduction&#40;move, get_move_score&#40;movelist&#41;, moves_searched, draft&#41; &#58; 0;
      /* Check extension&#58; extend checking moves */
      game->board.check = in_check&#40;&game->board, game->board.side_to_move&#41;;
      if &#40;game->board.check&#41; &#123;
         e = 1;
         r = 0;
      &#125;
      score = -search&#40;game, -&#40;alpha+1&#41;, -alpha, draft-1 + e - r, ply+1&#41;;

      /* Verification search, only useful when the window is not a null
       * window.
       */
      if &#40;score > alpha && score < beta&#41;
         score = -search&#40;game, -beta, -alpha, draft-1 + e, ply+1&#41;;

      takeback&#40;game&#41;;

      if &#40;score == ILLEGAL&#41; continue;

      if &#40;score > best_score&#41; &#123;
         best_score = score;
         best_move = game->best_move&#91;ply&#93; = move;
      &#125;

      if &#40;score > alpha&#41; &#123;    /* New best line found */
         alpha = score;
         best_move = move;

         adjust_history_score&#40;game, move, draft * draft&#41;;

         /* Update and store principle variation */
         backup_principle_variation&#40;game, ply, move&#41;;
      &#125;
      moves_searched++;
   &#125;

   if &#40;alpha >= beta&#41; &#123;        /* Beta cutoff */
      /* Store good moves in the killer slots, but only if&#58;
       *  - we were not in check at the beginning of this move
       *  - the move is not a promotion &#40;already high in the list&#41;
       *  - the move was not a capture &#40;already high in the list&#41;
       */
      store_killer&#40;game, best_move, ply&#41;;
      store_mate_killer&#40;game, best_move, ply, best_score&#41;;
      if &#40;prev_move == 0&#41;
         store_null_killer&#40;game, ply, best_move&#41;;

      game->branches_pruned_1st += &#40;moves_searched == 1&#41;;
      game->branches_pruned_lt3rd += &#40;moves_searched < 3&#41;;
      game->branches_pruned++;

      for &#40;int n=0; n<movelist->cur_move-1; n++)
         adjust_history_score&#40;game, movelist->move&#91;n&#93;, -draft * draft&#41;;
   &#125;


   /* Abort if we've exceeded our allowed time to think */
   if &#40;abort_search&#41; return 0;

   /* Store best move for retrieval from one level up in the search &#40;for IID&#41; */
   game->best_move&#91;ply&#93; = best_move;

   /* store evaluation in the transposition table */
   if (!have_hash&#41; &#123;
      hash_move = 0;
      hash_score_upper = CHECKMATE;
      hash_score_lower = -CHECKMATE;
      hash_depth_upper = 0;
      hash_depth_lower = 0;
   &#125;

   if &#40;best_score < beta&#41; &#123;
      hash_score_upper = best_score;
      hash_depth_upper = draft;
      hash_move = 0;
   &#125;
   if &#40;best_score > alpha&#41; &#123;
      hash_score_lower = best_score;
      hash_depth_lower = draft;
      hash_move = best_move;
   &#125; 
   if &#40;hash_depth_lower>0&#41; hash_score_lower = score_to_hashtable&#40;hash_score_lower, ply&#41;;
   if &#40;hash_depth_upper>0&#41; hash_score_upper = score_to_hashtable&#40;hash_score_upper, ply&#41;;
   store_table_entry&#40;game->transposition_table, game->board.hash, hash_depth_lower, hash_score_lower, hash_depth_upper, hash_score_upper, hash_move&#41;;

   return best_score;
&#125;

It doesn't have as many bells and whistles, and of course it has qsearch as a separate function, but overall I quite like the structure I have here. I don't use a separate root search function.

[Joost Buijs]

Code of search method does not fit on the screen. I tried to use more high level subroutines with unclear names and large parameter lists but that was a failure for you have to look up all the time.

Current lines of code for search is about 190.

In Nightmare there are many functions in the search() about 1100 lines in total.

Basically they are:

search_root();
search_pv();
search_zw();
search_pv_smp();
search_zw_smp();
quiescence_pv();
quiescence_zw();
quiescence_evasions_pv();
quiescence_evasions_zw();

The search could be made smaller by merging things but that will make it less easy to read.
The most annoying thing is that some parts of my main search are mirrored in my smp search and that I have to make changes to both of them, this is something I forgot a few times in the past.

[bob]

Code of search method does not fit on the screen. I tried to use more high level subroutines with unclear names and large parameter lists but that was a failure for you have to look up all the time.

Current lines of code for search is about 190.

In Nightmare there are many functions in the search() about 1100 lines in total.

Basically they are:

search_root();
search_pv();
search_zw();
search_pv_smp();
search_zw_smp();
quiescence_pv();
quiescence_zw();
quiescence_evasions_pv();
quiescence_evasions_zw();

The search could be made smaller by merging things but that will make it less easy to read.
The most annoying thing is that some parts of my main search are mirrored in my smp search and that I have to make changes to both of them, this is something I forgot a few times in the past.

That is THE reason I discontinued this bad practice several years ago.

I have a single Search() procedure, and a simple Quiesce() procedure. I have one special case, QuiesceEvasions() that I will get rid of pretty soon...