Move ordering contest

[michiguel]

So I propose we try just averaging the number of moves we had to play to get a cutoff - if no cutoff we don't average anything.

Anyone game?

I get this:

Code: Select all

pos  cutoffs     tries     bf  move  bm
1   10233881  12335221  1.205  exd4  Rxb4
2    7713263   9606398  1.245  O-O   O-O
3    7540416   8878716  1.177  Be2   Bxe4
4    7178019   9486906  1.322  Bxg6  Bxg6
5    8093288   9510076  1.175  b4    b4
6   10000027  11317711  1.132  f3    f3
7   13452869  15645366  1.163  Kg3   Kg3
8   13682823  15647401  1.144  Kg3   Kg3
9    8559713   9923587  1.159  c5    c5
10   8891653  10324336  1.161  Be2   Nxe6

I hope this means that Komodo's move ordering could be improved. This would be really good news for me. It looks like your numbers are better than mine. But somehow I expect that it will not turn out that way. Probably some detail of how pruning or LMR is done will make this invalid for comparison from one program to another.

I think we are overlooking a critical issue. The obtain a cut off, you can spend one move or more, and you are measuring the ratio between those two options. However, in many cases you can spend ZERO moves to obtain a cut off, and that is not being taken into account. When? hashtable cut offs, null move cut offs, and pruning methods based on eval (stand pat like methods). The better the engine, the more cut offs are obtain with ZERO moves. That of course is at the expense of number of cut offs with ONE move, so... it is reasonable that Komodo gets a lower efficiency ratio number. We should include a ratio with cut offs with ZERO moves compared to more.

If we have

Engine A (cut offs at moves)
0: **********************
1: ***************
2: ***
3: *
4: *
etc

Engine B (cut offs at moves)
0: *****
1: **************************
2: ***
3: *
4: *
etc

Engine A is better than B but with the ratio we are talking about, it looks worse since the column at "0" is not taken into account.

Miguel

[tpetzke]

Hi,

what does your color coding in the average column mean ? Is it an indication about the number of solved positions ?

Thanks
Thomas...

[Rebel]

Hi,

what does your color coding in the average column mean ? Is it an indication about the number of solved positions ?

Hi Thomas,

The grey exclusive ProDeo to highlight the drop down during the years.

Yellow - above 90% what was quite normal once.

Blue - below 90% the new road CC seems to take.

Green - Komodo's extreme 86%

Number of solutions has given no attention.

[Rebel]

I will propose a really simple alternative. Suppose we simply average the move number of the cutoff? Komodo don't know how many legal moves there are in a position because we don't generate them unless we have to, so HG's idea is not very workable. I could still do it the HG way but I would have to generate and count which would slow down the program a lot and be a little messy.

So I propose we try just averaging the number of moves we had to play to get a cutoff - if no cutoff we don't average anything.

Anyone game?

Please modify the below pseudo code.

Code: Select all

double search_efficiency_1, search_efficiency_2 = 0;   // initialize

if ( score >= beta )                                   // cutoff
 { search_efficiency_1++; 
   if ( move_count == 1 ) search_efficiency_2++; }

double f;                                              // calculate and display percentage
f = ( search_efficiency_2*100 ) / search_efficiency_1;
printf("Search Efficiency  : %.2f%% ",f);

