more moves in qsearch

[Daniel Shawul]

Hi
i recently tried searching more non-capture moves (other than checks)
in qsearch in the first 3 plies.
1. moves that attack any piece and SEE(move) >= 0
2. moves that take a hung piece to a safe square
The result was a 2 ply reduction in search depth, for a small improvent in tactics. I guess that the reason it did not work could be
1) that i am trying too many moves (may be i should try only forking moves)
2) I still apply the null move criteria in qsearch. I think that i should skip this when two of the side to move's pieces are "enprise" ,even though score >= beta.
Any thoughts appreciated
daniel

[Tony van Roon-Werten]

I think there is a more subtle reason why it doesn't work.

If you allow more moves in quiescence you should also allow moves that stop these moves, so mostly the problem is that you don't allow enough moves.

Suppose you allow passed pawn pushes in quiesce. If you don't allow blocking moves, quiesce will return with a score saying the pawn will promote if the opponent can't capture it.

If you allow "attacking the queen", do you also allow moving the queen away ? If you don't, and queen doesn't have a check or a good capture it will appear lost.

These additional moves only seem to work if you add them to the first ply of quiescence, but then it's still questionable if it works better than just searching a little deeper with normal search.

Tony

[Daniel Shawul]

Code: Select all

If you allow "attacking the queen", do you also allow moving the queen away ? If you don't, and queen doesn't have a check or a good capture it will appear lost.

Yes that is what i tried to do. If I generate attacking moves N plies in qsearch, i generate moves that move any attacked piece to a safe square N + 1 plies. But the later may not be done because of null move in qsearch. I think i have to detect cases like queen is attacked, two of our pieces are hung, king is unsafe etc and skip null move accordingly.

These additional moves only seem to work if you add them to the first ply of quiescence, but then it's still questionable if it works better than just searching a little deeper with normal search.

Too many moves in qsearch might not be worth the trouble. However trying only very specialized moves like forking moves in the whole of qsearch might improve tactics with no signifcant loss in search depth.

Thanks
daniel

[Daniel Shawul]

Actually the moves i wanted to try in qsearch are
- forking moves
- moves that attack a piece that is pinned on king.
- And their replies on the next ply.
With a piece list board representation this asks for some effort, I dont know if it is easier with bitboards.

[H.G.Muller]

This is indeed a problem that I am wrestling with as well.

Lately I tried to add check detection to my minimalist program micro-Max. So that in would not happily return the static evaluation when it is check-mated just before QS. If it was in check, it would then try any move in QS until it found a way to solve it with score better than the static evaluation.

Apart from the fact that it took a lot of time to test for check (due to primitive implementation, no doubt), even when awarded this extra time (i.e. allowed to search equal number of nodes), it was conclusively defeated by the version that played without this 'improvement'. Apparently most checks are not dangerous enough to make throwing in another move of full-width search pay off. Perhaps selective check evasion would do better, but in the current case the extra nodes it takes could be put to better use by just adding them to the full-width search.

