Quiescence Search doesn't improve strength

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 26134
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Quiescence Search doesn't improve strength

Post by hgm » Wed Mar 03, 2021 3:29 pm

lithander wrote:
Wed Mar 03, 2021 1:28 pm
These tables are meant to speed up the move generator, right? With those lookup tables do you think a mailbox board would be as fast as a bitboard based move generator on a modern 64bit CPU with hardware support for bitscan, popcount, leadingzeros and that kind of stuff?
I think it can be faster. But, as the saying goes, the proof of the pudding is in the eating.
Cool idea! So you start with the most valuable enemy pieces and your attack table tells you which move will attack them so it's already generated in MVV (even if not LVA) order?
Indeed, except that I also want it to be in LVA order. That is, the attack map would, for each possible victim, contain a word where each bit corresponds to an opponent piece. And the bits are assigned such that when you extract them with the trailing-zeros trick, they come out in LVA order. So basically you loop through the victims in a piece list (where you can also use a 'present' mask and bit extraction to not spend any time on pieces that are already captured) to get the corresponding attack-map elements in MVV order, and out of these you extract the set bits in LVA order.

There is one issue that complicates this, though: chess pieces come in 'value groups' (like two Rooks, or four minors), which really have to be treated together. You would not want to search a QxR before a PxR because you happened to start with the wrong Rook as victim, and the Pawn attacked the other. I want to solve that by making the attack-map elements 64 bits, using only 16 of those to indicate the attackers, with 3 zero bits as spacer in between. For the Rooks I could then combine the attacks on them by taking attackers[ROOK1] + 2*attackers[ROOK2], and extract the moves from there.

Basically this does away with capture generation and sorting completely. But of course you will have to update the attack map according to the moves that are made. But that just amounts to generating the captures of the moved piece from its new location (to enter those into the map) and in the old location (to erase those) by other means, and (sometimes) adding some discovered slider moves (all of which where targeting the evacuated square, and can be gotten from the attack-map element of the piece on it). So it should take only a fraction of the time conventional move generation requires.

Mike Sherwin
Posts: 281
Joined: Thu Aug 20, 2020 11:25 pm
Full name: Michael J Sherwin

Re: Quiescence Search doesn't improve strength

Post by Mike Sherwin » Wed Mar 03, 2021 4:52 pm

Uri Blass wrote:
Wed Mar 03, 2021 8:30 am
Mike Sherwin wrote:
Tue Mar 02, 2021 11:01 pm
mvanthoor wrote:
Tue Mar 02, 2021 10:33 pm
Mike Sherwin wrote:
Tue Mar 02, 2021 9:26 pm
Hmm, I was not trying to fool anyone. So, I'm glad you pointed that out. :)
And here I am, implementing hash move sorting... it does seem to work (the hash move gets a score high enough to move it to the front of the move list, as it is added to the MVV-LVA score that may have already been there, and is higher than the highest MVV-LVA score), and in most positions, there's a massive cut in the search tree... but it still only gains me some time; not even enough to make an extra ply in the middle game.

Talk about expectations.

I'm half expecting that one of these sorting options will "magically" get me from depth 7-8 to somewhere around 14, but it seems that, to some extent, the gain the hash move sorting makes, is partially off-set by the speed loss the engine incurs due to the probe.

