Move ordering at different (Knuth) node types

[Tom Likens]

Afternoon,

I've been experimenting lately with various move ordering schemes to reduce the size of the search tree. I've mainly been tracking two components,

1) the percentage of fail-highs at CUT nodes for the 1st, 2nd and 3rd moves
2) the percentage of times the 1st-10th moves at a PV node is the best move in the position.

As Gian-Carlo pointed out recently (1) isn't such a great indicator of tree size (it averages around 90-93% for the first move), but (2) is much more interesting, it averages around 50-65%, also for the first move. To really understand this, I break my search up into the following phases:

1. Hash move
2. Killer mates
3. Winning/Even captures
4. Killers (non-mate)
5. Queen promotions
6. Castling moves (kingside/queenside)
7. Winning even mundanes
8. Losing captures
9. Losing mundanes
10. Non-queen promotions

I verify of course, that I don't search any move more than once. The interesting thing about this is that if I track the percentage of each phase where the 1st, 2nd, 3rd etc. move caused a cutoff or was the best move--the move ordering is significantly different for CUT nodes versus PV nodes (I don't check ALL nodes, since they shouldn't produce a cutoff and order is unimportant).

Has anyone else seen a similar phenomenon? It may be advantageous to order the moves differently depending on the type of node we are searching. It's interesting, although the number of PV nodes is small compared to the number of CUT/ALL nodes, their overall effect on the size of the tree is enormous. Spending extra time ordering these nodes could potentially produce a huge benefit.

regards,
--tom

[mridul]

Afternoon,

I've been experimenting lately with various move ordering schemes to reduce the size of the search tree. I've mainly been tracking two components,

1) the percentage of fail-highs at CUT nodes for the 1st, 2nd and 3rd moves
2) the percentage of times the 1st-10th moves at a PV node is the best move in the position.

As Gian-Carlo pointed out recently (1) isn't such a great indicator of tree size (it averages around 90-93% for the first move), but (2) is much more interesting, it averages around 50-65%, also for the first move. To really understand this, I break my search up into the following phases:

1. Hash move
2. Killer mates
3. Winning/Even captures
4. Killers (non-mate)
5. Queen promotions
6. Castling moves (kingside/queenside)
7. Winning even mundanes
8. Losing captures
9. Losing mundanes
10. Non-queen promotions

I verify of course, that I don't search any move more than once. The interesting thing about this is that if I track the percentage of each phase where the 1st, 2nd, 3rd etc. move caused a cutoff or was the best move--the move ordering is significantly different for CUT nodes versus PV nodes (I don't check ALL nodes, since they shouldn't produce a cutoff and order is unimportant).

Has anyone else seen a similar phenomenon? It may be advantageous to order the moves differently depending on the type of node we are searching. It's interesting, although the number of PV nodes is small compared to the number of CUT/ALL nodes, their overall effect on the size of the tree is enormous. Spending extra time ordering these nodes could potentially produce a huge benefit.

regards,
--tom

Promotions come after killers for you ?
For me , they are at par - and sometimes higher than good captures.

for depth > some_value_based_on_initial_depth , I do detailed analysis to determine good moves/captures and order moves accordingly (like using hung piece info , etc).

Mridul

[Tom Likens]

Promotions come after killers for you ?
For me , they are at par - and sometimes higher than good captures.

for depth > some_value_based_on_initial_depth , I do detailed analysis to determine good moves/captures and order moves accordingly (like using hung piece info , etc).

Mridul

Hello Mridul,

Yes, the various phases are generated with separate move generators which has a (small) amount of overhead. In 99.9+% of the cases there are no promotion moves, so the overhead of calling the queen promotion move generator is simply wasted. In endgames where this matters, there is some disadvantage, but nothing significant in my testing and overall the benefit of not checking it outweighs the advantage seen in the late endgame.

I've toyed, but never seriously pursued, the idea of using the evaluation function to order the winning/even mundanes in the first few (upper) plies of the search. I do an extensive move ordering using the eval at the root, but not below the root, instead relying on the move ordering I previously posted.

regards,
--tom

[Uri Blass]

Hello Tom,

I think that it is a mistake generally to generate promotion after killers.

In most of the cases you can detect fast that there is no pawn in the 7th rank so there is no promotion so the overhead is not significant and when there is a pawn in the 7th rank it is important to check promotions.

