Ply one move sorting

[chrisw]

does anyone sort moves at ply one? presumably .....

what's your hit rate for finding the later bestmove (in an unsorted list a later bestmove should, on average, be found midway in the list)

anyone with better results than that? where on average is a bestmove found in your list? First 25%? first 30%?

Chris

I don't have any real data I can find, but a few years ago I changed the way I sort them.

I originally did a static eval of each move, and used SEE to determine whether the move appeared to lose material or not. I used this in Cray Blitz for years for the first sort for a brand new search.

A few years back, I replaced the SEE and eval with a simple call to Quiesce() after making each move, and using that score to sort them. I called Quiesce() with an open window to get a real score for each root move.

That's the sort for starting off. Once I do the first iteration, I then use the node count for the subtree produced by each root move to order them beyond that point. In general the best move from the previous iteration will have a node count _way_ bigger than any other move, unless there were "changes of mind" during that iteration where any one of the best moves could have the biggest count. To solve this, I always force the best move from ply-1 to the top of the list, and sort the rest based on their node counts.

We started doing this in Cray Blitz at the suggestion of Harry Nelson who was a fanatic about solving problem positions. He noticed that in a position where there is a deep winning combination on a move that looks bad at first, each iteration the size of the subtree for that move grows with respect to the subtrees of other moves, because it gets harder and harder to prove the move is bad. Until finally that move becomes best. The idea is to move those moves that are a bit harder to search closer to the front of the list to get to them sooner, rather than later (or never, if the iteration times out before they are reached.)

I do this today in Crafty, and several others have tried it and use it as well. Whether there are better approaches remains to be seen, but this does work pretty well...

Well, I have an idea I tested which is why I ask

would you be able to come up with some stats, say on a test suite of a zillion positions ...

how far down the move list is the bestmove (say anything found after 60 secs or so) - then average it over the N positions. express at percentage (with no sort giving result 50% presumably)

clearly if one can push the likely candidate bestmoves way up the front of the move list, this is equivalent to some search speed improvement (its faster to find a new best if its 3rd in the move list than if its 30th)

OK, I can do that. But it needs to be precisely specified what I am measuring.

option 1:

For each iteration, I simply count how many times the best move was first, or second or ... down to how many times was the best move last.

option 2:

Only count the final iteration stats, since those reflect what happened on the iteration that actually produced the move played...

It would be easy to do either way although option 1 would be the easiest to do for me. I could then run any number of test positions you choose and report back on the results.

One _important_ note however, is that root-move ordering for normal games is not the same as root-move ordering for problem positions. Typically a test position has some surprising move (commonly a sacrifice) that will look bad until the search goes deep enough to expose the "punch line"... Something that moves those surprising moves up will help tactical test positions but hurt normal chess. One example is trying all captures first, regardless of material gain or loss. That will help with tactical positions that have a sacrifice as a starting point, but will make the tree larger for normal positions.

So, tell me how to proceed and I will fire it up...

er, well I have neither the sources or the precise results of what I did a few years ago, so can only go by memory

let's makes some rules ...

run N test positions, or games positions or whatever you've got (I think I had about 2000+ test positions at the time)

junk anything that happens say for first 10 secs
then record whenever you get a new bestmove where it was in the movelist as a percentage (eg 5th out of 20 would be 25%) lets say for the next 50 secs.

average your percentage over N

for 2000 test positions that'll take 1.5 days or so


if times have changed and 10 secs -> 60 secs is silly with quad sx1000 turbo parallel or whatever the tech is nowadays, reduce time


anyway, you just need a consistent base for others to compare

IIRC the technique I used (which was quite brutal and could have been refined mucho) was getting 25% score (ie candidates were in first 25% of move list on average). if you and others are worse with current move sort, then we have an improvement - will then tell you what it is

Chris

[Harald Johnsen]

...
how far down the move list is the bestmove (say anything found after 60 secs or so) - then average it over the N positions. express at percentage (with no sort giving result 50% presumably)