Note the following (I might be doing something wrong here):
- I am NOT yet cutting off the entire search by hash value; I'm ONLY probing for the move to test the move sorting.
- I do the probe right before the moves are generated, and if there's a hash entry, I get the move from it; without paying attention to the depth the hash entry was stored for. Can this be done for the move, or should the depth be equal or greater, just as for the values?
- Then I sort the moves.
- I save a "best_move" for the move loop, to put in the hash table when Alpha is raised (where the PV is also updated)
- I put this best move into the hash table when I write the entry. I write an entry where Beta is raised, and just before Alpha is returned (same as is shown on Bruce Moreland's site). I also save the hash flags and evaluation score, but as said, I don't use them yet.
- I write "depth" into the hash entry... intuitively, this feels correct, but by checking some engines, I have seen one that writes ply's.

Some results:

For example, this is a run in a K+P vs. K endgame, without a hash table:

Code: Select all

info score cp 140 depth 1 seldepth 1 time 0 nodes 7 nps 0 pv e2e4
info score cp 90 depth 2 seldepth 2 time 0 nodes 26 nps 0 pv e2e4 e8f7
info score cp 140 depth 3 seldepth 3 time 0 nodes 100 nps 0 pv e1f2 e8f7 e2e4
info score cp 110 depth 4 seldepth 4 time 0 nodes 394 nps 0 pv e1f2 e8d7 e2e4 d7c6
info score cp 140 depth 5 seldepth 5 time 0 nodes 843 nps 0 pv e1d2 e8d7 d2c3 d7c6 e2e4
info score cp 110 depth 6 seldepth 6 time 0 nodes 3666 nps 0 pv e1d2 e8d7 d2c3 d7d6 c3d4 d6c6
info score cp 180 depth 7 seldepth 8 time 2 nodes 11114 nps 5557000 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4
info score cp 180 depth 8 seldepth 10 time 7 nodes 52829 nps 7547000 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6b5 e2e4 b5c6
info score cp 190 depth 9 seldepth 10 time 27 nodes 141749 nps 5249963 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4 d6c6 e4e5
info score cp 190 depth 10 seldepth 12 time 90 nodes 624560 nps 6939556 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4 d6e6 e4e5 e6f5
info score cp 190 depth 11 seldepth 14 time 293 nodes 1523320 nps 5199044 pv e1d2 e8d7 d2c3 d7c6 c3c4 c6d6 c4d4 d6c6 e2e4 c6d6 e4e5 d6c6
info score cp 190 depth 12 seldepth 16 time 829 nodes 5604808 nps 6760926 pv e1d1 e8d7 d1c2 d7c6 c2d3 c6b5 d3d4 b5c6 e2e4 c6d6 e4e5 d6e6 d4e4
info score cp 190 depth 13 seldepth 18 time 3158 nodes 16045639 nps 5080950 pv e1d1 e8d7 d1c2 d7c6 c2c3 c6c5 e2e4 c5d6 c3d4 d6e6 e4e5 e6f5 d4d5
info score cp 190 depth 14 seldepth 20 time 9473 nodes 62300713 nps 6576661 pv e1d1 e8d7 d1c1 d7c6 c1c2 c6b5 c2c3 b5c5 e2e4 c5c6 c3d4 c6d6 e4e5 d6e6 d4e4
info score cp 190 depth 15 seldepth 22 time 44420 nodes 215290136 nps 4846694 pv e1d1 e8d7 d1c1 d7c6 c1c2 c6b5 c2c3 b5c5 e2e4 c5d6 c3d4 d6e6 e4e5 e6f5 d4d5
Same run with a 32 MB Hash table (which in the end is only used 6.1%, because there are a lot of transpositions)

Code: Select all

info score cp 140 depth 1 seldepth 1 time 0 nodes 7 nps 0 pv e2e4
info score cp 90 depth 2 seldepth 2 time 0 nodes 21 nps 0 pv e2e4 e8f7
info score cp 140 depth 3 seldepth 3 time 0 nodes 55 nps 0 pv e2e4 e8f7 e1f2
info score cp 110 depth 4 seldepth 4 time 0 nodes 185 nps 0 pv e2e4 e8f7 e1f2 f7e6
info score cp 140 depth 5 seldepth 5 time 0 nodes 412 nps 0 pv e2e4 e8f7 e1f2 f7e6 f2e3
info score cp 110 depth 6 seldepth 6 time 0 nodes 2449 nps 0 pv e1d2 e8d7 d2c3 d7d6 c3d4 d6c6
info score cp 180 depth 7 seldepth 8 time 1 nodes 7339 nps 7339000 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4
info score cp 180 depth 8 seldepth 10 time 6 nodes 36287 nps 6047833 hashfull 2 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6b5 e2e4 b5c6
info score cp 190 depth 9 seldepth 10 time 23 nodes 100365 nps 4363696 hashfull 3 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4 d6c6 e4e5
info score cp 190 depth 10 seldepth 12 time 85 nodes 526843 nps 6198153 hashfull 6 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4 d6e6 e4e5 e6f5
info score cp 190 depth 11 seldepth 13 time 270 nodes 1274079 nps 4718811 hashfull 10 pv e1d2 e8d7 d2c3 d7c6 c3c4 c6d6 c4d4 d6c6 e2e4 c6d6 e4e5 d6c6
info score cp 190 depth 12 seldepth 16 time 780 nodes 4822260 nps 6182385 hashfull 14 pv e1d1 e8d7 d1c2 d7c6 c2d3 c6b5 d3d4 b5c6 e2e4 c6d6 e4e5 d6e6 d4e4
info score cp 190 depth 13 seldepth 18 time 2862 nodes 13443760 nps 4697331 hashfull 22 pv e1d1 e8d7 d1c2 d7c6 c2c3 c6c5 e2e4 c5d6 c3d4 d6e6 e4e5 e6f5 d4d5
info score cp 190 depth 14 seldepth 20 time 8767 nodes 53252243 nps 6074169 hashfull 36 pv e1d1 e8d7 d1c1 d7c6 c1c2 c6b5 c2c3 b5c5 e2e4 c5c6 c3d4 c6d6 e4e5 d6e6 d4e4
info score cp 190 depth 15 seldepth 22 time 39418 nodes 178134146 nps 4519107 hashfull 61 pv e1d1 e8d7 d1c1 d7c6 c1c2 c6b5 c2c3 b5c5 e2e4 c5d6 c3d4 d6e6 e4e5 e6f5 d4d5
As can be seen, at depth 15, the time without the hash table is 44.4 seconds. With hash table, the time is 39.42 seconds. The search tree has been cut from ~215 million moves, down to ~178 million moves. So yes, it does seem that the hash move sorting is working, but I had expected a lot more from it. One of the CCRL-testers said: "As soon as you implement a hash table, your engine will be at least at 2200 Elo". I don't really believe that anymore, except if the search cuts by hash value gives a massive improvement. I also still need to implement all the other sorting options, such as PV Move sort, killers, and heuristics. It could of course be that all of these sorting options, together with the search cut by hash value, gives a huge boost: in the same way as ELO_GAIN(PST + SQ) > (ELO_GAIN(PST) + ELO_GAIN(SQ))

I have a feeling my expectations are somewhat out of line here.

PS: I have checked the scoring. It works. I have a MOVE 64-bit int (within a struct), which also holds the sort score. The struct has a function called "add_value"; this is used to add the MVV_LVA value, and also the hash move value. It basically gets the current score, XOR's it out of the move, adds current+value together, shifts it left the correct number of bits, and XOR's it in again. I have checked the before and after, and the hash move score is correctly added.
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. Stockfish is Stockfish because it has "hundreds" of little things all finely tuned that give sometimes only a single elo and sometimes a bit more.

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!
I agree that producing something new is better than trying to compete with the best engines for rating.
There are many tasks that engines today do not know to do.

One of the things I would like to see is simply only material analysis of chess games.

I would like to see an engine that tell me something like based on an analysis that is 7 plies forward move A is winning a pawn and it can be a chess exercise to find why.

Engines like stockfish do not do it because:
1)I cannot know if +1 of the engine is positional or material
2)Search has pruning and extensions so I cannot know how many plies they really search even if they search for a fixed depth.
Hi Uri, Have you given up on programming? Movei was quite a good engine in its day. Anyway, if side A loses a pawn in 7 moves how would one know that A wins a knight in 9 moves or 11 moves? I see that example as problematic. What I see as easily doable is an engine that searches through a pgn file looking for forced mates in n moves and extracting the fen's to an EPD file.

