Move Ordering

[makc2299]

Hello chess programming community.
I've been reading the forum for a couple of months now and I'm truly amazed at what a great source of knowledge this is.

At the moment I am working on my little engine and, so far managed to deal with all troubles. But when I started digging into TT I decided to go back and review some earlier topics. So I wasn't really satisfied with my move ordering scheme, I did the standard: winning capture, first/second killer, counter move, history. I tried to improve some of these heuristics in ways suggested in older posts. For example for history i tried to use different increments like 1, depth, depth * depth (stick with depth * depth not found much difference between them), update history not only when score >= beta but also when score > alpha (no significant difference), give penalties to historical values for all moves before one which cause cut-off (this actually came across a few times in old posts and made a difference in my case). I also tried relative history heuristic idea of which seemed to me very convincing but turned out to be worse than normal history in my case. Maybe I messed up with the implementation but there are not many ways to do it, so I doubt. I think this is because the values resulting from division HH_MOVES[color][fromToIndex] / BF_MOVES[color][fromToIndex] often turned out to be 0 because the divisor is much larger, and this flushes the information about moves difference.

Worth mentioned that for testing these things I mostly relied on set of dozens fen positions by which I just looked at whether the number of notes had increased or not. I know it's not optimal, but I really can't afford to run a 1k game for each variation of the move ordering scheme. And even for the 200-300 games that I play, it seems that the result is highly dependent on time control as well.

For the counter move, I tried to change the replacement scheme so that table values are updated only if a new counter move was found at a greater depth than the previous one. No results, even though it sounds more reasonable to me than the usual case where the value is updated anywhere in the tree. Killer moves work fine, so I don't really bother with them.

But now to the point of why I even decided to write a post, quiet moves are not so important, since in most cases the cut-off is caused by TT and captures and for captures I want to figure out how to make ordering really efficient. Until now, I've used SEE to sort the entire list of captures which was not good enough as it created the wrong order for the sequences where P x B = 3, R x R (protected) = 0, so i have to stick with MVV/LVA order. But MVV/LVA has a flaw for HxL captures if victims attacked by more valuable attackers are defended. Now I estimate HxL by SEE and sort with LxH estimate by MVV\LVA. So that the values are comparable MVV/LVA calculate as MVV * F - LVA (i guess the figure always gets recaptured), F - a number large enough to give a right order, MVV and LVA - material value of figures. SEE value also multiplied by F. Promotions and capture promotions generate at the same stage as captures so I need to sort them together. I do it by SEE because I think it's the most accurate because promotions are often recaptured. And lastly, all equal captures are evaluated as follows. For PxP, NxN, BxB, RxR, QxQ I check if figure protected (calling isSquareAttacked() method) and if is, return MVV * F - LVA, if not protected return value attacked figure.

All of the above regarding capture order seems little overthinking to me and i i still not satisfied with that for LxH captures always assumes that attacker will be recaptured (but return attackers value also wrong). Is there a smarter way to do this ? It's also interesting how much information I can afford to get about the moves before it affects performance. For example for PxP, NxN, ... I call isSquareAttacked() method which is not cheap but cheaper than SEE. Is there a cheap way to get information about is the figure that make capture attacked itself or attacked figure is protected ?

So if anyone has any thoughts on all of the above, I'd love to read it.

[hgm]

I once implemented a cheap trick for guessing whether a piece would be protected. It used two global arrays

int protected[ply][square], currentNode[ply];

At the top of Search(), after incrementing the node counter, I remember its value:

currentNode[ply] = ++nodeCount;

Then in the move generator, for all (capture-capable) moves that hit a friendly piece, I do

protected[ply][toSquare] = nodeCount;

to mark the to-square as protected. When the child node then encounters a HxL capture, it considers the victim protected when

protected[ply-1][toSquare] == currentNode[ply-1]

This is not 100% reliable, because the move leading to the child could have destroyed the protection. But if there are many pieces, this is unlikely. And for move ordering you only need something that works most of the time to get an improvement. You could further improve the reliability by also remembering which piece was the protector, and comparing that with the piece moved to reach the child, and assuming that if these are the same, the protection was broken. (If there were no other protectores.) Again not infallible, but still more accurate.

By labeling protected pieces with the node count there is no need to entirely clear the board array for that ply to erase any existing protections it holds; incrementing the node count is enough for that.

[Mike Sherwin]

If depth > 3 (or maybe 2) just play each capture move and call Qsearch to score it.

[makc2299]

I once implemented a cheap trick for guessing whether a piece would be protected. It used two global arrays

int protected[ply][square], currentNode[ply];

At the top of Search(), after incrementing the node counter, I remember its value:

currentNode[ply] = ++nodeCount;

Then in the move generator, for all (capture-capable) moves that hit a friendly piece, I do

protected[ply][toSquare] = nodeCount;

to mark the to-square as protected. When the child node then encounters a HxL capture, it considers the victim protected when

protected[ply-1][toSquare] == currentNode[ply-1]