Uri

[Tom Likens]

Hello Tom,

I think that it is a mistake generally to generate promotion after killers.

In most of the cases you can detect fast that there is no pawn in the 7th rank so there is no promotion so the overhead is not significant and when there is a pawn in the 7th rank it is important to check promotions.

Uri

Hey Uri,

I'll give the reordering of promotions another try. It's been a long time since I measured its effect and a lot has changed in my program since then, so it may be better now.

OTOH, have you tried different reordering schemes based on the type of node you're searching in movei? I'm curious about other programmer's results.

regards,
--tom

[Uri Blass]

Hello Tom,

I think that it is a mistake generally to generate promotion after killers.

In most of the cases you can detect fast that there is no pawn in the 7th rank so there is no promotion so the overhead is not significant and when there is a pawn in the 7th rank it is important to check promotions.

Uri

Hey Uri,

I'll give the reordering of promotions another try. It's been a long time since I measured its effect and a lot has changed in my program since then, so it may be better now.

OTOH, have you tried different reordering schemes based on the type of node you're searching in movei? I'm curious about other programmer's results.

regards,
--tom

No

my ordering is the same in all types of nodes.

basically it is

hash
good captures and good promotions
killers.
other moves(first moves based on history value and after enough moves it is the same order as they were generated).

Uri

[mridul]

Promotions come after killers for you ?
For me , they are at par - and sometimes higher than good captures.

for depth > some_value_based_on_initial_depth , I do detailed analysis to determine good moves/captures and order moves accordingly (like using hung piece info , etc).

Mridul

Hello Mridul,

Yes, the various phases are generated with separate move generators which has a (small) amount of overhead. In 99.9+% of the cases there are no promotion moves, so the overhead of calling the queen promotion move generator is simply wasted. In endgames where this matters, there is some disadvantage, but nothing significant in my testing and overall the benefit of not checking it outweighs the advantage seen in the late endgame.

I've toyed, but never seriously pursued, the idea of using the evaluation function to order the winning/even mundanes in the first few (upper) plies of the search. I do an extensive move ordering using the eval at the root, but not below the root, instead relying on the move ordering I previously posted.

regards,
--tom

Hi Tom,

Hmm , I think I misread your post then.
I assumed you were talking only about move ordering - not about move generation.
But I think you have both going hand in hand ? Or maybe And there is some sort of incremental move generation happening ?

I just generate all moves upfront and then order them.

About different ordering based on type of node - i use the hash type to decide whether it is worth making a expensive ordering of moves.
Actually , it is a function of both depth remaining and node_type.

But then , in my moveordering a winning capture could get ordered as one of the last move to be searched ... if the move is leaving other pieces hanging , etc.

Regards,
Mridul

[Gian-Carlo Pascutto]

Afternoon,

I've been experimenting lately with various move ordering schemes to reduce the size of the search tree. I've mainly been tracking two components,

1) the percentage of fail-highs at CUT nodes for the 1st, 2nd and 3rd moves
2) the percentage of times the 1st-10th moves at a PV node is the best move in the position.

As Gian-Carlo pointed out recently (1) isn't such a great indicator of tree size (it averages around 90-93% for the first move), but (2) is much more interesting, it averages around 50-65%, also for the first move. To really understand this, I break my search up into the following phases:

1. Hash move
2. Killer mates
3. Winning/Even captures
4. Killers (non-mate)
5. Queen promotions
6. Castling moves (kingside/queenside)
7. Winning even mundanes
8. Losing captures
9. Losing mundanes
10. Non-queen promotions

I verify of course, that I don't search any move more than once. The interesting thing about this is that if I track the percentage of each phase where the 1st, 2nd, 3rd etc. move caused a cutoff or was the best move--the move ordering is significantly different for CUT nodes versus PV nodes (I don't check ALL nodes, since they shouldn't produce a cutoff and order is unimportant).

Has anyone else seen a similar phenomenon? It may be advantageous to order the moves differently depending on the type of node we are searching. It's interesting, although the number of PV nodes is small compared to the number of CUT/ALL nodes, their overall effect on the size of the tree is enormous. Spending extra time ordering these nodes could potentially produce a huge benefit.

regards,
--tom

I think what you say makes great sense. Time for some experiments :-P