User avatar
emadsen
Posts: 285
Joined: Wed Apr 25, 2012 11:51 pm
Location: Oak Park, IL, USA
Full name: Erik Madsen
Contact:

Re: Quiescence Search doesn't improve strength

Post by emadsen » Wed Mar 03, 2021 5:11 pm

lithander wrote:
Wed Mar 03, 2021 12:37 am
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.
OK. Once you add proper time management you'll be able to answer the question, "Do the benefits of the feature I just added outweigh the costs (slowdown) of the feature in timed games?"
lithander wrote: You get a huge compound benefit [for PST + QSearch] of 600 ELO.
That aligns with my test results of ~650 ELO.
lithander wrote: I'll provide my measurements as soon as I'm done with refactoring!
mvanthoor wrote:
Tue Mar 02, 2021 11:58 pm
Could be that we are somewhat misunderstanding each other; I did see an improvement when running QSearch...
Hopefully we're moving towards a shared understanding in this thread :)
My C# chess engine: https://www.madchess.net

User avatar
mvanthoor
Posts: 986
Joined: Wed Jul 03, 2019 2:42 pm
Location: Netherlands
Full name: Marcel Vanthoor
Contact:

Re: Quiescence Search doesn't improve strength

Post by mvanthoor » Wed Mar 03, 2021 9:27 pm

