Quiescence Search doesn't improve strength

[lithander]

I have tried to add quiescence search to MinimalChess my search which is basically just alpha-beta with move ordering. But it didn't improve playing strength at all. I've spent hours trying to find the bug and started to wonder if there's a bug at all? Could it be that q-search is working fine but doesn't provide a benefit because my search depth is rather shallow and the evaluation too simplistic?

I'm just counting material for my evaluation. I kept it that simple for now because it allows me to verify the correctness of the score manually.
But it means that my engine thinks that this is a neutral position, while Stockfish rates it as +17 for white!

[d]rn3rk1/1q1b1p2/2p5/p4p2/RbBP4/4QNP1/1P3PK1/1N3R2 b - - 5 21

Evaluating it by counting material evaluates to zero! Evaluating it using q-search also evaluates to zero, right? If material is all that matters that is correct. All previous positions are also neutral so the engine didn't do anything wrong so far by it's standards. But now there are only two moves that are not mate in 5 or less and to find them I'd need to search 10 plys deep which my engine can't do on fast time controls. Even if I find them this is a losing position. How would qsearch help with any of that?

So do you think there's likely a bug in my qsearch and once I fix it I should see a significant improvement in self play? Or could it be that there is no bug but without a more sophisticated evaluation function MinimalChess will just play itself into positions that are so hopeless that qsearch just doesn't make enough of a difference?

[hgm]

These are two separate problems: material-only evaluation or QS. The example only relates to the former. You need a King-Safety term in the evaluation to see how precarious the black position is. And if you don't have it, it is unavoidable that positions where the King Safeties differ much between the players get mis-evaluated.

Lack of QS, however, should in general lead to completely idiotic play up to an appreciable depth. What you typically see is that the engine thinks it can make a huge gain by grabbing a protected minor or Rook with its Queen on the last move before the horizon, and is willing to sacrifice minor material in the preceding moves in order to keep the opponent busy, so that he cannot 'rescue' the piece that is attacked by the Queen. E.g. it plays BxP right away, because it figures that when you recapture the Bishop, it would grab the piece the Queen attacks, gaining a Pawn in total. Or, when you don't recapture the bishop, it gained a Pawn immediately. Or it pushes a Pawn to an unsafe square to attack a piece.

It is hard to imagine that this kind of behavior would not severely damage its playing strength. And having QS should cure it.

If it doesn't, I would suspect QS is not working properly.

You could test the program at 1 ply + QS, to see if it blunders material away (which it would most certainly do at 1 ply without QS!). If you find a position where it does blunder, you could dump the search tree, and check what it faield to search that it should have searched.

[Sven]

This position is way too complex for testing whether qsearch works. You can simply play a few moves from the start position. A fixed search of few plies without QS will often return a material win due to the horizon effect. Let your engine search 3 plies from an opening position. Without QS it will see lines where the last ply is a capture but the recapture is beyond the horizon. That should go away with QS. To really test the strength improvement you need to play many automated games anyway, without vs. with QS. The improvement should always be very significant.

Of course even a 1-ply search would be sufficient here.

[lithander]

Thanks guys! Limiting the search depth instead of limiting the time in the self-play test makes a lot of sense. That way only correct implementation matters. If QS doesn't improve the play it must be a bug and can't be explained by the speed-reduction of the evaluation or anything like that. I'll try that!

[mvanthoor]

If you do not have any PST's, then where do you know where to put your pieces? Every position where material is equal will actually be considered equal, but that is of course not true.

With regard to testing QSearch: you can do this with a fixed ply of one. Set up a very simple position such as this:

[d]4r1k1/4nppp/2b5/1r2N3/5P2/3Q4/6PP/5RK1 w - - 0 1

Then set the depth to 1 and do a one-ply search. The engine will probably go for Qd3xb5, because that is the largest possible gain. If you implement QSearch correctly, the engine won't play that move, even on depth 1, because it will see that it will lose the Queen. If QSearch is working correctly, the engine should see, even on depth 1, that the correct move is Ne5xc6, because it removes the bishop defending Rb5. If black recaptures, the queen captures the Rook.

Rustic, depth 1 search:

Code: Select all

board

