Some thoughts on QS

[Rebel]

In its original definition a SEE is a function that REPLACES a quiescencesearch.

I remember the moment when I replaced SEE for QS (around 1983) and the huge elo jump it gave. QS produces a lot more reliable result of the leaf position than SEE possibly can.

[Don]

Best example is Chess Genius, no QS.

Wow! I didn't know CG did not use a quies search! That explains some things I didn't know about it.

I think you could build a very strong program without Q search if you set out to do so right from the start. The entire program could be built around the concept and it might work. Right now the top programs as well as komodo are so selective on the last few ply that it's much like an extended quies search anyway.

[diep]

Stupid thought by an idiot: prune if SEE < alpha. Even if we are not better positionally, we will probably be able to make up with material.

End of stupid thought.

Matthew:out

There are much better ways that if SEE < alpha. For example, winning a pawn is not a good capture if you are a rook down. What HG is talking is the case where opposing queens get into the opponent's side of the board and eat pieces left and right, all futile... Rather than eating, one side would actually choose to stop the other from raiding its pieces, but q-search doesn't understand that. I've seen huge qsearch spaces caused by this...

Perhaps a stupid idea, but what if we simply limited the number of non-recapturing consecutive captures by queens or perhaps anything? It's almost always the case that after any extended number of non-recapturing captures one of the sides blundered and should have played differently.

There is almost no strength loss if you put fairly severe limits on the quies search anyway, I think if you stop after 7 ply of quies there is very little strength loss - but I have not checked this recently and I'm unsure of the numbers.

I took this a bit further (probably too far) and limited the qsearch to only recaptures after the 4th ply. I can't say for certain if it provided any strength benefit to Myrddin. But a much better developed/debugged engine might show clearer gains.

jm

I will remind everyone that supposedly some versions of Junior had no q-search at all (whether this is true today or not is unknown). In the 70's, I just tacked on a SEE call to the last move made, to prevent a silly final move in the PV like QxP where the P was defended. This has actually worked. Be interesting to see how much of the q-search one can unload today in light of the very deep searches we do...

Best example is Chess Genius, no QS.

Oh really?
How did it find all those tactics 12 ply deeper always?

I remember the +12 ply settings, for its days it was impressive tactical.
Based upon which heuristics did it search deeper?

We both agree upon that using a full blown Qsearch is way better Ed - no discussion. Also it seems you're trying checks (giving check) moves in qsearch, right?

I do that in Diep as well - not doing that would considerable weaken Diep - but remember, Diep isn't getting 30 plies like the ivanhoes and the stockfishes get.

So picking up that tactics if you get outsearched might be very important and crucial.

For those engines getting that 30 plies - considering they razor and do futility - maybe it's less relevant - in the end their evaluation function is SIMPLE.

It's totally PSQ based positional. Remove PSQ - you remove their elo.

[Don]

Oh really?
How did it find all those tactics 12 ply deeper always?

I remember the +12 ply settings, for its days it was impressive tactical.
Based upon which heuristics did it search deeper?

Vincent,

It's not hard for me to believe. If I were using see() for quies, I would probably be a lot more creative about extending moves on the last ply - particularly captures and checks to help cover things SEE doesn't. In fact with some creativity and by looking at the score and the alpha/beta window and some knowledge of tactical motifs you might very well be able to judiciously extend the last ply, perhaps more than once to get most of the power back that you lose from SEE.

It's all semantics anyway, but CG has a highly selective extended search - and I'll bet that was where most of the magic was.

We both agree upon that using a full blown Qsearch is way better Ed - no discussion. Also it seems you're trying checks (giving check) moves in qsearch, right?

I do that in Diep as well - not doing that would considerable weaken Diep - but remember, Diep isn't getting 30 plies like the ivanhoes and the stockfishes get.

So picking up that tactics if you get outsearched might be very important and crucial.

For those engines getting that 30 plies - considering they razor and do futility - maybe it's less relevant - in the end their evaluation function is SIMPLE.

It's totally PSQ based positional. Remove PSQ - you remove their elo.

[bob]

Best example is Chess Genius, no QS.

Wow! I didn't know CG did not use a quies search! That explains some things I didn't know about it.

I think you could build a very strong program without Q search if you set out to do so right from the start. The entire program could be built around the concept and it might work. Right now the top programs as well as komodo are so selective on the last few ply that it's much like an extended quies search anyway.

It also might depend on the definition of q-search. For example, you can simply choose to not stop searching until you reach a quiet position... Basically your basic search becomes both...

[Don]

Best example is Chess Genius, no QS.

Wow! I didn't know CG did not use a quies search! That explains some things I didn't know about it.

I think you could build a very strong program without Q search if you set out to do so right from the start. The entire program could be built around the concept and it might work. Right now the top programs as well as komodo are so selective on the last few ply that it's much like an extended quies search anyway.

