Quiescence Failure For Chess Varient

[jdm64]

If you get non-sensical moves, my guess is that you have a search bug. By limiting the search depth to a very low value (like 1 or 2 ply), and examining the tree, it should be easy to find the variations that get a non-sensical score.

Well, I've done some basic testing just with Negascout (the tree becomes exponentially large at 3+ depth and I'm not sure how to display/visualize the tree). It gives reasonable results for depth 1 and 2 (ie. computer's move and counter move). But it falls apart setting the depth to 3, which would be the computer's second move. It seams that search becomes "unstable". Since my move ordering/scoring puts checking first, it thinks the best move is to place the opponent under check instead of capturing a piece (I'm assuming that it's finding a cutoff to soon?). Henceforth, it will sometimes place a piece that will instantly get captured because it thinks the opponent will go for the check instead. My evaluation function is similar to the following, and I calculate all moves for a ply then sort by score -- high to low.

Code: Select all

(white material) - (black material) + (huge check bonus)

There's a slight improvement if I make the leaf node return just the material score without the check bonus (while still keeping the same sort ordering). But, still about 50% of the values that propagate to the top should be much lower than they are (and a few are marked low, but are not). Many of those are moves that result in an instant capture. I'm beginning to think that material balance alone isn't going to work. Is there any changes in the search or evaluation that might counteract the insistence on checking, but without making the computer play only defensive?

[Greg Strong]

If you get non-sensical moves, my guess is that you have a search bug. By limiting the search depth to a very low value (like 1 or 2 ply), and examining the tree, it should be easy to find the variations that get a non-sensical score.

Well, I've done some basic testing just with Negascout (the tree becomes exponentially large at 3+ depth and I'm not sure how to display/visualize the tree). It gives reasonable results for depth 1 and 2 (ie. computer's move and counter move). But it falls apart setting the depth to 3, which would be the computer's second move. It seams that search becomes "unstable". Since my move ordering/scoring puts checking first, it thinks the best move is to place the opponent under check instead of capturing a piece (I'm assuming that it's finding a cutoff to soon?). Henceforth, it will sometimes place a piece that will instantly get captured because it thinks the opponent will go for the check instead. My evaluation function is similar to the following, and I calculate all moves for a ply then sort by score -- high to low.

Code: Select all

(white material) - (black material) + (huge check bonus)

There's a slight improvement if I make the leaf node return just the material score without the check bonus (while still keeping the same sort ordering). But, still about 50% of the values that propagate to the top should be much lower than they are (and a few are marked low, but are not). Many of those are moves that result in an instant capture. I'm beginning to think that material balance alone isn't going to work. Is there any changes in the search or evaluation that might counteract the insistence on checking, but without making the computer play only defensive?

Do you have a Check extension implemented? If not, I think you might be suffering from a horizon effect. Say we're searching to depth 3, and we're already at depth 2 and we're about to lose a piece. But if we give check, even if that check doesn't accomplish anything in the long run, it allows us to postpone that loss for a move, pushing the loss over the "horizon." This can lead to disasterous play if you are doing fixed depth and no q-search.

So, first test ... Add check extension - that is, at any position, if side-to-move is in check, add one to the remaining search depth.

Also, you should not order checking moves first. With check extension, if you put those moves first, the size of your tree will explode. You want to order captures first because those reduce the size of the tree.

For evaluation, I'd get rid of the bonus for checking positions. If you're going to expand your eval beyond straight material, the next best thing, and it's relatively easy, is piece-square-tables. Give pieces a bonus for being centralized, and a penalty for being sidelined, except the king, of course...

[hgm]

There's a slight improvement if I make the leaf node return just the material score without the check bonus (while still keeping the same sort ordering). But, still about 50% of the values that propagate to the top should be much lower than they are (and a few are marked low, but are not). Many of those are moves that result in an instant capture. I'm beginning to think that material balance alone isn't going to work. Is there any changes in the search or evaluation that might counteract the insistence on checking, but without making the computer play only defensive?

If your evaluation contains material only, the computer should play for the most material, rather than blundering it away. So it is clear that you have a bug, and adding other evaluation terms will not make it go away.

The most efficient way I know to debug this kind of thing is to put a print statement just after the recursive call, that prints ply, depth (and possibly IID depth), the move just searched and its score (and perhaps the best score so far). If that gives you to much output to manage, just put an if-clause in front of it to let the printing happen only in those nodes you are interested in. I usually have a global array of moves 'path', where I record the current path by setting path[ply] = currentMove; in MakeMove(), and a small routine that returns TRUE if the current path matches (the first part of) a given debugPath[], so that I can write: if(PathMatch()) printf(...);.

With this simple infra-structure in place, I then first print the scores of all moves in the root, (by having an empty debugPath[]), and if I see a move that seems to have a wrong score (bound), I add that move to the debugPath, and repeat the search. This then gives me the move list of the node the suspect move leads to, so I can see wich move is unjusty thought to refute it, or if the move that should have refuted it is searched at all. That makes you zoom in towards the problem pretty quickly.

[jdm64]

If your evaluation contains material only, the computer should play for the most material, rather than blundering it away. So it is clear that you have a bug, and adding other evaluation terms will not make it go away.

The most efficient way I know to debug this kind of thing is to put a print statement just after the recursive call, that prints ply, depth (and possibly IID depth), the move just searched and its score (and perhaps the best score so far). If that gives you to much output to manage, just put an if-clause in front of it to let the printing happen only in those nodes you are interested in. I usually have a global array of moves 'path', where I record the current path by setting path[ply] = currentMove; in MakeMove(), and a small routine that returns TRUE if the current path matches (the first part of) a given debugPath[], so that I can write: if(PathMatch()) printf(...);.

Thanks for the suggestion of printing debugging info. I was able to implement it.

From the what I've found with the little testing I've done, I made two modifications to the search. It no longer instantly blunders away it's pieces. But the changes I made make me wonder if there's another bug. Or maybe it's necessary because of the unique placement moves. Maybe I don't understand the search, but I've always seen the beta cutoff as: if (alpha >= beta) instead of what has seemed to improved my engine: if (alpha > beta). Also the ending fail-hard after searching all moves -- I've always seen it as return alpha. But, to prevent the stupid moves, I now return getMaxScore(ptr) which returns the highest score even if alpha wasn't improved.

My questions are:
Are my changes what are commonly found in other engines? Or is the search algorithm, now implemented incorrectly?
Should I be looking for another bug? Or does this seam natural for the unique rules of my chess game (being able to place pieces that can instantly be captured)?

[hgm]

This strongly suggest that there still is some other bug in the implementation of alpha-beta pruning. Normally, when alpha == beta you should be able to take the cutoff, as this means that in some lower node the score can now become at most equal to the best score you already had there, and in that case you stick with the move you already had.

Fail-hard is much more sensitive to such bugs than fail soft, because it always returns a score on the edge of the window when a cutoff occurs. So the slightest error in setting the window limits will make a branch that was cut fall in-window, so it will be chosen as new PV without having been fully searched. Fail soft can mask such bugs much easier, because most of the cutoffs have bounds well awa from the window, that stay out-of-window even when the window limits where not entirely correct.

The best way to find the bug is keep using fail hard and the test if(alpha>=beta) for cutoffs, and then tracing the tree to find how a score that was a bound (because of a beta cutoff) was able to propagate to the root and be treated as an exact score there. Another way to check it would be to explicitly keep track of the bound-type a score represents, and return that info together with the score itself. You cound then check for wrong usage of bound (e.g. a score that does not improve alpha should not be a lower bound, and a score that does improve alpha should not be a lower bound).

[adams161]

the type of error you are getting can be an evaluate error. simple errors are flipping the pieces your holding so holding a bishop actually you count for wrong side. one trick with evaluate is i play a game and flash the before search evaluate. i.e. call evaluate on the current position to be searched. if you don't see the score add up to what it should , you can catch stuff quick, like the pieces held not adding right.

Mike

[adams161]

missed reading full thread first. didnt get off first page this above might be covered

[jdm64]

This strongly suggest that there still is some other bug in the implementation of alpha-beta pruning. Normally, when alpha == beta you should be able to take the cutoff, as this means that in some lower node the score can now become at most equal to the best score you already had there, and in that case you stick with the move you already had.

Found the problem (hopefully)! It was a fairly stupid one. I didn't understand how KillerMove sort ordering worked. I was placing them first, but I guess I'm suppose to sort them after captures and only include non-captures for killermoves. Currently, I've removed the killermove altogether and it plays much faster/better.

I do have another question. The negascout re-search condition is (score > alpha && score < beta). Now my score is an int, and when it's searching in a null-window it would never do a re-search (beta = alpha + 1). I did some simple testing using (alpha >= score <= beta) and it plays about the same -- maybe a little worse. Why does the re-search that can't happen not destroy the search algorithm?

[hgm]

If beta = alpha+1 there is no need to do any re-search. The re-search is only needed because in nodes with open window you did search the move initially with a false beta, artificially set to alpha+1, rather than with the true beta. If the true beta already was alpha+1, you have done the correctsearch in the first place.

It is still suspect that changing the move ordering would give you other moves. Your killer code must have done more than merely changing the move ordering, if disabling it makes it play different moves. It sounds like in stead it made killer moves disappear altogether. I once had that error in one of my engines: I updated the killer table already in an early iteration of Internal Iterative Deepening, which effectively removed the killer from the move list, because the loop through 'remaining moves' assumed that the killer had already been searched in the killer phase, (and thus skipped it), which was not the case, because it was a new killer not yet present in the killer table when killer moves were put at the front of the move list.