clearly if one can push the likely candidate bestmoves way up the front of the move list, this is equivalent to some search speed improvement (its faster to find a new best if its 3rd in the move list than if its 30th)

There is a paper on the web about the change rate of the best move for some top engines depending on search time. Not exactly what you are looking for but there is some statistics.

HJ.

[mjlef]

does anyone sort moves at ply one? presumably .....

what's your hit rate for finding the later bestmove (in an unsorted list a later bestmove should, on average, be found midway in the list)

anyone with better results than that? where on average is a bestmove found in your list? First 25%? first 30%?

Chris

WhatI do is probably insane, but I do have reasons for it. I put all captures and queen promotions at the front of the list before the first itteration, sorted by expected SEE gain. Even losing ones, then non-captures sorted by history. If there is a ttable move or move from a previous PV it gets put in front. Whenever a new best move is found it just gets moved to the top of the list and shoves the others down. I find the search often oscillates between two moves being best and so this saves a bit there.

Why the losing captures early on? Losing captures are searched fast, since it is easy to prove a losing move sucks, and in doing so, it fills the ttable with lots of captures sequence info that then saves time on other stupid paths. Also, I would rather get through as many moves as possible and know that say I looked at half the available moves in the alloted time oves were instead of 3 or something if higher scoring moves were put first (which my statistically insignificant testing show generally take a lot more nodes to prove are not as good as the PV).

I am sure Bob's cluster can prove me wrong.

Mark

[chrisw]

does anyone sort moves at ply one? presumably .....

what's your hit rate for finding the later bestmove (in an unsorted list a later bestmove should, on average, be found midway in the list)

anyone with better results than that? where on average is a bestmove found in your list? First 25%? first 30%?

Chris

WhatI do is probably insane, but I do have reasons for it. I put all captures and queen promotions at the front of the list before the first itteration, sorted by expected SEE gain. Even losing ones, then non-captures sorted by history. If there is a ttable move or move from a previous PV it gets put in front. Whenever a new best move is found it just gets moved to the top of the list and shoves the others down. I find the search often oscillates between two moves being best and so this saves a bit there.

Why the losing captures early on? Losing captures are searched fast, since it is easy to prove a losing move sucks, and in doing so, it fills the ttable with lots of captures sequence info that then saves time on other stupid paths. Also, I would rather get through as many moves as possible and know that say I looked at half the available moves in the alloted time oves were instead of 3 or something if higher scoring moves were put first (which my statistically insignificant testing show generally take a lot more nodes to prove are not as good as the PV).

I am sure Bob's cluster can prove me wrong.

Mark

I doubt it is insane because its a very usual method of ply one sorting. I guess we tend to do that which we have the tools to do it with and all that stuff, SEE, captures etc are easily known via the usual functions used elsewhere in search.

I used to fiddle around with much the same ply one sort stuff, never really made much difference, and remember sitting in tournaments looking at my engine slowly grinding through the final iteration it had time for and hoping it would actually look at some desired move before timing out. Very frustrating. Or it would even eventually look at the move, and time out before completion - even more frustrating.

So, anything which statistically can bung candidate bestmoves up the frontal part of the move list is always desirable. It's an effective nps multiplier actually.

Anyway, interesting to know what your engines percentage hit rate is ....

Chris

[bob]

OK, I'm a bit concerned about the test positions, which might tend to produce numbers that don't match up with games. So how about this instead:

I collect the data you asked for, but I do it in longer games played on ICC, so that at the end of each game I get a summary that tells me how many times the chosen move was first, seconds, third, ..., 99th.

Before I start, one thing I do know is that for deep searches, the last iteration chooses the move ranked #1 about 85% of the time. The paper Monty and I wrote measured that in a different way, namely to determine how frequently we changed our mind (crafty that is) on the last iteration. The answer was about 15% of the time, which means 85% of the time the move from the previous iteration was best in this iteration as well.

[chrisw]