[Daniel Shawul]

Hi Tom
This is an interesting experiment.
Especially I am intrested in the accuaracy of prediction of CUT nodes.
After searching the first move(s) in an expected CUT node, if no fail high occurs, this is probably an ALL node. This i think is a good measure of our move ordering.
I think using the bare Knuth node type classification may not be the best.
For parllel search, prediction of node types is very important as this will avoid search overheads. Currently the best method is to search the first move and then do splitthing if this move does not fail high.(YBW concept).
The original DTS implementation by Hyatt used something like Knuth's node classification. I think nowadays people use DTS + YBW and got better results. (Some one can say something here:)

The move ordering experment could also be important for fail low reduction. Depending on the amount of fail high we get at the different node types, one can decide when to use the reduction (different bounds).
The improvement from doing this might be better than the one we get from smaller search tree due to better move ordering.

best
daniel

[Daniel Shawul]

I made a quick experiment on bt2630 and measured the flip rate (from cut to all node depending on the result of search of the first move only).
I will measure percentage of fail high on pv nodes (your criteria)later.

Code: Select all

pv            cut            all             flip
0.13   77.57   22.3   4.5
0.06   78.5   21.44   2.46
0.09   72.15   27.76   8.2
0.11   77.22   22.68   5.5
0.07   75.04   24.89   0.77
0.09   76.55   23.36   4.55
0.03   80.79   19.18   2.13
0.11   84.71   15.18   2.84
0.07   84.51   15.41   2.67
0.17   71.19   28.64   8.71
0.08   80.99   18.92   2.58
0.05   69.38   30.58   9.31
0.05   76.62   23.33   3.95
0.07   74.03   25.9   4.56
0.08   77.47   22.45   5.11
0.06   82.07   17.86   2.51
0.08   72.54   27.38   12.08
0.23   78.46   21.32   3.12
0.08   75.76   24.16   6.95
0.17   78.98   20.85   4.52
0.07   67.03   32.9   9.15
0.13   82.99   16.89   3.82
0.04   80.56   19.4   0.82
0.07   78.73   21.2   5.53
0.11   79.83   20.06   3.38
0.06   85.54   14.4   1.89
0.11   73.9   25.99   4.71
0.09   74.28   25.63   7.14
0.05   80.98   18.97   3.13
0.11   82.84   17.05   3.16

average
0.09   77.70   22.20   4.66




BT2630 is a tactical testsuite so it might not be a good represenative.
What is interesting for me is the flip rate is small in endgame position like 5 , 23. And very high in tactical postions like pos 17 (this one is similar to the famous WAC141).

[Daniel Shawul]

Ok i run the test on lct2 and bt2630.

Code: Select all

