Move order at ply one: a new idea

[mcostalba]

Dr. Hyatt, I think I really need your cluster here

I have read your interested thread of some time ago regarding the historical reasons why the ordering at ply one is done (when score is equal) counting the nodes searched by each move subtree during the previous iteration.

I think I have come up with a different idea that seems better in my tests but needs confirmation.

The idea is to count the beta-cut offs instead of the nodes.

The advantage is that you can differentiate between _our_ beta cutoffs and _opponent_ cutoffs. So you actually have two counters:

int64_t betaCounter[2];

That are reset to zero before searching each root move. When a beta cutoff occurs you increment the counter:

betaCounter[pos.sideToMove()]++;

When root search returns you store the two values:

ourBeta = betaCounter[us];
oppBeta = betaCounter[them];

At the beginning of the next iteration you sort root moves as usually but using betaCounter instead of nodes. So here we have different schemes both for sorting and for increment the counter:

SORTING POLICY:

- Sort on ourBeta value
- Sort on oppBeta value (seems the best!)
- Sort on sum of betas, i.e. on total beta number

INCREMENT POLICY

When a beta cutoff occurs

- Increment the counter (as seen previously)
- Add depth ( betaCounter[threadID][pos.sideToMove()] += depth; )
- Add negated depth (betaCounter[threadID][pos.sideToMove()] += 20-depth;)
- Add the ply (this gives advantage to subtrees that goes further in the search).


I really hope you find this idea interesting because I would like you give it a try on your big iron and post the results.

Thanks in advance
Marco

[Sven]

I have not tried this yet, but I have two questions regarding your very interesting idea:

- For move ordering at the root, sorting criteria must be applied to each single move in the root move list, so I guess one single pair of "beta counters" would not be sufficient. How do you manage this? How do you compare the number of beta cutoffs move A produced with the number of beta cutoffs of move B? I'm pretty sure you do this correctly but I just don't see it from your code example.

- How do you handle the best move, and all other root moves that do not fail low and therefore possibly do not produce a high number of cutoffs? Even when the best move will be sorted first for the next iteration since it becomes the hash move, other moves that don't fail low might become a problem since their number of cutoffs might be less comparable to that of other moves.

Sven

[mcostalba]

I have not tried this yet, but I have two questions regarding your very interesting idea:

- For move ordering at the root, sorting criteria must be applied to each single move in the root move list, so I guess one single pair of "beta counters" would not be sufficient. How do you manage this? How do you compare the number of beta cutoffs move A produced with the number of beta cutoffs of move B? I'm pretty sure you do this correctly but I just don't see it from your code example.

If you already have an implementation based on searched nodes, simply add two fields (ourBeta and theirBeta) to the same struct you use to store searched nodes for each move. In Stockfish/Glauring is struct RootMove. Then copy the results to them.

Conceptually and also technically it is almost the same of how you handle searched nodes for each move. Modifications in this regards are at a bare minimum. Actually you can implement the whole idea with about 10-20 lines of code.

- How do you handle the best move, and all other root moves that do not fail low and therefore possibly do not produce a high number of cutoffs? Even when the best move will be sorted first for the next iteration since it becomes the hash move, other moves that don't fail low might become a problem since their number of cutoffs might be less comparable to that of other moves.

Sven

I am not sure that a move that do not fail low does not produce an high number of cutoffs.

Actually I would be not surprised of the contrary: if a move doesn't fail low it means the search goes very deep before to return so an high number of cutoffs are produced in the secondary branches of the search.


Marco

[Sven]

How do you compare the number of beta cutoffs move A produced with the number of beta cutoffs of move B? I'm pretty sure you do this correctly but I just don't see it from your code example.

If you already have an implementation based on searched nodes, simply add two fields (ourBeta and theirBeta) to the same struct you use to store searched nodes for each move. In Stockfish/Glauring is struct RootMove. Then copy the results to them.

Conceptually and also technically it is almost the same of how you handle searched nodes for each move. Modifications in this regards are at a bare minimum. Actually you can implement the whole idea with about 10-20 lines of code.

O.k., now I got it.

- How do you handle the best move, and all other root moves that do not fail low and therefore possibly do not produce a high number of cutoffs?

I am not sure that a move that do not fail low does not produce an high number of cutoffs.

Actually I would be not surprised of the contrary: if a move doesn't fail low it means the search goes very deep before to return so an high number of cutoffs are produced in the secondary branches of the search.

Maybe you are right. I did a very quick test with my engine and saw a close relation between node count and number of cutoffs regarding their ordering, for each single root move. This includes also the best move and others that do not get refuted.

However, to get a significant improvement would require at least to get a different ordering based on cutoffs in "enough" cases, as compared to the ordering based on node counts. I doubt that currently but of course this can only be examined by trying it, which was your main intent here.

Sven

[bob]

How do you compare the number of beta cutoffs move A produced with the number of beta cutoffs of move B? I'm pretty sure you do this correctly but I just don't see it from your code example.

If you already have an implementation based on searched nodes, simply add two fields (ourBeta and theirBeta) to the same struct you use to store searched nodes for each move. In Stockfish/Glauring is struct RootMove. Then copy the results to them.

Conceptually and also technically it is almost the same of how you handle searched nodes for each move. Modifications in this regards are at a bare minimum. Actually you can implement the whole idea with about 10-20 lines of code.

O.k., now I got it.

