Speed up UpdatePieceList
Vincent Diepeveen
I discovered in GNU-chess v 4.0 (for dos)
something that can be speeded up( i am sorry for my bad
english ), hopefully i didn't find out the speed-up as second,
however it is a little speed up, but highly effective in
Nullmove/Quiescence search, as there will be captured many
pieces over there.
In UpdatePieceList( .. ) you can see something like
UpdatePieceList( short int sq, short int iop .. ) {
short int i;
..
if( iop == 1 ) { /* remove a piece from the piecelist */
..
for( i = Pindex[ sq ] ; i < PieceCnt[ side ] ; i++ ) {
Pindex[ i ] = i;
PieceList[ side ][ i ] = PieceList[ side ][ i+1 ];
}
...
}
else {
..
..
}
}
This slow 'shifting up the array PieceList' to fill the hole
PieceList[ side ][ i ] is not practically.
It is easier and faster to say just:
..
if( iop == 1 ) {
i = Pindex[ sq ];
if( i < PieceCnt[ side ] ) {
PieceList[ side ][ i ] = PieceList[ side ][ PieceCnt[ side ] ];
Pindex[ PieceList[ side ][ i ] ] = i;
}
PieceCnt[ side ]--;
}
else {...
....
Greetings, Vincent Diepeveen.
email: vdie...@cs.ruu.nl
--
+--------------------------------------+
|| email : vdie...@cs.ruu.nl ||
|| fidonet: 2:280/206.23 ||
+======================================+
DSMJL
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).
-->Mark
Vincent Diepeveen
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.
Did different persons both carrying different ideas wrote these routines?
Greetings, Vincent Diepeveen.
David Spencer
>
> In <2rqmo3$3...@search01.news.aol.com> ds...@aol.com (DSMJL) writes:
>
> >In article <CoGEL...@cs.ruu.nl>, vdie...@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
--
+ ------------------------+
| David Spencer |
| david-...@retix.com |
+ ------------------------+
Chua Kong Sian
: - 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
Chua Kong Sian
: 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.
After taking a look at the pl70 code, I discovered that the change has
already been implemented. This means that UpdatePieceList is pretty
efficient as it is.
Kong Sian
Dietrich J. Kappe
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
ka...@wimpy.cpe.uchicago.edu
-finger for PGP public key-
Bruce Moreland
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