Author: Christophe Theron
Date: 05:51:49 12/30/01
Go up one level in this thread
On December 30, 2001 at 05:39:58, Rafael Andrist wrote: >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. Long and unnecessary QSearches are very seldom. QSearch degenerates very quickly in 99.99% of the cases. There are extreme examples, but you will notice that they always come from artificial positions. Christophe >>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.