It also might depend on the definition of q-search. For example, you can simply choose to not stop searching until you reach a quiet position... Basically your basic search becomes both...

Exactly. I think that is basically what CG did but with some restrictions. It was not uncommon to see CG end a very long pv with a quiet move.

Here is some speculation - take it with a grain of salt but here are some observations and speculations about CG. If anyone knows more speak up! I think to this day we could still learn a lot from CG which in its heyday was untouchable:

CG also had a very funky style and I believe it was highly asymmetrical in search. Although it was quite strong tactically for it's day, it could see a threat against it much quicker that it could find a threat to its opponent - for example if the opponent threatened to win a piece, Genius would play a move that proved that it saw the threat and it would see this very quickly. But it would take a great deal more time for CG to find the threat. So if you didn't defend against the threat and then let Genius play for the opponent it would often take it a longer time to find the win than it did to defend against it in the first place even though it should have 1 ply advantage.

CG was very defensive, playing a boring ultra safe style and not taking any chances and sooner or later the opponent would make a mistake and CG would pounce - CG was not about to be the one to make the mistake as it never took any chances. I'm pretty sure a lot of that was in the search, not the evaluation. More evidence is the fact that PV's almost always showed an odd number of moves, such as 3, then 5, then 7, etc. CG could start with a negative depth - so it was doing several ply of selectivity and early iterations I think started in this part of the search which I believe was of a fixed length - such as 6 ply (I think Richard changed the number of selective ply over time but I believe it was fixed.) This part of the search I believe was like a super quies search but without the classic framework we are used to seeing.

I think the "always odd" PV's was a side effect of the asymmetrical search. Although I don't really know how it worked I think it pruned it's own moves much more heavily so that whatever path it took was under it's control - no surprises.

I also remember that Ossi Weiner (who seemed to always be by his side to prevent him from talking to anyone) once told me that Richard had found a special trick that gave him the equivalent of an extra ply of search over other programs - some sort of side-effect of how he generated moves or something like that. If wasn't futility or anything like that but he claimed that this was the secret sauce. He could have been just trying to throw me off the track as it did come across a little like double-talk - and he was rather ambiguous but I don't think he really understood the program so anything he knew was probably very abstract anyway. He may have been more involved in the evaluation of the program which was very solid, never playing foolish looking moves but never going for the gusto either.

A lot of people hated Richards programs and did not say nice things about it, even though it pretty much crushed everything it played, at least programs running on the equivalent hardware. You would hear derogatory comments suggesting that Genius didn't really know how to play chess, that it was playing dishonestly as if to make you beat yourself but I found that not very convincing since it usually beat everything it played.

[diep]

Best example is Chess Genius, no QS.

Wow! I didn't know CG did not use a quies search! That explains some things I didn't know about it.

I think you could build a very strong program without Q search if you set out to do so right from the start. The entire program could be built around the concept and it might work. Right now the top programs as well as komodo are so selective on the last few ply that it's much like an extended quies search anyway.

It also might depend on the definition of q-search. For example, you can simply choose to not stop searching until you reach a quiet position... Basically your basic search becomes both...

Exactly. I think that is basically what CG did but with some restrictions.

Well i'm not sure about you, but diep had a 7 ply selective search. Even with massive restrictions that really blows up the search you know. I don't need to give a lecture on that search is exponential, we all know that too well.

So all thoes tactics Genius picked up was very impressive even years after it reign i was impressed by it.

Now that said he didn't use nullmove and first 9 plies were fullwidth. It would be real interesting to know how the restrictions exactly worked.

I had a few positions where genius really had bugs in its selective search, but with the knowledge of today that could also have been an evaluation problem simply of the fullwidth part.

It was not uncommon to see CG end a very long pv with a quiet move.

Not only that, but doing all those checks and all it saw there that's really having a big costs in nodes - so the way how Richard Lang restricted that is more than interesting to know.

Richard Lang actually showed up at world champs 2000 - was very honoured (note the British spelling) to see him there.

Here is some speculation - take it with a grain of salt but here are some observations and speculations about CG. If anyone knows more speak up! I think to this day we could still learn a lot from CG which in its heyday was untouchable:

I had a selective search myself in Diep and i never managed to extend it that well like Genius did do.

Now Frans Morsch of course has a different viewpoint there. He said back then in 90s that the big secret of Genius and Frans own creatures were their huge nps. It's well possible that all this selectivity of Genius was possible because of the huge nps it had versus Diep.

CG also had a very funky style and I believe it was highly asymmetrical in search. Although it was quite strong tactically for it's day, it could see a threat against it much quicker that it could find a threat to its opponent - for example if the opponent threatened to win a piece, Genius would play a move that proved that it saw the threat and it would see this very quickly.

