aspiration search based on TT hits of lower plies?

[Zach Wegner]

Why would you do this when the PVS approach is well-known? That is about as "tight" an aspiration window as you could use, since the window is actually null.

This only matters on actual PV-type nodes, of which there are very few in a normal search...

The same reason you would do aspiration at the root. You use PVS there too right? The important thing is the first move.

Personally, I'm not going to bother with it due to my iterative search. I don't think it will make much of a difference anyways, as only the first branch searched will have an open window.

[cyberfish]

I still don't follow. how is it wasted effort to search with a null window, when you propose to replace this with a search of a _non-null_ window that is somehow offset from the current bounds? A null-window search is the most efficient search you can do. We don't do them at the first move of the root because we need to know the actual score. But once you have searched the few PV nodes, knowing the exact score becomes worthless...

Hmm, perhaps my understanding of PVS is wrong. My understanding of PVS -
assume the first move is going to be the best move
search the first move with a full window
search the remainder of the moves with a null window, but research with full window if the move turns out the be greater than alpha (meaning the initial assumption is incorrect)

When I say wasted effort, I was referring to the research that the engine will have to do if a move happens to be above alpha. In that case, the search with null window (although relatively cheap) is wasted.

What I am proposing is that, before doing the null window search, check the transposition table first. If, for instance, a search to depth 8 is needed, but a transposition table entry exists (for the position to be searched) to depth 6, and it indicates that the value of the node is between alpha and beta, we can skip the null window search (because we expect it to improve alpha), and search with a aspiration window (around the tabulated value) instead.

In pseudo code:

Code: Select all

Score search(alpha, beta) {
	check TT for a result that can be used directly(); //normal lookup

	check TT for a "suggestion"(); //same as normal lookup, except we want the result even if depth is not sufficient

	if ("suggestion" is a value between alpha and beta) {
		do an aspiration search around "suggestion"();
	} else if ("suggestion" > beta) {
		do a null window search to verify();
		if (returned score < beta) {
			research with original window();
		}
	} else if ("suggestion" < alpha) {
		do a null window search to verify();
		if (returned score > alpha) {
			research with original window();
		}
	}

	//...
}

[Harald Johnsen]

Ok I see.

You should try that (and post the results). I think that the non null window search will cost too much but i've not tried....

HJ.

[Karlo Bala]

Hmm, perhaps my understanding of PVS is wrong. My understanding of PVS -
assume the first move is going to be the best move
search the first move with a full window
search the remainder of the moves with a null window, but research with full window if the move turns out the be greater than alpha (meaning the initial assumption is incorrect)

When I say wasted effort, I was referring to the research that the engine will have to do if a move happens to be above alpha. In that case, the search with null window (although relatively cheap) is wasted.

What I am proposing is that, before doing the null window search, check the transposition table first. If, for instance, a search to depth 8 is needed, but a transposition table entry exists (for the position to be searched) to depth 6, and it indicates that the value of the node is between alpha and beta, we can skip the null window search (because we expect it to improve alpha), and search with a aspiration window (around the tabulated value) instead.

Hi

If you are on PV node (only node with open a-b window) then you are searching first move with open window and rest of moves with null window. Move ordering on PV (and every) node is based on TT probes, so node that you expect to improve alpha was already searched first. You can sometimes find rest of nodes in TT but evals of those nodes should be less or equal to alpha.

[Gerd Isenberg]

Hmm, perhaps my understanding of PVS is wrong. My understanding of PVS -
assume the first move is going to be the best move
search the first move with a full window
search the remainder of the moves with a null window, but research with full window if the move turns out the be greater than alpha (meaning the initial assumption is incorrect)

When I say wasted effort, I was referring to the research that the engine will have to do if a move happens to be above alpha. In that case, the search with null window (although relatively cheap) is wasted.

What I am proposing is that, before doing the null window search, check the transposition table first. If, for instance, a search to depth 8 is needed, but a transposition table entry exists (for the position to be searched) to depth 6, and it indicates that the value of the node is between alpha and beta, we can skip the null window search (because we expect it to improve alpha), and search with a aspiration window (around the tabulated value) instead.

In pseudo code:

Code: Select all

