Author: Vincent Diepeveen
Date: 12:26:33 12/27/99
Go up one level in this thread
On December 27, 1999 at 12:14:11, Robert Hyatt wrote: >On December 27, 1999 at 10:45:18, Vincent Diepeveen wrote: > >>On December 27, 1999 at 00:07:47, William Bryant wrote: >> >>>If your search fails low on the root PV move. >>>(IE. the full alpha beta window for the PV move returns a score <= alpha >>>and nothing is backed up into the PV array). >>> >>>Do you? >>> >>>1) Stop PVS and search the rest of the root moves for this iteration with a >>> full alpha beta window? >>> >>>2) Stop PVS until at least one move for this iteration falls into the alpha >>> beta window. If no moves fall into the window, research the whole >>> iteration with a lower window. (fail low). This means that you may end up >>> searching every move with a full alpha beta window which would take more >>> time before the fail low occurs. >>> >>>3) Stop now and lower the window and research with PVS. >>> >>>4) Do Nothing? >>> Continue the rest of the root moves within the -alpha-1, -alpha PVS window. >>> Only search moves outside the PVS window for the rest of this iteration >>> if they return a score > alpha on the PVS search. Hope that if the >>> every root move is going to fail low, that this will speed up the >>> search until the window is lower. >>> >>>5) Suggest something better. >> >>I'm not having this problem too much in DIEP. >>I'm searching using PVS, so i start with -infinite, infinite window. >>I don't have any problems with PV arrays, as i simply don't have >>a PV array. I only have 1 variable called: bestmove. >>The rest of the PV i get out of hashtable. >> >>How pvs works: >> search: >> alfabeta(-inf,inf); >> > > > >For me, adding aspiration search here helps significantly. IE start off >with alfabeta(last-X, last+X); >That (for me) reduces the size of the tree by 10% in the average case, >much more in wild tactical positions. IE a position where there are >zillions of mates, but none are forced. with -inf,+inf, you have to follow >all those mates to their conclusion. With last-X, last+X, you don't... Yes in my draughtsprogram Napoleon i am using aspiration search. For diep however it doesn't matter that much. Remember that diep uses very little nodes to search a tree at ply=n, even if i compare it to other programs which apply forward pruning. It's simply always researching the previous tree. It directly has quite good alfa and beta values. It's always busy researching that tree. The mainreason i didn't keep it in was because in positions that are tough for you (so positions where you must fight) and where score gets each ply lower, then suddenly higher. In those positions you're only busy researching without getting too soon to the next ply. If score is <= last-X you NEED to research. You can't skip to next ply. You need to research right after the first move fails low. Now if i search in DIEP with last-X as alpha then it has the bad tedency to return everywhere last-X and put that massively in hashtables. So a research is very expensive as it all need to be recomputed with new bounds. In some positions aspirationwindow in the root sure speeds up. Especially in positions where a certain move looks the best it works incredibly well. If you fail high, you just don't research and skip to the next ply. How exactly Frans is doing it i don't know this skipping. It seems to work great in his progs. But when i tried it, it worked great indeed for testsets where there is always at a certain point a move gonna fail high. Now all testsets have basically only 'bestmoves', so i feel majority here is loving this form of search here in advance... On the other hand all tough positions i had a few worstcases as described above so i kicked it. >Harry had one problem position where -inf,+inf could not ever return a good >score, yet last-X would find the solution very quickly (score was only +2 or >something). I don't doubt that there are many positions. I plan to retest my search with aspiration search again in future. For now i simply don't work at efficiency of DIEPs search (with exception of bugfixing in the parallel part). After having experimented about 2 years with all kind of different search things (especially forward pruning in all forms and sizes) which brought me nothing i have enough experimented with search this millennium. I'm kind of sick of search so to speak... ...i feel i wasted 2 years on search at least now... However the PVS idea of first move with alfa,beta then alfa,alfa+1 worked by far better for me than any other search, especially MTD and that sort of crap. >> alfabeta(int alfa,int beta,... >> >> firstmove: >> alfabeta(alfa,beta...); >> >> other moves: >> t = alfabeta(alfa,alfa+1... >> if( t > alfa && t < beta ) >> t = alfabeta(t,beta,...); >> >>>Fail low on the root move seem to bring my search to a crawl and I'm looking >>>for a way to be more efficient. >>> >>>Thanks in advance. >>> >>>William >>>wbryant@ix.netcom.com
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.