root move ordering

[bob]

Say, on a related note, I remember a discussion about a year ago about trying to order the root moves based on number of beta cut-offs instead of number of nodes. Has this ever been tested?

Not to my knowledge...

Certainly not by me.

[Greg Strong]

Say, on a related note, I remember a discussion about a year ago about trying to order the root moves based on number of beta cut-offs instead of number of nodes. Has this ever been tested?

Not to my knowledge...

Certainly not by me.

Too bad. I thought you were considering testing the idea, but I think that was right before the cluster burn-out.

[bob]

Say, on a related note, I remember a discussion about a year ago about trying to order the root moves based on number of beta cut-offs instead of number of nodes. Has this ever been tested?

Not to my knowledge...

Certainly not by me.

Too bad. I thought you were considering testing the idea, but I think that was right before the cluster burn-out.

Testing of late has been very spotty. The A/C system has some major problems and is up and down about like the stock market. Unfortunately the two clusters produce an enormous amount of heat, which requires a very large A/C system, which translates to "expensive to repair".

[rvida]

Say, on a related note, I remember a discussion about a year ago about trying to order the root moves based on number of beta cut-offs instead of number of nodes. Has this ever been tested?

I'm doing this in Critter but the difference is barely measurable if at all. And IIRC Stockfish does this too (or was that abandoned in later versions?)

Richard

[Ralph Stoesser]

Say, on a related note, I remember a discussion about a year ago about trying to order the root moves based on number of beta cut-offs instead of number of nodes. Has this ever been tested?

I'm doing this in Critter but the difference is barely measurable if at all. And IIRC Stockfish does this too (or was that abandoned in later versions?)

Richard

In SF 1.7.1 beta-counters are the second level sort criterium. First level sort criterium is move score.

(BTW, the code does not match the code remark. There is talk of node count as the second level sort criterium.)

[mcostalba]

Say, on a related note, I remember a discussion about a year ago about trying to order the root moves based on number of beta cut-offs instead of number of nodes. Has this ever been tested?

I'm doing this in Critter but the difference is barely measurable if at all. And IIRC Stockfish does this too (or was that abandoned in later versions?)

Richard

In SF 1.7.1 beta-counters are the second level sort criterium. First level sort criterium is move score.

(BTW, the code does not match the code remark. There is talk of node count as the second level sort criterium.)

Yes but we have a valid score only for PV move, the others are set to -infinite, so actually we order on beta cut-off.

Richard, you have two beta-cut off counters, one of yours cut-offs and another that counts opponent's cut-offs.

Which of the two do you use ? In SF we use (surprisinlgy) opponent's cut-offs.

[rvida]

Richard, you have two beta-cut off counters, one of yours cut-offs and another that counts opponent's cut-offs.

Which of the two do you use ? In SF we use (surprisinlgy) opponent's cut-offs.

Huh, it is quite hard for me to explain in English, but let's give it a try:

Critter does not differentiate on side-to-move, there is only one fail-high counter. It is incremented only on fail highs in "expected" ALL nodes. When a fail high occurs in an expected CUT node, it is not incremented.

Idea behind this is that if all goes as expected (search tree sorting is optimal) then all "expected" ALL nodes are "real" ALL nodes and no cut-offs should occur. The more unexpected cut-offs occurred, the harder is to refute my root move. Hard to refute moves are usually of higher quality than easy to refute moves.

I think that in an ideally ordered tree, this would exactly mimic your method of counting only opponent's cut-offs.

Richard

[Greg Strong]

Thanks, Richard, that's interesting. And your English is excellent, by the way!

[rvida]

I thought about this and there are some potential flaws with my method. I do not update the counter on hash cut-offs nor null move cut-offs. And in the null move search I am not sure if logic behind my method still holds.
I decided to do some experiments. I made a few modified builds of Critter and run through STS suite.

A: unmodified Critter
B: counting nodes
C: counting nodes but sorting in reversed order (to simulate worst case behavior)
D: SF method (counting every cut-off and sorting by opponent's counter)

A', B', C', D': same as above but with LMR disabled at root.

I wont bother you with numbers, just a few observations:
- difference between B and C (the worst case) was _much_ smaller with LMR off than with LMR enabled
- with root LMR enabled, the ranking from best to worst was: D, A, B, C
- with root LMR disabled, the ranking was: A, D, B, C but with very small differences between them

Now I will run a 1000 game match A vs D to see which is better.

[mcostalba]

I wont bother you with numbers, just a few observations:
- difference between B and C (the worst case) was _much_ smaller with LMR off than with LMR enabled

This is very intuitive. In root node, being an all node, you need to search all the moves and if LMR is disabled there is little difference if you search one move before another.

But with LMR everything changes ! the order in which you search the moves becomes of paramount importance.

This is a concept apparentely not difficult to grasp but there is people that _still_ keep saying that he doesn't bother to sort the non-captures above a certain point.

IMHO if you want to go along the super-aggressive LMR path, then you MUST properly order every move that you want to try because move ordering makes the difference between a working LMR and a crap.

In SF 1.8 I am now testing a slightly modified ordering of non-captures, to my surpirse this slightly change seems to introduce an interesting gain (around 10 ELO). I am sure that in case we had a traditional LMR instead of the beast that is now, this gap would have been much much smaller because the change is really tiny.