Some thoughts on QS

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.
Uri Blass
Posts: 9138
Joined: Wed Mar 08, 2006 11:37 pm
Location: Tel-Aviv Israel

Re: Some thoughts on QS

Post by Uri Blass » Fri Jul 20, 2012 9:45 pm

diep wrote:Uri,

You still seem to assume that Diep only has piece square tables is it?
No
but your example suggested more than 2 pawns difference in positional evaluation only based on piece square table(or maybe piece square table+mobility because the knight has also more squares to go from c5 relative to a6)

Note that even if I consider other factors I find it hard to justify 2 pawns
difference by a move like Na6-c5

Na6-c5 does not change the pawn structure and usually it also does not make a big change in king safety(the knight at c5 usually does not threat a square near the white king).

You may also evaluate threats against pieces(Nc5 threats the queen at b7 but usually the queen is not trapped by that move and that move does not threat another piece so I find it hard to justify a big bonus of more than 2 pawns in most cases).

I think that it may be logical to add 0.6 pawns and not more than it for
positional evaluation factors

something like
0.2 pawns for piece square table
0.2 pawns for mobility
0.2 pawns for the threat against the queen

diep
Posts: 1786
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Some thoughts on QS

Post by diep » Fri Jul 20, 2012 10:10 pm

Uri Blass wrote:
diep wrote:Uri,

You still seem to assume that Diep only has piece square tables is it?
No
but your example suggested more than 2 pawns difference in positional evaluation only based on piece square table(or maybe piece square table+mobility because the knight has also more squares to go from c5 relative to a6)

Note that even if I consider other factors I find it hard to justify 2 pawns
difference by a move like Na6-c5

Na6-c5 does not change the pawn structure and usually it also does not make a big change in king safety(the knight at c5 usually does not threat a square near the white king).

You may also evaluate threats against pieces(Nc5 threats the queen at b7 but usually the queen is not trapped by that move and that move does not threat another piece so I find it hard to justify a big bonus of more than 2 pawns in most cases).

I think that it may be logical to add 0.6 pawns and not more than it for
positional evaluation factors

something like
0.2 pawns for piece square table
0.2 pawns for mobility
0.2 pawns for the threat against the queen
"Uri,

The whole question was: if it would be possible to identify positions where such score swings occur, would you want to play that move in quiescencesearch?

That's the original question. "

You have no contribution to the discussion, just still busy with a few random moves you played yourself in opening?

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

Re: Some thoughts on QS

Post by hgm » Mon Jul 23, 2012 9:51 am

I have a QS scheme that I like now:

Code: Select all

