Checks in QSearch

Programming Topics (Computer Chess) and technical aspects as test techniques, book building, program tuning etc

Moderator: Andres Valverde

Checks in QSearch

Postby Dan Honeycutt » 23 Nov 2004, 20:07

Hi All:

My results with checks in qsearch have been spotty, at best. When I first implemented checks I ran some test positions to gather data on how many times a check actually did something - raise alpha or produce a cutoff. The result was about 1 percent of checks searched. I wasn't expecting a real high value - the better candidates (captures) were searched first - but 1 percent seemed low. I tried skipping the checks if the position was bad (standpat < alpha - 2 pawns). This raised the productive checks to about 2 percent. But my sense was that this was counterintuitive - it is in bad positions where a check might be the salvation.

A few questions:
Ross - you say that checks helped trace a lot. Have you gathered data similar to what I describe and, if so, what sort of productivity have you seen?
Tord - You mention improving by reducing the number of checks searched. How do you decide what is a good check or a probably futile check?
Anyone - I'm doing only checks by attack. I've considered adding checks by discovery but I don't know if it is worth the cost. Thoughts, experiences?

I have not tested as much as I should (and thanks Tord, I will do more tests with R=3). But from what testing I have done the results have been disappointing. Checks in qsearch makes short work of WAC 141 but I've found little else to recommend it.

Dan H.
Dan Honeycutt
 
Posts: 167
Joined: 28 Sep 2004, 15:49
Location: Atlanta Georgia, USA

Re: Checks in QSearch

Postby Ross Boyd » 23 Nov 2004, 21:52

Hi Dan,

First, there are conditions....
only do qs checks when the captures have NOT produced a cutoff.
only at the first ply.

Second,
It seems to be complemented nicely by having single-reply extensions and also Bruce Moreland's nullmove mate threat detection/extensions. I only use R=2 as I find R=3 creates tactical blindspots.

The single-reply to check extension is not implemented very well in TRACE. I don't have a special check evasion generator... so I only know there was a single reply after the makemove loop... I store the single reply as a flag in the hash table and rely on it being used at the NEXT search iteration...
This means that TRACE extends TWO ply when in check and the single reply
hash flag is set.... which has some side effects to do with hash instability.... the single-reply to check hash entries take depth precedence over other entries.... eg. draw scores can get 'buried'.
Future versions will extend a ply when GIVING check and then extend at the next ply when there is only a single evasion... I think this is a subtle but hoepfully more beneficial difference....

Okay, I haven't answered your question at all. As far as statistical analysis of the effectiveness of qs checks goes, I have nothing.... except 1000's of test games.... that show a marked improvement.

Regarding discoveries, yes, I do those. The only checks I don't do are castling and ep discoveries.... too rare... not worth the time.

0x88 lends some efficiencies to discovery ray detection. And direct checks can be optimised slightly for knights by making sure the knight is on the same color sq as the enemy king before generating moves.... and the same goes for bishops....

Good luck with it!

Ross
User avatar
Ross Boyd
 
Posts: 83
Joined: 26 Sep 2004, 23:07
Location: Wollongong, Australia

Re: Checks in QSearch

Postby Dan Honeycutt » 23 Nov 2004, 23:01

Hi Ross:

We are pretty similar. I do captures first, one reply and Moreland extension. I've been passing a "check depth" so I can do checks for no plys, first ply or n plys.

You are at odds with Tord on the null move R. I admit I have not tested this much.

I'll try discoveries. I agree that castling and ep checks are too rare to worry about.

I asked Tord, but I'll ask you too: do you do any sort of determination of good checks and bad checks to limit number of checks searched?

Thanks
Dan H.
Dan Honeycutt
 
Posts: 167
Joined: 28 Sep 2004, 15:49
Location: Atlanta Georgia, USA

Re: Checks in QSearch

Postby Anthony Cozzie » 24 Nov 2004, 00:11

I'll weigh in a bit here.

