When you do iterative deepening, should you prefer a quiescent search on each iteration?

Should you store positions found during the quiescent search in the transposition table?

Do you limit the number of plies for the capture search, or do you just wait for the beta cutoffs?

How, with the capture search, should I implement things like the quiescent searches due to poor king safety or checks?

Quote:

Original post by beneficii When you do iterative deepening, should you prefer a quiescent search on each iteration?

That question doesn't make much sense. There should be a quiescence search at each leaf of the tree. Well, assuming you are talking about chess (which would have been nice to mention in your post).

Quote:

Should you store positions found during the quiescent search in the transposition table?

Some programs do, some don't. It's probably a good idea, especially if you manage to make your quiescence search not have depth limits.

Quote:

Do you limit the number of plies for the capture search, or do you just wait for the beta cutoffs?

Some programs do, some programs don't.

Quote:

How, with the capture search, should I implement things like the quiescent searches due to poor king safety or checks?

Again, every program is different. At least you need to program check evasion in your quiescence search. Most programs will include some checks (for instance, checks with a single response). But you need to experiment a lot to find out what works best in your program.

Quote:

Original post by alvaro Quote: Original post by beneficii When you do iterative deepening, should you prefer a quiescent search on each iteration? That question doesn't make much sense. There should be a quiescence search at each leaf of the tree. Well, assuming you are talking about chess (which would have been nice to mention in your post). Quote: Should you store positions found during the quiescent search in the transposition table? Some programs do, some don't. It's probably a good idea, especially if you manage to make your quiescence search not have depth limits. Quote: Do you limit the number of plies for the capture search, or do you just wait for the beta cutoffs? Some programs do, some programs don't. Quote: How, with the capture search, should I implement things like the quiescent searches due to poor king safety or checks? Again, every program is different. At least you need to program check evasion in your quiescence search. Most programs will include some checks (for instance, checks with a single response). But you need to experiment a lot to find out what works best in your program.

Thanks for the response. Yes, I am talking about chess.

Quote:

That question doesn't make much sense. There should be a quiescence search at each leaf of the tree. Well, assuming you are talking about chess (which would have been nice to mention in your post).

I apologize. What I meant is that do you use it throughout iterative deepening? Do you do the quiescence search at the 1 ply search, and then again at the 2 ply search, and then again at the 3 ply search, and so on?

Quote:

Some programs do, some don't. It's probably a good idea, especially if you manage to make your quiescence search not have depth limits.

Because all branches from the node in a quiescence search would not be searched, however, we would not store any of those nodes as PV-nodes, right? Perhaps, I could store it as a PV-nodes, but just mark a flag that this was obtained in a quiescence search, and instead just use the score there as, say, something I could set the alpha as, to help with the alpha-beta pruning when I get to the deeper searches?

And then, basically, with a quiescent search, you would do the same alpha-beta pruning system, right?

Now if the quiescent search comes back with checkmate, you still don't know if you really have checkmate, right? So you would have to find some way to determine if the checkmate would be forced, right?

Quote:

Original post by beneficii Quote: That question doesn't make much sense. There should be a quiescence search at each leaf of the tree. Well, assuming you are talking about chess (which would have been nice to mention in your post). I apologize. What I meant is that do you use it throughout iterative deepening? Do you do the quiescence search at the 1 ply search, and then again at the 2 ply search, and then again at the 3 ply search, and so on?

Yes, you use it all the time.

Quote:

Quote: Some programs do, some don't. It's probably a good idea, especially if you manage to make your quiescence search not have depth limits. Because all branches from the node in a quiescence search would not be searched, however, we would not store any of those nodes as PV-nodes, right? Perhaps, I could store it as a PV-nodes, but just mark a flag that this was obtained in a quiescence search, and instead just use the score there as, say, something I could set the alpha as, to help with the alpha-beta pruning when I get to the deeper searches?

You can simply store the position normally but with a depth of zero. Quiescence search still has beta cuts like regular alpha-beta does, so you would store bound information normally. You would then only use that information in other quiescence searches, because the depth is not enough for anything else.

You are storing depth information in the transposition tables to only use the score if the depth in the table is at least as high as the current search, right?

Quote:

And then, basically, with a quiescent search, you would do the same alpha-beta pruning system, right?

Yes.

Quote:

Now if the quiescent search comes back with checkmate, you still don't know if you really have checkmate, right? So you would have to find some way to determine if the checkmate would be forced, right?

This is not correct. If the quiescence search comes back with checkmate and checkmate was in the alpha-beta window of the search, there is a mate. If this weren't the case, the losing side would have picked the stand-pat option at some point.