This is not 100% reliable, because the move leading to the child could have destroyed the protection. But if there are many pieces, this is unlikely. And for move ordering you only need something that works most of the time to get an improvement. You could further improve the reliability by also remembering which piece was the protector, and comparing that with the piece moved to reach the child, and assuming that if these are the same, the protection was broken. (If there were no other protectores.) Again not infallible, but still more accurate.

By labeling protected pieces with the node count there is no need to entirely clear the board array for that ply to erase any existing protections it holds; incrementing the node count is enough for that.

Interesting idea, I'll try it. Thanks.

[makc2299]

If depth > 3 (or maybe 2) just play each capture move and call Qsearch to score it.

I think this is the next step by heaviness after SEE use of which I tried to reduce. But I will take this idea into account. Thanks.

[AngularMomentum]

If depth > 3 (or maybe 2) just play each capture move and call Qsearch to score it.

Maybe I’m missing something, but isn’t this basically internal iterative deepening?

[Whiskers]

Hello chess programming community.
I've been reading the forum for a couple of months now and I'm truly amazed at what a great source of knowledge this is.

At the moment I am working on my little engine and, so far managed to deal with all troubles. But when I started digging into TT I decided to go back and review some earlier topics. So I wasn't really satisfied with my move ordering scheme, I did the standard: winning capture, first/second killer, counter move, history. I tried to improve some of these heuristics in ways suggested in older posts. For example for history i tried to use different increments like 1, depth, depth * depth (stick with depth * depth not found much difference between them), update history not only when score >= beta but also when score > alpha (no significant difference), give penalties to historical values for all moves before one which cause cut-off (this actually came across a few times in old posts and made a difference in my case). I also tried relative history heuristic idea of which seemed to me very convincing but turned out to be worse than normal history in my case. Maybe I messed up with the implementation but there are not many ways to do it, so I doubt. I think this is because the values resulting from division HH_MOVES[color][fromToIndex] / BF_MOVES[color][fromToIndex] often turned out to be 0 because the divisor is much larger, and this flushes the information about moves difference.

Worth mentioned that for testing these things I mostly relied on set of dozens fen positions by which I just looked at whether the number of notes had increased or not. I know it's not optimal, but I really can't afford to run a 1k game for each variation of the move ordering scheme. And even for the 200-300 games that I play, it seems that the result is highly dependent on time control as well.

For the counter move, I tried to change the replacement scheme so that table values are updated only if a new counter move was found at a greater depth than the previous one. No results, even though it sounds more reasonable to me than the usual case where the value is updated anywhere in the tree. Killer moves work fine, so I don't really bother with them.

But now to the point of why I even decided to write a post, quiet moves are not so important, since in most cases the cut-off is caused by TT and captures and for captures I want to figure out how to make ordering really efficient. Until now, I've used SEE to sort the entire list of captures which was not good enough as it created the wrong order for the sequences where P x B = 3, R x R (protected) = 0, so i have to stick with MVV/LVA order. But MVV/LVA has a flaw for HxL captures if victims attacked by more valuable attackers are defended. Now I estimate HxL by SEE and sort with LxH estimate by MVV\LVA. So that the values are comparable MVV/LVA calculate as MVV * F - LVA (i guess the figure always gets recaptured), F - a number large enough to give a right order, MVV and LVA - material value of figures. SEE value also multiplied by F. Promotions and capture promotions generate at the same stage as captures so I need to sort them together. I do it by SEE because I think it's the most accurate because promotions are often recaptured. And lastly, all equal captures are evaluated as follows. For PxP, NxN, BxB, RxR, QxQ I check if figure protected (calling isSquareAttacked() method) and if is, return MVV * F - LVA, if not protected return value attacked figure.

All of the above regarding capture order seems little overthinking to me and i i still not satisfied with that for LxH captures always assumes that attacker will be recaptured (but return attackers value also wrong). Is there a smarter way to do this ? It's also interesting how much information I can afford to get about the moves before it affects performance. For example for PxP, NxN, ... I call isSquareAttacked() method which is not cheap but cheaper than SEE. Is there a cheap way to get information about is the figure that make capture attacked itself or attacked figure is protected ?

So if anyone has any thoughts on all of the above, I'd love to read it.

For captures, PxP, NxN, are automatically good captures and should just be immediately sorted by MVV-LVA. SEE is generally only used when you have a bad capture, like a rook taking a knight, and are trying to make sure it doesn't actually win material like RxB NxB RxN. If a call to SEE winds up good, just return the MVV-LVA value of that capture.

For history heuristic Willow uses [depth * depth + depth - 1] as the history bonus, it gained about 10 elo over a simple depth*depth impl.

How strong is your engine right now? Depending on how good everything else is, it may be better to spend some time working on eval/other search stuff instead. If what you have is bug-free then it's already more than enough for a very strong engine.

Also, I know you don't really want to hear this, but you need to test all the changes you make fully. You can run the games at very short time controls like 8+0.08" to make them go faster, but if there's one thing that engine testing has taught me, it's that anything up to a couple hundred games is completely unreliable. A test can very easily start off at 50 +- 30 and then slowly sink back to nothing (or worse!) over the next thousand games. It may be annoying for you to have to wait, but trust me it's the best thing in the long run.