Author: Rafael Andrist
Date: 02:39:58 12/30/01
Go up one level in this thread
On December 29, 2001 at 11:40:30, Christophe Theron wrote: >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. I'm not familiar with MTD(f), but it should not cause several re-searches like MTF(f) seems to do. Since I'm still using Alpha-Beta with infinite starting window, it would probably give some speedup. With PVS you may gain nothing - I don't know. >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). The main goal is to avoid too long and unnecessary qsearches which may kill the program performance. >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 After rewriting my movegen, I'll try it out. regards Rafael B. Andrist
This page took 0 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.