pv   cut   all   flip   fh   fh_pv   fh_cut   fh_all   fh_3   fh_pv3   fh_cut3   fh_all3
0.13    77.47    22.40     4.53    32.33     0.11    87.06    12.83    31.39     0.10    89.66    10.24   
  0.06    78.21    21.73     2.40    23.62     0.05    90.73     9.22    23.33     0.05    91.87     8.08   
  0.08    71.92    28.00     8.56    39.66     0.05    79.33    20.61    37.66     0.05    83.55    16.40   
  0.09    77.17    22.74     5.50    37.62     0.06    86.82    13.12    36.20     0.06    90.23     9.72   
  0.06    73.67    26.27     0.67    11.13     0.12    90.70     9.18    11.05     0.12    91.34     8.55   
  0.08    76.94    22.98     4.49    28.92     0.06    86.26    13.67    28.16     0.06    88.60    11.34   
  0.03    80.50    19.47     2.20    21.72     0.03    89.30    10.67    21.23     0.03    91.36     8.61   
  0.09    84.46    15.45     2.91    22.94     0.08    87.39    12.53    22.28     0.08    89.96     9.96   
  0.07    84.58    15.35     2.57    17.57     0.09    85.41    14.50    17.13     0.09    87.59    12.33   
  0.15    70.36    29.49     9.29    38.08     0.12    78.03    21.85    36.54     0.10    81.30    18.59   
  0.09    81.36    18.55     2.46    22.87     0.10    89.82    10.07    22.47     0.10    91.42     8.49   
  0.05    69.46    30.50     9.48    39.62     0.03    80.02    19.95    37.92     0.03    83.61    16.36   
  0.05    76.57    23.38     3.95    39.35     0.03    90.61     9.36    38.51     0.03    92.58     7.39   
  0.06    74.69    25.25     4.27    22.76     0.05    79.88    20.07    21.94     0.05    82.88    17.07   
  0.08    77.19    22.73     5.30    35.71     0.06    86.42    13.52    34.64     0.05    89.09    10.86   
  0.05    82.56    17.39     2.28    28.55     0.04    92.16     7.80    28.06     0.04    93.76     6.20   
  0.07    72.25    27.68    11.62    36.13     0.05    69.00    30.95    33.82     0.05    73.70    26.25   
  0.20    78.59    21.21     3.10    27.80     0.17    90.20     9.63    27.29     0.17    91.88     7.95   
  0.07    75.49    24.44     6.91    36.48     0.05    81.68    18.26    35.26     0.05    84.51    15.44   
  0.14    78.63    21.23     4.52    27.87     0.11    83.85    16.04    26.95     0.10    86.70    13.20   
  0.06    66.76    33.18     9.23    41.91     0.03    81.08    18.89    39.77     0.03    85.43    14.54   
  0.12    83.05    16.83     3.81    25.87     0.12    85.73    14.15    25.13     0.10    88.27    11.62   
  0.03    80.46    19.51     0.75    30.65     0.02    97.58     2.40    30.56     0.02    97.88     2.10   
  0.07    79.03    20.90     5.22    28.04     0.05    84.10    15.85    26.95     0.05    87.49    12.46   
  0.10    79.65    20.25     3.35    23.99     0.12    86.59    13.29    23.42     0.11    88.71    11.18   
  0.05    85.55    14.40     1.95    19.29     0.07    89.96     9.98    18.89     0.06    91.84     8.10   
  0.09    74.16    25.76     4.52    28.43     0.06    85.06    14.87    27.59     0.06    87.66    12.28   
  0.08    74.64    25.28     7.06    38.53     0.05    83.11    16.84    36.80     0.04    87.01    12.95   
  0.05    80.50    19.45     3.30    29.33     0.03    89.47    10.50    28.78     0.03    91.17     8.81   
  0.11    82.86    17.02     3.07    24.88     0.10    87.99    11.91    24.24     0.09    90.32     9.58   


lct2 result