- How do you handle the best move, and all other root moves that do not fail low and therefore possibly do not produce a high number of cutoffs?

I am not sure that a move that do not fail low does not produce an high number of cutoffs.

Actually I would be not surprised of the contrary: if a move doesn't fail low it means the search goes very deep before to return so an high number of cutoffs are produced in the secondary branches of the search.

Maybe you are right. I did a very quick test with my engine and saw a close relation between node count and number of cutoffs regarding their ordering, for each single root move. This includes also the best move and others that do not get refuted.

However, to get a significant improvement would require at least to get a different ordering based on cutoffs in "enough" cases, as compared to the ordering based on node counts. I doubt that currently but of course this can only be examined by trying it, which was your main intent here.

Sven

When I have time, I will try to test this. It will take a bit of changing to the current code to both measure the cutoffs and then use them to sort the moves. I am not sure it will do better, although it might help in tactical test suites in some way. The one thing the current node count does not "capture" is "why is the sub-tree for this node larger than most others?" This could be because the cutoffs are not happening with the same frequency because at the new depth it is getting harder and harder to refute key branches. It could be because there are lots of checks that make the branh bushier than normal, even though the branch is not a real candidate to become best. It could be that the current move ordering is just not working very well, which makes the tree explode but again with no real chance to become the best move.

I am not quite sure how your idea will pick up on the last two cases and leave them low in the list, while picking up on the first one and moving it up as we do now.

I even want to run a cluster test with the node-sort disabled as I now (and have for a long while) sort the root moves with a q-search call after making each move which is more accurate than static ordering I had used in the past. It might well be best now to just leave the move list alone and let the best moves bubble to the top naturally...

[Gerd Isenberg]

Dr. Hyatt, I think I really need your cluster here

Poor Dr. Hyatt, so much to try

The idea of node counts is based on the assumption that those moves with huge counts are more likely to become the new pv. The scheme somehow penalizes moves with "well ordered" sub-trees

What about further statistics for instance how often re-searches at pv-nodes occur, and how often it was a false "alarm". For zero window nodes, one may consider the parity of the ply-distance to the pv-node above (expected cut-nodes are odd, expected all-nodes even). And how often they behave not as expected (for each root move).

Another thing to consider - if best so far > drawscore, and some other move returns a true draw score with a very small subtree - scoring this move high makes sense. If the first move suddenly fails low far below draw score in the next iteration, it is good to find a fast draw early, before searching for something better.

[Michael Sherwin]

Dr. Hyatt, I think I really need your cluster here

I have read your interested thread of some time ago regarding the historical reasons why the ordering at ply one is done (when score is equal) counting the nodes searched by each move subtree during the previous iteration.

I think I have come up with a different idea that seems better in my tests but needs confirmation.

The idea is to count the beta-cut offs instead of the nodes.

The advantage is that you can differentiate between _our_ beta cutoffs and _opponent_ cutoffs. So you actually have two counters:

int64_t betaCounter[2];

That are reset to zero before searching each root move. When a beta cutoff occurs you increment the counter:

betaCounter[pos.sideToMove()]++;

When root search returns you store the two values:

ourBeta = betaCounter[us];
oppBeta = betaCounter[them];

At the beginning of the next iteration you sort root moves as usually but using betaCounter instead of nodes. So here we have different schemes both for sorting and for increment the counter:

SORTING POLICY:

- Sort on ourBeta value
- Sort on oppBeta value (seems the best!)
- Sort on sum of betas, i.e. on total beta number

INCREMENT POLICY

When a beta cutoff occurs

- Increment the counter (as seen previously)
- Add depth ( betaCounter[threadID][pos.sideToMove()] += depth; )
- Add negated depth (betaCounter[threadID][pos.sideToMove()] += 20-depth;)
- Add the ply (this gives advantage to subtrees that goes further in the search).


I really hope you find this idea interesting because I would like you give it a try on your big iron and post the results.

Thanks in advance
Marco

My very first attempt at a chess program was in 6502 assembler on an Atari 800 and it could make a list of moves if given a position.

Then years later I got an IBM 8086 machine dirt cheap and translated the Atari assembler to IBM 16 bit assembler. But, before I could finish making it play chess (a long time had passed) I got an 80386. I translated the code to 32 bit and managed with some effort to create a working but not quite legal engine.

This engine could hold it's own against Chessmaster 5000 untill the endgame. Now here follows the interesting part.

It was a material only engine, except that it kept track of the beta cutoffs for the root moves like you describe. It then played the best material score that had the largest number of beta cutoffs. The play was 'inspired', however, it always made captures when it could as those get the highest number of cutoffs.

[mcostalba]

When I have time, I will try to test this.

Thanks !


Actually I would foreseen (with a big margin of error) that the ordering on the total number betas, us + opponent, would not differ to much form node counts.

The plus of this scheme is the flexibility and the possibility to tweak that you don't have for plain node counts.

As example I was surprised that first results show an advantage when you order on opponent beta (not on your good moves but on opponent good moves) this is somehow unexpected. Perhaps an explanation could be that when you find a real good move all the other moves of your ply will get a cutoff from the opponent becasue are sensibly lower then your first choice move.

Another promising tweak is the weighted increment on negated depth (betaCounter +=20-depth) or on ply number (betaCounter += ply). This gives bias to searches that go deeper. Note that also node count gives an indirect bias to deeper searches becasue number of nodes at low depths is bigger then at high depths. Weighting on ply just gives another push in the same direction.


Marco