The problem with not doing checks in Qsearch is that you can take a position where you are about to be mated, make a 3 ply search, and fail high due to null move. So, you find all mates where you are down material 3 ply earlier :) What is worse, is that if you extend on check evasion rather then giving check, and use R=3, you can make a 5 ply search and not realize you are getting mated :) There is no question, however, that it is expensive.

I personally use R=3 in Zappa. *However*, Ross is quite correct and it does cause tactical errors. To really use R=3 well, I think you need a *tactical* search: something that plays pins, forks, and other material gaining moves. However R=3 gives me an extra ply or so, so I think its worth it :)

I personally do unlimited checks in q-search, but I'm working on ways to limit them (but I haven't really had any good ideas yet). Oh. Actually I don't. Zappa doesn't try _any_ moves that lose in SEE in Q-search, and that includes checks. Really I'm almost at the point where I consider search pointless. Zappa doesn't lose that many games on tactics compared to the number it loses on evaluation issues, and I'd rather spend my time on fixing the evaluation.

anthony
Anthony Cozzie
 
Posts: 50
Joined: 17 Oct 2004, 19:35

Re: Checks in QSearch

Postby Dan Honeycutt » 24 Nov 2004, 02:53

Thanks Anthony:

I had not thought of SEE pruning the checks. Will give that a try.

I have tried other tactical moves along with checks. The problem I found with that, if I wasn't capturing and recovering material the next ply was happy to stand pat and simply ignore the fork, attack on the queen etc.

As to limiting checks I simply do (after captures are searched):

if (!checks_tried && depth > 0) {
checks_tried = TRUE;
generate_ checks();
continue;
} else return alpha;

Dan H.
Dan Honeycutt
 
Posts: 167
Joined: 28 Sep 2004, 15:49
Location: Atlanta Georgia, USA

Re: Checks in QSearch

Postby Ross Boyd » 24 Nov 2004, 11:32

Hi Dan
Code: Select all
I had not thought of SEE pruning the checks. Will give that a try.


Forgot to mention that.... I use futility/delta pruning and SEE pruning for the qs captures... and if they all fail I generate and try checks.... and apply SEE pruning only. Not exactly optimal... but better than nothing at all.

You are at odds with Tord on the null move R. I admit I have not tested this much.

Tord does things very differently inside Gothmog... lots of eval/static pruning and lots of compensating extensions.... Anthony said it when he described Zappa... you have to compensate for R=3 with detection of tactical themes and avoid pruning critical lines. Simple-minded engines like TRACE are better off with R=2. Maybe the next major rewrite will be different.

I would guess that almost all the top engines use a highly tuned tactical qs with special attention to hanging pieces,pins etc... the Crafty approach of a minimalist qs will only get you so far... I bet CT, Hiarcs, Shredder, Ruffian, King and Fritz are using something more sophisticated.

And its heartening to read about Slowchess' fantastic success with his tactical qs. Other engines will surely follow that upward path.

Cheers!
Ross
Last edited by Ross Boyd on 24 Nov 2004, 11:44, edited 1 time in total.
User avatar
Ross Boyd
 
Posts: 83
Joined: 26 Sep 2004, 23:07
Location: Wollongong, Australia

Re: Checks in QSearch

Postby Uri Blass » 24 Nov 2004, 11:44

I understood that what helped slowchess was new evaluation of passed
pawn and king safety.

I understood that checks in the qsearch only existed as an idea that is still not implemented.

The words of the programmer are in the bottom of this post.

Notice that he says:
"I haven't done nearly all this though" but also say that "a lot of the king safety and passed pawn scoring is new at least"

I understand from this that other things except king safety and passed pawn scoring are not new and the idea to add tactical stuff to the qsearch is still not implemented.



Here are the words of the programmer Jon Kreuzer:

