Move ordering contest

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

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.

The comparison was supposed to be done ONLY in the main search, not the quies. The only other time we would cutoff with zero moves is for null move pruning but I'm not counting those. One could argue that the null move itself is one move and not zero but in either case I am only interested in the move ordering at those nodes in the main search where the moves are generated and ordered.

This is also some issues concerning forward pruning and futility nodes where we only generated captures and checks. In theory those should always be expected ALL nodes where there would be cutoffs anyway.

There is some forward pruning in Komodo which you may be talking about. In some cases we throw out a move without playing it (or counting it) and that could skew my numbers - but I think it would make them look better, not worse. Again, I think at those nodes where this is done there would be few cutoffs anyway.




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

[hgm]

Well, if you exclude null move, why would you include the hash move? That is also a move you get for free, (without move generation or sorting), which tells you very little about whether your move ordering is any good. (It might have taken a lot of attempts to find that hash move.)

[Don]

Well, if you exclude null move, why would you include the hash move? That is also a move you get for free, (without move generation or sorting), which tells you very little about whether your move ordering is any good. (It might have taken a lot of attempts to find that hash move.)

The null move is not a move, and it's not even legal. It a device. The fact that it's even called a "move" influences the way we think about it. If it had been called something else such as "threat detection pruning" or "exchange side pruning" we would not be having this discussion.

However, this was presented as an argument for counting at zero - presumably you are saying that if you get a null move cutoff you can tally a zero? So then why would you be inconsistent about counting the null move? Is the "null move" a real move or not? You cannot have it both ways. If you consider it a real move and it produces a cutoff then you count it the same way as the other "real" moves.

I cannot even imagine a reasonable argument for not counting the hash table move - as it's very important to move ordering, which incidentally is the thing we are trying to measure. There is no requirement that you play the hash table move first, that is a program authors decision and I hope that you are not suggesting that we don't count things simply because you believe them best. Did you know that some of the best programs do not always store the "best" move in the hash table entry in some cases depending on the bounds? There is no reasonable argument for considering the hash table move as not being relevant to how the moves are ordered. If you look in any algorithms book under the chapter on heuristic search you will see that computer scientists consider this a move ordering issue.

[hgm]

I see no reason to count the null move as zero. It is a move that you search. Whether it is legal or not doesn't affect the tree size.

There is also no requirement to search the null move first. That is also a programmers decision.

If you can order the real moves such that you can get more cutoffs from the null move, it will shrink the tree much more than when you order the real moves to get an equal increase of the number of cutoffs of the first real move.

[michiguel]

I see no reason to count the null move as zero. It is a move that you search. Whether it is legal or not doesn't affect the tree size.

The count it as one, but it should be counted. That is my point. If you have a program without nullmove, it would appear that the move ordering is better since most likely any move that is tried first will get you a cut off. Not taking into account these nodes, penalizes null move programs.

Miguel

There is also no requirement to search the null move first. That is also a programmers decision.

If you can order the real moves such that you can get more cutoffs from the null move, it will shrink the tree much more than when you order the real moves to get an equal increase of the number of cutoffs of the first real move.

[tpetzke]

This is correct. But I'm quite certain that all programs that have published their numbers here are using a null move technique. So they are on almost equal ground.

"Almost" because the conditions in the program when a null move is tried might be different and programs that use it always might have an advantage compared with programs using it only if s_eval >= beta + margin (just to name one condition)

Thomas...

[hgm]

One program might be fastly more successful than another in achieving null-move cutoffs, at the expense of a slightly more 'risky' move ordering of the remaining moves. So there really is no evidence at all that they are 'on equal ground'.

[michiguel]

The comparison was supposed to be done ONLY in the main search, not the quies. The only other time we would cutoff with zero moves is for null move pruning but I'm not counting those. One could argue that the null move itself is one move and not zero but in either case I am only interested in the move ordering at those nodes in the main search where the moves are generated and ordered.

This is also some issues concerning forward pruning and futility nodes where we only generated captures and checks. In theory those should always be expected ALL nodes where there would be cutoffs anyway.

There is some forward pruning in Komodo which you may be talking about. In some cases we throw out a move without playing it (or counting it) and that could skew my numbers - but I think it would make them look better, not worse. Again, I think at those nodes where this is done there would be few cutoffs anyway.

There are more places in which it is possible to return beta (or higher) without doing any extra search. In main search, if "eval - margin - (lots of things here) >= beta" I return beta in the last couple of plies. Those are easy nodes in which for sure the first move I pick will return beta too. I am missing the chance to score big in those nodes with the ratio we are talking about. This is returning beta with no move searched, I believe that is zero.

My point is that a better engine will likely have more of these tricks, or more extended throughout the search. So it is not rare than Komodo score bad with the measurement we are talking about.

Miguel

[michiguel]

One program might be fastly more successful than another in achieving null-move cutoffs, at the expense of a slightly more 'risky' move ordering of the remaining moves. So there really is no evidence at all that they are 'on equal ground'.

Or doing NM in the last plies or not... which incidentally, are the most abundant nodes.

BTW, it is more important to have a better move ordering far from the leaves and those are less abundant, but that is a different issue.

Miguel

[hgm]

I never was able to make any sense of move-ordering statistics until I started taking them by depth remaining. At d=2 you will see completely different stats than at d=8, for instance.

I am not sure why the ordering would be more important at higher depth. In the end the number of leaves is just the product of the branching factor at each level, so it seems unimportant where you achieve the reduction. Or is it that at large depth a better order also causes more depth reduction?