Here would be a plan for dealing with a checkmate found during a quiescence search:

During each level of the quiescence search, the program would keep track of how deep it is from the original root move. As in all the searches, if the program finds checkmate, it will return -mate_score + num_plies_from_root_position. (And in the transposition table, this would be converted to +/-(mate_score - num_plies_from_position_in_table), which would be converted back when the table entry is retrieved, and found to be within the range of checkmate.)

If a node of the quiescent search finds checkmate, then it would return that score. The prior node would then see that a checkmate was found and, provided that the checkmate did not cause a cut-off, would perform a full-width search to see if checkmate is forcible within the same number of ply the checkmate was found. Once it saw that checkmate is not forcible, it would simply fail-soft and return the score found, which would be score used. But if checkmate is found to be forced from that position, then it simply would repeat that process up each level until the beginning of the quiescence search. If it reaches the beginning of the quiescence search, and still sees the checkmate is forced, then checkmate will be the score for the position.

The problem this would seem to cause is an explosion of nodes, but I would have to guess that if the checkmate is not forcible, then that would be found fairly quickly, and would help improve the accuracy of the search; otherwise, if a forcible checkmate is found, then that would probably cause massive cut-offs in the rest of the tree, returning a very good solution, and still saving time.

The only problems are some of the accuracy, because it would only search the same amount of ply as the checkmate that was found, meaning that it could miss a slightly deeper checkmate, but I suppose in any program like this, you can't catch every one.

Also, another interesting thing, is that with the full-width search mentioned above, that would probably lead to more quiescence searching, as in chess (and the chess variant mentioned) you could generally keep making captures until there are very few pieces on the board.

Quote:

This is not correct. If the quiescence search comes back with checkmate and checkmate was in the alpha-beta window of the search, there is a mate. If this weren't the case, the losing side would have picked the stand-pat option at some point.

I did not see your post before making mine, so I did not take this into account. So if quiescence comes back with checkmate, then it would have been forcible from the position the quiescence search started from? Well, if you find checkmate at q (quiescence)-ply 5, for example, you had generally only found it via capture moves, right? Couldn't there have been a move at, say, q-ply 3 that would not have allowed the checkmate to be forcible, but which was not searched because it was considered to be a quiet move?

Quote:

Original post by beneficii Quote: This is not correct. If the quiescence search comes back with checkmate and checkmate was in the alpha-beta window of the search, there is a mate. If this weren't the case, the losing side would have picked the stand-pat option at some point. I did not see your post before making mine, so I did not take this into account. So if quiescence comes back with checkmate, then it would have been forcible from the position the quiescence search started from? Well, if you find checkmate at q (quiescence)-ply 5, for example, you had generally only found it via capture moves, right? Couldn't there have been a move at, say, q-ply 3 that would not have allowed the checkmate to be forcible, but which was not searched because it was considered to be a quiet move?

OK, I've worked out the logic, and it seems you are right, even in the leftmost node:

Suppose we just entered the first level quiescence search from the leftmost node of our alpha-beta function, so we started off with (alpha, beta) as:

(-mate, +mate)

Well, we check and we get our stand pat score, which modifies the alpha:

(stand_pat, +mate)

Now we check our first capture move, and we pass down (-beta, -alpha), going to the next level as:

(-mate, -stand_pat)

We see that this position is checkmate, so we award it a score of -mate+total_depth, which does technically improve alpha, and this being a terminal node there are no moves to search, so we return -mate+total_depth. This is received in the parent node as mate-total_depth, which is greater than stand_pat, so replaces it as alpha, getting:

(mate-total_depth, +mate)

But this would hardly cause a problem, because this is positive mate, meaning that of course this player wants to make a move to cause checkmate, meaning that this is a legitimate checkmate.

Now let's look a little deeper, if we find the checkmate deeper in the quiescence search down the leftmost nodes:

We start off with:

(-mate, mate)

Then we get:

(stand_pat_uno, mate)

Then we look at our first move, passing down:

(-mate, -stand_pat_uno)

We get a stand pat score here too, which replaces -mate, but is less than -stand_pat_uno (otherwise we would get a cutoff):

(stand_pat_dos, -stand_pat_uno)

Then we look at the first capture there, and pass down again:

(stand_pat_uno, -stand_pat_dos)

And this is a checkmate node, and the stand pat score here is -mate+total_depth, but it is by no means greater than stand_pat_uno, so nothing happens, and there is no checkmate returned.

So I see your point, and thank you for this, as it does simplify things.

I'm glad you figured it out. By the way, which "Cordova" are you from?