Unordered moves phenomenon

[Cardoso]

Hi,
I gathered 50 test positions (some stable and equal and others sharper).
in order to isolate each individual move ordering algorithm, I decided to make a comparison base using just analysis with the hash move only moved to the first position.
From there I used the individual algorithms (killers/history/Counter Moves, etc) and compare to the base node count statistics of the version that just orders the hash move.
But I noticed that even the version using the hash move only had very good move ordering:
Instead of just making statistics when the first move fails high, I use stattistics for the first 4 moves.
So I have an array of 4 counters, 1st move FH, 2nd move FH, 3rd move FH...
So I went radical and removed move ordering completely.
Now just take a look at these statistics:
FHFN=59%15%7%5%
On the starting position I get 59% of FHs for the first move 15% of FHs for the second move, ....
I was expecting there percentages to be move even distributed, but when there is a FH, 59% if the time is the first move, and I can assure you the moves have the order that come from the move generator.
What is going on here ?
I even get rid of those fancy algorithms like LMR/Futility/Null move and made a plain alphabeta version because I couldn't believe my eyes.
Again, what is going on here?

best regards,
Alvaro

[elcabesa]

can you explain a little better?
I haven't understood what you mean by FH , FHFN.

[hgm]

With "removing move ordering completely" you also do not use MVV/LVA sorting on the captures?

This should normally be fatal. Engines that do not order captures in QS will run into search explosion by plunder raids at some time in almost every game. You will the suddenly see the depth drop from a reasonable value (say 11 ply) to 2 or 3 ply, sometimes even 1 ply. Of course they then usually play a blunder, and immediately lose.

QS as a capture search simply is not stable if you don't make any special attempt to put an end to plunder raids by first grabbing the Queens before anything else.

If you did not see that in any of your test positions, you were just lucky. 50 positions is not eough; games usually have more. So something that crashes you in practically every game has a good chance to be missed in 50 positions.

[Cardoso]

can you explain a little better?
I haven't understood what you mean by FH , FHFN.

Usually chess engine programmers maintain a statistic of how often the first move in the move list (after ordering) fails high.
And a reasonably number is 92%, wich means that when a fail high occurs, 92% of the time is first move on the list.
This is to have an idea on how good move ordering is on the engine.
However I decided to do this not only for move number one, but for the first 4 moves on the list.
FH = Fail High
FHFN can be: Fail High on the First Nth move.

Code: Select all

