Selective techniques

[mcostalba]

How do you define "move ordering success"? Is this percentage of nodes where you have searched the eventual best move first?

Yes, exactly.

No

I guess that you mean to percentage of nodes when first move fail high.

first move fail high does not mean searching the best move first because it is possible that there is a better move that can also fail high but you do not search.

Uri

At PV nodes, where all moves have to be searched, we still want to search the best move first, don't we?

So to be more precise, the number of nodes where the first move we search either lets us cut off (failing high) or stays the best move in case we don't fail high at all.

At PV nodes the first move is the PV move so of course is the best. It is not very clear to me what you are trying to say.

Anyhow, move ordering is very important especially in side branches, much less in PV nodes.

First because PV nodes are much much less then non-PV nodes, second because PV nodes are supposed to be like ALL nodes, i.e. they very rarely should fail high and if they do they should do with the first move that is the PV.

The problem of move ordering is mainly related to side branches (non PV nodes).

[OliverUwira]

The IMHO correct way to measure move ordering is to calculate the average move count of the move that produces a cut-off, i.e. the move that fails high.

Sometime it will be the first, sometime move 5 or move 12. Every time a move produces a cut-off then update the average move count:

Code: Select all

cutOffNr++;
cutOffDistance += moveIndex;

At the end the metric to evaluate move ordering is:

Code: Select all

    avgDistance = cutOffDistance / cutOffNr

The smaller the better of course.

This is actually how I am doing it. What would you say is an acceptable value for this ratio?

Only, just in the other thread I have asked where the cause of my engine's inability of reaching a greater depth more quickly might lie, and I suspected it might be search tree problems....

Now this measure you have proposed is around 1.25 to 1.3 for my engine... I wonder if this is all right. Actually it should be, but still I'm having almost the same problems like the ones Luca explained above.

I'm awaiting an eye opener, like you saying Stockfish has this measure at 1.10 or something like that (-:

[mcostalba]

I'm awaiting an eye opener, like you saying Stockfish has this measure at 1.10 or something like that (-:

In Stockfish is 1.37526

I also calculated another interesting statistic, that is the average as before but _only_ when the cut-off move is NOT the first.

In this case the average is 5.47242 but it happens very seldom because in 91% of cut nodes the first move is the cut move.

If you are slow to go deep perhaps you don't prune enough. For instance in Stockfish there is a terribly crude pruning rule that is:

Code: Select all

          // History pruning. See ok_to_prune() definition
          if (   moveCount >= 2 + int(depth)
              && ok_to_prune(pos, move, ss[ply].threatMove, depth)
              && bestValue > value_mated_in(PLY_MAX))
              continue;

This rule it means that if you are for instance at depth 2*OnePly (OnePly in Stockfish is 2) then after the move 2 + 4 = 6 you prune everything !!!!!

The only moves that are not pruned are the ones with a good history so that ok_to_prune() returns false.

You can imagine that with such a rule it is very easy to go deep with search and incredibly (at least for me) search quality doesn't seems to be too badly affected.

[metax]

Thank you for the answers.

In Stockfish is 1.37526

I also calculated another interesting statistic, that is the average as before but _only_ when the cut-off move is NOT the first.

In this case the average is 5.47242 but it happens very seldom because in 91% of cut nodes the first move is the cut move.

I measured this in ChessMind: The cut-off average is around 1.6, which seems to be very bad. The average when the cut-off move is not the first is 5.2 in ChessMind, but that happens more often than in Stockfish because only in 80-85% the cut-off move is the first.

If you are slow to go deep perhaps you don't prune enough. For instance in Stockfish there is a terribly crude pruning rule that is:

Code: Select all

          // History pruning. See ok_to_prune() definition
          if (   moveCount >= 2 + int(depth)
              && ok_to_prune(pos, move, ss[ply].threatMove, depth)
              && bestValue > value_mated_in(PLY_MAX))
              continue;

This rule it means that if you are for instance at depth 2*OnePly (OnePly in Stockfish is 2) then after the move 2 + 4 = 6 you prune everything !!!!!

The only moves that are not pruned are the ones with a good history so that ok_to_prune() returns false.