"This is an intermediate version, the idea was to completely change the eval (Make the eval more bloated while increasing lazy eval) and the search too (by adding a tactical quiescence search that includes checks and other moves.) I haven't done nearly all this though, so I don't claim this isn't mostly still the same Slow Chess. A lot of the King Safety and Passed Pawn scoring are new at least. Many other smaller eval changes and search changes (ie. finds some backrow mates in the QSearch now, etc.)"

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Checks in QSearch

Postby Uri Blass » 24 Nov 2004, 11:53

I can add that I already have checks in the qsearch for a long time so this idea is not new.

It is also used by gothmog and fruit so the explanation for the fact that slowchess is so strong is probably better evaluation.

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Checks in QSearch

Postby Ross Boyd » 24 Nov 2004, 12:01

Hi Uri,

Jon mentioned adding tactical elements to his qs... as well as the addition of king safety and passed pawn eval...

Before you start accusing me of claiming that Slowchess' improvement is solely based on tactical qs please read my other posts where I mention king safety and pawn eval as being also positive factors....

Note also, I claimed Slowchess would show a large improvement before the testers had even confirmed it.

Cheers,

Ross
User avatar
Ross Boyd
 
Posts: 83
Joined: 26 Sep 2004, 23:07
Location: Wollongong, Australia

Re: Checks in QSearch

Postby Uri Blass » 24 Nov 2004, 12:09

Hi Ross,

Here are again Jon's relevant words:

"the idea was to completely change the eval (Make the eval more bloated while increasing lazy eval) and the search too (by adding a tactical quiescence search that includes checks and other moves.) I haven't done nearly all this though"

In other words adding a tactical quiescence that include checks and other moves was his idea but it is still not implemented.

Later he says:

"so I don't claim this isn't mostly still the same Slow Chess. A lot of the King Safety and Passed Pawn scoring are new at least."

In other words king safety and passed pawn scoring are new.
Other things are not mentioned so I guess that they are not new otherwise he did not need to say that he has not done nearly all this though.

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Checks in QSearch

Postby Ross Boyd » 24 Nov 2004, 12:45

Uri,

Did you not read this?

Before you start accusing me of claiming that Slowchess' improvement is solely based on tactical qs please read my other posts where I mention king safety and pawn eval as being also positive factors....


And besides, Jon states he added some things to qsearch eg. backrank mate detection.... correct me if I'm wrong , but isn't this the type of feature you would see in a tactical qs?

I really don't want to waste time on semantic arguments. Jon has modified SC with changes to King eval, passed pawn eval, and other eval as well as mods to the qs including backrank mate threat detection. I am not saying the strength increase is solely due to tactical qs. If you were to read my original post directly after Jon's release announcement you would see that.

If you want to see it differently, so be it. I don't want to write any more about this. Its a drag Uri, and life's too short. Ok?

Ross
User avatar
Ross Boyd
 
Posts: 83
Joined: 26 Sep 2004, 23:07
Location: Wollongong, Australia

Re: Checks in QSearch

Postby José Carlos » 24 Nov 2004, 12:56

Over time of observation, though I haven't had the time and programming ability to prove it, I'm convinced that those two eval terms (king safety and passed pawns) are by far the most important. I've seen hundreds of games lost by Averno because of incorrect passed pawn eval (aganst stronger programs) and because of a king attack (mostly by human players).
I've managed to make some advance in pp eval in the last time, but only in simplified positions with little material. A strong/weak passed pawn in the midgame often decides a game, and strong programs always understand them much better than amateurs.
I find it hard to program it. As a human player, I feel when a pawn is dangerous or will likely fall, in which case I must use it to distract opponent's forces and quickly start attacking on the other side of the board.
I have no idea (so far) how to implement such knowledge.
_____________________________
José Carlos Martínez Galán
User avatar
José Carlos
 
Posts: 102
Joined: 26 Sep 2004, 03:22
Location: Murcia (Spain)

Re: Checks in QSearch

Postby Uri Blass » 24 Nov 2004, 13:02

Hi Ross,I read your posts.
I never claimed that you claimed that the improvement was only because of better qsearch.

I also know that you predicted the improvement in slowchess.