Code: Select all

  0.11    78.78    21.11     4.91    31.29     0.07    85.51    14.41    30.32     0.07    88.27    11.67   
  0.13    82.98    16.88     2.70    26.31     0.11    89.55    10.34    25.86     0.10    91.11     8.79   
  0.10    82.50    17.40     2.82    26.77     0.07    89.53    10.40    26.00     0.07    92.19     7.75   
  0.15    85.06    14.79     3.48    25.77     0.08    87.81    12.10    25.07     0.07    90.25     9.67   
  0.19    87.17    12.64     2.94    22.27     0.19    86.70    13.12    21.57     0.16    89.54    10.31   
  0.07    82.41    17.52     2.74    23.86     0.05    88.01    11.93    23.36     0.05    89.91    10.05   
  0.09    86.27    13.65     1.60    20.14     0.09    90.93     8.99    19.80     0.08    92.50     7.42   
  0.10    87.15    12.75     2.18    19.69     0.09    87.82    12.09    19.24     0.08    89.86    10.06   
  0.16    78.69    21.15     4.63    34.48     0.09    87.37    12.53    33.22     0.08    90.70     9.22   
  0.07    82.14    17.79     4.14    29.08     0.06    86.35    13.59    28.19     0.05    89.07    10.89   
  0.09    84.33    15.58     3.86    25.56     0.08    85.36    14.56    24.89     0.07    87.67    12.26   
  0.18    83.52    16.30     3.47    28.41     0.14    87.99    11.87    27.52     0.12    90.83     9.04   
  0.07    83.47    16.46     2.83    26.75     0.07    89.19    10.75    26.03     0.06    91.65     8.29   
  0.11    84.44    15.45     3.66    28.06     0.09    87.23    12.68    27.36     0.08    89.48    10.44   
  0.06    77.58    22.36     3.99    25.38     0.06    83.87    16.07    24.65     0.05    86.35    13.60   
  0.03    83.39    16.58     0.88    20.21     0.02    95.09     4.89    20.06     0.02    95.83     4.15   
  0.05    81.60    18.35     1.18    13.35     0.08    90.17     9.74    13.11     0.08    91.83     8.09   
  0.10    80.95    18.94     2.88    27.75     0.11    90.17     9.72    27.24     0.10    91.85     8.05   
  0.26    79.97    19.77     3.32    28.85     0.12    89.20    10.68    28.15     0.10    91.43     8.47   
  0.08    80.58    19.35     3.48    30.98     0.05    89.04    10.91    30.13     0.04    91.55     8.40   
  0.08    79.79    20.13     3.44    27.24     0.08    87.58    12.33    26.66     0.08    89.49    10.43   
  0.19    75.87    23.94     6.41    35.47     0.13    82.89    16.98    34.26     0.11    85.80    14.08   
  0.07    77.32    22.61     3.82    29.38     0.05    87.64    12.31    28.50     0.05    90.33     9.63   
  0.11    85.32    14.57     3.23    25.83     0.08    87.55    12.37    24.97     0.07    90.54     9.39   
  0.08    83.90    16.03     4.14    26.19     0.06    84.86    15.09    25.42     0.05    87.43    12.52   
  0.10    83.35    16.56     3.31    26.83     0.08    88.23    11.69    26.07     0.07    90.80     9.13   
  0.06    78.32    21.61     2.73    30.85     0.04    92.26     7.70    30.40     0.04    93.62     6.35   
  0.12    81.16    18.72     3.55    23.92     0.12    85.51    14.37    23.18     0.12    88.24    11.65   
  0.26    78.01    21.73     3.42    20.91     0.32    82.88    16.80    20.37     0.31    85.06    14.63   
  0.05    76.43    23.52     6.58    30.60     0.04    81.16    18.80    29.30     0.04    84.77    15.19   
  0.07    80.59    19.35     3.79    26.31     0.06    86.67    13.28    25.42     0.05    89.69    10.26   
  0.17    79.98    19.85     3.98    22.64     0.18    82.69    17.13    21.94     0.17    85.33    14.50   
  0.05    81.71    18.24     3.40    22.85     0.04    87.57    12.39    22.52     0.04    88.85    11.11   
  0.08    74.92    25.00     3.21    23.06     0.08    86.24    13.69    22.44     0.07    88.62    11.31   
  0.08    77.58    22.34     2.41    16.92     0.13    83.05    16.82    16.59     0.13    84.69    15.19

Average for both is:

Code: Select all

pv   cut   all   flip   fh   fh_pv   fh_cut   fh_all   fh_3   fh_pv3   fh_cut3   fh_all3
0.09   79.48   20.42   4.02   27.61   0.08   86.54   13.37   26.80   0.08   88.98   10.95


fh_3 is fail high in the first 3 moves, and flip is change from expected CUT node to an ALL node.

ps: how to post a spread sheat?
where did the test forum go?

[Tom Likens]

Ok i run the test on lct2 and bt2630.

Average for both is:

Code: Select all

pv   cut   all   flip   fh   fh_pv   fh_cut   fh_all   fh_3   fh_pv3   fh_cut3   fh_all3
0.09   79.48   20.42   4.02   27.61   0.08   86.54   13.37   26.80   0.08   88.98   10.95


fh_3 is fail high in the first 3 moves, and flip is change from expected CUT node to an ALL node.

ps: how to post a spread sheat?
where did the test forum go?

Daniel,

This is *excellent* information. I can't do it justice right now because of my involvement
in CCT8. But once that is complete, I intend to look over your data.

regards,
--tom

[Tom Likens]

I made a quick experiment on bt2630 and measured the flip rate (from cut to all node depending on the result of search of the first move only).
I will measure percentage of fail high on pv nodes (your criteria)later.

Code: Select all