Search(depth)
{
  startDepth = (depth == 10 ? 0 : 10); // IID only in horizon nodes
  for&#40;d = startDepth; d <= depth; d++) &#123; // IID
    bestScore = &#40;depth > 10 ? -INF &#58; Eval&#40;)); // depth 0-10 is all QS, so stand pat
    if&#40;bestScore >= beta&#41; return bestScore;

    for&#40; ALL_MOVES ) &#123;
      if&#40;depth<=10 && !MoveIsCapture&#40;move&#41;) continue; // only captures in QS
      replyDepth = d-1;
      if&#40;d<=10 && IsObviousGain&#40;move&#41;) replyDepth++; // maybe other depth limit than 10?
      if&#40;replyDepth < 0&#41; continue;

      MakeMove&#40;move&#41;;
      score = -Search&#40;replyDepth&#41;;
      UnMake&#40;);

      ...
    &#125;
  &#125;
&#125;
The subtlety is in the function IsObviousGain(). Without it (i.e. if it would always return FALSE), this would just be a QS with a depth limit, which is increased from 0 to 10 ply by IID in the horizon nodes (d=10). The idea is now to declare captures 'obvious gains' if the piece captured is worth more than he can recapture (on same or different square) on the next ply as Low x High or hanging piece. And then to extend such captures, so that even at d=0 it would continue to search them to unlimited depth.

The IID is only conceptual, and would in pratice be cut short through the usual depth bootstrapping: a stand-pat result in itself would be immediately valid upto d=10, as would any score where none of the branchess contained a fail low at d=0 (so that it might have been affected by the pruning of the non-obvious captures). Only in the latter case the depth backed-up towards the root would be < 10, and signal to the horizon node that further depth increase is necessary to get the next level of non-obvious tactics within the horizon. As soon as all moves return a 'saturated' depth with their score, no new iterations have to be performed.

The IsObviousGain criterion is inspired by the idea that when I capture something in face of a threat against a higher piece of mine, it is likely to loose material. But I don't want all my captures to be declared non-obvious in the face of a possible Q trade (i.e. he has Q x (protected Q)), so that they would eat one depth unit and would require an extra iteration. So I do not count equal or HxL attacks against a protected piece as threats against that piece. This is consistent with the fact that on the next ply the equal capture Q x (protected Q) would also not be an 'obvious gain', and thus not searched at d=0.

So a capture that qualifies for searching at d=0 will never have a reply searched at d=0 that captures an equal or higher piece. Every next capture after reaching d=0 has to be on a less valuable piece. This ensures you run out of moves pretty quickly, even in positions where plunder raids are possible. You just will not continue the plunder raid at any point where he can make an equal or better capture than you can as stm. This will be saved for the next QS-IID iteration, when (hopefully) more side branches of the plunder raid are resolved, narrowing the search window, and perhaps even alpha-beta pruning the entire plunder raid itself before you wasted time searching it to the end.

A slight refinement can be that you also take captures with the threatened piece into account. E.g. when (at d=0) I am not allowed to search captures of anything less than a Queen, because there is a PxR threat against me, but if one of the captures thus pruned is a BxR capture, a move (threatened R) x (protected B) should be an 'obvious gain', as his recapture of the R is outlawed by my pre-existing BxR.

User avatar
JVMerlino
Posts: 1124
Joined: Wed Mar 08, 2006 9:15 pm
Location: San Francisco, California

Re: Some thoughts on QS

Post by JVMerlino » Mon Jul 23, 2012 6:16 pm

Don wrote:
bob wrote:
ZirconiumX wrote: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

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Some thoughts on QS

Post by Don » Mon Jul 23, 2012 6:34 pm

JVMerlino wrote:
Don wrote:
bob wrote:
ZirconiumX wrote: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
If you want to put such a strict limit you probably should also include up-captures too - they are way too important.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.

bob
Posts: 20930
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Some thoughts on QS

Post by bob » Mon Jul 23, 2012 6:37 pm

JVMerlino wrote:
Don wrote:
bob wrote:
ZirconiumX wrote: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...

diep
Posts: 1786
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Some thoughts on QS

Post by diep » Tue Jul 24, 2012 9:10 am

bob wrote:
JVMerlino wrote:
Don wrote:
bob wrote:
ZirconiumX wrote: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...

A good example of a program that used to do it end 90s was Arthur.
A dutch program. It simply searched because of this 1 to 2 ply deeper.

The main disadvantage is a tactical one: you miss checks in qsearch.

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

Re: Some thoughts on QS

Post by Uri Blass » Tue Jul 24, 2012 9:21 am

diep wrote:
bob wrote:
JVMerlino wrote:
Don wrote:
bob wrote:
ZirconiumX wrote: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.

diep
Posts: 1786
Joined: Thu Mar 09, 2006 10:54 pm
Location: The Netherlands
Contact:

Re: Some thoughts on QS

Post by diep » Tue Jul 24, 2012 12:36 pm

Uri Blass wrote:
diep wrote:
bob wrote:
JVMerlino wrote:
Don wrote:
bob wrote:
ZirconiumX wrote: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.

the positional factors of this simple PSQ type program are easy to estimate in a static qsearch function, which is what we c all SEE.

A SEE = static exchange evaluation, that REPLACES quiescencesearch. Only last few years (last 10 years or so), suddenly a SEE means a function that estimates things just for 1 specific capture.

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

with such simple evaluation function that so heavily relies upon PSQ tables for positional consideration, i argue it might be possible to do without.

In case of diep: forget it.

User avatar
Rebel
Posts: 6374
Joined: Thu Aug 18, 2011 10:04 am

Re: Some thoughts on QS

Post by Rebel » Tue Jul 24, 2012 1:16 pm

bob wrote:
JVMerlino wrote:
Don wrote:
bob wrote:
ZirconiumX wrote: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.

Post Reply