OK, I'm a bit concerned about the test positions, which might tend to produce numbers that don't match up with games. So how about this instead:

I collect the data you asked for, but I do it in longer games played on ICC, so that at the end of each game I get a summary that tells me how many times the chosen move was first, seconds, third, ..., 99th.

Before I start, one thing I do know is that for deep searches, the last iteration chooses the move ranked #1 about 85% of the time. The paper Monty and I wrote measured that in a different way, namely to determine how frequently we changed our mind (crafty that is) on the last iteration. The answer was about 15% of the time, which means 85% of the time the move from the previous iteration was best in this iteration as well.

sounds a fine way to start off.

some thoughts:

it probably is the case that bestmove doesn't change after a few iterations in many positions - but I guess what is interesting for strong play are those cases where newbestmove is found. A high-quality game can often hinge on one magic move, which, for example, a GM might see, and we not, or a strong program see and we not. it's these critical moves that count, so speeding up the finding of them is advantageous for a prog - even if this doesn't occur every iteration.

since fancy moves are often game deciders, then it may be better to concentrate (for this test anyway) on fancy positions - either test positions or game positions where there's a mind change (well, by definition you're concentrating on that anyway) eg it's the 15% that count.

interested to see the stats for slow games ICC ....

if we can eventualy make yours faster on the critical cases then your ELO, win-rate stats also

Chris

[bob]

OK, first to recap my move ordering at the root. For iteration 1, I just make each root move and call Quiesce() with the resulting position and remember this score. After doing this for all moves, I sort them into descending order based on these scores.

Once I start an iteration, I count the nodes searched per individual ply-1 move, and at the end of the iteration, I re-sort all the moves in descending order on these node counts. Only special case is that I make sure that the best move from iteration n-1 is sorted first, regardless of its node count.

For this test, I only counted things after 10 seconds had elapsed, so that the shallow searches did not figure in to the results.

With that said, I did as I said and ran some longish games on our cluster. I played 5 opponents 160 games each, games were of the 60+60 type which average about 2 minutes a move or better.

84% of the time, the best move for iteration N was the best move from iteration N-1. 8% of the time, the best move from iteration N was the second move in the list. This is an example of the flip-flop you see where each iteration switches to a different move, but then the next iteration switches back. 4% of the best moves were ranked #3, which is probably just a more generalized case of the flip flop where now we are doing flip-flap-flop iteration by iteration. The remaining moves were scattered all over the move list, and while I did not go thru all the game move by move, in one case where the best move was ranked #23, this move was an unexpected tactical shot. Normally these moves move up the list iteration by iteration as they take longer and longer to refute, but occasionally one sits at the bottom or near the bottom until WHAM.

So for this test, roughly 19 of every 20 best moves came from the first three in the list. And 17 out of every 20 were already ranked first...

Any other kind of test or numbers to run???

[chrisw]

OK, first to recap my move ordering at the root. For iteration 1, I just make each root move and call Quiesce() with the resulting position and remember this score. After doing this for all moves, I sort them into descending order based on these scores.

Once I start an iteration, I count the nodes searched per individual ply-1 move, and at the end of the iteration, I re-sort all the moves in descending order on these node counts. Only special case is that I make sure that the best move from iteration n-1 is sorted first, regardless of its node count.

For this test, I only counted things after 10 seconds had elapsed, so that the shallow searches did not figure in to the results.

With that said, I did as I said and ran some longish games on our cluster. I played 5 opponents 160 games each, games were of the 60+60 type which average about 2 minutes a move or better.

84% of the time, the best move for iteration N was the best move from iteration N-1. 8% of the time, the best move from iteration N was the second move in the list. This is an example of the flip-flop you see where each iteration switches to a different move, but then the next iteration switches back. 4% of the best moves were ranked #3, which is probably just a more generalized case of the flip flop where now we are doing flip-flap-flop iteration by iteration. The remaining moves were scattered all over the move list, and while I did not go thru all the game move by move, in one case where the best move was ranked #23, this move was an unexpected tactical shot. Normally these moves move up the list iteration by iteration as they take longer and longer to refute, but occasionally one sits at the bottom or near the bottom until WHAM.