hgm wrote:
Wed Mar 03, 2021 9:54 am
mvanthoor wrote:
Wed Mar 03, 2021 2:01 am
However... it also seems to have lost the ability to mate with R + K vs K :shock: It drew at least 2 games, where it shuffled pieces around, stating "Mate in 5" (which would be correct), but then actually never mating. This is the sort of stuff I don't yet understand with regard to chess programming...
Indeed, that is the typical problem when you don't correctly score the mating distance. My engine Joker managed to salvage a draw once this way in the Leiden tournament, when it was at the losing end of a KQBK end-game. :lol:
I've seen Rustic with hash-tables save a few positions it would have otherwise lost (in self-play, up to now). I've even seen it *almost* save a position it would *definitely* have lost; but also seen it botch positions with a rook up because of the mate scores.
You probably don't adapt the mate scores you store to / read from the TT. Since mate scores depend on the distance of the node to the root, they would no longer be valid if they are probed in a node at another distance from the root. So you have to convert them to absolute 'mate-in-N' scores from the node itself before storing (by subtracting 'ply'), and then convert it back to the DTM from the root by adding (a possibly different) 'ply' on probing.
Yes. Mate scores are not adjusted yet.

For peopple who are interested in it:
Rustic + TT + TTMove ordering is +/- 100 Elo (50 Elo error bars) in self-play. I expect it to jump up, if the engine stops botching positions after fixing the mate scoring; when I added repetition detection, the engine stopped accepting draws in a won position, and it jumped over 60 Elo.

Exempting mate score adjustment, which just isn't in there yet, the hash table and hash move ordering seem to work as they should. When I disable the TT cutoffs but leave the move ordering in, the search tree gets smaller by 25-40% depending on the position. When I add the TT cuts back in, Rustic + TT habitually outcalculates Rustic without TT (otherwise exactly the same) by 1-4 ply depending on the position and game fase.
Author of Rustic.
Releases | Code | Docs

User avatar
mvanthoor
Posts: 986
Joined: Wed Jul 03, 2019 2:42 pm
Location: Netherlands
Full name: Marcel Vanthoor
Contact:

Re: Quiescence Search doesn't improve strength

Post by mvanthoor » Wed Mar 03, 2021 9:32 pm

