[Discussion] - Measuring move ordering

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Rebel
Posts: 4712
Joined: Thu Aug 18, 2011 10:04 am

[Discussion] - Measuring move ordering

Post by Rebel » Sat Feb 24, 2018 8:35 pm

I am trying to find a formula to measure move-ordering as best as possible and when agreed upon hold an educational (and fun) contest between engine authors.

I can think of 2 systems.

#1. the percentage when the first move of a move-list in the tree remains the best move at the end of the move-list. This might require an extra entry in the stack initialized with -infinity before the first move is searched.

#2. Similar to (#1) but the normal ALPHA check is used.

I simply introduced a third killer slot to do the job and at the end of the move-list check if there has been a change.

I took the first 100 positions of the STS test and the results (at 1 sec) are:

Code: Select all

       system #1                system #2
[1] - 79.30% (79.30%)    [1] - 95.31% (95.31%)
[2] - 77.54% (78.42%)    [2] - 93.17% (94.24%)
[3] - 73.41% (76.75%)    [3] - 86.09% (91.52%)
.....................    .....................
[100] 75.61% (77.07%)  [100] - 91.36% (93.06%)
Additionally I can think of a formula to measure the efficiency of the hash table.

Your thoughts please.

elcabesa
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: [Discussion] - Measuring move ordering

Post by elcabesa » Sun Feb 25, 2018 10:34 am

I don't understand what each line of your output means.

Code: Select all

       system #1                system #2
[1] - 79.30% (79.30%)    [1] - 95.31% (95.31%)
[2] - 77.54% (78.42%)    [2] - 93.17% (94.24%)
[3] - 73.41% (76.75%)    [3] - 86.09% (91.52%)
.....................    .....................
[100] 75.61% (77.07%)  [100] - 91.36% (93.06%) 

User avatar
hgm
Posts: 23724
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: [Discussion] - Measuring move ordering

Post by hgm » Sun Feb 25, 2018 12:04 pm

In my experience such statistics is totally meaningless unless you split it up by (remaining) depth. Otherwise it would be totally dominated by QS. While having good move ordering in nodes close to the root is just as important (and much more difficult, as you also have to consider non-captures there). Also, the fact that you usually have a hash move tends to obscure the importance of move ordering; at some point you must have found this move, and it is much more important how much effort that took.

Finally, it might make sense to distinguish between in-check nodes and other nodes, as the usual heuristics for ordering usually do not work very whel when in check. And a lot there depends on whether you have legal or pseudo-legal generation; if you would count all the pseudo-legal moves that are not valid evasions, in-check nodes would seem very bad. But of course all these moves require at most a 1-node tree to refute, no matter what the requested depth is. OTOH, trying an inadequate legal move when in check is very expensive, because it is extended.

User avatar
Rebel
Posts: 4712
Joined: Thu Aug 18, 2011 10:04 am

Re: [Discussion] - Measuring move ordering

Post by Rebel » Sun Feb 25, 2018 3:51 pm

elcabesa wrote:I don't understand what each line of your output means.

Code: Select all

       system #1                system #2
[1] - 79.30% (79.30%)    [1] - 95.31% (95.31%)
[2] - 77.54% (78.42%)    [2] - 93.17% (94.24%)
[3] - 73.41% (76.75%)    [3] - 86.09% (91.52%)
.....................    .....................
[100] 75.61% (77.07%)  [100] - 91.36% (93.06%) 
           
 |      |       |
 |      |       |
 |      |       --> average percentage pos 1-100
 |      |
 |      --> percentage the first move was the best move
 |
 ---> position

User avatar
Rebel
Posts: 4712
Joined: Thu Aug 18, 2011 10:04 am

Re: [Discussion] - Measuring move ordering

Post by Rebel » Sun Feb 25, 2018 4:00 pm

hgm wrote:In my experience such statistics is totally meaningless unless you split it up by (remaining) depth. Otherwise it would be totally dominated by QS. While having good move ordering in nodes close to the root is just as important (and much more difficult, as you also have to consider non-captures there). Also, the fact that you usually have a hash move tends to obscure the importance of move ordering; at some point you must have found this move, and it is much more important how much effort that took.