Score search(alpha, beta) {
	check TT for a result that can be used directly(); //normal lookup

	check TT for a "suggestion"(); //same as normal lookup, except we want the result even if depth is not sufficient

	if ("suggestion" is a value between alpha and beta) {
		do an aspiration search around "suggestion"();
	} else if ("suggestion" > beta) {
		do a null window search to verify();
		if (returned score < beta) {
			research with original window();
		}
	} else if ("suggestion" < alpha) {
		do a null window search to verify();
		if (returned score > alpha) {
			research with original window();
		}
	}

	//...
}

In your pseudo code you need to be more precise what between alpha and beta means, guess > alpha and < beta, but not >= alpha and <= beta as your other cases suggest. Thus, it only occurs at the rare pv-nodes where your window is already open - but never on expected cut- or all-nodes which already are null-window searches.

In PVS you eventually re-search at pv-nodes after the first move(s) were tried with open window and an alpha improvement as trigger for further null-window searches of the remaining moves. You may count how often re-searches occur.

Many programs use different search-routines for open and closed windows as proposed in the VARIABLE DEPTH SEARCH paper by T.A. Marsland and Y. Björnsson:
http://www.cs.ualberta.ca/~tony/RecentP ... and-8b.pdf

[CThinker]

Why would you do this when the PVS approach is well-known? That is about as "tight" an aspiration window as you could use, since the window is actually null.

This only matters on actual PV-type nodes, of which there are very few in a normal search...

Because my move ordering is not perfect, resulting in wasting a lot of time searching with a null window. What I want to do is to use the transposition table entry (even if not deep enough) to assist in making the guess, as opposed to always guess that the first move is the best move. For instance, if the transposition table returns a score between alpha and beta, I won't bother trying to search with a null window.

Then, I guess, what needs to be worked on is your move ordering. PVS itself is predicated on perfect move ordering.

[bob]

I still don't follow. how is it wasted effort to search with a null window, when you propose to replace this with a search of a _non-null_ window that is somehow offset from the current bounds? A null-window search is the most efficient search you can do. We don't do them at the first move of the root because we need to know the actual score. But once you have searched the few PV nodes, knowing the exact score becomes worthless...

That is correct, but the algorithm is recursive. Search the first root move with a normal window. Search the first move at ply=2 with a normal window. repeat until you get to the tips.. Then, as you back up, since you have searched the first move at each ply with a normal window, you start searching the remainder of the moves at every ply (including the root) with a null-window. You only re-search with a normal window when the null-window search fails high.

In a 16 ply search, where you don't change your mind (the first move is best) you might search 16 nodes with a full window, and the remainder of them with a null-window. 16 is a tiny percent of the total nodes searched...

Hmm, perhaps my understanding of PVS is wrong. My understanding of PVS -
assume the first move is going to be the best move
search the first move with a full window
search the remainder of the moves with a null window, but research with full window if the move turns out the be greater than alpha (meaning the initial assumption is incorrect)

When I say wasted effort, I was referring to the research that the engine will have to do if a move happens to be above alpha. In that case, the search with null window (although relatively cheap) is wasted.

What I am proposing is that, before doing the null window search, check the transposition table first. If, for instance, a search to depth 8 is needed, but a transposition table entry exists (for the position to be searched) to depth 6, and it indicates that the value of the node is between alpha and beta, we can skip the null window search (because we expect it to improve alpha), and search with a aspiration window (around the tabulated value) instead.

This is a standard idea in null-move search already. We can use hash hits (on entries with insufficient draft to terminate the search) to indicate that a reduced-depth null-move search will fail low. But for normal searches where do you get that hash table entry from? Hardly any hash entries are "exact" anyway, so you will hardly ever see that happen...

In pseudo code:

Code: Select all

Score search(alpha, beta) {
	check TT for a result that can be used directly(); //normal lookup

	check TT for a "suggestion"(); //same as normal lookup, except we want the result even if depth is not sufficient

	if ("suggestion" is a value between alpha and beta) {
		do an aspiration search around "suggestion"();
	} else if ("suggestion" > beta) {
		do a null window search to verify();
		if (returned score < beta) {
			research with original window();
		}
	} else if ("suggestion" < alpha) {
		do a null window search to verify();
		if (returned score > alpha) {
			research with original window();
		}
	}

	//...
}

[cyberfish]

Ah I see. Thanks for the explanation.