Quiescence Search doesn't improve strength

[mvanthoor]

No. Up to my first functional min/max version I hadn't discovered this forums yet. I didn't know that I'd eventually have to pit it against Rustic Alpha and so I didn't worry about how others were doing it. In other words I hadn't fallen into this rabbit hole called 'chess programming' yet.

Oops. Chess programming can be somewhat addictive, one of the reasons being that it is quite objective; you can test your engines against others, and see the objective progress you're making (or not).

I'd like it a lot if you'd add PST's and QSearch (and if you don't have it, MVV-LVA and check extensions). Then you'd really have a complete, minimal chess engine. Even if you leave it at that and start over with a bitboard engine (I would, because you WILL eventually end up there), MinimalChess 0.1 and 0.2 will be good engines to test against for newcomers. There's a lot of crap down there in the rating list, especially below 1500. It would be perfect if you kept the binaries and code online.

I think I didn't even know the words "bitboard" and "mailbox" and just reinvented the wheel because it didn't seem so hard that you'd need to read books or look at other implementations. I still like the resulting move generator code. I think it's pretty, because it's simple. When I forced my wife to watch my making-of videos she understood my explanation of how the move gen works just so. As she's not a programmer I doubt that would have been the case with bitboards!

That's good. Even if you leave MinimalChess as it is after version 0.2 (just rename it to 1.0, and be done with it), it will be a stable engine with easy to understand code in C#, a language you don't see often in chess engine programming.

I also often explain things to my GF. She's not a programmer either, but she often understands things before I even finish my sentences. I hope that this means that I'm explaining my stuff well, and thus I know what I'm doing and implementing. When she begins a sentence with "This might be a stupid question, but...", I already know: "Damn. There it goes... if I program this like I explained, it won't work."

I don't think you can add and subtract ELO points like that. Otherwise, just play against a random mover and win all games and you get infinity ELO and you've solved Chess!

If you have engine X with feature Y, and X with feature A, you can measure the differences; but you're right, it's guesswork for an engine X with both feature X and Y. In a chess engine, features are interdependent. If you measure the Elo-gain of feature Y, it may be more or less, depending on the fact if you have A already implemented or not.

Don't you worry! You're completely safe at this point.

Code: Select all

Score of MinimalChess 0.2.4 PST+Q vs Rustic: 13 - 49 - 13 [0.260]
...      MinimalChess 0.2.4 PST+Q playing White: 7 - 25 - 6  [0.263] 38
...      MinimalChess 0.2.4 PST+Q playing Black: 6 - 24 - 7  [0.257] 37
...      White vs Black: 31 - 31 - 13  [0.500] 75
Elo difference: -181.7 +/- 81.2, LOS: 0.0 %, DrawRatio: 17.3 %
75 of 100 games finished.

...but it's doing good against Sargon 1978 (1249 Elo on CCRL)

To some extent, I had expected more from adding PST's and QSearch. Can I download the binary already? I wonder what the reason for the difference is. Could it be speed only?

PS: Have implemented check extension? "if in_check { depth += 1} " just before "if depth == 0 { qsearch() }"? It is very bad to go into qsearch if you're in check, because not all check evasions will be calculated (as QSearch only does captures).

Code: Select all

Score of Sargon 1978 vs MinimalChess 0.2.4 PST+Q: 8 - 46 - 10 [0.203]
...      Sargon 1978 playing White: 3 - 24 - 5  [0.172] 32
...      Sargon 1978 playing Black: 5 - 22 - 5  [0.234] 32
...      White vs Black: 25 - 29 - 10  [0.469] 64
Elo difference: -237.5 +/- 97.0, LOS: 0.0 %, DrawRatio: 15.6 %
64 of 100 games finished.

So, I'd estimate MMC with QSearch and PST in it's current form to be at 1400-1500 ELO.

Yes, indeed; but it's a N=1 test obviously. The engine used can make a big difference. In CCRL:
Rustic vs. ShallowBlue (1705) => 21.5 − 10.5
Rustic vs. TSCP (1725) => 9 − 23

Rustic makes use of Shallow Blue's weaknesses; TSCP makes use of Rustic's weaknesses. You have to test against a range of engines for an accurate rating.

If you really want it I can send you the binary via PM. But I would prefer to take my time to make sure everything these new features are implemented to the best of my ability before I release a version with PSTs and QSearch. C# makes it easy to rapidly prototype stuff before you optimize it. For example the SortMvvLva is only a few lines of code currently and took me 10 minutes to write. I love C# making that possible. But then I've spend hours looking for a bug that probably is just a performance problem. So, as I've just painfully learned, you can implement a perfectly good optimization like qsearch so inefficiently that it negates it's effect entirely under certain conditions (e.g. too simplistic eval, depth > 7plys).

I'd love to have the preliminary binary.

I wouldn't be surprised if the move ordering that looks up pieces in the board array and recomputes the score each time whatever sort-algorithm C# uses behind the scene needs to compare two elements. I know of course how this could be implemented faster but "premature optimization is the root of all evil"... well in this case Donald Knuth's aphorism was misleading me.

Code: Select all

        public static void SortMvvLva(List<Move> moves, Board context)
        {
            int Score(Move move)
            {
                Piece victim = context[move.ToIndex];
                Piece attacker = context[move.FromIndex];
                //Rating: 100 * Victims value first, offset by the attackers value
                return (victim == Piece.None) ? 0 : ((100 * (int)victim) - (int)attacker);
            }
            moves.Sort((a, b) => Score(b).CompareTo(Score(a)));
        }

Two things:

- Implement a piece-list, so you know where your pieces are. I even do this with bitboards, so I don't have to iterate over 12 bitboards to find the piece I need, and it already is a speed gain. Let alone if you make a piece list and you don't have to iterate over 64 squares.
- Don't sort the move list. You're doing unnecessary work, because some of the moves will never be tried due to cutoffs. Implement a score() function (where you give each move its MVV-LVA score), and a pick() function (where you set the move with the best score in the first spot of the move list just before you start iterating).

[mvanthoor]

I haven't found time and concentration to put much thought into it but at the moment I'm not yet sure how not testing for checks would work. Wouldn't you play illegal moves without noticing? Or is that so rare it doesn't matter?
Also interesting idea to not sort all the captures fully but just start with the most promising one and play the rest in any order.

Your make/unmake (or copy/test) functions test move legality; so you should be safe from making an illegal move even in qsearch. One thing to make sure is that you are NOT IN CHECK at depth == 0 where you enter qsearch. You do so by searching another ply first. "if in_check { depth += 1 }". This makes sure that "if depth == 0 { qsearch() }" does not happen, and alpha/beta goes one move deeper. This is called a check extension.

[hgm]

Wouldn't you play illegal moves without noticing? Or is that so rare it doesn't matter?
Also interesting idea to not sort all the captures fully but just start with the most promising one and play the rest in any order.

If you allow illegal moves in QS, the reply would automatically try to capture the King, as this is also a capture. That is both true in the case where you already were in check and didn't do anything about it, as well as in the case where you made an illegal move that exposed your King anew. So you will need a way to prevent illegal moves anyway, even when not in check. I tacitly assumed that the way in which you do this would also deal with the case where you already are in check and do not cure that. Micro-Max does this by noticing when a capture captures a King, and immediately returning a score +INFINITY for that (without actually searching that capture). It just means that most of the captures it tries when in check will get a -INFINITY score, except the one that captures the checker, or the capture of an unprotected piece with the King. It wouldn't see non-capture evasion of the King, or interposition, but by allowing stand-pat it assumes that one such move exists and will not lead to loss of material, so that the current static evaluation gives the score for it.

(Funny story: in my first Chess program I thought it would be sufficient to just give the King a very high piece value, without preventing further search. That did not work at all: when I checked the computer's King, it replied with a counter check, so that capturing his King would be an equal trade, no matter how much the King was worth!)

[hgm]

Your make/unmake (or copy/test) functions test move legality; so you should be safe from making an illegal move even in qsearch. One thing to make sure is that you are NOT IN CHECK at depth == 0 where you enter qsearch. You do so by searching another ply first. "if in_check { depth += 1 }". This makes sure that "if depth == 0 { qsearch() }" does not happen, and alpha/beta goes one move deeper. This is called a check extension.

Correct, but beware: you can also be put in check when you already are in QS. The piece that made previous capture of the opponent might now check you, or it might have delivered a discovered check. If you do have a separate qsearch() function, the if(inCheck) depth++; in your full-width search routine would not catch that. You would have to do something similar in your qsearch(). But the latter might of course not use any depth parameter at all.

Of course you don't have any of these problems if you use the same search routine for both the full-width search and QS.

[mvanthoor]

Correct, but beware: you can also be put in check when you already are in QS. The piece that made previous capture of the opponent might now check you, or it might have delivered a discovered check. If you do have a separate qsearch() function, the if(inCheck) depth++; in your full-width search routine would not catch that. You would have to do something similar in your qsearch(). But the latter might of course not use any depth parameter at all.

Of course you don't have any of these problems if you use the same search routine for both the full-width search and QS.

I use a separate QSearch function, and my engine has never lost a game due to an illegal move. I don't do anything with regard to checks in QSearch. Are you saying that I have been _lucky_ for thousands of test games?

I'll have to set up a position specifically for this.

[hgm]

How often does your engine play a move without searching any deeper than just QS?

[mvanthoor]

How often does your engine play a move without searching any deeper than just QS?

I'm afraid I don't really understand what you mean. In my engine, QSearch is the last thing it does with regard to searching deeper; after that is the evaluation if there's nothing more to capture.

[lithander]

How often does your engine play a move without searching any deeper than just QS?

I'm afraid I don't really understand what you mean. In my engine, QSearch is the last thing it does with regard to searching deeper; after that is the evaluation if there's nothing more to capture.

What HGM means is that if you don't consider checks properly in your QS it might consider illegal moves in your QSearch which doesn't really cause you to play an illegal move unless your normal search depth would be zero. Which of course it never is!

[Mike Sherwin]

Just some thoughts about Qsearch. The regular search suffers badly from the horizon effect. If the search is deep enough it is not so noticeable in the quality of moves because there are more alternative lines to switch to later. Where it is (or should be) noticeable is in search speed. Alpha-beta search works best when it has more accurate scores to backup and prune against. And the better the evaluation function is the better the pruning will be and the deeper the search will search in a given time. Also more time will be spent in Qsearch than any other part of the search. That should tell us just how valuable that accurate scores returned from Qsearch are.

Given the above there is something I'm getting ready to try. My proposal is to enter Qsearch with a depth parameter of 2. (Or maybe just doing this in the last 2 ply of the full search) Then in Qsearch do not decrement the depth for captures or promotions or maybe pawn to the 7th (2nd) or even castling. It might cut a couple of ply off of the iterative depth but nothing will really be lost. And maybe it will improve the accuracy of the scores returned.

[mvanthoor]

What HGM means is that if you don't consider checks properly in your QS it might consider illegal moves in your QSearch which doesn't really cause you to play an illegal move unless your normal search depth would be zero. Which of course it never is!

If that is indeed what he means: yes, you could indeed consider an illegal capture, but it will obviously never be played because make() will immediately call unmake() and return false. To do this, make() uses square_attacked() to see if the king is in check.

I think it would not be good to check if the king is actually in chekck while in qsearch, because in that case, I'd need to call square_attacked() for every move (in my current move generator).