Page 1 of 1

Move ordering question

Posted: Sat Jun 11, 2011 3:19 am
by sluijten
Let's assume we always search the best move first.
If that is the case, then the order of the remaining moves does not matter anymore, right?
Theoretically, we only have to place best move first to get the most cut-offs?

Re: Move ordering question

Posted: Sat Jun 11, 2011 3:52 am
by Dirt
Yes.

Re: Move ordering question

Posted: Sat Jun 11, 2011 3:57 am
by sluijten
So no need to order *all* moves? Just the first 3 to 5 would be OK too?

Re: Move ordering question

Posted: Sat Jun 11, 2011 4:34 am
by bob
sluijten wrote:Let's assume we always search the best move first.
If that is the case, then the order of the remaining moves does not matter anymore, right?
Theoretically, we only have to place best move first to get the most cut-offs?
correct...

Re: Move ordering question

Posted: Sat Jun 11, 2011 4:34 am
by bob
sluijten wrote:So no need to order *all* moves? Just the first 3 to 5 would be OK too?
Most already do this...

Re: Move ordering question

Posted: Sat Jun 11, 2011 4:51 am
by sluijten
sometimes it feels good to reinvent the wheel ... ;-)

Re: Move ordering question

Posted: Sat Jun 11, 2011 6:05 am
by sje
sluijten wrote:Theoretically, we only have to place best move first to get the most cut-offs?
Well, if the program somehow knew that the first move at a node was the best, then the answer is yes.

However, there is no such guarantee.

Most programs will try a full ordering at the root and possibly at each PV node in a PVS-type search. The idea here is that a fail-high on a zero-width search means a re-search at PV nodes and when this happens, it's better to have it happen sooner rather than later to have a chance to raise alpha (and possibly beat beta as well to make for a cut-off).

Also, the sooner a possible move change at the root occurs, the better the chance that it will occur prior to hitting some time limit.

Re: Move ordering question

Posted: Sat Jun 11, 2011 6:35 am
by hgm
Note, however, that putting the (scorewise) best move first doesn't necessarily give you the smallest tree. If a move with lower score still scores above beta, and has a much smaller tree, it would be preferable to search that first.

This is why we order null move before all others. It is seldomly the best, but, due to the reduction, has by far the smallest tree.

Similarly, if the best move would be delivering check, and you do check extension, it would not be such a hot move to try first. If you are ready substantially ahead, but cannot afford a null move becase the previous opponent move happened to attack one of your heavy pieces, and there are no hostages to execute, the most profitable cut-move candidate would be one that withdraws the piece to a really safe place behind your own lines, even if that is a poor move mobility or piece-square-wise. because then you are less likely to run into new attacks on it, for which you again have to take action rather than null moving, as you would when hanging around in the center. Hit and run! It is a strategic mistake to try to keep hitting after a successful hit.

Re: Move ordering question

Posted: Sat Jun 11, 2011 7:44 am
by Desperado
sluijten wrote:So no need to order *all* moves? Just the first 3 to 5 would be OK too?
Well, of course there might be some other aspects to take into consideration.

just my 2 cents :)

cent 1:

Think of LMR, which is based on the assumption that the moves in front
have a higher probability to improve alpha or to find a beta cut.

So if you build your reduction scheme on movecount and dynamic R for
_lateMoves_ , and you want to be more correct _statistically_ , i am sure
it is better to order "all" moves.

cent 2:

if your intention is to gain speed by saving _move ordering overhead_ ,
imho there are more _speed sensitive_ parts which can be improved.
The reason is because you spend most of the time in quiescence nodes,
where you (i think) normally only order small capture lists, which are relative short anyway. The _inner_ nodes wont save you _much_ time,
and therefore full move ordering might be the better choice.

regards Michael

Re: Move ordering question

Posted: Sat Jun 11, 2011 9:31 pm
by Sven
sje wrote:
sluijten wrote:Theoretically, we only have to place best move first to get the most cut-offs?
Well, if the program somehow knew that the first move at a node was the best, then the answer is yes.
... and as a side-effect, that program would already know the PV of chess ;-)

Sven