So for this test, roughly 19 of every 20 best moves came from the first three in the list. And 17 out of every 20 were already ranked first...

Any other kind of test or numbers to run???

That's already pretty good!

OK, I guess where we are going to be most interested from a chess game point of view is in finding a new shot, a wholly unexpected move of game-changing character.

Now it may well be that your nodecount sort algorithm actually acts as a sufficient sniffer of potential newbestmove such that an improvement that tried to override that is actually no improvement at all.

Anyway, from your figures, and throwing out the no-change iterations

8% = 2nd
4% = third
4% = scattered

50% of the time, you pick 2nd
25% of the time, you pick 3rd
25% of the time, it's random(ish)

the scope for improving this lies in trying another sort mechanism on the remaining moves from 3 to end or 4 to end, I would guess. Does that make sense?

Might be an idea first to take 4 to end at start of each iteration and genuinely randomise them with a card shuffle algorithm. Any change (deterioration) to search time?

One thought did occur to me ....... if these results are from games, are you timing out before the end of an iteration? Or timeout only at iteration end?

Chris

[bob]

OK, first to recap my move ordering at the root. For iteration 1, I just make each root move and call Quiesce() with the resulting position and remember this score. After doing this for all moves, I sort them into descending order based on these scores.

Once I start an iteration, I count the nodes searched per individual ply-1 move, and at the end of the iteration, I re-sort all the moves in descending order on these node counts. Only special case is that I make sure that the best move from iteration n-1 is sorted first, regardless of its node count.

For this test, I only counted things after 10 seconds had elapsed, so that the shallow searches did not figure in to the results.

With that said, I did as I said and ran some longish games on our cluster. I played 5 opponents 160 games each, games were of the 60+60 type which average about 2 minutes a move or better.

84% of the time, the best move for iteration N was the best move from iteration N-1. 8% of the time, the best move from iteration N was the second move in the list. This is an example of the flip-flop you see where each iteration switches to a different move, but then the next iteration switches back. 4% of the best moves were ranked #3, which is probably just a more generalized case of the flip flop where now we are doing flip-flap-flop iteration by iteration. The remaining moves were scattered all over the move list, and while I did not go thru all the game move by move, in one case where the best move was ranked #23, this move was an unexpected tactical shot. Normally these moves move up the list iteration by iteration as they take longer and longer to refute, but occasionally one sits at the bottom or near the bottom until WHAM.

So for this test, roughly 19 of every 20 best moves came from the first three in the list. And 17 out of every 20 were already ranked first...

Any other kind of test or numbers to run???

That's already pretty good!

OK, I guess where we are going to be most interested from a chess game point of view is in finding a new shot, a wholly unexpected move of game-changing character.

Now it may well be that your nodecount sort algorithm actually acts as a sufficient sniffer of potential newbestmove such that an improvement that tried to override that is actually no improvement at all.

Anyway, from your figures, and throwing out the no-change iterations

8% = 2nd
4% = third
4% = scattered

50% of the time, you pick 2nd
25% of the time, you pick 3rd
25% of the time, it's random(ish)

the scope for improving this lies in trying another sort mechanism on the remaining moves from 3 to end or 4 to end, I would guess. Does that make sense?

Might be an idea first to take 4 to end at start of each iteration and genuinely randomise them with a card shuffle algorithm. Any change (deterioration) to search time?

One thought did occur to me ....... if these results are from games, are you timing out before the end of an iteration? Or timeout only at iteration end?

Chris

I "sort of" time out before an iteration ends, with the exceptional condition that I never time out until the current move being searched at the root is completed. THe idea here is that if I am going to switch to this move, it will take much longer than other moves to search and I don't want to quit too soon and give up on what might be a winning move. If I am not going to change to this move, the search flies by anyway and there is little cost.

