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.

[Rebel]

I think a better measure might be to give the second move half credit, the 3rd move 1/4 credit, and so on. A BIG part of the move ordering in Komodo is how the moves that are NOT either the history move or a capture or killer. This would impact that, but I don't think it would show the full power.

I think you are right on both accounts.

[petero2]

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;

[hgm]

Loop forever?

As to the move ordering problem: It is not the probability of the first-move cut, but the average number of moves that is related to tree size. (80% first move and the remaining 20% second move would be better than 90% first move and the remaining 10% equally distributed between move 2-30: 1.2 moves vs 2.5 move). So it would be better to increase count1 by the number of searched moves in a cut-node, and count2 by the total nnumber of moves in that node, and print count1*100/count2 afterwards.

In the face of reductions, even that is meaningless: even if the null move would have only 60% chance on a cutoff, and the best capture would have 90% chance, it is better to try the null move first if the reduction would make its search 10 times cheaper: 0.6*0.1 + 0.4*0.9*1.1 = 0.42, while 0.9*1 + 0.1*0.6*1.1 = 0.966, more than 2 times as large.

[petero2]

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.

[rjgibert]

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.

[Don]

I think a better measure might be to give the second move half credit, the 3rd move 1/4 credit, and so on. A BIG part of the move ordering in Komodo is how the moves that are NOT either the history move or a capture or killer. This would impact that, but I don't think it would show the full power.

I think you are right on both accounts.

I said that wrong but I think you get the point. I meant after the hash move, captures and killers we have all the rest of the moves, and that is critical to Komodo. Most programs do the hash, captures and killers more or less the same and correctly but many don't do well with the other moves and that is a really big deal.

But I think there is a reasonable way to "instrument" move ordering. I suggested the half credit for each successive move but perhaps HG's idea is better. It comes down to the nodes where you actually get cutoffs - measuring the average number of moves you had to play to get there or perhaps or some weighted average of those. If I understand HG he would measure it based on how many choices you had? I'm going to reread his suggestion.

[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.

[Don]

I think a better measure might be to give the second move half credit, the 3rd move 1/4 credit, and so on. A BIG part of the move ordering in Komodo is how the moves that are NOT either the history move or a capture or killer. This would impact that, but I don't think it would show the full power.

I think you are right on both accounts.

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?

[Don]

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.