🚀 go-pugleaf

Marcel van Kervinck (buex95a@asterix.urc.tue.nl) wrote:
: Robert Hyatt (hyatt@cis.uab.edu) wrote:
: > Bruce pointed out one important thing that's been overlooked:  After
: > searching a move at any ply, the ordering information likely changes
: > because the history values are modified by any search done below that
: > move.  As a result, the ply=N move list would have to be re-sorted each
: > time, or else part of the benefit of the history heuristic would go
: > lost.

: Yes. That is correct. On the other hand, re-scoring each move every
: time you select one makes selecting more expensive, since you have
: to look up the history values over and over again.

However, this isn't an issue, as this lookup is simply one memory
reference, which the selection sort has to do just like any other
sorting algorithm.  The advantage seems reasonably significant
since move ordering is *the* most critical issue in alpha/beta
searches...


: As always in (chess) programming: it's a trade-off you have to consider,
: and you have to try dozens of possibilities before you can select one. And
: once you've made choice, it affects other parts of your program as well...

: > That's one of the nice things about the history heuristic and selection
: > sort approach... you search the first move, then when it's time to select
: > the next move at that ply, the search below that move has updated the history
: > counts for the moves that were good at deeper levels so they can be tried
: > at this level also.  Sorting up front misses this benefit.

: You have to compare both before you can draw conclusions. Have you
: done that?

Yes.  In the beginning I used the history values to order the moves
with one big sort, then searched them.  I used a classic quick-sort
to do this, ignoring the time it took.  The issue was, sorting up
front was bad for several reasons.  (1) the first move usually is
enough to cause a cutoff (capture).  As a result, I generate captures
separately and pick the likely cutoff-causers before doing anything
else... sorting captures is quickest with a simple bubble sort because
many are generated in the right order already and the bubble sort can
exit after N operations if the list is in order.  (2) early in the
search, the history values might be zero or very low.  If you use
only what you know at the front to order the ply=2 moves, the moves
are not ordered very well and the tree gets bigger.  If you do a
simple selection sort, the first non-capture might not be best, but
the next one has a good chance since it's selected by being good at
other nodes below the first one searched.

In short, you are looking at the wrong place to speed things up.  The
selection sort is a negligible part of the total search time.  Trying to
shave it further, at the expense of even slightly worse move ordering is not
going to pay dividends...  1% faster sorting is quickly swamped by a 2%
larger tree...


: > In any case, done as we are doing this, the difference in complexity is
: > minimal...  because we don't try every move via a selection sort, only the
: > first 5 or so.  When you look at the actual instruction counts, I suspect
: > the selection sort actually executes fewer total instructions anyway, which
: > is the main consideration.  The selection sort doesn't contribute a significant
: > amount to the total search time in profiling results...

: If you suspect so, give instruction counts. It's easily quantifiable.

Here's the *complete code* for Crafty.  the main part for comparison is
the first loop below which is the selection sort code.  In that, I see the
following:

  test to see if this entry is a move or has already been searched
            before (=0)
  jump if =0 to increment to next loop iteration.
    and operation on the move fetched and tested above to get the lower
        order 12 bits used for the move history lookup.
    memory fetch to grab the history value.
    comparison to see if this is best value so far
    jump if not to loop increment
      store history value as best so far
      save pointer to the corresponding move
  loop increment
  test loop index and jump to beginning if not done

In short, very tight and cache-friendly code.  However, as I said, the
actual issue is not the sorting code, but the tree efficiency.  That's
paramount.

  case HISTORY_MOVES_2:
    bestval=0;
    bestp=0;

/* loop to find move with best history value */

    for (movep=last[ply-1];movep<last[ply];movep++)
      if (*movep) {
        index=*movep&4095;
        history_value= (wtm) ? history_w[index] : history_b[index];
        if (history_value > bestval) {
          bestval=history_value;
          bestp=movep;
        }
      }
/* test to see if we found anything with a non-zero value, if so
   use it, if not fall into the next phase which tries moves in the
   order they appear in the list.  */

    if (bestval) {
      current_move[ply]=*bestp;
      *bestp=0;
      next_status[ply].remaining++;

/* if 3 history moves don't produce a cutoff, give up and take
   moves in order.  Complexity = 3*(N-1) worst case to try three
   selection sort moves.  */

      if (next_status[ply].remaining > 3) {
        next_status[ply].phase=REMAINING_MOVES;
        next_status[ply].last=last[ply-1];
      }
      return(HISTORY_MOVES_2);
    }

: 	Marcel
: --  _   _
:   _| |_|_|
:  |_    |_     Marcel van Kervinck
:          |_|  buex95a@urc.tue.nl