define MAXFHFMOVES 4
int64_t fail_high_first_n[MAXFHFMOVES];


			if (value > alpha) {
				bestmove = thread->currentmove[ply];
				if (value >= beta) {				
					if (NMoves(ply) > 1) {
						thread->fail_highs++;
						if (!moves_searched) {
							thread->fail_high_first_move++;							
						}
#if MAXFHFMOVES
						if &#40;moves_searched < MAXFHFMOVES&#41;  thread->fail_high_first_n&#91;moves_searched&#93;++;
#endif
					&#125;
					return value;
				&#125;
				alpha = value;
			&#125;

Somewhere else in the code I print this statistic&#58;
	string FHFN = "";
#if MAXFHFMOVES
	FHFN = "***FHFN=";
	for &#40;int i = 0; i < MAXFHFMOVES; i++) &#123;		
		FHFN += my_Str&#40;&#40;int64_t&#41;(&#40;double&#41;&#40;thread->fail_high_first_n&#91;i&#93;) / &#40;thread->fail_highs&#41;*100.0&#41;) + "% ";
	&#125;
	PrintGeneralText&#40;"fail_highs = " + my_StrComma&#40;thread->fail_highs&#41;);
#endif

[Evert]

Well, one consideration is that you don't need the "best" move to cut, just a reasonable one. A second consideration is that following a major blunder, there are probably several moves that will cut.
So this may not be so unreasonable (to be sure, 59% cuts on the first move is aweful).

[Cardoso]

With "removing move ordering completely" you also do not use MVV/LVA sorting on the captures?

This should normally be fatal. Engines that do not order captures in QS will run into search explosion by plunder raids at some time in almost every game. You will the suddenly see the depth drop from a reasonable value (say 11 ply) to 2 or 3 ply, sometimes even 1 ply. Of course they then usually play a blunder, and immediately lose.

QS as a capture search simply is not stable if you don't make any special attempt to put an end to plunder raids by first grabbing the Queens before anything else.

If you did not see that in any of your test positions, you were just lucky. 50 positions is not eough; games usually have more. So something that crashes you in practically every game has a good chance to be missed in 50 positions.

Sorry I should have said my engine is a spanish checkers engine.

[Uri Blass]

Hi,
I gathered 50 test positions (some stable and equal and others sharper).
in order to isolate each individual move ordering algorithm, I decided to make a comparison base using just analysis with the hash move only moved to the first position.
From there I used the individual algorithms (killers/history/Counter Moves, etc) and compare to the base node count statistics of the version that just orders the hash move.
But I noticed that even the version using the hash move only had very good move ordering:
Instead of just making statistics when the first move fails high, I use stattistics for the first 4 moves.
So I have an array of 4 counters, 1st move FH, 2nd move FH, 3rd move FH...
So I went radical and removed move ordering completely.
Now just take a look at these statistics:
FHFN=59%15%7%5%
On the starting position I get 59% of FHs for the first move 15% of FHs for the second move, ....
I was expecting there percentages to be move even distributed, but when there is a FH, 59% if the time is the first move, and I can assure you the moves have the order that come from the move generator.
What is going on here ?
I even get rid of those fancy algorithms like LMR/Futility/Null move and made a plain alphabeta version because I couldn't believe my eyes.
Again, what is going on here?

best regards,
Alvaro

I see nothing strange here.

with random order of moves you often get fail high in the first move simply because you do not need the best move to fail high.

The more interesting question is what is the percentage of cases that you search best move first.

You need to do a lot of additional searches to find the answer because normal search to find a move that fail high does not find the best move and you do not know if the first move that fail high is really the best move.

Uri

[Cardoso]

Well, one consideration is that you don't need the "best" move to cut, just a reasonable one. A second consideration is that following a major blunder, there are probably several moves that will cut.
So this may not be so unreasonable (to be sure, 59% cuts on the first move is aweful).

Yes I dumped some positions where the FH happened, as well as the move list.
And the dumped positions are easily failing high positions, so almost any move would fail high.
But now the question is why do these easily failing high positions occur so often?

[Cardoso]

Hi,
I gathered 50 test positions (some stable and equal and others sharper).
in order to isolate each individual move ordering algorithm, I decided to make a comparison base using just analysis with the hash move only moved to the first position.
From there I used the individual algorithms (killers/history/Counter Moves, etc) and compare to the base node count statistics of the version that just orders the hash move.
But I noticed that even the version using the hash move only had very good move ordering:
Instead of just making statistics when the first move fails high, I use stattistics for the first 4 moves.
So I have an array of 4 counters, 1st move FH, 2nd move FH, 3rd move FH...
So I went radical and removed move ordering completely.
Now just take a look at these statistics:
FHFN=59%15%7%5%
On the starting position I get 59% of FHs for the first move 15% of FHs for the second move, ....
I was expecting there percentages to be move even distributed, but when there is a FH, 59% if the time is the first move, and I can assure you the moves have the order that come from the move generator.
What is going on here ?
I even get rid of those fancy algorithms like LMR/Futility/Null move and made a plain alphabeta version because I couldn't believe my eyes.
Again, what is going on here?

best regards,
Alvaro

I see nothing strange here.

with random order of moves you often get fail high in the first move simply because you do not need the best move to fail high.

The more interesting question is what is the percentage of cases that you search best move first.

You need to do a lot of additional searches to find the answer because normal search to find a move that fail high does not find the best move and you do not know if the first move that fail high is really the best move.

Uri

You are right, the FH positions I dumped are positions in wich another move easily FH, but why do this happens so often? I mean in all positions that FH why most of them are positions where several other moves FH?

The more interesting question is what is the percentage of cases that you search best move first.

That is interesting, but to really find that we would need a full search with alpha = value and beta=MATE to confirm the first move is really the best or not. Very expensive, but maybe worth a try.

Maybe at low depths we could force finding the best move, maybe something like this:

Code: Select all

   if (value > alpha) { 
        bestmove = thread->currentmove[ply]; 
		thread->bestmove[ply] = thread->currentmove[ply]; 
		if (value >= beta) {
            // real best move search, only at low depths and in case the static evaluation is 
            // above beta by some margin, to give some degree of certainty we can have other moves 
            // that fail high 
            if &#40;depth < 4*PLY && static_eval - PAWN_VALUE/2 > beta&#41; &#123; 
               int value2 = Search&#40;thread, value, MATE, color, depth, ply + 1&#41;; 
               if &#40;value2 > value&#41; &#123; 
                  value = value2; 
                  bestmove = thread->bestmove&#91;ply+1&#93;;                      
               &#125; 
            &#125; 
             
            return value; 
        &#125;
        alpha = value; 
   &#125;

Maybe you can think of additional conditions to restrict doing the real best move search.[/quote]

[Edsel Apostol]

You are right, the FH positions I dumped are positions in wich another move easily FH, but why do this happens so often? I mean in all positions that FH why most of them are positions where several other moves FH?

Since you are not doing any move ordering at all, it is possible that the moves being tried the first few times are crappy moves. At the next ply there will be a lot of moves to counter those crappy moves even if they are also random.

What is the order in which you generate moves? Do you generate captures first? Pawn moves?