Back to the issue... yes, it would be interesting to try to find a way to sniff out the good moves that occur late in the list. How to pull that off would be an interesting approach.

The node count idea came from Harry Nelson because he was always working on problems with various problem composers around the world, and he noticed that the actual solution move had a growing node count with respect to the rest of the moves, iteration by iteration. But it turned out that this carried over generally to playing games as well. We've been doing it this way since somewhere in the late 1980's or maybe very early 1990;s... and I carried this over into Crafty as well...

[chrisw]

OK, first to recap my move ordering at the root. For iteration 1, I just make each root move and call Quiesce() with the resulting position and remember this score. After doing this for all moves, I sort them into descending order based on these scores.

Once I start an iteration, I count the nodes searched per individual ply-1 move, and at the end of the iteration, I re-sort all the moves in descending order on these node counts. Only special case is that I make sure that the best move from iteration n-1 is sorted first, regardless of its node count.

For this test, I only counted things after 10 seconds had elapsed, so that the shallow searches did not figure in to the results.

With that said, I did as I said and ran some longish games on our cluster. I played 5 opponents 160 games each, games were of the 60+60 type which average about 2 minutes a move or better.

84% of the time, the best move for iteration N was the best move from iteration N-1. 8% of the time, the best move from iteration N was the second move in the list. This is an example of the flip-flop you see where each iteration switches to a different move, but then the next iteration switches back. 4% of the best moves were ranked #3, which is probably just a more generalized case of the flip flop where now we are doing flip-flap-flop iteration by iteration. The remaining moves were scattered all over the move list, and while I did not go thru all the game move by move, in one case where the best move was ranked #23, this move was an unexpected tactical shot. Normally these moves move up the list iteration by iteration as they take longer and longer to refute, but occasionally one sits at the bottom or near the bottom until WHAM.

So for this test, roughly 19 of every 20 best moves came from the first three in the list. And 17 out of every 20 were already ranked first...

Any other kind of test or numbers to run???

That's already pretty good!

OK, I guess where we are going to be most interested from a chess game point of view is in finding a new shot, a wholly unexpected move of game-changing character.

Now it may well be that your nodecount sort algorithm actually acts as a sufficient sniffer of potential newbestmove such that an improvement that tried to override that is actually no improvement at all.

Anyway, from your figures, and throwing out the no-change iterations

8% = 2nd
4% = third
4% = scattered

50% of the time, you pick 2nd
25% of the time, you pick 3rd
25% of the time, it's random(ish)

the scope for improving this lies in trying another sort mechanism on the remaining moves from 3 to end or 4 to end, I would guess. Does that make sense?

Might be an idea first to take 4 to end at start of each iteration and genuinely randomise them with a card shuffle algorithm. Any change (deterioration) to search time?

One thought did occur to me ....... if these results are from games, are you timing out before the end of an iteration? Or timeout only at iteration end?

Chris

I "sort of" time out before an iteration ends, with the exceptional condition that I never time out until the current move being searched at the root is completed. THe idea here is that if I am going to switch to this move, it will take much longer than other moves to search and I don't want to quit too soon and give up on what might be a winning move. If I am not going to change to this move, the search flies by anyway and there is little cost.

Back to the issue... yes, it would be interesting to try to find a way to sniff out the good moves that occur late in the list. How to pull that off would be an interesting approach.

The node count idea came from Harry Nelson because he was always working on problems with various problem composers around the world, and he noticed that the actual solution move had a growing node count with respect to the rest of the moves, iteration by iteration. But it turned out that this carried over generally to playing games as well. We've been doing it this way since somewhere in the late 1980's or maybe very early 1990;s... and I carried this over into Crafty as well...

Well, my approach (not in CSTal btw) was via neural network. Needless to say I wrote my own generally controllable one in C. I didn't do it too seriously for chess, I was just looking around at things that ANNs could do and things that they couldn't.

What it could do reasonably well was ply one move sorting.