emadsen wrote:
Wed Mar 03, 2021 5:11 pm
lithander wrote: You get a huge compound benefit [for PST + QSearch] of 600 ELO.
That aligns with my test results of ~650 ELO.

Hopefully we're moving towards a shared understanding in this thread :)
Looks like it, because my testing also revealed a +/- 600 Elo difference for PST + SQ vs no PST and no QS. It seems that adding PST + QS adds +/- 600 Elo to an engine (for a test of n=3), independent of the rest of the engine.
Author of Rustic.
Releases | Code | Docs

User avatar
Bo Persson
Posts: 192
Joined: Sat Mar 11, 2006 7:31 am
Location: Malmö, Sweden
Full name: Bo Persson

Re: Quiescence Search doesn't improve strength

Post by Bo Persson » Thu Mar 04, 2021 8:14 am

mvanthoor wrote:
Wed Mar 03, 2021 9:32 pm
emadsen wrote:
Wed Mar 03, 2021 5:11 pm
lithander wrote: You get a huge compound benefit [for PST + QSearch] of 600 ELO.
That aligns with my test results of ~650 ELO.

Hopefully we're moving towards a shared understanding in this thread :)
Looks like it, because my testing also revealed a +/- 600 Elo difference for PST + SQ vs no PST and no QS. It seems that adding PST + QS adds +/- 600 Elo to an engine (for a test of n=3), independent of the rest of the engine.
Probably not "independent".

Adding some capabilities - anything - to an engine that is totally stupid *will* of course increase its strength a lot. Adding the same capabilities to an engine that already contains other features will probably not add *that* much to its strength.

Uri Blass
Posts: 8975
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Quiescence Search doesn't improve strength

Post by Uri Blass » Thu Mar 04, 2021 4:52 pm

Mike Sherwin wrote:
Wed Mar 03, 2021 4:52 pm
Uri Blass wrote:
Wed Mar 03, 2021 8:30 am
Mike Sherwin wrote:
Tue Mar 02, 2021 11:01 pm
mvanthoor wrote:
Tue Mar 02, 2021 10:33 pm
Mike Sherwin wrote:
Tue Mar 02, 2021 9:26 pm
Hmm, I was not trying to fool anyone. So, I'm glad you pointed that out. :)
And here I am, implementing hash move sorting... it does seem to work (the hash move gets a score high enough to move it to the front of the move list, as it is added to the MVV-LVA score that may have already been there, and is higher than the highest MVV-LVA score), and in most positions, there's a massive cut in the search tree... but it still only gains me some time; not even enough to make an extra ply in the middle game.

Talk about expectations.

I'm half expecting that one of these sorting options will "magically" get me from depth 7-8 to somewhere around 14, but it seems that, to some extent, the gain the hash move sorting makes, is partially off-set by the speed loss the engine incurs due to the probe.