Finding restrictions that work are not easy you know. 12 plies selective search on top of your normal search it's a LOT of plies.

I believe personally the weak spot of Genius was not its search - that was its strong point. Its evaluation was really ugly bad.

This could indicate just as well that the tricks he used in the selective search were purely tactical moves and not positional moves.

So it's quite possible that if we hear how he did do it, that it involves selecting just tactical moves in asymmetric manner, meaning it's worth 0 elopoints now.

Even then it's one of those things i'd really like to hear one day!

But it would take a great deal more time for CG to find the threat. So if you didn't defend against the threat and then let Genius play for the opponent it would often take it a longer time to find the win than it did to defend against it in the first place even though it should have 1 ply advantage.

CG was very defensive, playing a boring ultra safe style and not taking any chances and sooner or later the opponent would make a mistake and CG would pounce

Well this was an evaluation issue i suspect.

- CG was not about to be the one to make the mistake as it never took any chances.

Practical that's describing the rybka/fruit clone style as well today. If your evaluation positional is simpler than your opponents then being passive and sit and wait is what usually works well as then you can't make knowledge mistakes either.

Of course things are much better tuned today, which seem it play sometimes more agressive, but if you'd compare Fruit/Rybka style with for example Stockfish you'll see that SF is far more agressive.

For Diep, SF is a far tougher opponent to fight...

I'm pretty sure a lot of that was in the search, not the evaluation. More evidence is the fact that PV's almost always showed an odd number of moves, such as 3, then 5, then 7, etc. CG could start with a negative depth - so it was doing several ply of selectivity and early iterations I think started in this part of the search which I believe was of a fixed length - such as 6 ply (I think Richard changed the number of selective ply over time but I believe it was fixed.) This part of the search I believe was like a super quies search but without the classic framework we are used to seeing.

There were lots of programmers with weirdo ideas in those days.

Some programmers, with strong top programs, holy believed, like a religion, in always having an even number of moves, even at odd plies.

That was guys who already did do nullmove...

I think the "always odd" PV's was a side effect of the asymmetrical search. Although I don't really know how it worked I think it pruned it's own moves much more heavily so that whatever path it took was under it's control - no surprises.

You make it seem like as if Genius was the first deep mainline checker?

I also remember that Ossi Weiner (who seemed to always be by his side to prevent him from talking to anyone)

You mean to sue yet another person. I remember more than 1 event where opponents of Ossi's henchmen ended up with more courtcases than fingers at a persons hand.

Default was starting 5 courtcases or so. In Europe you are not allowed to defend yourself if the courtcases are above a specific amount of money. Lawyer costs you do not get back (in theory it would be possible - but i've never heard of someone getting it back). So without a ton of cash on the bank you'd be bankrupt.

That had formidable stopping power.

Would one of the Rybka/Fruit clones have cloned Genius, then Ossi would've been able to even ship a dentist at them getting their teeth as payment as he'd win all those courtcases.

once told me that Richard had found a special trick that gave him the equivalent of an extra ply of search over other programs - some sort of side-effect of how he generated moves or something like that. If wasn't futility or anything like that but he claimed that this was the secret sauce.

Oh well i'm not so of a believer in that. I tend to remember how end 90s multicut was suddenly there and then new versions of all these engines appeared. I could be wrong but seemed to me they searched a ply deeper because of multicut.

However it worked total crap.

I don't know why some engines today use it.

Works for Diep at bullet yet not at slow time controls.

That said - multicut is a real invention by Ingvi Bjornsson. It's a real big find by Ingvi - seems not working for chess though, except when you're prepared to sacrafice your hashtables cutoff rate - which is a bad deal IMHO.

He could have been just trying to throw me off the track as it did come across a little like double-talk -

Find me one manager who doesn't speak about the miracles of what they sell...

and he was rather ambiguous but I don't think he really understood the program so anything he knew was probably very abstract anyway. He may have been more involved in the evaluation of the program which was very solid, never playing foolish looking moves but never going for the gusto either.

Oh comeon have some mercy with those grandmasters - Ossi contributing chessknowledge would have been a disaster ending up with sure courtcases against his old chess teachers, not to mention against any chess book he'd read.

A lot of people hated Richards programs and did not say nice things about it, even though it pretty much crushed everything it played, at least programs running on the equivalent hardware.

Well most of the victories of Genius are from before my time. But what i later heard is that some of the Dutch programmers, they all told me, that Richard Lang always ran at far faster hardware than they did. Factors faster according to them. I wasn't there of course, but if Richard lang had motorola 68xxx and they ran on 1Mhz h8's i can imagine that wasn't a fair contest. Back in those days a ply extra was game over.

You would hear derogatory comments suggesting that Genius didn't really know how to play chess, that it was playing dishonestly as if to make you beat yourself but I found that not very convincing since it usually beat everything it played.

It sure dominated!

[Steve Maughan]

Hi Don,

Over the years I've had quite a few conversations with Richard. Here's what I know (and I'm sure he wouldn't mind me sharing).

• CG doesn't have a Q Search as Ed rightly said
  I know from playing with the engines its search is extremely asymetrical i.e it searches broadly on opponents moves and narrow on its own moves
  It doesn't use null move (or didn't back in 2000)
  It keeps an incremental attack table for each square
  It uses evaluation terms at each node to prune (in lieu of null move)

