Starting with quiescence search

[hgm]

I have not followed the development of your engine for some time, so this (perhaps stupid) question:

Did you already implement alpha-beta pruning? (And do you also do that in QS?)

[Luis Babboni]

:
...
Did you already implement alpha-beta pruning? (And do you also do that in QS?)

Yes and yes.

In fact is not the same algorithm it seems other engines uses. For example, not have Beta! But as far as I understand, do the same function as good as alpha beta.

[hgm]

OK. I asked because the total game tree of QS (i.e without alpha-beta pruning) usually totally explodes, because it contains plunder raids, where both sides keep capturing with the same piece (usually a Queen) gobbling up all other opponent pieces. With alpha-beta pruning, and sorting the move so that you try capturing the most-valuable piece first, usually puts a quick stop to that, through a beta cutoff.

Best way to diagnose the problem would be to collect some statistics on how many nodes are visited by QS (measured by comparing the nodes before and after the call to QS in the non-QS nodes that call them). And then printing the position(s) where this count is exceptionally high, and print the entire QS tree from that position, to see if the search makes sense.

[Luis Babboni]

OK. I asked because the total game tree of QS (i.e without alpha-beta pruning) usually totally explodes, because it contains plunder raids, where both sides keep capturing with the same piece (usually a Queen) gobbling up all other opponent pieces. With alpha-beta pruning, and sorting the move so that you try capturing the most-valuable piece first, usually puts a quick stop to that, through a beta cutoff.

Best way to diagnose the problem would be to collect some statistics on how many nodes are visited by QS (measured by comparing the nodes before and after the call to QS in the non-QS nodes that call them). And then printing the position(s) where this count is exceptionally high, and print the entire QS tree from that position, to see if the search makes sense.

Thanks HG! I´ll try to make that kind of count.

What my engine do not have is move ordering*, and is not easy to do it cause the way I did the moves generator**, may be this is the difference. I mean, I guessed having or not move ordering will not make difference ina sense that of course better with moves ordering but in any way with QS will be better than without QS.

*: I could choice between fixed order (first pawns, later A rook, B knight, C bishop, queen, king, F bishop, G knight and last H rook with some directions first on each piece) or totally random order between pieces and some random for directions changing the order random for each new halfmove.
**: I´m prety sure I´ll need a different moves generator when I´ll rewrite the engine code but still I do not want to do it cause I´m prety sure that as far I could advance now with actual code, less times I´ll need to rewrite the code in the future knowing better the stuff I will need to fight with.
(I hope my english was enough not bad to make at least an indian explanation)

[Sven]

OK. I asked because the total game tree of QS (i.e without alpha-beta pruning) usually totally explodes, because it contains plunder raids, where both sides keep capturing with the same piece (usually a Queen) gobbling up all other opponent pieces. With alpha-beta pruning, and sorting the move so that you try capturing the most-valuable piece first, usually puts a quick stop to that, through a beta cutoff.

Best way to diagnose the problem would be to collect some statistics on how many nodes are visited by QS (measured by comparing the nodes before and after the call to QS in the non-QS nodes that call them). And then printing the position(s) where this count is exceptionally high, and print the entire QS tree from that position, to see if the search makes sense.

Thanks HG! I´ll try to make that kind of count.

What my engine do not have is move ordering*, and is not easy to do it cause the way I did the moves generator**, may be this is the difference. I mean, I guessed having or not move ordering will not make difference ina sense that of course better with moves ordering but in any way with QS will be better than without QS.

*: I could choice between fixed order (first pawns, later A rook, B knight, C bishop, queen, king, F bishop, G knight and last H rook with some directions first on each piece) or totally random order between pieces and some random for directions changing the order random for each new halfmove.
**: I´m prety sure I´ll need a different moves generator when I´ll rewrite the engine code but still I do not want to do it cause I´m prety sure that as far I could advance now with actual code, less times I´ll need to rewrite the code in the future knowing better the stuff I will need to fight with.
(I hope my english was enough not bad to make at least an indian explanation)

To make it clear: without move ordering you might be wasting a lot of your time, and your chess engine development efforts might come to an end very soon. All you are currently doing may be good to improve your engine from, say, ELO 1000 to 1100 (to give just a wild guess - I have no idea about the current strength of Soberango) but not more. An engine without move ordering will not be better with QS than without QS (it will probably even play worse) since the computational effort to perform QS without move ordering will outweigh the benefit of using QS to resolve captures in non-quiet positions, and in the end your engine will probably search less deep than without QS given the same time. Move ordering is important for full-width search, and usually helps to shrink the tree size by an order of magnitude; for QS move ordering is simply essential, you cannot do any effective QS without it. As soon as the opponent has made a bad (and losing) capture with his queen you *need* to start by capturing that queen first, otherwise the search will explode badly. And that happens frequently whenever queens are on the board. Similar things can also happen with other pieces.

