Page 1 of 1
Qsearch() variant
Posted: Thu Sep 10, 2020 1:32 am
by Mike Sherwin
Are there any engines that use or any information for or any opinions of the following pseudo code for a Qsearch()?
Code: Select all
s32 Qsearch(s32 alpha, s32 beta) {
u32 etypes, fig, ts;
s32 fs, score;
u64 epieces, fpieces;
etypes = type[otm];
while (etypes) {
_BitScanForward(&fig, etypes);
if (mat[stm] - mat[otm] + value[fig] <= alpha) break;
etypes ^= 1 << fig;
epieces = piece[otm][fig];
do {
_BitScanForward64(&ts, epieces);
epieces ^= 1 << ts;
fpieces = AttackersOf[otm](ts);
while (fpieces) {
fs = Sort(&fpieces);
if (!Legal(fs, ts) continue;
MakeMove(fs, ts, fig);
score = -Qsearch(-beta, -alpha);
TakeBack(fs, ts, fig);
if (score >= beta) return beta;
if (score > alpha) alpha = score;
}
} while (epieces);
}
return alpha;
}
Re: Qsearch() variant
Posted: Thu Sep 10, 2020 8:29 am
by hgm
This seems an ordinary MVV/LVA capture search with delta pruning. (Except that you don't use ane margin for the latter, which seems bad.) Doesn't everyone use that? The Ippolit QS looks much the same.
Re: Qsearch() variant
Posted: Thu Sep 10, 2020 11:33 am
by Mike Sherwin
hgm wrote: ↑Thu Sep 10, 2020 8:29 am
This seems an ordinary MVV/LVA capture search with delta pruning. (Except that you don't use ane margin for the latter, which seems bad.) Doesn't everyone use that? The Ippolit QS looks much the same.
Okay, so you are saying that this is the most common way or maybe the only way. In RomiChess I generate all the moves and place them in a list and then sort the moves to find the next move. In the pseudo code above only one move at a time is generated and made and there is no move list.
So the difference is one of efficiency? And what you are calling delta pruning, I thought that it was just catching the stand pat condition earlier. Since this sides score is <= alpha before calling -Qsearch it is detecting score >= beta and since the highest valued pieces are captured first there are no more captures that will exceed alpha. What am I missing?
Re: Qsearch() variant
Posted: Thu Sep 10, 2020 6:23 pm
by hgm
Yes, delta pruning, aka futility pruning, is pre-empting the stand-pat cutoff. But the latter is done based on the full evaluation, not just on the material term. To account for the difference one usually estimates an upper limit for the full evaluation after the intended move. Either as the incremental evaluation plus a margin for the worst case of all other terms, or as the current full evaluation, plus the change in the material (PST) term, plus a margin representing the worst-case change of the other terms. The latter method usually allows a smaller margin.
As for the sorting: I suppose you would still need some list for all attackers of a certain value class, and then sort that. But I admit this is a form of 'staged' move generation, and not everyone does that. In particular, generating moves in MVV order is not easy in naive mailbox representations, as the tend to generate moves per attacker, rather than per victim. In Spartacus I use 0x88 capture tests for all opponent pieces in MVV order; the idea was to replace that by generation from the attack map, but it never got to that before the project derailed. In Inferno I do generate the captures directly in MVV order from the attack map. Also there I have to do the LVA sorting for each value class separately, and I have to 'splice in' the multiple captures.
Re: Qsearch() variant
Posted: Thu Sep 10, 2020 6:56 pm
by Mike Sherwin
hgm wrote: ↑Thu Sep 10, 2020 6:23 pm
Yes, delta pruning, aka futility pruning, is pre-empting the stand-pat cutoff. But the latter is done based on the full evaluation, not just on the material term. To account for the difference one usually estimates an upper limit for the full evaluation after the intended move. Either as the incremental evaluation plus a margin for the worst case of all other terms, or as the current full evaluation, plus the change in the material (PST) term, plus a margin representing the worst-case change of the other terms. The latter method usually allows a smaller margin.
As for the sorting: I suppose you would still need some list for all attackers of a certain value class, and then sort that. But I admit this is a form of 'staged' move generation, and not everyone does that. In particular, generating moves in MVV order is not easy in naive mailbox representations, as the tend to generate moves per attacker, rather than per victim. In Spartacus I use 0x88 capture tests for all opponent pieces in MVV order; the idea was to replace that by generation from the attack map, but it never got to that before the project derailed. In Inferno I do generate the captures directly in MVV order from the attack map. Also there I have to do the LVA sorting for each value class separately, and I have to 'splice in' the multiple captures.
Okay, so the pseudo code is not so "cookie cutter" after all. What makes it possible is ... I don't know what to call it ... maybe a type exist on board bit wise selector variable. And what would make that type selector variable possible is keeping track of the number of each kind of piece in MakeMove/TakeBack. When a piece is captured for example, bw_type_sv &= (num > 0) << type. Or when a piece is uncaptured, bw_type_sv |= 1 << type.
Re: Qsearch() variant
Posted: Thu Sep 10, 2020 7:33 pm
by hgm
Well, the bitboard representation doesn't offer that much advantage over mailbox: you still have to loop over attacker piece types, and determine which pieces of each type actually do attack the given square. You have hidden that in the function AttackersOf(). This is not necessarily faster than running through the piece list, and throwing a 0x88 test to check for alignment.
Also, you don't seem to address the problem of equal victims. E.g. you could have two Rooks, one attacked by a Queen, the other by a Pawn. If you happen to extract the first Rook first, you would search QxR before PxR, in violation of MVV/LVA. For this reason my preferred representation for Chess encodes all captures as a bit set, where every bit corresponds to a given (attacker, victim) pair, ordered such that they would extract in MVV/LVA order. This attack map can be incrementally updated by clearing the bits of attacks that are made impossible (e.g. by capturing the attacker, or moving it away), and setting those for newly created attacks.
Re: Qsearch() variant
Posted: Thu Sep 10, 2020 8:10 pm
by Mike Sherwin
Just fyi, I'm working on my statistical based searcher. The only evaluation during search is material. And then the root moves are weighted by statistical analysis with data collected during the search. Yes the two rook situation does violate strict MVV-LVA move generation but that is quickly remedied when the queen is taken. And the two rook type situations are probably rare enough that not doing the extra work to detect them is of greater benefit. But I could be wrong about that.