Move ordering contest

[Rebel]

Don't take the subject line too serious, it's meant as fun mainly but perhaps there is some learning effect also. So let's compare your move ordering with others and how efficient it is.

Some time ago Don courageously stated Komodo has the best move ordering of all, so Don, here is your chance to proof it

I made a little script for just 10 positions as an opening move for further discussion, on the result page suggested 2 better proposals. But for a start check it out first.

http://www.top-5000.nl/motest.htm
http://www.top-5000.nl/moresu.htm

This isn't a good way to compare move ordering efficiency between programs. The more selective searchers will prune away substantial parts of the tree, that less selective searchers will still consider. This will bias the results. You admit as much on your results page.

Your confirmation of my observation over there is an indication you are correct, also various submissions seem to confirm it. I will post the results tomorrow. What a pity.

So far, out of 8 submissions, the best one seems to be Cheese 1.5 beta at 92.04% averaged and the worst is Komodo CCT at 86.22% averaged despite something like a 700 point rating advantage. A fair comparison between programs seems problematic.

First results are up.

Perhaps there is a relationship between the higher the ELO the lower your move ordering percentage, now that would be real funny.

Took an old version (1.1) from 2005 long before I heard of LMR and other stuff what is common today. I use LMR nowadays but not aggressively and there is a drop of 1.3% (most likely) because of that, not counting some progress that has been during the years on move ordering, meaning that the real drop is somewhat higher. There obviously is a relationship, more reductions / pruning the move ordering percentage shrinks. Just look at Komodo.

My results are invalid as I did not clear the data between runs. So the final number is actually the average of all the samples.

I see. You naughty one

Nevertheless the logic is clear. When you effectively reduce and prune the bad moves, the AB cutoff at move-1 becomes under pressure, thus the percentage will lower.

[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);

[Don]

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

[petero2]

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);

If your search looks like this:

Code: Select all

int search(...) {
  ...
  for (all moves) {
    ...
    makeMove(...);
    score = -search(...);
    unMakeMove(...);
    ...
    if (score >= beta)
      return score;
    ...
  }
  ...
}

void iterativeDeepening(...) {
  ...
  while (time left) {
    depth++;
    ...
    search(...);
    ...
  }
  ...
}

Change it to this:

Code: Select all

int nCutOffs;
int nCutOffTries;

int search(...) {
  ...
  int tries = 0;
  for (all moves) {
    ...
    makeMove(...);
    score = -search(...); tries++;
    unMakeMove(...);
    ...
    if (score >= beta) {
      nCutOffs++;
      nCutOffTries += tries;
      return score;
    }
    ...
  }
  ...
}

void iterativeDeepening(...) {
  ...
  nCutOffs = nCutOffTries = 0;
  while (time left) {
    depth++;
    ...
    search(...);
    ...
  }
  ...
  printf("Branching factor at cut nodes: %.3f\n", nCutOffTries / (double)nCutOffs);
}

[petero2]

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

[Don]

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.

[petero2]

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.

It's hard to tell what is causing this. One possible explanation (just a guess) is that my program, being much weaker than your program, spends more time at uninteresting parts of the search tree, where good move ordering might be easier to achieve.

[bob]

Don't take the subject line too serious, it's meant as fun mainly but perhaps there is some learning effect also. So let's compare your move ordering with others and how efficient it is.

Some time ago Don courageously stated Komodo has the best move ordering of all, so Don, here is your chance to proof it

I made a little script for just 10 positions as an opening move for further discussion, on the result page suggested 2 better proposals. But for a start check it out first.

http://www.top-5000.nl/motest.htm
http://www.top-5000.nl/moresu.htm

This isn't a good way to compare move ordering efficiency between programs. The more selective searchers will prune away substantial parts of the tree, that less selective searchers will still consider. This will bias the results. You admit as much on your results page.

Your confirmation of my observation over there is an indication you are correct, also various submissions seem to confirm it. I will post the results tomorrow. What a pity.

So far, out of 8 submissions, the best one seems to be Cheese 1.5 beta at 92.04% averaged and the worst is Komodo CCT at 86.22% averaged despite something like a 700 point rating advantage. A fair comparison between programs seems problematic.

First results are up.

Perhaps there is a relationship between the higher the ELO the lower your move ordering percentage, now that would be real funny.

Took an old version (1.1) from 2005 long before I heard of LMR and other stuff what is common today. I use LMR nowadays but not aggressively and there is a drop of 1.3% (most likely) because of that, not counting some progress that has been during the years on move ordering, meaning that the real drop is somewhat higher. There obviously is a relationship, more reductions / pruning the move ordering percentage shrinks. Just look at Komodo.

My results are invalid as I did not clear the data between runs. So the final number is actually the average of all the samples.

I see. You naughty one

Nevertheless the logic is clear. When you effectively reduce and prune the bad moves, the AB cutoff at move-1 becomes under pressure, thus the percentage will lower.

Sorry, but I don't follow that reasoning at all. How do reductions and pruning affect which move is best and which move will cause a cutoff? Are you assuming the pruning or reductions are being done at the WRONG place???

[bob]

http://www.top-5000.nl/motest.htm

Here is a trick question related to the sample code on the above page. What does this program do?

Code: Select all

#include <stdio.h>
int main&#40;) &#123;
    float f, sum = 0;
    for &#40;f = 0; f < 20000000; f++)
        sum += f;
    printf&#40;"sum = %f\n", sum&#41;;
    return 0;
&#125;

This, perhaps, using gcc 4.7.2 on my macbook:

scrappy% ./tst
sum = 200679662551040.000000
scrappy%

I assume you would expect the thing to be done in 32 bit fp math, so that the inc by 1 turns into an inc by 0 when the decimal points are aligned using a 32 bit float??? This version of gcc (on my mac) seems to like the xmm stuff which works cleanly here.

[bob]

Loop forever?

Exactly, at least if IEEE 754 float math is used, which is the case with many compilers on standard PC hardware.

For the same reason, the sample code will give wrong results if there are more than 2^24 beta cutoffs within the 30s search time period. My program got at most 15e6 cutoffs for the 10 test positions, but a faster program could easily get wrong results.

I don't use floats for my "fail high percentage" that is output by Crafty. It has always been done, back to the cray blitz days, as

fh = 100 * fail-highs-1st / fail-highs;

with 64 bit ints, there is no danger of overflow.