I also remember that Jon said something about backrank mate detection
but I am not sure if he claimed that it is implemented in the new slow chess and I will read again.

I wonder why he claimed
"I haven't done nearly all this though" if he really implemented checks in the qsearch.

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Checks in QSearch

Postby Uri Blass » 24 Nov 2004, 13:13

Hi Ross,

Yes he said that backrow mates are implemented

Here are his words that are relevant to the new slowchess:
"Many other smaller eval changes and search changes (ie. finds some backrow mates in the QSearch now, etc.)"

This make me wonder why he said
"I haven't done nearly all this though" and why he tries to hide it by the "smaller" word to give the impression that he did not do significant changes(I remember that he also said in the beginning that he did not work on slowchess for a long time so based on his words I could not guess significant improvement).

I said nothing at that time but I expected the new slowchess to be weaker because I know that if I try to do changes that are not changing weights in the program without serious testing and without spending significant time then I will probably have a weaker version not because the idea is bad but because I will probably have bugs.

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Checks in QSearch

Postby Jon Kreuzer » 24 Nov 2004, 23:21

The differences in search between 2.94 and Blitz weren't major enough that I felt it really deserved the new version labeling system yet.

Slow Chess has had check responses in the Qsearch for a while (to captures that also check), and did check for some mate-in-1's right before entering the Q search.

Now, the Qsearch checks for Backrow mates, and also knight forks (of the king and queen or rook) in the first ply, but I haven't tried a general test of any reasonable checking move. I also wanted to move my not ending the search (after a 1-reply to check, etc.) to the QSearch, so it would only search tactical follow up moves, but need the general checking moves in the QSearch first.
Also it doesn't enter the Qsearch when depth = 0 is reached after some moves (Blitz has more cases of this than previous version, like if a pawn attacks a piece pinned to the enemy king, it searches another ply since that piece will probably be captured for a gain next move.)
Jon Kreuzer
 
Posts: 26
Joined: 12 Nov 2004, 03:19
Location: United States

Re: Checks in QSearch

Postby Uri Blass » 25 Nov 2004, 10:10

Hi again ross,
It is annoying when you blamed me for not reading your posts.

I read your posts near the time that they were written.
I did not respond to them at that time and I did not mention them in my reply but your consequence that I did not read them is wrong.

I knew all the time that you claimed that slowchess's good results are both because of search and evaluation.

The things that I wrote meant that I disagreed that search was a significant factor and at least Jon made the impression that search changes was not a significant factor in the changes.

When I think about it again,I do not know what to believe and it is dangerous to trust my impression from Jon's posts because my impression was also that
Slowchess did not become better and doing a big change in the evaluiation without testing is usually not going to cause big improvement not because the idea is bad but because of bugs or wrong weights.

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Checks in QSearch

Postby Ross Boyd » 25 Nov 2004, 12:57

Hi Uri,

You're not the only one who was annoyed. I thought you were nitpicking my post for no constructive purpose. Well, I've thought about it and think I know where you were coming from. I see now how anyone could have drawn the conclusion that I said Slowchess' improvement was all about tactical qs. It was on that note that I ended a post....
Well, I didn't intend that and sometimes I waffle on without taking care to be precise with words.

To clarify, I'm as curious as anyone as to how Slowchess has surged ahead. Certainly king safety is very beneficial, and so is passed pawn scoring... and having an 'intelligent' qs is also going to be good on paper. I haven't written a decent qs yet so I'm assuming there are some Elo points to be found in there. Anyway....

Uri, to clear things up between us, I'm sorry for my curt responses. Let's forget it and move on. The WB forum would not be the same without you.

Now if TRACE can start beating Movei, I'll be happy. :)

Regards,
Ross
User avatar
Ross Boyd
 
Posts: 83
Joined: 26 Sep 2004, 23:07
Location: Wollongong, Australia

Re: Checks in QSearch

Postby Uri Blass » 25 Nov 2004, 13:55

Hi Ross,

