Author: Vasik Rajlich
Date: 15:08:15 06/19/05
Go up one level in this thread
On June 19, 2005 at 15:36:47, Vincent Diepeveen wrote: >On June 18, 2005 at 14:19:00, Vasik Rajlich wrote: > >>On June 18, 2005 at 11:09:51, Vincent Diepeveen wrote: >> >>>On June 18, 2005 at 06:09:10, Vasik Rajlich wrote: >>> >>>>On June 18, 2005 at 00:37:52, Ricardo Gibert wrote: >>>> >>>>>On June 17, 2005 at 20:39:58, Ricardo Gibert wrote: >>>>> >>>>>>On June 17, 2005 at 18:56:08, Vincent Diepeveen wrote: >>>>>> >>>>>>>On June 16, 2005 at 18:42:44, Vasik Rajlich wrote: >>>>>>> >>>>>>>>On June 16, 2005 at 13:31:39, Vincent Diepeveen wrote: >>>>>>>> >>>>>>>>>On June 16, 2005 at 05:22:26, Vasik Rajlich wrote: >>>>>>>>> >>>>>>>>>>On June 15, 2005 at 22:40:22, Tor Alexander Lattimore wrote: >>>>>>>>>> >>>>>>>>>>>Hi >>>>>>>>>>>Is it possible to use a single variable in the MTD(f) search? Something like >>>>>>>>>>>this: >>>>>>>>>>> >>>>>>>>>>>int MTD(int depth, int guess) >>>>>>>>>>>{ >>>>>>>>>>> if (depth<1) return Evaluate(); >>>>>>>>>>> MOVE move_to_search; >>>>>>>>>>> int best=-INFINITY; >>>>>>>>>>> GenMoves(); >>>>>>>>>>> while (GetNextMove(&move_to_search)) >>>>>>>>>>> { >>>>>>>>>>> PlayMove(move_to_search); >>>>>>>>>>> val = -MTD(depth - 1, -guess + 1); >>>>>>>>>>> UnPlayMove(move_to_search); >>>>>>>>>>> if (val>best) >>>>>>>>>>> { >>>>>>>>>>> best=val; >>>>>>>>>>> if (val>=guess) >>>>>>>>>> >>>>>>>>>>You missed a line here. Fail-hard is "return guess", fail-soft is "return val". >>>>>>>>>> >>>>>>>>>>Fail soft helps when you need to re-search, so it helps more in MTD (f) than >>>>>>>>>>PVS, and doesn't matter at all in pure alpha-beta. >>>>>>>>> ^^^^^^^ >>>>>>>>>I guess you meant a small typo here. doesn't ==> does >>>>>>>>> >>>>>>>> >>>>>>>>Actually I just forgot about hash effects at the next iteration. Without those, >>>>>>>>the statement would be true .. (as far as I can see) >>>>>>> >>>>>>>The hashtable is the thing that is refuting so so many algorithms... ...one of >>>>>>>them is for example no-progress pruning. With a hashtable it is an incorrect way >>>>>>>to search. >>>>>> >>>>>> >>>>>>I've "reverse engineered" the no progress pruning algorithm and it does not >>>>>>depend on the transposition table. Unless I've somehow reverse engineered it >>>>>>"improperly," the idea appears to be 100% sound to me. >>>>> >>>>>I've thought it over and I think understand what it is you're getting at now. >>>>>Interesting. >>>>> >>>>>Thanks for making me think! >>>>> >>>> >>>>Yes, but it's nothing unusual. One extreme is to do like Uri and not even use >>>>the hash table for transpositions. Most people just live with these things. >>>> >>>>Note BTW that "no progress pruning" should be "no progress reduction" - as >>>>always. So these problems won't kill you, they'll just give you some >>>>non-theoretical values. >>>> >>>>Vas >>> >>>If your definition of "won't kill you" means that the computer won't pick up a >>>rifle and fire you dead litterary, then you might be correct. >>> >>>However if "won't kill you" refers to: "it will not back up very poor moves to >>>the root", then that's not true. >>> >>>When i refer to 'incorrect' way to search i do not mean that the last few plies >>>of the search you *might* get an error sometimes. It refers to that incorrect >>>scores get backed up to the root regurarly and regurarly lose games for you. >>> >>>Of course such effects are measurable only when software plays strong and when >>>you do accurately test say a 1000 games at tournament level against a variaty of >>>opponents and then compare the 2 runs of 500 games with each other. >>> >>>Such tests only commercials are doing. Not a single amateur is. >>> >> >>I would be really surprised if there was some pruning or search control which >>would fail only because of interactions with HT. >> >>Let's imagine that without any hash table, some "no progress reduction" works, >>ie. program plays stronger. If this is true, then the chance is 98% that no >>progress reduction also works (ie. makes the program play stronger) when you do >>use a hash table. > >I would expect Uri Blass write such a posting and am rather amazed you did it >here. > >You are obviously going to store thanks to no progress pruning in your hashtable >nodes as a fail high whereas in reality it is a fail low and vice versa. You can >simulate this behaviour very easily in your program. > Search is full of not-correct stuff. If you don't like it, you won't use HT, null move, aspiration windows, etc .. The question is, how often are you going to come to a position where no progress has been made the last few moves, then later come to that same position in a different path where progress was made, and the extra few plies of search would have flipped your score. Vas >Just give randomly a cutoff from hashtable, before checking the hashtable. > >After you tested that at Crafty or something, please let me know how many rating >points it has become stronger or weaker and after you were kicked a 1000 times >please tell me whether you conclude it still is a correct form of search. > >Vincent > >>Vas >> >>>> >>>>>> >>>>>> >>>>>>> >>>>>>>>Vas >>>>>>>> >>>>>>>>>> >>>>>>>>>>Vas >>>>>>>>>> >>>>>>>>>>> } >>>>>>>>>>> } >>>>>>>>>>> return (best); >>>>>>>>>>>} >>>>>>>>>>> >>>>>>>>>>>perhaps there is something very wrong with this? or perhaps it's used already, I >>>>>>>>>>>just noticed that on Aske Plaat's site he always uses an Alpha-Beta search with >>>>>>>>>>>0 width windowed searches, but doesn't this do the same thing? Is using >>>>>>>>>>>fail-soft type algorithms used in MTD(f) since it could well help zoom into the >>>>>>>>>>>correct score sooner? >>>>>>>>>>> >>>>>>>>>>>Cheers >>>>>>>>>>>Tor
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.