Author: Christophe Theron
Date: 08:40:30 12/29/01
Go up one level in this thread
On December 28, 2001 at 07:38:24, Rafael Andrist wrote:
>On December 28, 2001 at 06:14:32, Uri Blass wrote:
>
>>On December 28, 2001 at 05:36:52, Rafael Andrist wrote:
>>
>>I understand the idea of the uncomplete flag but
>>it is not clear to me that it is a good idea.
>>
>>If you set uncomplete flag only to repeat the search later then
>>you may waste more nodes.
>
>If you hash qsearch (of course only the completed subtrees of the qsearch), it
>should not cost very much. But it heavily depends on how you implement it.
>
>example:
>inside the normal search you have a subtree with node S on its root. S has three
>successor nodes: A,B and C.
>
>if the qsearches of A and B are incomplete, but the one of C finishes causing a
>beta cutoff, time and nodes were saved
>
>unfortunately, it is very likely that if qsearch of A is incomplete, also the
>qsearches of B and C will be incomplete because S allows too long capture
>sequences. Now three things depending on implementation are possible:
>1) igore it (what you suggest)
>2) a) re-do the qsearches without limit (if you don't hash qsearch, this is
>expensive)
> b) re-do the qsearches with a wider limit (iterative deepening for qsearch,
>only recommendable when hashing q-nodes)
>3) mark S as incomplete and re-search S again if it could be relevant for the
>value of the whole tree. If you later need to do that, the infos in the hash
>about the qsearches A-C will be surely lost. Another problem is that you don't
>know which qsearches of A,B,C were incomplete.
>
>2a is easy to implement and no relevant information is lost, but the possible
>gain is also relative small. At least, this avoids the problem not seeing a mate
>in 1 because of too long qsearches.
>I don't know if 3 gains more than it loses, I would have to test it out.
I have read your suggestion quickly, so pardon me if I don't get it right, but
what you suggest reminds me of MTD(f), or using a narrowed alpha-beta window
like aspiration search.
What you call "incomplete evaluation" is the case where you do not have
evaluation(node)=E, but you just have evaluation(node)<=LowBound or
evaluation(node)>=HighBound (something that you can indeed store in the hash
table and use to save time when you do a re-search).
BUT:
1) I doubt it will work, because such systems only work when you have a good
guess for the real evaluation of the root node (in our case it is the root of
the QSearch). The static eval is not a good guess of the QSearch result, and
using a SEE to get a better guess is going to cost you too much time.
2) If it works, you are going to get a fantastic gain by applying it to the
WHOLE SEARCH, not just the QSearch. But again, I think it already exists under
the name "MTD(f)" or "aspiration search".
In any case, it seems very difficult to know if it can work without actually
trying it. I have a negative opinion about it, but who knows?
Christophe
This page took 0.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.