🚀 go-pugleaf

news@uchinews.uchicago.edu (News System) writes:
>
> In article <2s678r$h7m@nuscc.nus.sg> nsrccks@leonis.nus.sg (Chua Kong Sian) writes:
> 
>    I'll talk about the pick() routine first as its easier :).  The post
>    is right that pick() is a bubble sort (or maybe selection sort which
>    is just as bad).  However most of the time it is unnecessary to
>    completely sort the movelist.  This is because if a move is "picked"
>    and causes a beta cut, then the rest of the moves need not be searched
>    and thus any effort spent in sorting them would have been wasted.  So
>    IMHO, I think pick() works pretty efficiently.
> 
> If you're going to sort a short list with an O(n^2) time algorithm,
> its better to use insertion sort. That way, if the list is already
> close to being in order, you get close to linear performance.
> 
> --
> Dietrich Kappe
> kap1@wimpy.cpe.uchicago.edu
> -finger for PGP public key-

I've got my own chess program I'm building.  One of the first things I
tried to do to get performance out of it was make this "sort" super-
spiffy.  Wrong!

Kong Sian is right.  You don't want to sort the move list here at all.
Here are the cases:

1) You get a cutoff on the first move you look at.  This involves N-1
compares if you do a sequential search (like "pick"), and happens a lot
of the time.  If you'd fully sort the move list in this case you will
do a heck of a lot more than N-1 compares, I don't care how good your
sort is.

2) You get a cutoff in the first few moves.  Same basic deal as above.

3) You have to look at all of the moves.  You still want to look at the
moves in best-first order if you can, but after you've looked at the
best move it doesn't matter any more what order you look at the moves
in.  In this case the fully sorted list is "best", but you still don't
need to sort the list fully in practice.  I use something similar to
"pick", but I only call it to pick the first few candidate moves, after
that I just grab them sequentially.  I figure that if my top five or so
candidates don't produce the best move, my sort key is probably useless.

Given N=35, show me a sort that works in lots less than 5N compares and
I'll use it.  If you can't do this, you're slower.

bruce