Quiescence Search doesn't improve strength

[mvanthoor]

Just for move ordering I don't think the depth matters. I do think that you should get a lot more than what you did though. And 2200 from 1500 just because of adding a TT is nowhere near reality.

I suspected as much, that 1680 -> 2200 wouldn't be a reality. However, note that the way in which I determine my "best move" is still very primitive: it's only material+PST. Maybe this gets better automatically, after the evaluation improves. And, as said, I don't yet do search cuts on hash value.

Unless a super genius comes along, and I'm talking like a dignitary from heaven, the days of the lone programmer competing with the top engines is way past us. I mean without digging into SF code for example. It would be better if Lithander, you and I joined forces and we can invite HGM to join with us also as well as anyone else to produce something new. I don't know how that would work but it would be excellent if it can be done. It would require each of us keeping our egos in check though, lol!

Thanks for the invitation, but you wouldn't want me on a team like that... on the one end, I would love to, but on the other end, I have way too many hobbies already. Reading, PLAYING chess, WRITING a chess engine, and in due time, I also want to write my own user interface and a PicoChess clone in Rust, so I can actually understand it properly. This means I often work on these projects in fits and starts; sometimes putting in 40 hours a week next to my full time job, sometimes leaving it hanging around for 4 weeks while I research something at the speed of 2 hours a day once a week...

[Ras]

The problem here is that Rustic itself is so fast (>5 million nps in the endgame, in some positions), that the search tree cut gotten by the hash move move probe/sort is offset by the speed loss of the engine overall.

That will sort itself out once Rustic becomes slower with a more elaborate evaluation function including the pawn structure evaluation (which usually goes into a simple replace-always pawn hash table). Also, connecting the rooks to the pawn eval to put them on open or half-open files, and to attack enemy backward pawns and such. All of that would also make the search trees larger due to more eval variation, but the main hash table will help to cope with the fallout. Not sure whether you already have history and depth killers, but that will likely also slow down your move generator.

[emadsen]

It would be quicker to run a test again, than to try to find what I said in this thread I have seen a noticable improvement with QSearch enabled, a noticable improvement with PST's on top of material only, and a massive (more than 500 Elo) with both enabled.

Wow, communication breakdown. Am I speaking Greek here?? I'm trying to help but I feel we're talking past each other. I'm responding to Thomas stating this:

3.) This was the 2nd learning: You need a better eval [EM: better than material-only] for QSearch to provide a significant boost to playing strength.

My test directly contradicts that. Though I noted perhaps my test is not an apples-to-apples comparison due to me stripping down a mature engine and you and Thomas building up new engines. So if Thomas is not seeing a significant Elo boost from q-search, he may want to reexamine a) his q-search implementation and b) his testing regimen.

[mvanthoor]

Wow, communication breakdown. Am I speaking Greek here?? I'm trying to help but I feel we're talking past each other. I'm responding to Thomas stating this:

3.) This was the 2nd learning: You need a better eval [EM: better than material-only] for QSearch to provide a significant boost to playing strength.

My test directly contradicts that. Though I noted perhaps my test is not an apples-to-apples comparison due to me stripping down a mature engine and you and Thomas building up new engines. So if Thomas is not seeing a significant Elo boost from q-search, he may want to reexamine a) his q-search implementation and b) his testing regimen.

Could be that we are somewhat misunderstanding each other; I did see an improvement when running QSearch, only on top of material evaluation. Note that I use different material values than Thomas; when I've been watching his video's, he looked up the value of the pieces and implemented them like that. I wouldn't be surprised if a queen is 900, a rook 500, a knight and bishop 300, and pawns 100; in that case, trading a knight for 3 pawns is exactly the same as trading a knight and two pawns for a raook, or two minor pieces for 6 pawns... that probably messes up your evaluation. I have different values, which are more to my style; normally, I prefer to keep the queen instead of 2 rooks, normally I prefer to have a bishop instead of a knight, or a minor piece instead of 3 pawns, and my material values reflect that. So, some trades that are "good (enough)" in Thomas's engine, are not good or very good in mine.

[mvanthoor]

That will sort itself out once Rustic becomes slower with a more elaborate evaluation function including the pawn structure evaluation (which usually goes into a simple replace-always pawn hash table). Also, connecting the rooks to the pawn eval to put them on open or half-open files, and to attack enemy backward pawns and such. All of that would also make the search trees larger due to more eval variation, but the main hash table will help to cope with the fallout. Not sure whether you already have history and depth killers, but that will likely also slow down your move generator.

Nope. I don't have killers and history yet, nor PV Sorting. Those will be next, after the hash table. Maybe it would have been better to do them the other way around, but reading around the internet led me to believe that the hash table would get MASSIVE speed gains. It does, in the endgame, and I've always known that; but in the middle game it's decidedly lackluster, with regard to move sorting. There's a definite gain, but much less than I had expected.

Ah, well; Rustic + Hash move sorting against Rustic without it, ended up at +10 Elo for the latter, with an 80 Elo error bar. I assume that if I had run a much longer match, it would have been about equal; as expected, as only the hash move sorting doesn't gain enough speed to consistently add 2+ ply to the search.

I'm now going to run a test with a version of the hash table that also cuts off on retrieved evaluation, but without provisions for mate scoring at the moment... so that might mess it up. We'll see.

[Ras]

but without provisions for mate scoring at the moment... so that might mess it up.

