move ordering statistic

[Andrew Shapira]

There is a move ordering metric that I call "beta efficiency". It might be interesting to hear what people measure for it in their programs.

Beta efficiency can be computed as follows. Whenever a beta cutoff occurs, compute the number 1 / s, where s is the position in the sort order of the move that caused the beta cutoff. (The first move has s=1.) Beta efficiency is the average of the quantity 1/s, averaged over all beta cutoffs that occur.

For example, if, every time a cutoff occurs, the move that causes the cutoff is the first move in the sorted move list, s will always be 1, and the beta efficiency will be 1. On the other hand, if the cutoffs that occurred were always found at the last move in the sorted move list, beta efficiency would be around 3%, if there are about 33 legal moves per position.

Beta efficiency might be a good measure of the effectiveness of move ordering when move ordering really matters.

What does Crafty get?

(I measure beta efficiency in my own program, but cannot report any data right now because I was measuring it wrong, and am in the middle of a bunch of changes so I can't gather correct statistics.)

[Klaus Friedel]

Some statistics of Snitch:

WAC at 5 sec:
296/300 solved.
Not solved: WAC120, WAC163, WAC230, WAC235
Fail High after 1: 94.59 %
Beta efficency : 96.58 %
Qsearch: 10.52 %

For the initial position (30 sec) i get:
Fail High after 1: 94.2%
beta efficency : 96.6

Regards,

Klaus Friedel

[Tord Romstad]

Some statistics of Snitch:

WAC at 5 sec:

Hi Klaus,

I think tactical test positions are almost the worst possible thing you could choose for collecting move ordering statistics. The search trees will probably look totally different from the ones you get during an average search in a real game.

The only good way to measure this would be to play several full games and collect statistics from all searches. I'll see if I find the time to do such an experiment with Glaurung this weekend.

Tord

[Klaus Friedel]

Hi Tord,

your right a tactical test suite might not be the best, but I think we should compare the same set of positions so I would prefere testsets here.
I fact the numbers between tactical and positional positions differ only slightly - at least for Snitch.

I did more tests. First I compared the tactical (king safty) part of the WM-Test positions with the positional subset of WM-test.

###################################
WM-Test (K) at 10 sec
Fail High after 1: 95.42 %
Beta Efficency : 97.15 %
Qsearch : 6.51 %
Hash hit : 33.31 %
PVS researchs : 3.06 %
Full eval : 10.37 %
###################################
WM-Test (P) at 10 sec
7/36 solved
Fail High after 1: 94.55 %
Beta Efficency : 96.58 %
Qsearch : 6.62 %
Hash hit : 33.29 %
PVS researchs : 3.35 %
Full eval : 12.49 %

Only a small difference of about 0.5 between positional and tactical.

To see how the value changes at higher depth I repreted the tests with longer timecontrol.
Again the positional subset of WM-test:

WM-Test (P) at 2 sec
6/36 solved
Fail High after 1: 94.38 %
Beta Efficency : 96.48 %
Qsearch : 6.93 %
Hash hit : 38.71 %
PVS researchs : 2.84 %
Full eval : 14.67 %
###################################
WM-Test (P) at 60 sec
11/36 solved
Fail High after 1: 94.63 %
Beta Efficency : 96.62 %
Qsearch : 6.57 %
Hash hit : 26.58 %
PVS researchs : 3.85 %
Full eval : 10.57 %

Only a very small increase for longer timecontrols. So short timecontrols should be sufficient to get a significant value for beta efficency.

Klaus

Hi Klaus,

I think tactical test positions are almost the worst possible thing you could choose for collecting move ordering statistics. The search trees will probably look totally different from the ones you get during an average search in a real game.

The only good way to measure this would be to play several full games and collect statistics from all searches. I'll see if I find the time to do such an experiment with Glaurung this weekend.

Tord

[Andrew Shapira]

Some statistics of Snitch:

WAC at 5 sec:

Hi Klaus,

I think tactical test positions are almost the worst possible thing you could choose for collecting move ordering statistics. The search trees will probably look totally different from the ones you get during an average search in a real game.

The only good way to measure this would be to play several full games and collect statistics from all searches. I'll see if I find the time to do such an experiment with Glaurung this weekend.

Tord

Any news?

[Richard Allbert]

Ok, Just in case someone wants to the results from a weak and in progress engine, Lime v50... after 30s from the start position. No PVS search though, but includes null move, and 32MB hash. This version is in very early stages, a complete rewrite. But slower than the previous one already!

Code: Select all

nodes = 7299072
qnodes = 2905612
totalnodes = 10204684
nullatt = 73177
nullcuts = 44873
incheck extensions 175648
quies incheck extensions 180345
givecheck extensions 0

Beta cut = 913162
Beta sum = 783736
Beta eff = 85.8266 %
bestmove e2e4


Beta sum is the sum of 1/s, beta cut is the number of beta cut offs.

It seems to be a nice way of doing the statistic, and will be very useful. Thank you!

[toma]

I use something very similar for my measurments. I simply use medium move number that produced beta cutoff. This method should give the same idea of how good is your move ordering but it avoids the need to know how many legal moves exist in the position so it is simpler if you have incremental generation of moves. Practically the only piece of code you need to add to your search function is:

if(maxvalue>=beta)
{
#ifdef CUT_PERF
beta_cut+=moves_tried;
beta_cut_cnt++;
#endif
...
}

Please let me know if you see some flow in this method. Thank you.

Toma Roncevic

[Richard Allbert]

Yes, agreed.

I have taken the tests a step further, and built the categories for move ordering into an orthogonal array (DOE Taguchi style). The test is with 50 positions I have selected from games - 10 Nunn positions, 20 relatively equal midgame positions, and 20 equal endgame positions - and none of them with a forced first move.

Unfortunately, I won't have much time this weekend, but will try and run the test next week.

Richard