🚀 go-pugleaf

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.

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?

> 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.

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