As Don said, I think there are probably gems in CG that would benefit the current crop of engines. Richard basically had to figure all of this stuff out for himself. He also had to grapple with limited hardware. It's quite amazing really.

Best regards,

Steve

[Uri Blass]

Stupid thought by an idiot: prune if SEE < alpha. Even if we are not better positionally, we will probably be able to make up with material.

End of stupid thought.

Matthew:out

There are much better ways that if SEE < alpha. For example, winning a pawn is not a good capture if you are a rook down. What HG is talking is the case where opposing queens get into the opponent's side of the board and eat pieces left and right, all futile... Rather than eating, one side would actually choose to stop the other from raiding its pieces, but q-search doesn't understand that. I've seen huge qsearch spaces caused by this...

Perhaps a stupid idea, but what if we simply limited the number of non-recapturing consecutive captures by queens or perhaps anything? It's almost always the case that after any extended number of non-recapturing captures one of the sides blundered and should have played differently.

There is almost no strength loss if you put fairly severe limits on the quies search anyway, I think if you stop after 7 ply of quies there is very little strength loss - but I have not checked this recently and I'm unsure of the numbers.

I took this a bit further (probably too far) and limited the qsearch to only recaptures after the 4th ply. I can't say for certain if it provided any strength benefit to Myrddin. But a much better developed/debugged engine might show clearer gains.

jm

I will remind everyone that supposedly some versions of Junior had no q-search at all (whether this is true today or not is unknown). In the 70's, I just tacked on a SEE call to the last move made, to prevent a silly final move in the PV like QxP where the P was defended. This has actually worked. Be interesting to see how much of the q-search one can unload today in light of the very deep searches we do...

Well there is a difference in saying 'no qsearch' and 'qsearch replacement function that statically estimates the qsearch value.

That last was seemingly the case with Junior some years ago.

In a book from Jaap v/d Herik from mid 80s you can already read about this, could be it was written in Dutch though.

Possibly he wasn't the first...

With Diep i can't do this, but if your evaluation is relative simple, say basically PSQ and material eval, like the rybka clones, i wouldn't see why it wouldn't be possible to build something like that. Note that i'm not saying it's the BEST solution. But it sure is fast...

I think that it is wrong to call "basically PSQ and material eval" to
the evaluation of every program that evaluates
1)mobility
2)king safety
3)pawn structure
4)passed pawns(that are evaluated not only based on pawn structure but also based on the location of both kings and on the question if they are blocked).

I am sure that every competitve program does it including Junior and
all the Ippolit derivatives.

Remove the PSQ's from ivanhoe and then test its elo please.
then report back, ok?

simple test.

then we talk again and you will know what i mean with 'basically a PSQ program with a good material evaluation.

I did not try it but I think that a fair test is going to be to tune the other evaluation weights(for example bigger mobility scores for knights if piece square table encourage knights in the centre).

My guess is that ivanhoe without piece square table can be stronger than ivanhoe that has only piece square table evaluation.

[Rebel]

Hi Don,

Over the years I've had quite a few conversations with Richard. Here's what I know (and I'm sure he wouldn't mind me sharing).

• CG doesn't have a Q Search as Ed rightly said
  I know from playing with the engines its search is extremely asymetrical i.e it searches broadly on opponents moves and narrow on its own moves
  It doesn't use null move (or didn't back in 2000)
  It keeps an incremental attack table for each square
  It uses evaluation terms at each node to prune (in lieu of null move)

Yes, all of that. I have seen part of his documentation, the Ossi papers as I have called them. They were wrongly (as I later found out) mailed to me instead of Richard's home address, a package of 200 A4 pages. Ossi wrote very instructive an detailed eval terms with clarifying diagrams that went into some form of PST structure initialized before the search started. Hundreds of patterns and pawn structures. Hence CG had a fast eval driven by a kind of sophisticated PST based system.

On my question, how do you do your selective search he answered, by just throwing away all the bad moves.

As Don said, I think there are probably gems in CG that would benefit the current crop of engines. Richard basically had to figure all of this stuff out for himself. He also had to grapple with limited hardware. It's quite amazing really.

Absolutely. Someone should ask if he still has the Ossi papers and if he is willing to scan them.