aspiration search based on TT hits of lower plies?

[cyberfish]

So far, I have only seen aspiration search at the root node. I assumed it is because it is only possible at the root node since a previous score is available from iterative deepening. However, has anyone tried doing an aspiration search at a non-root node using scores from the transposition table for a shallower depth? (which would otherwise be ignored)

For instance, if the engine needs to search a position to depth 7, but the transposition table only has a score for this position at depth 5, is it possible to run an aspiration search based on that score (@ depth 5)?

Thanks!

[cyberfish]

actually, to generalize it further, if the TT suggests a fail-high (out of the ab window), the engine can then search with a null window first. Likewise for a fail-low.

[Tord Romstad]

So far, I have only seen aspiration search at the root node. I assumed it is because it is only possible at the root node since a previous score is available from iterative deepening. However, has anyone tried doing an aspiration search at a non-root node using scores from the transposition table for a shallower depth?

I've been thinking about it a few times, but never actually tried it. I always thought I should make aspiration windows work at the root first, but I never succeeded.

PV nodes are a lot like root nodes, so it definitely makes sense to do similar things in both types of nodes. Using the same move ordering techniques at PV nodes as in the root is also worth trying. It is also possible to use fail highs and fail lows at internal PV nodes for time managment decisions, in basically the same way most programs do it at the root (I already do this, but so far only to a very limited extent).

Tord

[cyberfish]

Thanks!
I already have it working at root. Just wondering if I can apply it to other nodes as well.

[Harald Johnsen]

actually, to generalize it further, if the TT suggests a fail-high (out of the ab window), the engine can then search with a null window first. Likewise for a fail-low.

What you want to do is a real search with a null window. Look the web or the archive for PVS (principal variation search).

In PVS you do a full window (or aspiration window) search to find your pv.
Than you do a null window search with the remaining move, just to verify that they are useless (val <= alpha).
If you are unlucky (val > alpha) one of this useless variation becomes your new principal variation. This is where you need to do a re-search to get the real score and the real pv.

HJ.

BTW you should rewrite your search code à la negamax ; in your minimax code you need to duplicate all your code with inegality reverted, I predict a lot of bugs there.

[cyberfish]

thanks
I am already doing PVS. What I am suggesting is that, perhaps we can use the transposition table to get a better guess? (for instance on a PV node)

In a sense, I am trying to improve PVS using the TT (since non-PV nodes would most likely have fail-low scores in the TT anyways (from a shallower depth), so in what I suggested, it would be searched with a null window anyways). In other words, instead of guessing that every move after the first or two will fail-low, rely on the TT to suggest fail-lows.

TT can also suggest fail-highs, meaning the current node will be searched with a null window first. (I am not sure how this relates to PVS, but I have a feeling that they are related)

BTW you should rewrite your search code à la negamax ; in your minimax code you need to duplicate all your code with inegality reverted, I predict a lot of bugs there

done that a while ago.

[Dann Corbit]

Thanks!
I already have it working at root. Just wondering if I can apply it to other nodes as well.

It certainly would not hurt to try it. It sounds like a very good idea to me. It's really how we play as humans too, I think. We give more concentration to the parts of the good plan that we are forming than to alternatives, unless an alternative suddenly becomes a better plan.

[bob]

So far, I have only seen aspiration search at the root node. I assumed it is because it is only possible at the root node since a previous score is available from iterative deepening. However, has anyone tried doing an aspiration search at a non-root node using scores from the transposition table for a shallower depth? (which would otherwise be ignored)

For instance, if the engine needs to search a position to depth 7, but the transposition table only has a score for this position at depth 5, is it possible to run an aspiration search based on that score (@ depth 5)?

Thanks!

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...

[cyberfish]

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.

[bob]

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.

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...