Some thoughts on QS

[diep]

I realize you don't like plunder raids - writing some knowledge there and debugging that well should solve it. For Diep the discussion is a different one - there is no doubt between that doing great captures and giving great checks is a good idea in Qsearch.

Indeed, plunder raids are the main problem I am battling. When a piece like a Lion manages to jump to a safe square within the opponent's camp, it can then start to pick off all neighboring pieces 'en passant', as it were, ending on the same safe square as it was. There could be upto 8 such neighbors, and the Lion could capture them in 8! = 40,320 different orders. If the opponent is then doing the same with his Lion...

You need for sure a hashtable inside qsearch.

Some older Diep versions around the days i introduced todays qsearch, they also could in some cases waste thousands of nodes in qsearch (yes that really brought tactical playstrength - less relevant for todays search depths).

In Diep every ply is the same for hashtable. You can do this only if every ply you do the same thing, that trick only works if you also see things to the bitter end in qsearch.

As for your huge game - a qsearch that's eating so many nodes, it's simply part of the game, you have to accept it - just like ladders with go - and do big effort to do it more efficient. You can't do without hashtable simply in such case.

Tactics in chess are relative easy and initial evaluation also is relative easy to do reasonable as the center is so important in chess. We have been spoiled there.

The game you play it's maybe possible, after statistical analysis, that always starting in a specific order you can skip doing the 'worse moves'. This is very tricky and can dramatically limit the size of your qsearch. It might be too dubious though.

Investing big time in a very good qsearch is really important in any game.

In this case you might also increase strength using an old trick that doesn't work well for chess actually.

During trying moves in qsearch you'll soon discover whether the opponent has big tactical threats. You might consider extending there. In this manner you pick up massive tactics, of course at a huge price, but it's picking up that much tactics that it's giving a huge boost in playstrength. You can see it as an additional 2 ply selective search that gets effectively added.

However where most 'good captures', say taking a pawn on b7, can increase the score, as the queen is dangerous there and can be forced to go back, it'll increase score say 0.5 pawn or so.

Yet playing the move Na6-c5 increases score a lot more, say 2.2 pawns effectively. From shitty mobility to great center control, besides the usual bonuses.

In fact previous move the opponent might've played just a relative 'bad move' just to get the LMR reduction in order to avoid you from playing Na6-c5.

Absolutely right; such huge score swings causes a terrible 'positional' horizon effect, just as bad as captures do without QS. I already saw that in Joker, where the castling bonus was more than 1 Pawn and awarded at the time of the actual castling. It starts to sac Pawns to push the opponent's castling over the horizon.

Moves like that deserve to be searched in QS, because a position where you can do them cannot be described as 'quiet'. I once considered to search Pawn pushes in QS, because they can also give huge score swings (e.g. when creating a passer). And like captures, they are irreversible. So in the end you would run out of them. And futility pruning would take care of most of them in practice anyway.

Of course an alternative, and perhaps more efficient way of solving it would be to distribute the bonus over several moves. E.g. with castling you can already give a bonus for each square between King and Rook that gets evacuated, and with the Pawns you can give a bonus for candidate passers, and majorities. But for the Na6-c5 example there seems no way to 'soften' it.

You could extend this to such moves as Na6-c5, based on some static (PST-like) score threshold. Searching only moves along the gradient of a static board table effectively makes them irreversible too. Only when you have a moving target (like the King for checks) you have the danger of infinite recursion.

Having worlds largest chess evaluation by far sometimes means simply that IF it sees something to be good, it really causes a dramatic swing.

I don't think any other evaluation in computerchess is having any chance just evaluation versus evaluation. You really have to consider that Diep gets outsearched by a quadritrillion plies, as even depth contests they make 0% chance.

