Ply one move sorting

[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...

I asked about timeout, because, if you timeout before the iteration end (and I take your point that you always wait for current root move to complete) then, that means, that in the final iteration the results for bestmove-changemind for our test could be skewed (by not looking at the full move list).

[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...

I asked about timeout, because, if you timeout before the iteration end (and I take your point that you always wait for current root move to complete) then, that means, that in the final iteration the results for bestmove-changemind for our test could be skewed (by not looking at the full move list).

Certainly correct. I could avoid counting anything until an iteration completes, which means a last partial iteration would not influence the data...

[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...

I asked about timeout, because, if you timeout before the iteration end (and I take your point that you always wait for current root move to complete) then, that means, that in the final iteration the results for bestmove-changemind for our test could be skewed (by not looking at the full move list).

Certainly correct. I could avoid counting anything until an iteration completes, which means a last partial iteration would not influence the data...

May as well give that test run a shot. Is it worth also doing a timing test on a 4 to N random shuffle vs the current sort method - see how much speed improvement over random you already got?

If you reckon it is worthwhile, I can whizz you through the neural network idea. It will involve writing your own ANN, but that should take no more than a week (I built mine basically on Chapter 8 of Hopgood, Intelligent Systems for Engineers and Scientists - which has all the required info, including the back-error propagation algorithm needed for learning, and prob the most complex part to do).

Chris

[mambofish]

For small lists, insertion sort is better than bubble sort. It's even more so on modern hardware.

Well, for really small lists up to 7 or 8 items, a network sort blows everything else out of the water. Ermintrude sorts the moves at every ply in the tree and uses a network sort if there are 7 or less moves found, and a fast heapsort if there are more. Typically, in qsearch, there are only a few captures at any one ply, and as the program spends most of its time in qsearch, the cost of sorting is neglible.