A strange search function

[Mike Sherwin]

The idea is simple -- a more tactically aware quiescence search. It allows a non capture move by both sides at anytime but only once. It may also be very good for playing many very fast internal games for use in real time learning using a portion of the allotted time.

Code: Select all

static s32 SearchOneQ(Thread* t, s32 alpha, s32 beta, s32 stm_d, s32 otm_d) {
	sMove list[140];
	s32 legal, score, eval;
	eval = Evaluate(t);
	if (eval >= beta) return beta;
	legal = GenCaptures(t, list);
	if (!legal) return ILLEGAL;
	for (s32 i = 0; list[i].ft != ES; i++) {
		Sort(&list[i]);
		MakeMove(t, &list[i]);
		score = -SearchOneQ(t, -beta, -alpha, otm_d, stm_d);
		TakeBack(t, &list[i]);
		if (score > alpha) {
			if (score >= beta) return beta;
			alpha = score;
		}
	}
	if (stm_d) {
		GenNonCaptures(t, list);
		for (s32 i = 0; list[i].ft != ES; i++) {
			MakeMove(t, &list[i]);
			score = -SearchOneQ(t, -beta, -alpha, otm_d, stm_d - 1);
			TakeBack(t, &list[i]);
			if (score > alpha) {
				if (score >= beta) return beta;
				alpha = score;
			}
		}
	}
	return alpha;
}

[tmokonen]

Have you tried this out in RomiChess? It's a unique idea, and I might try it out just to see how well it works, but I'm wondering if it would be too explosive.

[hgm]

This is the same as doing an extra ply of full-width search, but extend captures in the final ply by one full ply. But since the latter already means extra work, you would of course not have the time for an extra FW ply at all; your FW search depth would drop by more than one ply.

I have experimented with re-capture extensions in micro-Max, but then I applied those at every depth, not just in the final ply. Initially this brought some Elo, but after I had implemented TT and null move it backfired, and I took it out.

I usually have the opposit problem as is being addressed here; in many variants a conventional all-captures (or even all-non-bad-captures) QS is prone to search explosion. Sooner or later the game gets to a position where 99.99% of all nodes are QS nodes, and it has already difficulty finishing the 1-pl y root iteration. With usually a blunder as a consequence, because it overlooked all threats through non-captures. So I am more interested in what captures I could prune with minimal loss of accuracy than how I could improve QS accuracy by searching additional moves.

So in the AI of the Interactive Diagram I use a very light QS; the only moves that are always searched are capture of the last-moved piece ('recaptures'), or that slide over the square that was evacuated ('pin enforcement'), and then only if these are LxH or the piece is unprotected. The equal captures, and other LxH or any x unprotected captures are only extended half a ply (for discovered slider threats, or continuation with the previously moved piece), or not at all. If the remaining search depth is less than half a ply, the captures that get a half-ply extension are simply pruned.

Because the AI doesn't really know what is protected and what not, captures are allowed to 'borrow' the extension they might get if the victim was unprotected, but when move generation in the daughter then finds a capture on the piece, it subtract the borrowed amount from the remaining depth again, and if the latter drops below zero immediately returns a +INF score, as if a King was captured. This effectively cause the speculatively searched capture to be pruned as if it was an illegal move. A smarter implementation that at any time would be aware of what is protected (e.g. because it uses an attack map) would not have to do it in such a cumbersome way, and could prune the moves before they are searched.

By having such a light QS I can afford more depth in the full-width search, and each extra ply in the root not only can do an extra non-capture, but also two more captures that got a half-ply extension in QS, or one more that was not extended. So the search isn't as blind as you might expect. It just tries to produce a better balance between likely-good, likely-bad and non-captures. So that it doesn't get suckeredso easily in a wild goose chase of likely-bad captures at the expense of the non-captures.

[Dann Corbit]

The idea is simple -- a more tactically aware quiescence search. It allows a non capture move by both sides at anytime but only once. It may also be very good for playing many very fast internal games for use in real time learning using a portion of the allotted time.

Code: Select all

static s32 SearchOneQ(Thread* t, s32 alpha, s32 beta, s32 stm_d, s32 otm_d) {
	sMove list[140];
	s32 legal, score, eval;
	eval = Evaluate(t);
	if (eval >= beta) return beta;
	legal = GenCaptures(t, list);
	if (!legal) return ILLEGAL;
	for (s32 i = 0; list[i].ft != ES; i++) {
		Sort(&list[i]);
		MakeMove(t, &list[i]);
		score = -SearchOneQ(t, -beta, -alpha, otm_d, stm_d);
		TakeBack(t, &list[i]);
		if (score > alpha) {
			if (score >= beta) return beta;
			alpha = score;
		}
	}
	if (stm_d) {
		GenNonCaptures(t, list);
		for (s32 i = 0; list[i].ft != ES; i++) {
			MakeMove(t, &list[i]);
			score = -SearchOneQ(t, -beta, -alpha, otm_d, stm_d - 1);
			TakeBack(t, &list[i]);
			if (score > alpha) {
				if (score >= beta) return beta;
				alpha = score;
			}
		}
	}
	return alpha;
}

I proposed a very similar idea as an alternative to standard qsearch a long time ago, calling it BMOBUN.
BMOBUN stood for: Best Move Only, Back up N times.
The idea is that you don't just exhaust captures. Your qsearch performs the best move only (instead of a capture) until it fails low or exhausts a depth counter. If it fails low, back up (decrementing N which is your allowed back up count) and do the second best move.

It is not exactly the same as your idea, but it has similarities in my view.
There are two parameters D is the allowed search depth and N is the allowed takeback count.

They don't have to be constants. For instance, D could be search depth times two and N could be search depth divided by two.

[hgm]

What do you mean by 'best move'? It seems to me you can only know what the best move is after you searched all...

[Rebel]

The idea is simple -- a more tactically aware quiescence search. It allows a non capture move by both sides at anytime but only once. It may also be very good for playing many very fast internal games for use in real time learning using a portion of the allotted time.

I tried that intensively in the 90's in all kind of variations, nothing good came from it. Instead I learned - get out of QS as soon as possible, which gave elo after all.

[chrisw]

In QS do you do equal captures or only those that gain something?
If gain only, then is N=B or B>N? Eg do you take “equal” NxB captures but not NxN, BxB nor BxN?
Do you take equal PxP?

[Dann Corbit]

What do you mean by 'best move'? It seems to me you can only know what the best move is after you searched all...

When you pick a move to search, how do you choose it? Is it in the hash? Is it a killer move? Etc. You pick the first move in your search list. 95%of the time it will be the right move. For the 5% wrong guesses you have takebacks.

[hgm]

When you pick a move to search, how do you choose it? Is it in the hash? Is it a killer move? Etc. You pick the first move in your search list. 95%of the time it will be the right move. For the 5% wrong guesses you have takebacks.

OK, so it is the first move of your static ordering. But that would always be a capture, right? In QS you would only very rarely have hash moves or killers. (And the killers would come after the captures anyway.)

It seems to me that putting a limit on the number of backups would mostly cause pruning of moves at the first or second ply of QS (depending on which of the two fails low). That seemes pretty risky. In a tactically complex situation you might only get to trying the first move. And if you use MVV/LVA sorting it could very well be a bad capture.

[Dann Corbit]

In my tests it did not outperform normal qsearch. I think today you might eval the top five candidates with the "small net" if you don't have any reasons to choose one over the others.