Diep has by far the best evaluation, though untuned parameters still make it doubt a lot and that eats more nodes. Several posters here under which Don seem to not see the difference between a great evaluation with superior chessknowledge versus a well tuned evaluation with very little knowledge. It's very easy to outdo with a well tuned evaluation the bad tuned superior chessknowledge as the simpler evaluation when well tuned will strategically play better. Diep can be like god positionally, it really suffers especially in opening from strong tuning which would otherwise also have it play strategically better.

Huge score swings as the above are a result usually of a lot of patterns suddenly coming together.

The very careful tuning of diep where i historically always tuned parameters very low, it is effective, but if some well tuned evaluation has the simpler version of the pattern and has it well tuned, it'll go for that whereas diep gets little points and loses it there; only if more patterns hop in, it'll be convinced there. That means that the generic case goes wrong sometimes - suicide in todays chess.

Being well tuned versus superior knowledge are 2 total different things.

In many positions i just can't even start to compare Diep's evaluation with other evaluations. The well tuned evaluations there might pick the best move at a 1 ply search, but they're not seldom 0.5 to 1.0 pawn off from what the position should be. Diep usually is closer to that 'human natural score' there, but that doesn't mean it picks at 1 ply the correct move more.

A clear proof how important nowadays parameter tuning is.

I'm investing a lot of time there right now.

past few years i started to assume that tuning the parameters better is especially helping the evaluation around qsearch. The above Na6-c5 problem i described is nearly impossible to avoid. We don't know beforehand that the huge score swing is Na6-c5. Much bigger scoreswing could be Qd2-h6. Could be +20 pawns in case of Diep, in some positions.

King safety can easily deliver 50 pawns bonus. It's amazing how many cases where dozens of pawns happen, that this is also very true, as most of that code is years 90 code.

[hgm]

You need for sure a hashtable inside qsearch.

I agree. The bigger the board, the more you will benefit from it. On a huge board there are likely to be many independent tactical skirmishes. Especially unsound captures, as they will not be 'cashed' and accumulate. The (capture, recapture) pairs can then be performed in any order, leading to lots of transpositions.

In Diep every ply is the same for hashtable. You can do this only if every ply you do the same thing, that trick only works if you also see things to the bitter end in qsearch.

Indeed, and this 'same thing' requirement is what makes me weary of making the selection of moves to search path-dependent.

As for your huge game - a qsearch that's eating so many nodes, it's simply part of the game, you have to accept it - just like ladders with go - and do big effort to do it more efficient. You can't do without hashtable simply in such case.

If its part of the game, then indeed there is no escaping. But I asked to people who play Chu Shogi (only 12x12, and actually a pretty interesting game), and they told me that they usually don't consider plunder raids, and in particular not those where a Lion is just sitting inside the enemy camp picking off its neighbors one by one. When I asked the said: "that is easily refuted, because while the Lion is making captures you tighten the net around it to close off its escape route, and it will get lost". But that means that the standard refutation is by non-capture, so that a capture search will never see it!

Maybe QS when a Lion is on the rampage is just a waste of time, and something like a 'half QS' is needed, where one side (that with the Lion) only makes captures, and the other side tries everything, or at least everything that affects the neighborhood of the Lion.

[diep]

You need for sure a hashtable inside qsearch.

I agree. The bigger the board, the more you will benefit from it. On a huge board there are likely to be many independent tactical skirmishes. Especially unsound captures, as they will not be 'cashed' and accumulate. The (capture, recapture) pairs can then be performed in any order, leading to lots of transpositions.

In Diep every ply is the same for hashtable. You can do this only if every ply you do the same thing, that trick only works if you also see things to the bitter end in qsearch.

Indeed, and this 'same thing' requirement is what makes me weary of making the selection of moves to search path-dependent.

For the same reason giving a bonus for castling in makemove - no matter how effective at small search depths, it's dubious.

As for your huge game - a qsearch that's eating so many nodes, it's simply part of the game, you have to accept it - just like ladders with go - and do big effort to do it more efficient. You can't do without hashtable simply in such case.