Finally, it might make sense to distinguish between in-check nodes and other nodes, as the usual heuristics for ordering usually do not work very whel when in check. And a lot there depends on whether you have legal or pseudo-legal generation; if you would count all the pseudo-legal moves that are not valid evasions, in-check nodes would seem very bad. But of course all these moves require at most a 1-node tree to refute, no matter what the requested depth is. OTOH, trying an inadequate legal move when in check is very expensive, because it is extended.
Forgot to say (indeed) that QS nodes doesn't count, only the main search. Of course the hash table is part of the quality of the move ordering, I don't see a problem.

elcabesa
Posts: 815
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: [Discussion] - Measuring move ordering

Post by elcabesa » Sun Feb 25, 2018 5:27 pm

ops sorry, it was easy to understand.

some other questions:
1) are you considering only cutoff node or every node in your search?
2) in system 1, are you testing all the move-list disabling beta cutoff or other prunings?
3) system2 means how many times 1° move is enough to cause a cutoff?

thank you

User avatar
hgm
Posts: 23724
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: [Discussion] - Measuring move ordering

Post by hgm » Sun Feb 25, 2018 6:13 pm

Rebel wrote:Forgot to say (indeed) that QS nodes doesn't count, only the main search. Of course the hash table is part of the quality of the move ordering, I don't see a problem.
Well, d=1 is usually also completely different from higher depths.

jwes
Posts: 778
Joined: Sat Jul 01, 2006 5:11 am

Re: [Discussion] - Measuring move ordering

Post by jwes » Sun Feb 25, 2018 6:35 pm

Rebel wrote:I am trying to find a formula to measure move-ordering as best as possible and when agreed upon hold an educational (and fun) contest between engine authors.

I can think of 2 systems.

#1. the percentage when the first move of a move-list in the tree remains the best move at the end of the move-list. This might require an extra entry in the stack initialized with -infinity before the first move is searched.

#2. Similar to (#1) but the normal ALPHA check is used.

I simply introduced a third killer slot to do the job and at the end of the move-list check if there has been a change.

I took the first 100 positions of the STS test and the results (at 1 sec) are:

Code: Select all

       system #1                system #2
[1] - 79.30% (79.30%)    [1] - 95.31% (95.31%)
[2] - 77.54% (78.42%)    [2] - 93.17% (94.24%)
[3] - 73.41% (76.75%)    [3] - 86.09% (91.52%)
.....................    .....................
[100] 75.61% (77.07%)  [100] - 91.36% (93.06%)
Additionally I can think of a formula to measure the efficiency of the hash table.

Your thoughts please.
There are two other measures I have thought about.
1. Average number of moves looked at before the best move is found, e.g. if the best move is found first 90% and second 10%, the average is 1.1 or if the best move is found first 90% and tenth 10%, the average is 2.
2. Number of nodes searched when the best move is searched / number of nodes searched when the all moves are searched. This seems most directly correlated with improvements in move ordering though the effect of the hash table is difficult to quantify.

jdart
Posts: 3825
Joined: Fri Mar 10, 2006 4:23 am
Location: http://www.arasanchess.org

Re: [Discussion] - Measuring move ordering

Post by jdart » Mon Feb 26, 2018 12:53 am

I have some instrumentation I can turn on that will print out the % of times the 1st, 2nd, 3rd or 4th move was returned from the search and improved the initial alpha value (node->best_score > node->alpha).

Usually after the 4th move you are looking at small percentages.

--Jon

Cardoso
Posts: 293
Joined: Thu Mar 16, 2006 6:39 pm

Re: [Discussion] - Measuring move ordering

Post by Cardoso » Fri Mar 02, 2018 5:46 pm

I only tested the percentage of fail highs for the first 4 moves and returning immediately on a fail high.
So I can have 87% 5% 2% and 1% for the first 4 moves.
However these readings can change drastically if I only measure this if the remaining depth > 5*PLY
I'm at work so I can't test to see the exact differences but if I only measure this at depths > 5*PLY I can get something like:
95% 2% 1% and 1% for the first 4 moves.
And this makes sense to me, depth=0 dominates the statistics, and how good can be an hash move (killers/counter moves/history moves) at depth=0?
Test this yourself and see the differences.
And if you only measure at depths > 10*PLY then you will get even better move ordering, so depth really influences the readings.

Post Reply