I experimented with null move in QS, to use the null-move score rather than the static evaluation if no other QS-allowed move beat it, but allowing the moves to solve the identified threat Tony talks about as well.
(E.g., if the opponent's last move threatens my Queen with a Bishop through a discovered threat, I would allow moves with the Queen and captures of this Bishop.) As soon as I find a single move that beats the static evaluation, I disable the search of such moves again. This was very similar to the check test, except that it would also work for other pieces than a King. And it decreased the result in self-play even more...

Part of the failure might be due to the minimalist implementation. If I could selectively check (in 0x88 fashion) what the opponent's last move threatened, and the selectively generate counter measures (rather than just panicking and doing a full extra node) I might benifit from such an advanced QS. But now it was simply too expensive to be worth it. Even though I was extremely conservative in the use of these extra QS moves: null-move was allowed only after it was established that there were no old-fashioned QS moves that beat the static score (in an aspirated search), and threat-evasion moves only if there was a threat, only until I found one that worked, and searched with beta lowered to the static score, so that it would not try to gain anything by such a move, just solve the threat.

Part of what makes it so expensive is that in the old scheme the static score can be used in QS to cause an immediate beta cutoff before generating any moves, while in this scheme either the initial QS or the null-move search will be an all-node (as far as generating the moves is concerned). So I still have not abandoned this idea in the context of separate accounting of ply depth for each side. If one of the sides is in QS but the other still has plies to burn, the null-move search in QS would not be a QS extension but would be regularly paid for. In that case allowing defensive moves in QS if the opponent can effect threats within his regular ply budget would not be that expensive: the nature of full-width is such that this opponent would attempt nonsense in most cases anyway, to which the null-move would already be satisfactory defense, with (re)capture of the piece he moves as a good 'plan B'.

[Ryan Benitez]

I got slightly negative results adding fork moves to qsearch. The results where within margin of error close to the results without. I only did pawn and minor piece forks and only if the fork attacks 2 pieces of greater value. I think my logic could be improved on this. The idea of adding moves that attack any piece and SEE >= 0 is an interesting idea but maybe too time consuming.

Ryan

[Daniel Shawul]

Yes it could be time consuming especially if tried everywhere in quiescence. The reason why i generate all attacks of a piece is because i can do this easily with my data structure. Moves like checks, forks, and attacks on pinned pieces are all subsets of this, and i dont need separate functions.
I haven't tried hard to decrease the amount of moves tried. but i intend to do a SEE on all of the side to move's pieces before applying null move.
This requres some serious change in my qsearch like removing lazy eval and eval cache. so finally there may be nothing to gain but i think for a serious tactical improvement i need to try this in the whole of qsearch rather than first 3 plies.

[Uri Blass]

Yes it could be time consuming especially if tried everywhere in quiescence. The reason why i generate all attacks of a piece is because i can do this easily with my data structure. Moves like checks, forks, and attacks on pinned pieces are all subsets of this, and i dont need separate functions.
I haven't tried hard to decrease the amount of moves tried. but i intend to do a SEE on all of the side to move's pieces before applying null move.
This requres some serious change in my qsearch like removing lazy eval and eval cache. so finally there may be nothing to gain but i think for a serious tactical improvement i need to try this in the whole of qsearch rather than first 3 plies.

I think that trying too many moves in the whole of the qsearch cannot be productive.
I think that it may be better to reduce the number of moves that you try deep in the qsearch.


Another question:

You said that your result was a 2 ply reduction in search depth, for a small improvent in tactics.

What do you mean by small improvement.

Do you mean that it did only slightly better at the same depth in tactical test suites or do you mean that it did only slightly better at the same time in tactical test suites?

[Daniel Shawul]

I experimented with null move in QS, to use the null-move score rather than the static evaluation if no other QS-allowed move beat it, but allowing the moves to solve the identified threat Tony talks about as well.

Do you do a non-zero depth null move in qsearch? I only do a zero depth IE eval() null move.

(E.g., if the opponent's last move threatens my Queen with a Bishop through a discovered threat, I would allow moves with the Queen and captures of this Bishop.) As soon as I find a single move that beats the static evaluation, I disable the search of such moves again. This was very similar to the check test, except that it would also work for other pieces than a King. And it decreased the result in self-play even more...

Since i search all non-losing captures in qsearch what i need to consider is only taking my queen to a safe square. I guess in your case you only do recaptures of the last moved piece. I think that you can't easily detect hung pieces once you start considering threats on pieces other than (king , queen) , and hidden attacks (not just by the last moved piece).
I do it with 0x88 style but it is still very expensive. Especially generation of moves that take a hung piece to a safe square asks for a lot of effort.

Part of what makes it so expensive is that in the old scheme the static score can be used in QS to cause an immediate beta cutoff before generating any moves, while in this scheme either the initial QS or the null-move search will be an all-node (as far as generating the moves is concerned). So I still have not abandoned this idea in the context of separate accounting of ply depth for each side. If one of the sides is in QS but the other still has plies to burn, the null-move search in QS would not be a QS extension but would be regularly paid for. In that case allowing defensive moves in QS if the opponent can effect threats within his regular ply budget would not be that expensive: the nature of full-width is such that this opponent would attempt nonsense in most cases anyway, to which the null-move would already be satisfactory defense, with (re)capture of the piece he moves as a good 'plan B'.

This sounds interesting. I never tried different search depths for different sides. How does this interact with alpha-beta? The reason why i ask is that alpha - beta assumes what is good for us is equally bad for opponent.
But if the search depths are different , this may not hold true any more.
[/code]

[Daniel Shawul]

Code: Select all

You said that your result was a 2 ply reduction in search depth, for a small improvent in tactics.

What do you mean by small improvement.

Do you mean that it did only slightly better at the same depth in tactical test suites or do you mean that it did only slightly better at the same time in tactical test suites?
 


When i says faster i meant smaller depth. To compare the the two versions i think i have to optimize this first.
It did not find any more solution on bt2630 inact it lost one (I think positional). It solved some positions from ecmgcp that earlier verions did not solve but i haven't run it on the whole testsuite. I did this only for the version which considers evasion of pieces to safe square only if there is a fork or a pin on king.

[H.G.Muller]

Do you do a non-zero depth null move in qsearch? I only do a zero depth IE eval() null move.

No, that is part of the problem. To recognize a threat, I have to do a depth of at least one. In principle, this is no problem, to get the score of a recapture you also do a depth-1 search on it. (So a depth-0 = QS search on the reply.) So it is not any more expensive than any other QS move. It is just that the old version frequently cuts off on the 'depth-0 null-move search', without considering any move. (At the expense of being totally blind for any threat.)

Since i search all non-losing captures in qsearch what i need to consider is only taking my queen to a safe square. I guess in your case you only do recaptures of the last moved piece.

That and lower takes higher (i.e. 'obviously winning' captures). Otherwise I could not recognize any threat after null move, since there is nothing to recapture then.

I think that you can't easily detect hung pieces once you start considering threats on pieces other than (king , queen) , and hidden attacks (not just by the last moved piece).

This might be one of the reasons that it did not work in the minimalist approac. I have no SEE there, basically the QS is a recursive implemantation of SEE, with only recaptures. The lower x higher does not catch higer x undefended lower, making the threat-detection overlook lots of threats (but not on King or Queen, though).

I do it with 0x88 style but it is still very expensive. Especially generation of moves that take a hung piece to a safe square asks for a lot of effort.

Yes, without a SEE I simply try the moves and search. Very expensive... In my serious engine I have a very light recapture search that is hardly more work than a SEE, but even there it is expensive.

This sounds interesting. I never tried different search depths for different sides. How does this interact with alpha-beta? The reason why i ask is that alpha - beta assumes what is good for us is equally bad for opponent.
But if the search depths are different , this may not hold true any more.

This is not different from when you use a single search depth. Also there the score depends on the search depth. There always is only a single score that you use in the ordinary way. (I am also working on developing a 'contingency minimax', which works with score ranges, but this is very experimental...). The scores are simply parameters that control the tree that you will search, but within the allowed tree I you do ordinary minimax and alpha-beta.

The big problem is in the hash. To satisfy a request on a hit, the stored depth should be upward compatible, i.e. the depth for both sides should be larger or equal to the requested depths. The biggest problem, though, is when you have to decide about replacement. The depth becomes a two-dimensional quantity, and there is no ordering of 2D quantities... So if I have depth (5,3) in the table, and I needed and calculated (4,4), should I replace? If you replace only based on least-recent used, it is no problem, but if you want to make a decision based on depth it is not clear what you should do. With a single depth, when I do a search at a lower depth than was in the table, because the bound in the table was not good enough to be used with the current window, I overwrite the larger depth, to prevent that useless deep entries with worthless bounds after a score readjustment (due to deepening) will poison the hash table. I am not sure that this would be the best here.

So I plan to go for the most-equal depth, because I expect the most balanced score for that. Giving one side more depth will tip the score in his favor (not to much, if you included adequate defensive moves in QS). This is not so bad, it will discourage each side from wasting its ply budget on delaying tactics, because that will hurt himself more than the opponent. I would perform (internal) iterative deepening in such a way that I deepen the side with the smallest depth first, to steer the search and hash content to balanced entries.

[Tord Romstad]

Hi
i recently tried searching more non-capture moves (other than checks)
in qsearch in the first 3 plies.
1. moves that attack any piece and SEE(move) >= 0

I haven't tried this. Sounds very expensive.

2. moves that take a hung piece to a safe square

I did this for a while in Gothmog (my previous engine), but with several restrictions. I searched such moves only when all of the following criteria were satisfied:

• Static eval > alpha
• (Static eval) - (SEE value of hanging piece) < alpha
• At least two hanging pieces, or a single hanging piece with low safe mobility

At such nodes, I would replace the stand pat score with a null move search, and generate safe moves for the hanging piece(s).

I am not sure how well this really worked, though. I have never tried anything similar in Glaurung.

Tord

[Dann Corbit]

Hi
i recently tried searching more non-capture moves (other than checks)
in qsearch in the first 3 plies.
1. moves that attack any piece and SEE(move) >= 0
2. moves that take a hung piece to a safe square
The result was a 2 ply reduction in search depth, for a small improvent in tactics. I guess that the reason it did not work could be
1) that i am trying too many moves (may be i should try only forking moves)
2) I still apply the null move criteria in qsearch. I think that i should skip this when two of the side to move's pieces are "enprise" ,even though score >= beta.
Any thoughts appreciated
daniel

I have a similar (but even more radical) idea I call BMOBUN (Best Move Only, Back Up N-times).

The idea is to do a normal search with a branching factor of 1. So we search only the pv nodes. Of course, you will find sometimes that your first guess of the next new pv node was bad. So you have to back up and try a different choice. Hence the 'N' term to allow a fixed number of back-up operations.

The idea behind it is that captures to reach a quiet state are often bad ideas that we would not really do in the game state. Quite often, a quiet move of some kind is much better or more threatening than a capture.

So a pv node only method to extend the search in lieu of quiescense was born. You should also have a depth limiting step, because you probably do not want to probe forward for the theoritical maximum number of steps.

The nice thing about it is that you can use your already debugged search to do it -- you just search one node instead of all of them (most of the time, of course).

[Daniel Shawul]

I haven't tried this. Sounds very expensive.

Yes it seems so expensive but actually it not very expensive.
Most moves of this kind have SEE < 0, there are usually not enough
squares where you can safely attack opponent pieces.
Anyway i limited this to moves attacking two pieces.
I also added another criteria on the evasion moves, do evasions only when the previous move is a non-capture (IE forking move).
Now the branching factor is almost the same as it used to be, only thing is that the NPS has dropped by 50-70%.

Daniel