Quiescence Search doesn't improve strength

[mvanthoor]

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];

LOL. Epic. Must be a regression due to me going on a refactoring spree and throwing the evaluation out and/or jacking around with the values and PST's. (Ive tested, reverted, and reset stuff numerous times before I settled on what I now have); going back to basics when I decided to build the engine one tiny step at a time. I started out with the "normal" values we humans use (900, 500, 300, 300, 100), but later changed them to what Max Euwe used: 950, 450, 320, 300, 100. And later, I changed 300 for the knight to 310 to keep it instead of 3 pawns.

When you read Max Euwe's old books, which were epic stuff regarding chess education up to the late 80's, in the Netherlands, you'll see that he often preaches that "Two rooks are not a queen, three pawns are never a bishop but may be a knight, and you can never exactly compensate a rook with minor pieces and pawns."

That is true with his values:
Q > 2x R
R > B + P, but R < B + 2x P
B > 3x pawn, but N = 3x pawn.

I'll have to change those values to what they originally were and then do a test run. If Rustic drops in strength, can I then say I've proven one of the greatest chess teachers in history to be wrong? (I doubt it... I assume Euwe came to his values in combination with lots of other evaluation terms. Around... 1930 or so... when computers weren't that hot yet.)

[mvanthoor]

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?

That was basically it. I was (also) probing the hash table at the root (where ply == 0), which most engines I've checked don't do. If the search returned without actually having built a PV of at least one move, iterative deepening crashed on root_pv[0] (which would be the best move). Now I don't probe the PV in the root, so there is at least ONE best move, one level up in iter_deep(), and I added a check to see if the PV isn't empty. It seems to work now. I'm already testing.

I forgot to check a variable for length before accessing it. I'm so ashamed. That's such a ... C ... thing. I'll have to put the PV into an Option<T>

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?

I have 2 types, called Move and HashMove. Move contains a 64-bit integer, into which I can stuff whatever I need in the search. The first 24 bits of that integer are the actual move, before the bits with search information come (they hold the sorting score, for example.) So when I save my move to the hash table, I use a member function on the move: current_move.to_hash_move(). That creates the HashMove type, with only the first 24 bits holding the actual move. When I get a move back from the hash table, I pass it into sort_moves(movelist, hash_move). There, I do MVV-LVA, and while running through the move list, I compare the hash move to all moves: current_move.is_hash_move(hm). If this function returns true, I add (at the moment) 60 to the sort score of that move in the move list, which will be guaranteed to put it in front of everything, as the highest MVV_LVA score is 55 (for now).

I want to keep this under one byte. I'm not a fan of "lets 500 million to the sort score, so we KNOW it will be first", or MVV_LVA scores that run in the hundreds.

[mvanthoor]

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.

The TT-version is now working, and it is clearly stronger than the non-TT-version. The difference now stands at +/-150 Elo (but which large error bars still), in self-play, which would put Alpha 2 at around a tentative +/- 1800 Elo. (No other changes but addition of the hash table.) I've seen the TT-version save a few games it would previously have lost, by finding just the right defense. I have also seen it make a comeback from 2 pawns down to ALMOST win the game; it was just one step short of promoting first.

However... it also seems to have lost the ability to mate with R + K vs K 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...

Drawing games that are clearly won costs a lot of Elo-points (as can be seen in Pulse 1.7.2, with its repetition detection bug).

[Ras]

That was basically it. I was (also) probing the hash table at the root (where ply == 0), which most engines I've checked don't do.

I do, but I don't return hash scores if I have a hash hit with sufficient hash depth in a PV node. This is to avoid chopped off PVs. It also helps against running into a wall in the main iterative deepening once the main depth is large enough and then there's no proper PV for the leftmost path because it's chopped off due to hash table overwrites earlier.

When I get a move back from the hash table, I pass it into sort_moves(movelist, hash_move). There, I do MVV-LVA, and while running through the move list, I compare the hash move to all moves: current_move.is_hash_move(hm).

Yeah, this matching means that you'll not run into illegal hash moves.

I want to keep this under one byte.

Same here.

However... it also seems to have lost the ability to mate with R + K vs K

That might indeed be due to the lacking mate distance adjustment in conjunction with returning hash scores also in PV nodes.

[Uri Blass]

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.

[hgm]

But what if the engine was multithreaded and was using all the threads? Then every thread would be using a single pipeline anyway.

This argument is not dependent on multi-threading: it applies to every core / hyperthread individually. Each cores is 'super-scalar', meaning they can do multiple instructions in parallel, nowadays 4 per clock. (With some restrictions on the instruction type; e.g. loading from memory/cache or multiplying might be limited to 1 or 2 per clock.) Each core can do that.

The point is that for the execution speed of a single search thread, on a CPU that can do only 1 instruction per clock it is important to do as little as possible in total, as nothing can ever be done 'on the side'. With multiple instructions per clock you very quickly run into the situation where instructions have to wait for completion of other instructions, to use their result. If that is the bottleneck, the rate of 4 instructions per clock might be impossible to reach, and the execution pipelines will remain partly idle.

With ts = someTable[ts]; in a tight loop, the next iteration must wait for the fetching of ts for the current iteration to finish, before it can start the access itself. With ts = someTable[i++]; the dependency is only on i, where you cannot start using it before the increment in the previous iteration is finished. But an increment instruction only takes a single clock.

[hgm]

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 always like trodding through uncharted territory. I am a bit busy now trying to develop en engine for Korean Chess with a good evaluation. But I am already itching to try an experiment on search speed:

* Program a simple alpha-beta search (+QS) with material+PST evaluation, and MVV/LVA sorting. No hash table, no killer or history move sorting, as I am not interested in time-to-depth, but just on how many nps it can do. Test if on some middle-game positions (e.g. KiwiPete). No promotions, castling or e.p. capture either; these are so rare that they can always be added later without significant impact on speed.
* Start with a conventional 16x12 mailbox board + piece list, as a reference case, to see if this can get close in seed to Carnivor.
* Then add a neighbor table for eliminating the need to scan the board for the nearest piece in a given direction during capture generation.
* Then add an attack table, to make it possible to generate the captures by victim, rather than by attacker.
* Then do away with the conventional move list in QS, and the corresponding move sorting, but extract the captures to search directly from the attack map.
* Finally I want to extend the evaluation with a mobility term, both in the simple mailbox+piecelist case, and the attack-map case (where it should be practically free).

[Mike Sherwin]

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 always like trodding through uncharted territory. I am a bit busy now trying to develop en engine for Korean Chess with a good evaluation. But I am already itching to try an experiment on search speed:

* Program a simple alpha-beta search (+QS) with material+PST evaluation, and MVV/LVA sorting. No hash table, no killer or history move sorting, as I am not interested in time-to-depth, but just on how many nps it can do. Test if on some middle-game positions (e.g. KiwiPete). No promotions, castling or e.p. capture either; these are so rare that they can always be added later without significant impact on speed.
* Start with a conventional 16x12 mailbox board + piece list, as a reference case, to see if this can get close in seed to Carnivor.
* Then add a neighbor table for eliminating the need to scan the board for the nearest piece in a given direction during capture generation.
* Then add an attack table, to make it possible to generate the captures by victim, rather than by attacker.
* Then do away with the conventional move list in QS, and the corresponding move sorting, but extract the captures to search directly from the attack map.
* Finally I want to extend the evaluation with a mobility term, both in the simple mailbox+piecelist case, and the attack-map case (where it should be practically free).

That sounds like a good idea. Then what turns out to be faster can be the basis for an engine or for someone to start their own engine. However to do justice to the discovery, magic bitboards should be included? Okay, back to bed I go.

[hgm]

However... it also seems to have lost the ability to mate with R + K vs K 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.

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.

I have 2 types, called Move and HashMove. Move contains a 64-bit integer, into which I can stuff whatever I need in the search. The first 24 bits of that integer are the actual move, before the bits with search information come (they hold the sorting score, for example.) So when I save my move to the hash table, I use a member function on the move: current_move.to_hash_move(). That creates the HashMove type, with only the first 24 bits holding the actual move. When I get a move back from the hash table, I pass it into sort_moves(movelist, hash_move). There, I do MVV-LVA, and while running through the move list, I compare the hash move to all moves: current_move.is_hash_move(hm). If this function returns true, I add (at the moment) 60 to the sort score of that move in the move list, which will be guaranteed to put it in front of everything, as the highest MVV_LVA score is 55 (for now).

I want to keep this under one byte. I'm not a fan of "lets 500 million to the sort score, so we KNOW it will be first", or MVV_LVA scores that run in the hundreds.

I typically encode moves as 32-bit integers toSqr + (fromSqr << 8) + (sortKey << 24). I can then compare them as (unsigned) integers for the purpose of sorting. I usually don't bother to search the hash move in the move list, for upgrading the sort key before sorting, and then extract it. Instead I play the hash move before generating any moves, hoping that it will cause a beta cutoff (as it apparently did before, or it would not have been hash move), so that I don't have to generate moves at all. This after some minimal testing to make sure the hash move cannot crash my engine in the 'once-per-day' event of a hash-key collision. (E.g. whether the piece on the from-square is mine, and the victim is a non-royal opponent.)

If the hash move fails low, I just put it at the front of the move list after move generation, and start searching at the second move. I don't bother removing the hash move from the move list; when it will be encountered a second time it will cause a hash cutoff which again will fail low. The overhead is small (especially when you do the hash probe for the child before the MakeMove()), and much less than running through the move list to locate it.

[lithander]

* Start with a conventional 16x12 mailbox board + piece list, as a reference case, to see if this can get close in seed to Carnivor.
* Then add a neighbor table for eliminating the need to scan the board for the nearest piece in a given direction during capture generation.
* Then add an attack table, to make it possible to generate the captures by victim, rather than by attacker.

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?

* Then do away with the conventional move list in QS, and the corresponding move sorting, but extract the captures to search directly from the attack

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?

I like that there's not one "right" way to do these things.