Move ordering question

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
sluijten
Posts: 44
Joined: Wed Apr 13, 2011 10:43 am
Contact:

Move ordering question

Post by sluijten » Sat Jun 11, 2011 3:19 am

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?

Dirt
Posts: 2851
Joined: Wed Mar 08, 2006 9:01 pm
Location: Irvine, CA, USA

Re: Move ordering question

Post by Dirt » Sat Jun 11, 2011 3:52 am

Yes.

sluijten
Posts: 44
Joined: Wed Apr 13, 2011 10:43 am
Contact:

Re: Move ordering question

Post by sluijten » Sat Jun 11, 2011 3:57 am

So no need to order *all* moves? Just the first 3 to 5 would be OK too?

bob
Posts: 20636
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Move ordering question

Post by bob » Sat Jun 11, 2011 4:34 am

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...

bob
Posts: 20636
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Move ordering question

Post by bob » Sat Jun 11, 2011 4:34 am

sluijten wrote:So no need to order *all* moves? Just the first 3 to 5 would be OK too?
Most already do this...

sluijten
Posts: 44
Joined: Wed Apr 13, 2011 10:43 am
Contact:

Re: Move ordering question

Post by sluijten » Sat Jun 11, 2011 4:51 am

sometimes it feels good to reinvent the wheel ... ;-)

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Move ordering question

Post by sje » Sat Jun 11, 2011 6:05 am

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.

User avatar
hgm
Posts: 23772
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Move ordering question

Post by hgm » Sat Jun 11, 2011 6:35 am

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.

User avatar
Desperado
Posts: 638
Joined: Mon Dec 15, 2008 10:45 am

Re: Move ordering question

Post by Desperado » Sat Jun 11, 2011 7:44 am

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

Sven
Posts: 3829
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: Move ordering question

Post by Sven » Sat Jun 11, 2011 9:31 pm

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

Post Reply