Here is those same 10 positions when I take the AVERAGE move number of the cutoff. I think this will be much more meaningful. (I also clear the data between runs

I would expect any reasonable program to get an average cutoff of less than 2 easily. And I'm not sure even this method is ideal but it's surely better. Note: the best you could score on this is 1.0 and only if you always get a cutoff on the first move:

Search Efficiency : 1.321
Search Efficiency : 1.245
Search Efficiency : 1.254
Search Efficiency : 1.300
Search Efficiency : 1.236
Search Efficiency : 1.282
Search Efficiency : 1.232
Search Efficiency : 1.254
Search Efficiency : 1.251
Search Efficiency : 1.259

Okay, just to be sure I need a confirmation the new code is correct before I make a new page.

Code: Select all

double search_efficiency_1, search_efficiency_2 = 0;   // initialize

if ( score >= beta )                                   // cutoff
 { search_efficiency_1++;  
   search_efficiency_2 += move_count }    // *** changed ***

double f;                                              // calculate %
f = ( search_efficiency_2*100 ) / search_efficiency_1;
printf("Search Efficiency  : %.2f%% ",f);

[Rebel]

I think we are overlooking a critical issue. The obtain a cut off, you can spend one move or more, and you are measuring the ratio between those two options. However, in many cases you can spend ZERO moves to obtain a cut off, and that is not being taken into account. When? hashtable cut offs, null move cut offs, and pruning methods based on eval (stand pat like methods). The better the engine, the more cut offs are obtain with ZERO moves. That of course is at the expense of number of cut offs with ONE move, so... it is reasonable that Komodo gets a lower efficiency ratio number. We should include a ratio with cut offs with ZERO moves compared to more.

Suggestion, we only measure till move_count=5. If we are at the end of the move list we add 6.

Changes are marked with ***

Code: Select all

double search_efficiency_1, search_efficiency_2 = 0;   // initialize 

if ( score >= beta )                                   // cutoff 
 { search_efficiency_1++;  
   if (move_count<=5) search_efficiency_2 += move_count; }    // ***

end of move list : search_efficiency_2 += 6  // ***

double f;                                              // calculate % 
f = ( search_efficiency_2*100 ) / search_efficiency_1; 
printf("Search Efficiency  : %.2f%% ",f);

[Evert]

This just measures % of cutoffs caused by the first move, right? That's part of Jazz' standard output (suppressed under XBoard though). For this set of positions the lowest I get is 87.6% (position 10) and the highest if 94.4 (position 8). Most of the other ones are 89% or better.

I have to ask though: how serious is the "best move" listed here? Jazz only "gets" 2/10 of them.

[hgm]

Why would you do that? Seems to me this completely spoils any significance of the measurement. What makes the difference between a good and a very poor move ordering is whether in nodes where null, hash and killers do not work you will get your cutoff on average after 8 moves or after 20. Almost every engine does the first 6 moves in exactly the same order anyway.

Some other points of concern:

Engines might do null-move pruning in a different part of the code as beta cutoffs on normal moves (as you need a different MakeMove routine for null move, and you don't have to increase alpha if the null move scores above it, etc.). Should this code patch also count cutoffs due to null move, and should the null move be counted in the node's move_count?

How about stand-pat cutoffs? Should these be counted as a cutoff after 0 moves?

[hgm]

That's part of Jazz' standard output (suppressed under XBoard though).

Note that if you consider this important info, there is nothing against printing it in the Thinking Output as part of the PV field (as long as you enclose it in braces, so it will look as a PGN comment when XBoard tries to parse the PV).

If you don't want to print it with every new PV, but (say) only after the search, you can emit a dummy Thinking Output line that has score = nodes = time = 0 (so just the latest depth and the PV field), and XBoard will treat the PV field as an 'info string', displaying it in the Engine Output window over the full width, ignoring it for the purpose of PV parsing.

[tpetzke]

I have to ask though: how serious is the "best move" listed here? Jazz only "gets" 2/10 of them.

iCE finds 5, Dirty 6 and Texel (I think) 7.

In one of the unsolved positions I gave iCE a bit more time and it found the move with an additional ply (48 seconds). So I guess the given best moves are somehow correct.

Thomas...

[Uri Blass]

I think that numbers are meaningless here.

I suspect that an engine with only material evaluation is going to have better move ordering by your definition because in most cases it is going to start with a move that does not lose material based on the depth that it can see so the move is going to create a cutoff.

More extreme example is an engine that has draw evaluation for every position that is not checkmate.

I suspect that this engine may show almost always cutoff in the first move
and it does not mean a good move ordering.