pv            cut            all             flip
0.13   77.57   22.3   4.5
0.06   78.5   21.44   2.46
0.09   72.15   27.76   8.2
0.11   77.22   22.68   5.5
0.07   75.04   24.89   0.77
0.09   76.55   23.36   4.55
0.03   80.79   19.18   2.13
0.11   84.71   15.18   2.84
0.07   84.51   15.41   2.67
0.17   71.19   28.64   8.71
0.08   80.99   18.92   2.58
0.05   69.38   30.58   9.31
0.05   76.62   23.33   3.95
0.07   74.03   25.9   4.56
0.08   77.47   22.45   5.11
0.06   82.07   17.86   2.51
0.08   72.54   27.38   12.08
0.23   78.46   21.32   3.12
0.08   75.76   24.16   6.95
0.17   78.98   20.85   4.52
0.07   67.03   32.9   9.15
0.13   82.99   16.89   3.82
0.04   80.56   19.4   0.82
0.07   78.73   21.2   5.53
0.11   79.83   20.06   3.38
0.06   85.54   14.4   1.89
0.11   73.9   25.99   4.71
0.09   74.28   25.63   7.14
0.05   80.98   18.97   3.13
0.11   82.84   17.05   3.16

average
0.09   77.70   22.20   4.66




BT2630 is a tactical testsuite so it might not be a good represenative.
What is interesting for me is the flip rate is small in endgame position like 5 , 23. And very high in tactical postions like pos 17 (this one is similar to the famous WAC141).

Hey Daniel,

Now that I'm getting a chance to look at this it's really intriguing. I wonder if the low flip rate in the endgame positions is due to the higher
effectiveness of the hash table. An interesting experiment would be to either:

a) turn off the hash table
b) reduce its size and see what the effect on the above numbers becomes

Or perhaps even more directly, to vary the size of the hash table in increments and map the flip rate to the variations in size.

regards,
--tom

[Tom Likens]

Ok i run the test on lct2 and bt2630.

Average for both is:

Code: Select all

pv   cut   all   flip   fh   fh_pv   fh_cut   fh_all   fh_3   fh_pv3   fh_cut3   fh_all3
0.09   79.48   20.42   4.02   27.61   0.08   86.54   13.37   26.80   0.08   88.98   10.95


fh_3 is fail high in the first 3 moves, and flip is change from expected CUT node to an ALL node.

Daniel,

Actually, my critiera was a bit different than just the fail-high percentage at PV nodes. I was (and am) interested in the percentage of times the first move searched at a PV node returns the *best* score at that node, since improving this number should help reduce the tree, (although your idea about using the information to make better late-move reductions is clever).

Thinking about your posted numbers I'm wondering if the percentage of fail-highs seen at PV nodes isn't a direct measure of how appropriately the aspiration window has been set at the root. It would be interesting to run an experiment where the aspiration window was varied to determine if the fail-highs at PV nodes also varied in the opposite direction, (this would also be affected, I believe by the type of search you have--e.g. either fail-soft or fail-hard).

regards,
--tom

P.S. Sorry, for coming up with experiments for you, but I currently unable to access my chess computer until this Friday

[Daniel Shawul]

Code: Select all

Actually, my critiera was a bit different than just the fail-high percentage at PV nodes. I was (and am) interested in the percentage of times the first move searched at a PV node returns the *best* score at that node, since improving this number should help reduce the tree, (although your idea about using the information to make better late-move reductions is clever).


yes i havent yet implemented your idea fully. My worry is that the number of pv nodes in a given search is so little it might not be statistically significant to measure move ordering at pv nodes only. Also since we give everything to get the move ordering right at pv nodes, this might not be represenative of all the other nodes. We usually have a hashtable move to search there, and if not, we do IID and get the "best" move.

Inspired by this discussion i changed the reduction bounds according to node types. At PV nodes i do it after 6 moves have been searched, at CUT nodes after 3, and at ALL nodes after 1 move. This really gave better results than using 3 for all. My reason for using low value at ALL nodes is that move ordering does not matter there and fail high do not necessarily show at the first 3 moves , unlike at cut nodes.

Code: Select all

Thinking about your posted numbers I'm wondering if the percentage of fail-highs seen at PV nodes isn't a direct measure of how appropriately the aspiration window has been set at the root. It would be interesting to run an experiment where the aspiration window was varied to determine if the fail-highs at PV nodes also varied in the opposite direction, (this would also be affected, I believe by the type of search you have--e.g. either fail-soft or fail-hard).


You are right that fail high's at pv nodes are not measure of move ordering. there should be no fail highs at pv nodes with (-inf,inf) i guess.

I also run similar experiment for IID searches at different node types, will post those when you are ready. I am beginning to like this experimental stuff

regards
daniel