If its part of the game, then indeed there is no escaping. But I asked to people who play Chu Shogi (only 12x12, and actually a pretty interesting game), and they told me that they usually don't consider plunder raids, and in particular not those where a Lion is just sitting inside the enemy camp picking off its neighbors one by one.

Plunder raids also in chess are important part of the game simply.
Maybe not the type of plunderraid you guess. It's more like: if i go
with my queen and other pieces loot your queenside and you try mine,
do i keep with a pawn up at the end?

In nearly all cases such plunder raids mean 1 specific side wins. So taking a look at them is very crucial.

When I asked the said: "that is easily refuted, because while the Lion is making captures you tighten the net around it to close off its escape route, and it will get lost". But that means that the standard refutation is by non-capture, so that a capture search will never see it!

then you will have to consider such moves. This is not so difficult as it seems. In Diep's evaluation i managed to write hung piece code already mid 90s. You have to face it simply that you need more knowledge for this game to write an efficient search.

Note that in such case it's tactical quickly above the level of any human.

Maybe QS when a Lion is on the rampage is just a waste of time, and something like a 'half QS' is needed, where one side (that with the Lion) only makes captures, and the other side tries everything, or at least everything that affects the neighborhood of the Lion.

I don't know the rules of the game, but obviously 'shutting off moves' are part of qsearch then.

You might want to scale up to 2 different types of searches.

First normal alfabeta with whatever we know. Then a selective search,
then a very limited qsearch.

The selective search you simply do after mainsearch. You should limit how many plies it is.

A disadvantage of this division is that, unless if you limit it to 2 plies, the selective search is bad for hashtable.

2 ply at least in chess is the most effective depth to pickup majority of things.

The boost from a 1 ply search to a 2 ply search gives the biggest eloincrease i would blindfolded guess (except if you consider going from 0 to 1). Moving from 2 to 3 really is peanuts compared from 1 to 2.

Maybe it's an idea to limit qsearch a bit and do captures and 'hang the piece' moves in a selective search. You'll have to figure out what and how.

Additionally you could consider also to just make selective knowledge. Only if some high piece that captures a range, i assume it's a valuable piece, has done a capture you try to specifically get that one hung.

Either way, you will have to find a way to see all those tactics.

[hgm]

Plunder raids also in chess are important part of the game simply.
Maybe not the type of plunderraid you guess. It's more like: if i go
with my queen and other pieces loot your queenside and you try mine,
do i keep with a pawn up at the end?

In nearly all cases such plunder raids mean 1 specific side wins. So taking a look at them is very crucial.

I am afraid you could be right. But is would be very nasty if it tries to figure out in how many million ways it could do the raid, to be finally left with only a Pawn after finding the optimum. Because a Lion can capture stuff 'en passant' (it can do two King moves per turn, and thus capture and withdraw with a large choice of withdrawal squares), basically everything counts as unprotected.

Depth-first is not really an efficient search method for optimizing plunder raids. Perhaps IID in QS (or at least from the horizon nodes) is the answer. For a fixed depth you would have many branches that are interrupted in mid-tactics, and you would have to find a way to score those. Just counting wood would be pretty meaningless, but with a static algorithm determinig all SEEs for and against you it might be possible to get a more meaningful score, which you then refine in the next iteration. (I know the terms SOMA and super-SOMA, but have never looked up how these actually work...)

Another 'branch termination' could indeed be to allow only same-square recaptures beyound a certain QS-level, and then iterate in the horizon node to push back that level step by step.

[diep]

Plunder raids also in chess are important part of the game simply.
Maybe not the type of plunderraid you guess. It's more like: if i go
with my queen and other pieces loot your queenside and you try mine,
do i keep with a pawn up at the end?

In nearly all cases such plunder raids mean 1 specific side wins. So taking a look at them is very crucial.

I am afraid you could be right. But is would be very nasty if it tries to figure out in how many million ways it could do the raid, to be finally left with only a Pawn after finding the optimum. Because a Lion can capture stuff 'en passant' (it can do two King moves per turn, and thus capture and withdraw with a large choice of withdrawal squares), basically everything counts as unprotected.

