🚀 go-pugleaf

Yves Debillo�z (101361.2061@CompuServe.COM) wrote:
: brucemo <brucemo@nwlink.com> wrote in article 
: <32B864E7.2A6E@nwlink.com>...
: 

: Sorting seems ok for the main moves, it is not important to sort 
: bad moves.
: 

: Can we consider updating the algorithm in order to stop after 'n' 
: good
: moves are found.
: 

: -- 
: Yves Debillo�z, Belgium
: 101361.2061@compuserve.com
: yde@ficsgrp.com
: http://ourworld.compuserve

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.

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.

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