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?
Move ordering question
Moderators: hgm, Rebel, chrisw
-
- Posts: 2851
- Joined: Wed Mar 08, 2006 10:01 pm
- Location: Irvine, CA, USA
-
- Posts: 44
- Joined: Wed Apr 13, 2011 12:43 pm
Re: Move ordering question
So no need to order *all* moves? Just the first 3 to 5 would be OK too?
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Move ordering question
correct...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?
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Move ordering question
Most already do this...sluijten wrote:So no need to order *all* moves? Just the first 3 to 5 would be OK too?
-
- Posts: 44
- Joined: Wed Apr 13, 2011 12:43 pm
Re: Move ordering question
sometimes it feels good to reinvent the wheel ...
-
- Posts: 4675
- Joined: Mon Mar 13, 2006 7:43 pm
Re: Move ordering question
Well, if the program somehow knew that the first move at a node was the best, then the answer is yes.sluijten wrote:Theoretically, we only have to place best move first to get the most cut-offs?
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.
-
- Posts: 27790
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Move ordering question
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.
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.
-
- Posts: 879
- Joined: Mon Dec 15, 2008 11:45 am
Re: Move ordering question
Well, of course there might be some other aspects to take into consideration.sluijten wrote:So no need to order *all* moves? Just the first 3 to 5 would be OK too?
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
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Move ordering question
... and as a side-effect, that program would already know the PV of chesssje wrote:Well, if the program somehow knew that the first move at a node was the best, then the answer is yes.sluijten wrote:Theoretically, we only have to place best move first to get the most cut-offs?
Sven