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
Unordered moves phenomenon
Moderators: hgm, Rebel, chrisw
-
- Posts: 362
- Joined: Thu Mar 16, 2006 7:39 pm
- Location: Portugal
- Full name: Alvaro Cardoso
-
- Posts: 855
- Joined: Sun May 23, 2010 1:32 pm
Re: Unordered moves phenomenon
can you explain a little better?
I haven't understood what you mean by FH , FHFN.
I haven't understood what you mean by FH , FHFN.
-
- Posts: 27795
- Joined: Fri Mar 10, 2006 10:06 am
- Location: Amsterdam
- Full name: H G Muller
Re: Unordered moves phenomenon
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.
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.
Last edited by hgm on Tue Oct 03, 2017 8:16 pm, edited 1 time in total.
-
- Posts: 362
- Joined: Thu Mar 16, 2006 7:39 pm
- Location: Portugal
- Full name: Alvaro Cardoso
Re: Unordered moves phenomenon
Usually chess engine programmers maintain a statistic of how often the first move in the move list (after ordering) fails high.elcabesa wrote:can you explain a little better?
I haven't understood what you mean by FH , FHFN.
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 (moves_searched < MAXFHFMOVES) thread->fail_high_first_n[moves_searched]++;
#endif
}
return value;
}
alpha = value;
}
Somewhere else in the code I print this statistic:
string FHFN = "";
#if MAXFHFMOVES
FHFN = "***FHFN=";
for (int i = 0; i < MAXFHFMOVES; i++) {
FHFN += my_Str((int64_t)((double)(thread->fail_high_first_n[i]) / (thread->fail_highs)*100.0)) + "% ";
}
PrintGeneralText("fail_highs = " + my_StrComma(thread->fail_highs));
#endif
-
- Posts: 2929
- Joined: Sat Jan 22, 2011 12:42 am
- Location: NL
Re: Unordered moves phenomenon
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).
So this may not be so unreasonable (to be sure, 59% cuts on the first move is aweful).
-
- Posts: 362
- Joined: Thu Mar 16, 2006 7:39 pm
- Location: Portugal
- Full name: Alvaro Cardoso
Re: Unordered moves phenomenon
Sorry I should have said my engine is a spanish checkers engine.hgm wrote: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.
-
- Posts: 10282
- Joined: Thu Mar 09, 2006 12:37 am
- Location: Tel-Aviv Israel
Re: Unordered moves phenomenon
I see nothing strange here.Cardoso wrote: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
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
-
- Posts: 362
- Joined: Thu Mar 16, 2006 7:39 pm
- Location: Portugal
- Full name: Alvaro Cardoso
Re: Unordered moves phenomenon
Yes I dumped some positions where the FH happened, as well as the move list.Evert wrote: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).
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?
-
- Posts: 362
- Joined: Thu Mar 16, 2006 7:39 pm
- Location: Portugal
- Full name: Alvaro Cardoso
Re: Unordered moves phenomenon
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?Uri Blass wrote:I see nothing strange here.Cardoso wrote: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
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
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.The more interesting question is what is the percentage of cases that you search best move first.
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 (depth < 4*PLY && static_eval - PAWN_VALUE/2 > beta) {
int value2 = Search(thread, value, MATE, color, depth, ply + 1);
if (value2 > value) {
value = value2;
bestmove = thread->bestmove[ply+1];
}
}
return value;
}
alpha = value;
}
-
- Posts: 803
- Joined: Mon Jul 17, 2006 5:53 am
- Full name: Edsel Apostol
Re: Unordered moves phenomenon
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.Cardoso wrote: 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?
What is the order in which you generate moves? Do you generate captures first? Pawn moves?