Note the following (I might be doing something wrong here):
- I am NOT yet cutting off the entire search by hash value; I'm ONLY probing for the move to test the move sorting.
- I do the probe right before the moves are generated, and if there's a hash entry, I get the move from it; without paying attention to the depth the hash entry was stored for. Can this be done for the move, or should the depth be equal or greater, just as for the values?
- Then I sort the moves.
- I save a "best_move" for the move loop, to put in the hash table when Alpha is raised (where the PV is also updated)
- I put this best move into the hash table when I write the entry. I write an entry where Beta is raised, and just before Alpha is returned (same as is shown on Bruce Moreland's site). I also save the hash flags and evaluation score, but as said, I don't use them yet.
- I write "depth" into the hash entry... intuitively, this feels correct, but by checking some engines, I have seen one that writes ply's.

Some results:

For example, this is a run in a K+P vs. K endgame, without a hash table:

Code: Select all

info score cp 140 depth 1 seldepth 1 time 0 nodes 7 nps 0 pv e2e4
info score cp 90 depth 2 seldepth 2 time 0 nodes 26 nps 0 pv e2e4 e8f7
info score cp 140 depth 3 seldepth 3 time 0 nodes 100 nps 0 pv e1f2 e8f7 e2e4
info score cp 110 depth 4 seldepth 4 time 0 nodes 394 nps 0 pv e1f2 e8d7 e2e4 d7c6
info score cp 140 depth 5 seldepth 5 time 0 nodes 843 nps 0 pv e1d2 e8d7 d2c3 d7c6 e2e4
info score cp 110 depth 6 seldepth 6 time 0 nodes 3666 nps 0 pv e1d2 e8d7 d2c3 d7d6 c3d4 d6c6
info score cp 180 depth 7 seldepth 8 time 2 nodes 11114 nps 5557000 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4
info score cp 180 depth 8 seldepth 10 time 7 nodes 52829 nps 7547000 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6b5 e2e4 b5c6
info score cp 190 depth 9 seldepth 10 time 27 nodes 141749 nps 5249963 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4 d6c6 e4e5
info score cp 190 depth 10 seldepth 12 time 90 nodes 624560 nps 6939556 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4 d6e6 e4e5 e6f5
info score cp 190 depth 11 seldepth 14 time 293 nodes 1523320 nps 5199044 pv e1d2 e8d7 d2c3 d7c6 c3c4 c6d6 c4d4 d6c6 e2e4 c6d6 e4e5 d6c6
info score cp 190 depth 12 seldepth 16 time 829 nodes 5604808 nps 6760926 pv e1d1 e8d7 d1c2 d7c6 c2d3 c6b5 d3d4 b5c6 e2e4 c6d6 e4e5 d6e6 d4e4
info score cp 190 depth 13 seldepth 18 time 3158 nodes 16045639 nps 5080950 pv e1d1 e8d7 d1c2 d7c6 c2c3 c6c5 e2e4 c5d6 c3d4 d6e6 e4e5 e6f5 d4d5
info score cp 190 depth 14 seldepth 20 time 9473 nodes 62300713 nps 6576661 pv e1d1 e8d7 d1c1 d7c6 c1c2 c6b5 c2c3 b5c5 e2e4 c5c6 c3d4 c6d6 e4e5 d6e6 d4e4
info score cp 190 depth 15 seldepth 22 time 44420 nodes 215290136 nps 4846694 pv e1d1 e8d7 d1c1 d7c6 c1c2 c6b5 c2c3 b5c5 e2e4 c5d6 c3d4 d6e6 e4e5 e6f5 d4d5
Same run with a 32 MB Hash table (which in the end is only used 6.1%, because there are a lot of transpositions)

Code: Select all

info score cp 140 depth 1 seldepth 1 time 0 nodes 7 nps 0 pv e2e4
info score cp 90 depth 2 seldepth 2 time 0 nodes 21 nps 0 pv e2e4 e8f7
info score cp 140 depth 3 seldepth 3 time 0 nodes 55 nps 0 pv e2e4 e8f7 e1f2
info score cp 110 depth 4 seldepth 4 time 0 nodes 185 nps 0 pv e2e4 e8f7 e1f2 f7e6
info score cp 140 depth 5 seldepth 5 time 0 nodes 412 nps 0 pv e2e4 e8f7 e1f2 f7e6 f2e3
info score cp 110 depth 6 seldepth 6 time 0 nodes 2449 nps 0 pv e1d2 e8d7 d2c3 d7d6 c3d4 d6c6
info score cp 180 depth 7 seldepth 8 time 1 nodes 7339 nps 7339000 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4
info score cp 180 depth 8 seldepth 10 time 6 nodes 36287 nps 6047833 hashfull 2 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6b5 e2e4 b5c6
info score cp 190 depth 9 seldepth 10 time 23 nodes 100365 nps 4363696 hashfull 3 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4 d6c6 e4e5
info score cp 190 depth 10 seldepth 12 time 85 nodes 526843 nps 6198153 hashfull 6 pv e1d2 e8d7 d2c3 d7c6 c3d4 c6d6 e2e4 d6e6 e4e5 e6f5
info score cp 190 depth 11 seldepth 13 time 270 nodes 1274079 nps 4718811 hashfull 10 pv e1d2 e8d7 d2c3 d7c6 c3c4 c6d6 c4d4 d6c6 e2e4 c6d6 e4e5 d6c6
info score cp 190 depth 12 seldepth 16 time 780 nodes 4822260 nps 6182385 hashfull 14 pv e1d1 e8d7 d1c2 d7c6 c2d3 c6b5 d3d4 b5c6 e2e4 c6d6 e4e5 d6e6 d4e4
info score cp 190 depth 13 seldepth 18 time 2862 nodes 13443760 nps 4697331 hashfull 22 pv e1d1 e8d7 d1c2 d7c6 c2c3 c6c5 e2e4 c5d6 c3d4 d6e6 e4e5 e6f5 d4d5
info score cp 190 depth 14 seldepth 20 time 8767 nodes 53252243 nps 6074169 hashfull 36 pv e1d1 e8d7 d1c1 d7c6 c1c2 c6b5 c2c3 b5c5 e2e4 c5c6 c3d4 c6d6 e4e5 d6e6 d4e4
info score cp 190 depth 15 seldepth 22 time 39418 nodes 178134146 nps 4519107 hashfull 61 pv e1d1 e8d7 d1c1 d7c6 c1c2 c6b5 c2c3 b5c5 e2e4 c5d6 c3d4 d6e6 e4e5 e6f5 d4d5
As can be seen, at depth 15, the time without the hash table is 44.4 seconds. With hash table, the time is 39.42 seconds. The search tree has been cut from ~215 million moves, down to ~178 million moves. So yes, it does seem that the hash move sorting is working, but I had expected a lot more from it. One of the CCRL-testers said: "As soon as you implement a hash table, your engine will be at least at 2200 Elo". I don't really believe that anymore, except if the search cuts by hash value gives a massive improvement. I also still need to implement all the other sorting options, such as PV Move sort, killers, and heuristics. It could of course be that all of these sorting options, together with the search cut by hash value, gives a huge boost: in the same way as ELO_GAIN(PST + SQ) > (ELO_GAIN(PST) + ELO_GAIN(SQ))

I have a feeling my expectations are somewhat out of line here.

PS: I have checked the scoring. It works. I have a MOVE 64-bit int (within a struct), which also holds the sort score. The struct has a function called "add_value"; this is used to add the MVV_LVA value, and also the hash move value. It basically gets the current score, XOR's it out of the move, adds current+value together, shifts it left the correct number of bits, and XOR's it in again. I have checked the before and after, and the hash move score is correctly added.
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. Stockfish is Stockfish because it has "hundreds" of little things all finely tuned that give sometimes only a single elo and sometimes a bit more.

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!
I agree that producing something new is better than trying to compete with the best engines for rating.
There are many tasks that engines today do not know to do.

One of the things I would like to see is simply only material analysis of chess games.

I would like to see an engine that tell me something like based on an analysis that is 7 plies forward move A is winning a pawn and it can be a chess exercise to find why.

Engines like stockfish do not do it because:
1)I cannot know if +1 of the engine is positional or material
2)Search has pruning and extensions so I cannot know how many plies they really search even if they search for a fixed depth.
Hi Uri, Have you given up on programming? Movei was quite a good engine in its day. Anyway, if side A loses a pawn in 7 moves how would one know that A wins a knight in 9 moves or 11 moves? I see that example as problematic. What I see as easily doable is an engine that searches through a pgn file looking for forced mates in n moves and extracting the fen's to an EPD file.
I stopped programming and did not do something in the last years.
If I come back it is not going to be for generating the best elo but for other things.