[Sven]

:
...
Did you already implement alpha-beta pruning? (And do you also do that in QS?)

Yes and yes.

In fact is not the same algorithm it seems other engines uses. For example, not have Beta! But as far as I understand, do the same function as good as alpha beta.

You need both alpha and beta for a correct implementation of the algorithm, even with minimax instead of negamax, even with an iterative solution instead of a recursive one. Otherwise you cannot do correct cutoffs for both players, at most for one of them. You have to maintain one bound against which you check for a cutoff of the currently moving side (beta), and the second bound (alpha) which you save and use it when moving to the child node where you check for a cutoff from the opponent's viewpoint. You cannot take the same bound for both, that will yield wrong results.

[hgm]

Sven puts it very well: move ordering is the single most important thing creating strength in an engine. Without good move ordering even alpha-beta pruning hardly improves anything.

Note that you should not order the moves by which piece moves, but by which piece is captured. This is not the most naturalway to generate moves, so most engines decouple move generation from actually searching the moves, by storing the moves in an array as they are generated, then sorting the array in the desired order, and only after that run through the array to search any moves.

Even in micro-Max / Fairy-Max, which does not store the moves in an array, but searches them in the order they are generated, I use a trick to make sure the first move that is being searched is the one that captures the most valuable piece in QS, or, for deeper searches, the move identified as best in a less deep search (either transferred through the TT, or, lacking that, calculated on the spot by IID). The fact that IID always starts at QS level furthermore guarantees that all captures are searched before any quiet moves.

[Luis Babboni]

Thanks HG and Sven for your time!

Actually I think I understand first Sven answer, that QS without move ordering could be even worst than not do QS.
Yes, you was too accurate, actual CCRL 40/4 Soberango´s ELO is 1027.

About HG answer may be I´ll try to do a move ordering with some trick as he saids cause Soberango do not store moves. With the idea of depth first, I generate one move, go deeper, generate one move go deeper and so on till max depth and evaluate, then return and generate the next move for max depth - 1 and go deeper again, evaluate and so on till complete this branch and then return to max depth -2, go deeper and so on. What are TT and IID?
The other option is to start the code again with all what I learned till now, but I still think I´ll could do a better new code if first I complete the understand of esentials ideas. I still do not know nothing about endgames, tablabases or hash tables and even my evaluation use just count the material.

About the Sven second answer, that alpha beta needs alpha and beta , I still not understand it. I´ll must studie that again, I was sure I found a way as good without two bounds (improved the reach depth one ply compared with minimax that means as minimax around 30 times faster) but reading you, I bet I´m wrong.

[bob]

Thanks H.G.!

I´do not understand since this point of your explanation:

(b)
...
and assume all non-captures will not change the score compared towhat it currently is. (I.e. include the static evaluation instead of any non-captures in the set of possible actions from which you take the best. This is usually implemented by trying the static evaluation first, in the hope this will cause a beta cutoff so that you never get to searching any captures.)

I evaluate the positions at the end nodes.
An end-node was for me till now depth=maximumdepth.
What I´m trying to do is to understand a capture as a no-end node and just go one ply further.

What about include checks not just captures?
It seems cause my code is far simplier to me to include just captures than include captures and checks.

This is a normal quiescence. At the top, before you search any captures, compute the static evaluation for the position and set alpha to that value. Then search only the captures (or checks also if you want) to see if they can improve the alpha bound.

Yes, it is simpler to include just captures and that is perfectly OK for getting started. Later you will probably want to add checking moves as well to the q-search. But I (and most) don't do anything about checks inside the q-search as the cost can outgrow the benefit...

Note that if you do checks also at the first ply of the q-search, you must include searching ALL legal moves at the second ply (to escape those checks) otherwise including the checks is pointless if the opponent can stand pat while in check.

[hgm]

TT = Transposittion table = hash table, where you store the result (score and best move) of any node you searched. If you then search one ply deeper in the next iteration of Iterative Deepening you normally find the result you had for that node in the previous iteration, which you now want to search one ply deeper. The chances that the best move you had then still is the best move now are very high (like 90%), so you can start searching that move.

IID =Internal Iterative Deepening. This is a technique where you do not only iterate the depth in the root node, but i every node. E.g. when you want to search the root 3 ply deep, you must search all the rootdaughters 2 ply deep, but each time you arrive in such a node you will first search it 1 ply deep to get a best move, and only then search it 2 ply deep, starting with the best move from the 1-ply search. You would only do that when the result of the 1-ply search was not left in the TT from the time when you did the 2-ply iteration in the root.