You can imagine that with such a rule it is very easy to go deep with search and incredibly (at least for me) search quality doesn't seems to be too badly affected.

And you are sure that this is NOT very tactically dangerous?! Seems incredible for me...

Then I should implement history heuristic anyway to make this pruning possible?

edit:

Code: Select all

&& bestValue > value_mated_in(PLY_MAX)

value_mated_in(PLY_MAX) returns the value for _being_ checkmated, not for checkmating yourself, right? Otherwise that would bring almost no performance.
Why is this condition necessary?

[opraus]

If your best score so far is getting mated, you want to continue to look

[OliverUwira]

I'm awaiting an eye opener, like you saying Stockfish has this measure at 1.10 or something like that (-:

In Stockfish is 1.37526

I also calculated another interesting statistic, that is the average as before but _only_ when the cut-off move is NOT the first.

In this case the average is 5.47242 but it happens very seldom because in 91% of cut nodes the first move is the cut move.

If you are slow to go deep perhaps you don't prune enough. For instance in Stockfish there is a terribly crude pruning rule that is:

Code: Select all

          // History pruning. See ok_to_prune() definition
          if (   moveCount >= 2 + int(depth)
              && ok_to_prune(pos, move, ss[ply].threatMove, depth)
              && bestValue > value_mated_in(PLY_MAX))
              continue;

This rule it means that if you are for instance at depth 2*OnePly (OnePly in Stockfish is 2) then after the move 2 + 4 = 6 you prune everything !!!!!

The only moves that are not pruned are the ones with a good history so that ok_to_prune() returns false.

You can imagine that with such a rule it is very easy to go deep with search and incredibly (at least for me) search quality doesn't seems to be too badly affected.

Well, it seems that my move ordering is not too bad apparently, at least for nodes where I want a cut off quick. Come to that, I actually sometimes try two hash moves first, which might be beneficial. This happens if the "replace-always" and the "replace-if-deeper" entries hold two different moves. I'll check how often this is the case (-:

What apart from that comes to my mind is that too many researches in PVS could also be the cause of my problems. To get a cutoff, an OK move as the first try might often suffice, but at a PV node, the penalty for having to open the search window again and doing a research must surely be significant.

[mcostalba]

If your best score so far is getting mated, you want to continue to look

It was reported that the relased 1.5.1 sometime says that has found a mate say in 8 moves and then the mate disappears at the next opponent's move.

It was reported also that in some test positions the shown moves-to-mate count is not the correct one.

With this fix (that is not in the released sources) theese strange behaviours were all fixed and the performance impact is kept to a bare minimum.

Yes, the rationale is that if you are in a mated position you don't want to prune any possible _escape_ move otherwise you could end up the move's loop for that node with none found and report to the caller you are in a mated positions while actually this could not be true.

[metax]

I now try captures before killer moves (and exclude them from the killers), which gave me some performance. I now reach ply 10 with 1.7 million nodes from the starting position, which is at least better than before. But remarkably, this doesn't show up in the statistics: The move ordering success percentage has dropped from 86% to 84% and the cut-off average is still 1.58 (same as before). How is that possible?

[OliverUwira]

I now try captures before killer moves (and exclude them from the killers), which gave me some performance. I now reach ply 10 with 1.7 million nodes from the starting position, which is at least better than before. But remarkably, this doesn't show up in the statistics: The move ordering success percentage has dropped from 86% to 84% and the cut-off average is still 1.58 (same as before). How is that possible?

I would run a more significant test. Especially the starting position might not be the best position to try captures before killer moves.

The advantage of non-capture killer moves is that they tend to contain strong positional moves or quiet threats like trapping e.g. a white bishop at b3 and black pawns at a6,b5,c5 by means of c5-c4. At nodes where you don't have a hash move, you'll have difficulty bringing these moves up front in your move list without having them in a killer slot.

And especially from the starting position, you'll have plenty more good quiet moves as in, say, a wild middlegame melêe.

I take it that you only try the good captures before the killers?

[metax]

I try all captures before the killers because I haven't got any SEE yet. But that was not my point. I wondered why the statistics didn't get better, but the _performance_ increased anyway, even from the starting position.