Depth-first is not really an efficient search method for optimizing plunder raids. Perhaps IID in QS (or at least from the horizon nodes) is the answer. For a fixed depth you would have many branches that are interrupted in mid-tactics, and you would have to find a way to score those. Just counting wood would be pretty meaningless, but with a static algorithm determinig all SEEs for and against you it might be possible to get a more meaningful score, which you then refine in the next iteration. (I know the terms SOMA and super-SOMA, but have never looked up how these actually work...)

Another 'branch termination' could indeed be to allow only same-square recaptures beyound a certain QS-level, and then iterate in the horizon node to push back that level step by step.

what's known is not gonna work here of course. never heard of SOMA before, is it a sexual disease for middle aged men?

I've never followed the literally idea of those definitions. Building something yourself that carefully selects moves in a real well manner is total crucial here.

Probably in this game with a 1 ply search and good quiescencesearch you kick 99.99% of humankind.

[ZirconiumX]

Plunder raids also in chess are important part of the game simply.
Maybe not the type of plunderraid you guess. It's more like: if i go
with my queen and other pieces loot your queenside and you try mine,
do i keep with a pawn up at the end?

In nearly all cases such plunder raids mean 1 specific side wins. So taking a look at them is very crucial.

I am afraid you could be right. But is would be very nasty if it tries to figure out in how many million ways it could do the raid, to be finally left with only a Pawn after finding the optimum. Because a Lion can capture stuff 'en passant' (it can do two King moves per turn, and thus capture and withdraw with a large choice of withdrawal squares), basically everything counts as unprotected.

Depth-first is not really an efficient search method for optimizing plunder raids. Perhaps IID in QS (or at least from the horizon nodes) is the answer. For a fixed depth you would have many branches that are interrupted in mid-tactics, and you would have to find a way to score those. Just counting wood would be pretty meaningless, but with a static algorithm determinig all SEEs for and against you it might be possible to get a more meaningful score, which you then refine in the next iteration. (I know the terms SOMA and super-SOMA, but have never looked up how these actually work...)

Another 'branch termination' could indeed be to allow only same-square recaptures beyound a certain QS-level, and then iterate in the horizon node to push back that level step by step.

what's known is not gonna work here of course. never heard of SOMA before, is it a sexual disease for middle aged men?

I've never followed the literally idea of those definitions. Building something yourself that carefully selects moves in a real well manner is total crucial here.

Probably in this game with a 1 ply search and good quiescencesearch you kick 99.99% of humankind.

http://chessprogramming.wikispaces.com/ ... 0Algorithm

Matthew:out

[Uri Blass]

I am still looking for a pruning method in QS that is more effective in preventing search explosion through plunder raids of powerful pieces. One way to achieve this could be more aggressive pruning of captures that seem bad. Normally this is done only for captures that seem bad by SEE, i.e. through recapture on the same square. But this does not help against plunder raids, where two powerful pieces clean out the board, never exposing themselves to recapture in the process.