8   . . . . r . k .
7   . . . . n i i i
6   . . b . . . . .
5   . r . . N . . .
4   . . . . . I . .
3   . . . Q . . . .
2   . . . . . . I I
1   . . . . . R K .

    A B C D E F G H

Zobrist key:        543ca32189ca3dfe
Active Color:       White
Castling:           -
En Passant:         -
Half-move clock:    0
Full-move number:   1

go depth 1
info score cp 420 depth 1 seldepth 5 time 0 nodes 10 nps 0 pv e5c6
bestmove e5c6

However, the best move for black is to not recapture after Nxc6, because it will then only lose a bishop instead of a rook.

Depth 2:

Code: Select all

go depth 2
info score cp 420 depth 1 seldepth 5 time 0 nodes 10 nps 0 pv e5c6
info score cp 405 depth 2 seldepth 6 time 0 nodes 139 nps 0 pv e5c6 b5b2

As you can see, black moves the Rook away. What it can not see using QSearch is that white can now capture Nxe7+, because if black recaptures with the Rook Re8xe7, he will be mated on the back rank with Qd5d8+. You need more search depth for that. After Nxc6 Rb2 Nxe7 Rxe7 the position is quiet, and it's the best position black can see on depth 2.

It can't yet see it at depth 3, but at depth 4, it sees that covering the knight on e7 (with Rb5b7) to not lose more material is essential:

go depth 3
info score cp 420 depth 1 seldepth 5 time 0 nodes 10 nps 0 pv e5c6
info score cp 405 depth 2 seldepth 6 time 0 nodes 139 nps 0 pv e5c6 b5b2
info score cp 420 depth 3 seldepth 6 time 0 nodes 571 nps 0 pv e5c6 b5c5 c6d4

go depth 4
info score cp 420 depth 1 seldepth 5 time 0 nodes 10 nps 0 pv e5c6
info score cp 405 depth 2 seldepth 6 time 0 nodes 139 nps 0 pv e5c6 b5b2
info score cp 420 depth 3 seldepth 6 time 0 nodes 571 nps 0 pv e5c6 b5c5 c6d4
info score cp 445 depth 4 seldepth 10 time 1 nodes 4897 nps 4897000 pv e5c6 b5b7 d3e4 b7c7

When doing a full search, you can see how far QSearch (and check extension) actually extends (in the seldepth parameter):

Code: Select all

info score cp 420 depth 1 seldepth 5 time 0 nodes 10 nps 0 pv e5c6
info score cp 405 depth 2 seldepth 6 time 0 nodes 139 nps 0 pv e5c6 b5b2
info score cp 420 depth 3 seldepth 6 time 0 nodes 571 nps 0 pv e5c6 b5c5 c6d4
info score cp 445 depth 4 seldepth 10 time 1 nodes 4897 nps 4897000 pv e5c6 b5b7 d3e4 b7c7
info score cp 445 depth 5 seldepth 11 time 7 nodes 19523 nps 2789000 pv e5c6 b5b7 d3e4 b7c7 c6d4
info score cp 445 depth 6 seldepth 14 time 43 nodes 171114 nps 3979395 pv e5c6 b5b7 d3e4 b7c7 c6d4 c7c3
info score cp 445 depth 7 seldepth 16 time 226 nodes 700354 nps 3098912 pv e5c6 b5b7 f1e1 b7c7 c6d4 c7c5 d3e4
info score cp 475 depth 8 seldepth 18 time 1458 nodes 5656060 nps 3879328 pv e5c6 b5b7 f1e1 f7f6 d3e4 g8f8 f4f5 f8f7
info score cp 615 depth 9 seldepth 20 time 7543 nodes 26768146 nps 3548740 pv e5c6 b5b7 f1e1 f7f5 c6d8 b7b4 d3d5 g8h8 d5d7 e8d8 d7d8
info score cp 610 depth 10 seldepth 22 time 45987 nodes 173177588 nps 3765794 pv e5c6 b5b7 f1e1 f7f5 c6d8 b7b4 d3d5 g8h8 d5d7 e8d8 d7d8 e7g8

