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

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

[F. Bluemers]

I had similar code already (first move %) in Dirty.
No special treatment for positions with one move though:
hash 128:
91.89
93.04
93.41 wrong move (Be2)
88.31
94.91 Wrong move (Ne4)
93.06 Wrong move (Rc1)
89.43
94.63
95.45
94.43 Wrong move(Be2)

Best
Fonzy

[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

Hi Ed,

I cannot think of a way to prove which program has the best move ordering. Neither can I prove that Komodo has great move ordering. If I said Komodo has the best move ordering of all it was a guess as its almost an unprovable assertion since so much is going on inside any good chess program. It's a fair bet to claim any top 5 program has superior move ordering to most other chess programs.

In the development of BeeKay I discovered how enormously the program benefits from move ordering however. After having basic good move ordering (all the standard things with hash table move and capture ordering, killers, etc) I added all the stuff that affects the ordering of the "other" moves and the gain was astounding. So move ordering beyond the basics is a critical necessity for building a top chess program.

Note that LMR and forward pruning is strongly affected by move ordering - so they work hand in hand, you cannot have one with the other and do it well.

I don't see any problem with taking the test, I'll give it a try, but I will have to do this after the MP release as I must not be distracted before that. Please remind me if I forget.

Don

[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

I ran the test as it was easy enough to do, so you may post the numbers whenever you get to it.

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

Why is this a problem? He is simply measuring "when you get a fail high, what percentage of the time is it on the first move searched?" You can prune whatever you want, but you STILL get fail highs. The higher this percentage, the better a parallel search will work and the closer the tree size approaches the optimal (minimal) tree that must be searched.

[bob]

A few notes here, since I have done this zillions of times now...

(1) the set of positions is important. If you have one where a program changes its mind many times near the end, this percentage will drop. If a program is locked on a single move for the entire time, the percentage will be pretty high. That makes the test sensitive to evaluation AND search differences between two programs, more than the actual move ordering.

(2) fixed depth can also influence the results. As can non-fixed depth. For the same issues given in (1). If the depth is not enough to find a different move, the percentage will be high. If the depth is just enough so that you begin to realize (or actually see) that a different move is best, the percentage will drop. If the depth goes beyond that which is needed to find the best move, it climbs again. This makes it just as sensitive to other parts of the program (eval, search, extensions, reductions. pruning) as it is sensitive to actual move ordering...

(3) you are obviously correct that 10 is not enough. I have a bunch of randomly chosen positions from GM-level games that might work. They were chosen at random between moves 10 (or so) and 40 (or so), with side to move chosen randomly as well (the positions are simply chosen from the positions between moves 10 and 40, with the correct side to move).

However, I don't think there is a hill of beans difference between programs today. Hash, captures first, then killers is used by everybody, and that gets almost everything there is to get. Anything that improves ordering below that point is NOT going to influence this fail-high percentage significantly, it is already too late...

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

Why is this a problem? He is simply measuring "when you get a fail high, what percentage of the time is it on the first move searched?" You can prune whatever you want, but you STILL get fail highs. The higher this percentage, the better a parallel search will work and the closer the tree size approaches the optimal (minimal) tree that must be searched.

I suspect this is a relatively fair comparison between 2 versions of the same program, but I don't see how it can be used to prove one program has better move ordering. The scoring resolution is just one example of how this would not be valid.

However, it may be a very good way to determine if you have made improvements in the move ordering - this is something that I have often done with Komodo anyway and I think a lot of other programmers do this also.

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.

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

Why is this a problem? He is simply measuring "when you get a fail high, what percentage of the time is it on the first move searched?" You can prune whatever you want, but you STILL get fail highs. The higher this percentage, the better a parallel search will work and the closer the tree size approaches the optimal (minimal) tree that must be searched.

I suspect this is a relatively fair comparison between 2 versions of the same program, but I don't see how it can be used to prove one program has better move ordering. The scoring resolution is just one example of how this would not be valid.

However, it may be a very good way to determine if you have made improvements in the move ordering - this is something that I have often done with Komodo anyway and I think a lot of other programmers do this also.

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 don't see how it will be a big gain. My FH% has always been in the 90+% range, I've been displaying this number since the Cray Blitz days. That means that only 10% (or less usually) of the time can you improve things. The cost of the ordering has to be minimal, because of the ALL nodes where ordering is completely irrelevant and any cost incurred is pure overhead. Approaching 100% is impossible, which means there is not a lot to work with. If you use move ordering for something else, such as LMR, then there could be a gain, but not in the base FH% I don't believe. I think Jonathan Schaeffer studied this years ago and defined "strongly-ordered game tree" as one where the best move is the first one searched, at least 90% of the time. The very premise of iterated search makes it impossible to get to 100% even if one ignores the concept that perfect ordering is impossible without advanced knowledge of the final best move / PV, and even then, it won't be best at shallow searches, making 100% impossible.

Doesn't seem like a lot of room left to improve on once one reaches the magic 90% range, and just good captures, hash and killers will do that.

Credit for 2 and such doesn't make much sense to me in this context. I suppose one might simple gather stats on fail-high nodes and produce a histogram of the number of moves searched to get a fail-high. However, the basic issue still remains. It is FAR more important to get the best move first than it is to get the second-best move second...

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

Why is this a problem? He is simply measuring "when you get a fail high, what percentage of the time is it on the first move searched?" You can prune whatever you want, but you STILL get fail highs. The higher this percentage, the better a parallel search will work and the closer the tree size approaches the optimal (minimal) tree that must be searched.

I suspect this is a relatively fair comparison between 2 versions of the same program, but I don't see how it can be used to prove one program has better move ordering. The scoring resolution is just one example of how this would not be valid.

However, it may be a very good way to determine if you have made improvements in the move ordering - this is something that I have often done with Komodo anyway and I think a lot of other programmers do this also.

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 don't see how it will be a big gain.

But I don't think it's a big gain, just a small improvement.

I feel that it more scientific if you want to put it that way because it's better to get a cutoff on the 2nd move than the 3rd move, and it's better to get a cutoff on the 3rd than the 4th and so on. This gives most of the credit to the first move without completely ignoring all the other data.

This is design philosophy in Komodo anyway, we generally avoid "hard edges" or "all or nothing" decisions whenever it seems to make some sense to us.

My FH% has always been in the 90+% range, I've been displaying this number since the Cray Blitz days. That means that only 10% (or less usually) of the time can you improve things. The cost of the ordering has to be minimal, because of the ALL nodes where ordering is completely irrelevant and any cost incurred is pure overhead. Approaching 100% is impossible, which means there is not a lot to work with. If you use move ordering for something else, such as LMR, then there could be a gain, but not in the base FH% I don't believe. I think Jonathan Schaeffer studied this years ago and defined "strongly-ordered game tree" as one where the best move is the first one searched, at least 90% of the time. The very premise of iterated search makes it impossible to get to 100% even if one ignores the concept that perfect ordering is impossible without advanced knowledge of the final best move / PV, and even then, it won't be best at shallow searches, making 100% impossible.

Doesn't seem like a lot of room left to improve on once one reaches the magic 90% range, and just good captures, hash and killers will do that.

Credit for 2 and such doesn't make much sense to me in this context. I suppose one might simple gather stats on fail-high nodes and produce a histogram of the number of moves searched to get a fail-high. However, the basic issue still remains. It is FAR more important to get the best move first than it is to get the second-best move second...