There are special engines that search for mates.
I do not know of engines that search for a forced draw.

Material wining of course is dependent on the number of plies you search forward
but I believe that for training it is better to have the option to train only in problems that you need to see small number of plies forward.

Of course some of them can be bad problems in the meaning that you win material but practically lose the game if you search deeper but even if this is the case then it may be interesting to know it.

It may be interesting to take a big pgn file and to see in how many cases the side to move win a pawn based on 1 ply search,3 plies search,5 plies search,....

It may be interesting to see how much material you win also with qsearch or without it(qsearch can be defined to include all captures or maybe to include all captures and replies to check or maybe to include all captures ,replies to check and moves that threat the opponent king in the first ply of the qsearch and I guess with more moves in the qsearch there will be less changes betwee results of search with odd number of plies and even number of plies).

Probably with no qsearch from the opening position when you search at least 5 plies forward
you win a pawn if you search forward odd number of plies and lose a pawn if you search even number of plies and I guess you will see nothing different in the depth that engines can practically search forward.

User avatar
lithander
Posts: 161
Joined: Sun Dec 27, 2020 1:40 am
Location: Bremen, Germany
Full name: Thomas Jahn

Re: Quiescence Search doesn't improve strength

Post by lithander » Mon Mar 08, 2021 8:21 pm

