🚀 go-pugleaf

David Spencer (dspencer@mproj.retix.com) wrote:

: In article <CqB7u6.Ftu@cs.ruu.nl> vdiepeve@cs.ruu.nl (Vincent Diepeveen) writes:


: > 
: > In <2rqmo3$34j@search01.news.aol.com> dsmjl@aol.com (DSMJL) writes:
: > 
: > >In article <CoGEL1.5Ao@cs.ruu.nl>, vdiepeve@cs.ruu.nl (Vincent
: > >Diepeveen) writes:
: > >
: > >The reason the present UpdatePieceList is the way it is goes:
: > >
: > >It keeps the piece list in an order that is more effective in keeping
: > >the
: > >tree small (efficiency).
: > 
: > Why does there exist a function 'pick' that gets the best
: > move from the movelist: if all moves are picked, then you have
: > a bubblesort( after experimenting in my own programm with heapsort,
: > my conclusion was that this pick function, so bubblesort, was  
: > better as any other sort, as memcpy is the most slowest command on the PC, 
: > except HALT .....-)))
: > of the list, in both cases it doesn't matter the way it is generated.

: I believe the answer is that, in general, a large % of the time the
: first move will be the "best" so that it's a waste of time to sort
: when the first move will do.  And if the 1st isn't the best, then the
: 2nd best probably is....this of course is the whole point of move
: ordering heuristics.

: 		- Dave

I didn't see the first 2 post, so my answer may be way off course.
There appears to be 2 questions, whether the UpdatePieceList can be
speeded up and whether pick() is efficient.

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.

As for the UpdatePieceList() routine, it is divided into 2 parts.
One part is when a capture move is unmade.  In this case, the captured
piece is simply placed right at the end of the list.  The other part
is when a capture move is made.  In the current implementation, if the
captured piece lies in the middle of the list, all the pieces after
it is shifted up to fill the empty slot.  This is of course inefficient.
It would be easier if the piece at the end of the slot is moved to the
empty slot.  

Note the the order of the pieces in the PieceList does not affect the
move ordering significantly.

I will try to see if I can speed up the UpdatePieceList() routine and
post a patch and some reports here.  

Regards.

Kong Sian