Not in terms of playing strength. I had it without mate distance adjustment for years, and I only fixed that because I found it annoying that the engine would occasionally report a wrong root mate distance.

[lithander]

Thanks Erik for taking the time to make tests of your own!

I disagree with #2. In my experience, fixed depth games cannot accurately measure engine strength, either in a gauntlet against other engines or in a self-testing match.

My simple engine just does iterative deepening until it runs out of time. If I limit depth and not time all it changes is that I pretend it ran out of time after reaching a specific iteration of the search. Now, with no further code-changes it will always produce the same result on a slow or fast computer. It will also produce the same results independent on how performant your implementation is.
Adding a very inefficient but correct Quiescence implementation will provide a strength improvement under these testing conditions that is an upper bound on the gain you can expect under real conditions. Testing my Qsearch that way I saw an improvement of well over 100 Elo. I can't say exactly how much because, as you say: the exact number would have meant nothing so I didn't write it down.

But it was high enough to show that there's a benefit which is just negated by the fact that my quiesence implementation is slowing search down so much that I didn't see it.

#3 makes no sense to me. An engine that evaluates positions solely by material is strategically stupid (not knowing how to develop pieces) and ignorant of the danger posed by passed pawns and attacks on squares near the king. However, if it has a correct quiescence search implementation, it can find discovered checks, forks, attacks on overloaded pieces, etc... all of which win material.

I took MadChess 3.0 Beta (2570 Elo), removed all eval terms except material, and ran a gauntlet tournament against other engines of varying strength, from TSCP 1.81 (1751 Elo) to Sungorus 1.4 (2311 Elo) at 2m+1s time control. I got this result:

Code: Select all

MadChess 3.0 Beta, Material Only,   No Quiescence = 1746 Elo
MadChess 3.0 Beta, Material Only, With Quiescence = 1915 Elo

This suggests a correct implementation of quiescence search is worth 169 Elo. I only had time for a quick test so the error bars are like +/- 50 Elo.

MadChess 3.0 Beta has a fairly fast bitboard implementation, doesn't allocate memory during search, has a hash table for score cutoffs and best moves, orders quiet moves by history heuristic score, implements null move and LMR (reducing between 3 and 6 ply), etc...

So perhaps my experience differs from yours due to me coming at the problem from the opposite direction as you: I've stripped down a mature engine. You're building up a new engine. Perhaps the difference between me finding quiescence search to be worth 169 Elo and you and Marcel finding it not worth much at all (both for material-only eval) can be explained away by the non-linear manner in which chess engine features combine. But, in my opinion, I don't think so. An engine with a correct quiescence search implementation should be stronger than one without it, even if it evaluates only material, because it's less vulnerable to hanging pieces due to the horizon effect.

Of course if you pit both versions of the engine against competitors that are > 300 Elo points stronger, it's likely to lose so often that quiescence search doesn't matter. But when pitted against nearly equal competitors, the version with quiescence search should be measurably stronger.

Marcel also did the same test as you and stripped down his engine:

Rustic Alpha 1: 1680 Elo
Rustic PASTA: 1200 Elo (without PST, -480 Elo)
Rustic YOLO: 1095 Elo (without PST, without QSearch, -105 Elo)

And later he added: Not having QSearch loses +/- 400 Elo.

Which means adding PSTs alone is only worth ~200 Elo. Adding QSearch alone is only worth ~100 ELO.
But if you use them together you get more than the sum of it's parts. You get a huge compound benefit of 600 ELO.
That's a significant synergy!

You get more out of QSearch then Marcel did, which may be due to the fact that your stripped down engine still plays at a higher strength then ours do with all features enabled! Who knows what other synergies are still at play?

And me? After adding PSTs I saw a huge jump in playing strength as well. Depending on what PSTs I use I'm now between 180 and 80 ELO behind Rustic. (Tested with 1000 games each so the numbers are somewhat accurate) I'm currently looking for ways to optimize the QSearch and move ordering to close that gap a little more.

I'll provide my measurements as soon as I'm done with refactoring!

[mvanthoor]

Not in terms of playing strength. I had it without mate distance adjustment for years, and I only fixed that because I found it annoying that the engine would occasionally report a wrong root mate distance.

There is a much bigger problem... I can probe the hash table correctly, but at some point, when I return the found value from alpha_beta, the engine crashes with an array index out of bounds... and I don't know where I'll have to make a debug build and hope to get some more information on this. Up to now, the engine has never crashed even once on me during a game. Damn. As far as I can see, I did everything correctly, up to and including probing the hash table for a move and sorting on it.

[lithander]

I prefer to keep the queen instead of 2 rooks, normally I prefer to have a bishop instead of a knight, or a minor piece instead of 3 pawns, and my material values reflect that. So, some trades that are "good (enough)" in Thomas's engine, are not good or very good in mine.

You prefer the queen over two rooks? Not according to your code or am I to stupid to read it?

https://github.com/mvanthoor/rustic/blo ... on/defs.rs

Code: Select all

pub const PIECE_VALUES: [u16; 6] = [0, 900, 500, 320, 310, 100];

[Ras]

at some point, when I return the found value from alpha_beta, the engine crashes with an array index out of bounds...

Maybe the search doesn't return a move because it's failing low somewhere, but you try to access the move list one level up with some best_index which is invalid because it was never made valid one level down, which in turn is because no move improved alpha one level down, i.e. all failed low?

Also, what do you do with a hash move? Do you have some guards to make sure that a hash move will not crash the engine in case of a key collision?