The idea is that a capture is bad if after making it, the opponent captures something even bigger, so that in two ply you achieved nothing other than lowering the current eval. But this is a bit too simple, because even with SEE the two ply do have a side effect, namely that you lured another, potentially more valuable piece to the capture square. (I don't want to consider side effects like discovered threats; these are too rare to make that pay off.)

If you capture Qx(protected R) it seems a bad idea, because after recapture you are down Q vs R. It could still end well if the recapturer is Q, and you had a second attacker (say K) on the square, which now does KxQ. SEE would catch that. But now consider the case where there is a pre-existing attack on your Q, and you can play NxR. The NxR looks good SEE-wise, because he can only recapture the less valuable N. But of course the situation is just as bad as wit Qx(protected R), because he will not recapture N, but Q. The pre-existing attack on your Q counts as pre-emptive protection of everything, as it were.

But again, there is the exception that the attack on your Q is with Q, and your Q was protected, so that the initial Rook capture is merely followed by a Queen trade. So perhaps we should only consider threats that are Low x High captures, or captures of unprotected pieces. (Or, in a more refined treatment, have SEE > 0.) In the face of a Qx(unprotected Q) threat it certainly seems unwise to capture a Rook. Even if it is PxR. This can help stopping unpromising plunder raids at an earlier stage; e.g. if I can do Qx(unprotected B) in the face of an existing threat Qx(unprotected R), it doesn't really further my cause to play QxB, despite its SEE of +3. The situation is in a sense similar as for an (unsupported R)x(protected B) capture, which has SEE = -2. So with the threatening loss of -5, it seems wise to prune anything that does not at least capture +5, even if it has SEE > 0.

This is not the whole story, though. There is an essential difference between retaliation on the same square and that on a different square: the initial capturer survives, and any new attacks it might have from the new location remain in existence after the retaliation. With exchange on the same square no new moves are created (ignoring discovered threats). If after PxR our P would check his K, we would not be put off by a threat against our unprotected Q. So in deciding whether a SEE>0 capture should be pruned because of a pre-existing counter threat, it should be taken into account not only what we capture, but also whether what we attack with that capture neutralizes the counter threat. E.g. if we have a hanging R, subject to PxR, but we can play Nx(unprotected B), where the N then attacks a Q, that latter attack serves as a pre-emptive defense of our R. Even if the Q is protected we stand to gain Q-N = +6 from that attack, outweighing the -5 loss of the Rook, with a B already in the pocket. So the capture is promising, and should not be pruned.

In summary:
* 'obvious threats' against us are attacks against unprotected pieces.
* The 'value' of such threats is defined as the value of the hanging piece.
* Captures of pieces worth less than the value of the worst threat against us are candidates for pruning, even if they have SEE>0.
* If such candidates create a new attack on an unprotected piece for us that is at least equal in value to our threatened piece, we must not prune.
* In addition, captures with our most-threatened piece must be searched even if they have SEE<0 when we have an attack against an unprotected more (or equally) valuable piece.

The latter because they create a situation in the daughter node where he now faces a threat of a hanging valuable piece against him, and will thus prune the recapture of our suicide attack, so that the SEE is not relevant. In fact we should even try it when the values are equal: although he now will not prune the recapture, we will cash our threat when he makes it, and it will be a mere trade (after we grabbed something with the initial capture). So the trade is material for tempo, which is not obviously bad, and thus does not deserve to be pruned.

I realize you don't like plunder raids - writing some knowledge there and debugging that well should solve it. For Diep the discussion is a different one - there is no doubt between that doing great captures and giving great checks is a good idea in Qsearch.

However where most 'good captures', say taking a pawn on b7, can increase the score, as the queen is dangerous there and can be forced to go back, it'll increase score say 0.5 pawn or so.

Yet playing the move Na6-c5 increases score a lot more, say 2.2 pawns effectively. From shitty mobility to great center control, besides the usual bonuses.

In fact previous move the opponent might've played just a relative 'bad move' just to get the LMR reduction in order to avoid you from playing Na6-c5.

The big pain is recognizing which moves are gonna give this huge score increase.

Shouldn't we do more last few plies there than just some captures?

It's more of a philosophical question as testing things out there could involve writing massive knowledge code for move ordering - in short the huge difference in Diep in this case between a knowledgeable evaluation.

Worlds most knowledgeable evaluation, versus the relative simplistic move ordering and relative simple move choice in qsearch where only checks and captures get considered in the current Diep incarnation, as far as i can check (debug). Note i am sure i consider more in move ordering than any other program, yet still it's relative simple compared to evaluation, as otherwise the program would slow down too much; the question is not on the ordering so much, it's about whether we still want to try moves and when?

Shouldn't there be more sophisticated termination prior to jumping into qsearch? (regardless of the question, which only comes AFTER that, is in determining WHICH actual moves might give this huge score increase).

I composed a game when Qxb7 Na6-c5 is really relevant

1.c4 Na6 2.Qb3 d6 3.Nf3 Bf5 and now Qxb7 Nc5 is good for white
based on houdini

My opinion is that giving 2.2 pawns bonus for that move does not make sense.

some analysis by houdini

[D]r2qkbnr/ppp1pppp/n2p4/5b2/2P5/1Q3N2/PP1PPPPP/RNB1KB1R w KQkq - 2 4

Houdini_15a_x64:

24/57 04:04 1,046,988,655 4,273,000 +0.43 Qb3xb7 Na6-c5 Qb7-b4 Ra8-b8 Qb4-a5 g7-g6 d2-d4 Nc5-e4 g2-g3 Bf8-h6 Nb1-d2 Ne4xd2 Nf3xd2 Ng8-f6 Bf1-g2 Qd8-d7 Qa5xa7 O-O b2-b3 Bh6-g7 O-O c7-c5 Qa7xd7 Nf6xd7 Bc1-b2 c5xd4 a2-a4 Nd7-c5 Rf1-d1 Nc5xb3 Nd2xb3 Rb8xb3
25/57 07:50 2,043,323,188 4,345,000 +0.49 Qb3xb7 Na6-c5 Qb7-b4 a7-a5 Qb4-a3 Ng8-f6 g2-g3 e7-e6 d2-d4 Nc5-d7 Nb1-c3 Bf8-e7 Bf1-g2 Nf6-e4 O-O O-O Bc1-e3 h7-h6 d4-d5 Ne4xc3 Qa3xc3 e6-e5 Nf3-d2 Nd7-f6 c4-c5

[diep]

Uri a few points, where to start explaining this to you.

You picked *a* position with white to move, and *a* single position would prove anything at all according to you?

You say something about evaluating moves.

Diep is evaluating positions, not moves.

If you feel evaluating moves is better, i'd suggest you modify TSCP again to experiment with that.

I've done that discussion already in 90s and want to claim victory for the leaf evaluators, as i predicted would be best.

Then you throw a 24 ply analysis from some rybka/fruit clone against it, in a position where you have white to move rather than black, and white just picked up a pawn with a knight that only for tactical reasons has to leave a6, and in itself doesn't have a good spot on c5.

For this given position you want to prove that white is ok or something?

How is that having any relation to what i posted?

Fruit is an engine with very little knowledge, which plays moves based upon tuning, not becasue the score actual reflects any reality, let alone that it reflects the luxuryproblem that a lot of patterns with mobility give.

Obviously it's the last engine interesting to compare versus diep in STATICALLY evaluating positions.

[Uri Blass]

Of course usually programs evaluate positions and not moves
and my intention in the words:
"2.2 pawns bonus for that move" is simply about the difference between static evaluation before the move and static evaluation after the move(when of course moving means that you lose the right to move).

It is logical to have bigger static evaluation for knight at c5(white to move) relative to knight at a6(black to move) but certainly not 2.2 pawns and even not 0.5 pawn difference.

Your words:
"playing the move Na6-c5 increases score a lot more, say 2.2 pawns effectively"

I simply find it not logical.

There may be positions when you get initiative that worth more than one pawn by a move like Na6-c5 but I believe that in the majority of the positions it does not happen and I believe that having a huge bonus in the evaluation for relatively small difference may push the program to make wrong sacrifices.

[diep]

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 change the discussion to something total irrelevant, in my own words your statement: "i don't understand how a knight on a6 versus the same knight on c5 can give in *some* position a huge difference in score"

And then you show up with a position where the knight is no good on c5 at all, where white wins a pawn and a 23 ply search of some beancounter to prove that winning a pawn is a great thing

Your next reply you write something *total* different suddenly. Namely about 'majority of positions'.

That's total different than your previous writing.

You just keep changing the story isn't it?

But in all this i get the impression that you seem to assume that Diep's only bonus for a knight gets from the piece square tables, is it?