Testing for Move Ordering Improvements

[Ferdy]

Script and STS sample files are now available. Only tested on windows. The script is written in python 2.7.11. I will later upload the exe file.

https://github.com/fsmosca/Move-Ordering-Spy

[D Sceviour]

I am thinking about tracking the frequency at which these moves are encountered and if they are the PV or CUT move.

The frequency of a move and the importance of a move are not necessarily the same thing. For example, it is important to examine checking moves first (or to examine without reduction), but they may not occur that often in a move list. Checking moves may not produce cutoffs, but that does not mean they are not important.

[cetormenter]

Indeed, if you use the ordering also to determine reduction, it becomes another matter. But in principle these are not the same. "Has a high probability to fail high" is something completely independent from "needs a large depth to see the merit".

So perhaps it would be better to maintain two history scores: one updated by low-depth searches, one updated by high-depth searches. Moves with a much better 'deep history' than 'shallow history' (relative to the maximum history score in the respective tables) should not be reduced. The best history of the two should decide the order.

So it would be perfectly possible that an earlier late move is searched with a reduced depth, because its shallow history is pretty good, and a move with a somewhat lower deep-history score (and therefore searched later) is not reduced, because it had a totally appalling shallow-history score. Of course it would be beneficial in general to postpone deeper searches to the end of the list, if they do not have a significantly larger probability to fail high than a shallower search, in the hope that a cutoff by one of the shallower moves makes the expensive deep search unnecessary.

I tried a very quick and dirty version of what you described here in Nirvana and was able to achieve quite a significant gain. I simply segmented my history table into multiple sub tables based of the remaining depth. At 60 seconds a game I got a gain of 19 +- 10 elo.

I collected some data as well and saw that my history table results sharply differed from the move's cutoff probability at around depth 15. Using a "normal" history implementation, moves with a positive history score only caused a cut off in about 4% of cases when the remaining depth was greater than 15. Using the new implementation that number jumped up to about 10%.

[cdani]

Indeed, if you use the ordering also to determine reduction, it becomes another matter. But in principle these are not the same. "Has a high probability to fail high" is something completely independent from "needs a large depth to see the merit".

So perhaps it would be better to maintain two history scores: one updated by low-depth searches, one updated by high-depth searches. Moves with a much better 'deep history' than 'shallow history' (relative to the maximum history score in the respective tables) should not be reduced. The best history of the two should decide the order.

So it would be perfectly possible that an earlier late move is searched with a reduced depth, because its shallow history is pretty good, and a move with a somewhat lower deep-history score (and therefore searched later) is not reduced, because it had a totally appalling shallow-history score. Of course it would be beneficial in general to postpone deeper searches to the end of the list, if they do not have a significantly larger probability to fail high than a shallower search, in the hope that a cutoff by one of the shallower moves makes the expensive deep search unnecessary.

I tried a very quick and dirty version of what you described here in Nirvana and was able to achieve quite a significant gain. I simply segmented my history table into multiple sub tables based of the remaining depth. At 60 seconds a game I got a gain of 19 +- 10 elo.

I collected some data as well and saw that my history table results sharply differed from the move's cutoff probability at around depth 15. Using a "normal" history implementation, moves with a positive history score only caused a cut off in about 4% of cases when the remaining depth was greater than 15. Using the new implementation that number jumped up to about 10%.

Nice! I had decided to wait to see the results of the new version of Andscacs 0.90 to explain it, but I will say that 0.90 already has a first version of multiple depth history! Really curious that we coincide
I'm investigating further.

[cdani]

Nice! I had decided to wait to see the results of the new version of Andscacs 0.90 to explain it, but I will say that 0.90 already has a first version of multiple depth history! Really curious that we coincide
I'm investigating further.

I can give some extra details, like that an extra history table related to depth 10 and higher already gives most of the win, at least the way I have done it.

[cdani]

I can give some extra details, like that an extra history table related to depth 10 and higher already gives most of the win, at least the way I have done it.

And of course more history stuff means more opportunities somewhere else... Ahem...