Ok no problem.

In the last days I did not work on improving the playing strength of movei but on building tools that will help me to check for bugs.
I still have bugs in these tools at this moment so it is not finished.

I am afraid to do significant change in my evaluation because I am afraid to generate new bugs inspite of the fact that mobility evaluation,king safety evaluation and pawn structure evaluation should be improved.

My search also should be improved(for example no internal iterative deepening and no special function to generate only captures when movei loop on all the moves to find captures).

The way that I use hash should be improved and when I think about the amount of things that should be improved(only by implementing stuff that is in Crafty) I can be very optimistic because there are also a lot of directions for improvement that are not in Crafty.

I think that being better than shredder8 on one processor is an easy job for a good programmer with the ideas that I have.

Unfortunately I am not a good programmer so you can expect movei to be significantly weaker than shredder8 in the next year.

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Re: Checks in QSearch

Postby Ross Boyd » 25 Nov 2004, 15:11

Hi Uri,

In the last days I did not work on improving the playing strength of movei but on building tools that will help me to check for bugs.
I still have bugs in these tools at this moment so it is not finished.


Chess engine debugging tools are not often talked about. It would be interesting to hear what some authors are using.

Coincidentally, today, I was thinking about writing some search debugging tools. For instance, I'm trying to figure out why my engine doesn't choose a certain line...it would be great to have a builtin routine to specify a PV and when the line is searched it prints out the score and the reasons why it was pruned/failed low/ etc etc... That's on the todo list.

For eval, I have a routine which analyses fens and compares 1 ply evals with their mirror.... this finds all kinds of stupid asymmetric bugs.

But I still don't have a test suite routine... still doing that by hand via Arena and Fritz. Another thing on the todo list....

And talking of bugs... I found one yesterday which was cause for great celebrations. Every time I let TRACE analyse overnight she crashed. Yet, she never crashed in OTB games. It has had me utterly perplexed for months. I thought it was something to do with a hash table collision. Then later, I thought it was some data being written past the end of an array. And finally I tried increasing the stack space.... but it still crashed .... then I noticed when it crashed the node counter was close to 2^32.... ah ha.....

It turned out my makemove() routine was returning like this

return ++nodes;

If a move is illegal it returns 0;

Well, you guessed it... the node counter was 'wrapping' back to 0 when it hit 2^32 and so it returned 0 when it should have returned non-zero....

What a relief it was to find it... however it means having to release 1.34 for anyone who wants to run long searches.

Uri, it will be interesting to see how Movei fares with IID. It helped me by about 18% IIRC. And do you plan to add hash pruning at some time? Would Movei benefit? I know TRACE would be too slow without the hash pruning... it does very little pruning apart from null move and qs pruning...
In the main search it only extends.... probably way too much...

Getting late here...

Regards,

Ross
User avatar
Ross Boyd
 
Posts: 83
Joined: 26 Sep 2004, 23:07
Location: Wollongong, Australia

Re: Checks in QSearch

Postby Uri Blass » 25 Nov 2004, 17:12

Hi Ross,
The idea that I use is to find information both on pgn file and epd file.
The information needs to be the same in both cases and later when I implement some new evaluation stuff I can detect a bug if the information is not the same because of some wrong update in makemove or wrong calculation from scratch of the information when the calculation based on fen is not wrong.

One note about pruning is that I found that pruning that was counter productive in test suites is probably productive in games at least for movei.

I guess that I will probably add hash pruning but it is not the top priority for me and there are other things to do first.

I probably need first to improve things to make hash pruning productive
and it is not easy and I guess that there are more easy improvements.

The next step in the search will probably be remembering the depth in one variable instead of remembering it in 2 variables and I already did some preperation for it.

Uri
User avatar
Uri Blass
 
Posts: 727
Joined: 09 Oct 2004, 05:59
Location: Tel-Aviv

Next

Return to Programming and Technical Discussions

Who is online

Users browsing this forum: Google [Bot] and 6 guests