With regard to the position you provided, Rustic sees that black will end up in the negative. The negative becomes larger as it searches deeper (hopefully it'll be able to go deeper this weekend):

Code: Select all

go
info score cp 10 depth 1 seldepth 5 time 0 nodes 55 nps 0 pv b7b6
info score cp -10 depth 2 seldepth 12 time 0 nodes 936 nps 0 pv b7c7 g2g1
info score cp -35 depth 3 seldepth 13 time 3 nodes 20333 nps 6777667 pv f8e8 e3g5 g8f8 g2g1
info score cp -40 depth 4 seldepth 19 time 32 nodes 155622 nps 4863188 pv f8e8 e3g5 g8f8 g5f6 e8e7
info score cp -135 depth 5 seldepth 20 time 178 nodes 761646 nps 4278910 pv f8c8 e3g5 g8f8 g5f6 f8g8 c4f7 g8h7
info score cp -135 depth 6 seldepth 22 time 2151 nodes 6929962 nps 3221740 pv f5f4 e3f4 b4e7 f4e4 e7f6 a4a2
info score cp -230 depth 7 seldepth 25 time 32941 nodes 100337476 nps 3045975 pv f5f4 e3e5 b4e7 f1h1 e7f6 e5f6 f4g3 f2g3 b7b2

[lithander]

With regard to testing QSearch: you can do this with a fixed ply of one. Set up a very simple position such as this:

[d]4r1k1/4nppp/2b5/1r2N3/5P2/3Q4/6PP/5RK1 w - - 0 1

Then set the depth to 1 and do a one-ply search. The engine will probably go for Qd3xb5, because that is the largest possible gain. If you implement QSearch correctly, the engine won't play that move, even on depth 1, because it will see that it will lose the Queen. If QSearch is working correctly, the engine should see, even on depth 1, that the correct move is Ne5xc6, because it removes the bishop defending Rb5. If black recaptures, the queen captures the Rook.

What it can not see using QSearch is that white can now capture Nxe7+, because if black recaptures with the Rook Re8xe7, he will be mated on the back rank with Qd5d8+. You need more search depth for that. After Nxc6 Rb2 Nxe7 Rxe7 the position is quiet, and it's the best position black can see on depth 2.

Thanks for the testcase and the walkthrough. Especially the explanation helps considering my chess knowledge is way below the average chess programmer. (working on it) But your example however does not make me happy because it seems to confirm what is my core problem: Qsearch seems fine but it doesn't help the engine play better.

Here are my PVs with QSearch enabled:

Code: Select all

info depth 1 score cp 400 nodes 44 nps 44000 time 0 pv e5c6
info depth 2 score cp 400 nodes 126 nps 126000 time 1 pv e5c6 b5b7
info depth 3 score cp 400 nodes 2082 nps 1041000 time 2 pv e5c6 b5b7 c6e7
info depth 4 score cp 400 nodes 5281 nps 293388 time 18 pv e5c6 b5b7 c6e7 e8e7
info depth 5 score cp 400 nodes 77744 nps 1274491 time 61 pv e5c6 b5b7 c6e7 b7e7 d3b5

MinimalChess moves the rook away but to a position where it can then recapture the Knight after Nxe7+ with the Rook Rb7xe7 while the other rook still prevents back-rank check. Notice how it homes in on that PV right from the start. (is it luck?) Also note how the cp evaluation is 400 all the time, no horizon effect that I can see. (good, right?) And that's the resulting position:

[d]4r1k1/4rppp/8/8/5P2/3Q4/6PP/5RK1 w - - 0 3

Counting material that's 400cp and it's quiet. Stockfish says it's +4.3!
Well done QSearch, right?

But the problem is that without QSearch enabled the best move 'e5c6' is found after 2 plys, too.

Code: Select all

info depth 1 score cp 600 nodes 45 nps 9000 time 5 pv d3b5
info depth 2 score cp 100 nodes 176 nps 25142 time 7 pv e5c6 e7c6
info depth 3 score cp 600 nodes 1863 nps 266142 time 7 pv e5c6 e7c6 d3b5
info depth 4 score cp 400 nodes 4210 nps 382727 time 11 pv e5c6 b5b7 c6e7 e8e7
info depth 5 score cp 600 nodes 54877 nps 2743850 time 20 pv e5c6 b5b7 d3e3 e7c6 e3e8
info depth 6 score cp 400 nodes 134142 nps 1023984 time 131 pv e5c6 b5b7 d3e3 e8f8 c6e7 b7e7
info depth 7 score cp 800 nodes 2016171 nps 2839677 time 710 pv e5c6 b5b7 d3e4 b7d7 c6e7 g8h8 e4h7

And after searching 7 plys it comes up with a PV that starts with "e5c6 b5b7 d3e4..." which leads to this position:

[d]4r1k1/1r2nppp/2N5/8/4QP2/8/6PP/5RK1 b - - 2 2

Counting material that's 400cp, too, but Stockfish says it's +5.4! It's better! Not by my rudimentary evaluation where it is equal but objectively.

So your testcase seems to confirm that:
(1) QSearch appears to work fine
and
(2) Searching 7 or 8 plys deep *without* QSearch produces lines that are actually better than the ones with QSearch enabled.

And running tournaments with both versions confirms that this is not an outlier. I can't wrap my head around it.

(But I will do these test HGM and Sven suggested. That's methodical and sound and doesn't require me to think so much! )

[mvanthoor]

Counting material that's 400cp and it's quiet. Stockfish says it's +4.3!
Well done QSearch, right?

It seems alright to me. Rustic says (with it's simple material count and PST eval) that the position is +4.15 for white. (Which is probably correct; +5 for the rook, and the additions or subtractions is PST stuff.)

But the problem is that without QSearch enabled the best move 'e5c6' is found after 2 plys, too.

Given enough time, a deeper search will find the same things as QSearch will find. The point of QSearch is to find the good and bad captures faster. (Especially if you do MVV-LVA move ordering in QSearch.) As you can see in my seldepth, the depth is only 10, but the deepest QSearch it did while reaching that depth was up to 22 ply. So, if you have no QSearch, the engine would find the same results at around 22 ply, but it must search a lot more moves to get there. QSearch just does extra plies, on top of the depth, but with only captures, and it cuts off bad captures ASAP to reach the quiet positions ASAP.

And after searching 7 plys it comes up with a PV that starts with "e5c6 b5b7 d3e4..." which leads to this position:

[d]4r1k1/1r2nppp/2N5/8/4QP2/8/6PP/5RK1 b - - 2 2

Counting material that's 400cp, too, but Stockfish says it's +5.4! It's better! Not by my rudimentary evaluation where it is equal but objectively.

Rustic says +5.20 after depth 9:

Code: Select all

info score cp -445 depth 1 seldepth 5 time 0 nodes 67 nps 0 pv b7c7
info score cp -445 depth 2 seldepth 6 time 0 nodes 247 nps 0 pv b7c7 c6d4
info score cp -445 depth 3 seldepth 9 time 0 nodes 3549 nps 0 pv b7c7 c6d4 c7c3
info score cp -445 depth 4 seldepth 10 time 2 nodes 10554 nps 5277000 pv b7c7 c6d4 g7g6 d4f3
info score cp -435 depth 5 seldepth 13 time 15 nodes 71055 nps 4737000 pv b7c7 c6d4 e8d8 f4f5 e7d5
info score cp -440 depth 6 seldepth 13 time 79 nodes 311096 nps 3937924 pv b7c7 c6e5 e7c6 f1c1 e8e6 c1d1
info score cp -430 depth 7 seldepth 17 time 514 nodes 2327429 nps 4528072 pv b7c7 c6a5 c7d7 a5c4 d7d8 f1e1 f7f5
info score cp -445 depth 8 seldepth 19 time 4252 nodes 16370321 nps 3850028 pv b7c7 f1e1 g7g5 c6b4 c7c5 b4d3 c5a5 g2g3
info score cp -520 depth 9 seldepth 21 time 34351 nodes 152524057 nps 4440164 pv b7c7 f1e1 f7f6 c6e7 c7e7 e4e7 e8e7 e1e7 f6f5 e7d7
info score cp -520 depth 10 seldepth 23 time 243133 nodes 951206137 nps 3912287 pv b7c7 f1e1 f7f6 c6e7 c7e7 e4e7 e8e7 e1e7 g7g5 f4g5 f6g5

So your testcase seems to confirm that:
(1) QSearch appears to work fine
and
(2) Searching 7 or 8 plys deep *without* QSearch produces lines that are actually better than the ones with QSearch enabled.

And running tournaments with both versions confirms that this is not an outlier. I can't wrap my head around it.

(But I will do these test HGM and Sven suggested. That's methodical and sound and doesn't require me to think so much! )

I think you're suffering from the fact that your engine is floundering around.

Because you -only- have material counting, every position where material is equal, the position is equal. That is not true. Your engine is basically playing like the beginner of beginners: If I go here, I won't lose material. That's good. But, the beginner doesn't see that a piece on that square will be completely out of play, for example. An engine with PST's will put its pieces on good squares (if the PST's are good), and will thus get into a better position.

Your engine doesn't know what a "good" or "bad" position is. You have to have something else but material count to make that clear; if you don't, the engine will have no way to know what to do if the material is equal. Beginners have the same problem: if material is equal, they don't know what to do, because they can't yet see that "this bishop is bad", "that rook is out of play", "this pawn is weak", "if I get the center, I get attacking chances".

I'll see what happens if I disable PST's in Rustic and play a match, but I suspect it won't be pretty...

My suggestion would be to implement Rustic's PST's and see what happens if you run a match against Minimal Chess without those PST's. (The reason is that... uh... I wrote them myself. I'm a fairly decent +/- 1850 Elo chess player; up to +/- 2000 when I actually put some effort in. My PST's are sound for an engine just starting out, and they do include some positional knowledge. They contain what I'd teach to a beginner about "good squares for pieces".)

[Sven]

[...] does not make me happy because it seems to confirm what is my core problem: Qsearch seems fine but it doesn't help the engine play better.
[...] So your testcase seems to confirm that:
(1) QSearch appears to work fine
and
(2) Searching 7 or 8 plys deep *without* QSearch produces lines that are actually better than the ones with QSearch enabled.

And running tournaments with both versions confirms that this is not an outlier. I can't wrap my head around it.

(But I will do these test HGM and Sven suggested. That's methodical and sound and doesn't require me to think so much! )

Don't cry Better believe us: a "classical" chess engine needs QSearch, otherwise it will play bad chess. Play enough games between withoutQS and withQS and let statistics decide ... you'll see a difference of certainly much more than 100 Elo points.

[mvanthoor]

I have removed the PST's from the evaluation. (The tables and calculations are still there obviously, but the eval doesn't take them into account anymore; just commented out one line.)

QSearch is still there.

The result is "Rustic PASTA", which stands for "Program Actively Seeks The Abyss". The result isn't pretty. It actually flounder around as suspected as soon as there's nothing to threaten or capture. The only reason it starts somewhat decently is because CuteChess uses an 8 full move opening book. PASTA is losing one game after another, against Rustic Alpha 1 (the same version that is at 1680 in CCRL). As it stands now, after 20 games or so, it looks like PASTA will be 520 Elo points weaker than Alpha 1. (CCRL 1160 effectively, in self-play.)

So... if you add PST's to your program, you can indeed expect a massive Elo boost. I wouldn't try to come to any conclusions about QSearch before you can actually put your pieces on decent squares.

[lithander]

Don't cry Better believe us: a "classical" chess engine needs QSearch, otherwise it will play bad chess. Play enough games between withoutQS and withQS and let statistics decide ... you'll see a difference of certainly much more than 100 Elo points.

I do believe you. And I implemented it. But that the engine continues to play very bad chess, hence the tears.

I have removed the PST's from the evaluation. QSearch is still there. As it stands now, after 20 games or so, it looks like PASTA will be 520 Elo points weaker than Alpha 1. (CCRL 1160 effectively, in self-play.)

Thanks for doing that! I'm (almost ) convinced that I need PSTs in my chess engine! (No, really, I will add them asap)

If you'd run Rustic PASTA against a Rustic PASTA without QSearch is there a significant difference between both versions? If yes: My implementation is probably faulty. If they both play 'abysmal' without much difference my QSearch may actually be okay and the evaluation just needs to be better before it shows.