mvanthoor wrote:
Wed Mar 03, 2021 9:32 pm
emadsen wrote:
Wed Mar 03, 2021 5:11 pm
lithander wrote: You get a huge compound benefit [for PST + QSearch] of 600 ELO.
That aligns with my test results of ~650 ELO.

Hopefully we're moving towards a shared understanding in this thread :)
Looks like it, because my testing also revealed a +/- 600 Elo difference for PST + SQ vs no PST and no QS. It seems that adding PST + QS adds +/- 600 Elo to an engine (for a test of n=3), independent of the rest of the engine.
Finally, here are my test results which basically confirm the synergy of ELO(PST + QS) > ELO(PST) + ELO(QS)

Code: Select all

Rank Name                       Elo     +/-   Games   Score    Draw 
   1 QSearch + PSTs           	315      45     300   86.0%   18.7% 
   2 PSTs                        28      31     300   54.0%   40.0% 
   3 QSearch                   -124      31     300   32.8%   39.7% 
   4 Baseline                  -171      32     300   27.2%   38.3% 
So just adding QSearch to a material-only engine was +50 ELO, just adding PSTs provided +200 ELO despite the horizon effect. Finally the combination of PSTs + QSearch was worth +500 ELO in self play. Almost double of what the sum of it's parts would suggest.
Minimal Chess. My very first chess engine! Details on Youtube & Github

User avatar
hgm
Posts: 26134
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Quiescence Search doesn't improve strength

Post by hgm » Mon Mar 08, 2021 8:49 pm

A surprisingly large cooperative effect. I would not have expected that.

User avatar
mvanthoor
Posts: 986
Joined: Wed Jul 03, 2019 2:42 pm
Location: Netherlands
Full name: Marcel Vanthoor
Contact:

Re: Quiescence Search doesn't improve strength

Post by mvanthoor » Mon Mar 08, 2021 10:35 pm

lithander wrote:
Mon Mar 08, 2021 8:21 pm
So just adding QSearch to a material-only engine was +50 ELO, just adding PSTs provided +200 ELO despite the horizon effect. Finally the combination of PSTs + QSearch was worth +500 ELO in self play. Almost double of what the sum of it's parts would suggest.
Cool :)
hgm wrote:
Mon Mar 08, 2021 8:49 pm
A surprisingly large cooperative effect. I would not have expected that.
It seems, when the engine thinks a bit deeper, the effect gets larger: in Rustic, I tested this effect PST+QSearch = +600 Elo over an engine that is material only without QSearch. That suggests that, in very simple engines without other evaluation terms, this effect gets larger when the engine can reach larger depths.
Author of Rustic.
Releases | Code | Docs

Post Reply