Author: Robert Hyatt
Date: 07:42:30 02/04/01
Go up one level in this thread
On February 04, 2001 at 07:28:38, Tony Werten wrote: >On February 03, 2001 at 22:45:07, Robert Hyatt wrote: > >>On February 03, 2001 at 20:43:13, Tony Werten wrote: >> >>>On February 03, 2001 at 18:33:28, Robert Hyatt wrote: >>> >>>>On February 03, 2001 at 05:53:20, Tony Werten wrote: >>>> >>>>>On February 02, 2001 at 21:33:10, Robert Hyatt wrote: >>>>> >>>>>>On February 02, 2001 at 14:42:23, Alvaro Jose Povoa Cardoso wrote: >>>>>> >>>>>>>On February 01, 2001 at 18:37:48, Robert Hyatt wrote: >>>>>>> >>>>>>>>On February 01, 2001 at 16:27:29, Tony Werten wrote: >>>>>>>> >>>>>>>>>On February 01, 2001 at 14:19:25, Alvaro Jose Povoa Cardoso wrote: >>>>>>>>> >>>>>>>>>>Does any one tried to use just Upperbounds and Lowerbounds in hashing, ignoring >>>>>>>>>>ExactScore entries? >>>>>>>>>>My question has to do with the fact that if we use ExactScores we don´t get long >>>>>>>>>>PVs to feed in the next iteration, even if we extend PVs from hash. >>>>>>>>>>My testing shows that if we do not use ExactScore entries in the hash table, we >>>>>>>>>>end up with very long PVs that can be fed into the next iteration in order to >>>>>>>>>>aproximate the minimal tree. After all, ExactScores are rare compared to >>>>>>>>>>Upperbounds and Lowerbounds. >>>>>>>>>> >>>>>>>>>>Can someone comment on this? >>>>>>>>> >>>>>>>>>One of us is missing something. The PV is always exact. If you don't store >>>>>>>>>exact, you don't have a pv. I don't know what you get from the hashtable, but it >>>>>>>>>isn't a PV. >>>>>>>>> >>>>>>>>>I take my PV from hashtable and I (almost) always get a long pv, at least as >>>>>>>>>long as the search depth. >>>>>>>>> >>>>>>>>>Tony >>>>>>>>> >>>>>>>>>> >>>>>>>>>>Thank you >>>>>>>>>>Alvaro Cardoso >>>>>>>> >>>>>>>> >>>>>>>>He is talking (I think) about a PV that is cut short when you get an EXACT >>>>>>>>hash hit. IE in crafty, where a PV ends with <HT> which sometimes happens >>>>>>>>at ply=2/3/4 and results in a very short PV. I use internal iterative deepening >>>>>>>>to help search around this the next iteration, however.. >>>>>>> >>>>>>> >>>>>>>That is exactly what I was talking about. When I get an EXACT hash hit the PV is >>>>>>>cut short, and extending it from the hash table doesn't help much, I just get >>>>>>>1-3 moves from the hash, perhaps there is something wrong with my program. >>>>>>>Also, and in response to Dr. Robert Hyatt, I can´t execute the assignment >>>>>>>because my program is the portuguese version of checkers. I hope you don't mind >>>>>>>if I ask questions not related to the game of chess. >>>>>>> >>>>>>>Thank you >>>>>>>Alvaro Cardoso >>>>>> >>>>>>That is a perfectly normal problem. My PV is often shorter than it should >>>>>>be due to an EXACT hash hit. Nothing you can do about it, not that there >>>>>>is anything wrong with it. >>>>> >>>>>I still don't get how you can have a short pv if you have a exact hashhit. >>>>> >>>>>Maybe run a test where you add in your pv, the bounds it got. My guess is you're >>>>>last move is a BELOW_ALFA hit. ( That was a problem I had before ) >>>>>It was caused because I raised alfa after nullmove, sometimes making it the best >>>>>score and having a bogus best_move which couldn't be found in hashtable. >>>>> >>>>>cheers, >>>>> >>>>>Tony >>>> >>>>It happens all the time. You get an EXACT hash hit while searching the PV, >>>>so you stop and use that score instantly. How can you fill in the _rest_ of >>>>the PV moves since you didn't search any deeper. I see this so often that I >>>>eventually added the <HT> indicator to the PV to let everyone know it really >>>>should be longer but was cut short by an EXACT hash hit. >>>> >>>>If you never get a short PV, you have something broken somewhere.. >>> >>>But if you get a <HT> you must have searched it the previous ply, so it's still >>>in your tables ? Or you've searched it this ply and you should not have >>>overwritten it. ( or you have something broken somewhere .. ) >>> >>>Tony >>> >>>PS very strange strange that if you don't get an error you must have something >>>broken. >> >> >>No, because this is _not_ an error. It is a well-known occurrence when you >>hash. >> >>The <HT> can come from any of the following: >> >>1. deep ponder search where the opponent made a different move than you >>expected. IE You were expecting him to play Nc3 and your PV was e5 Re1. >>But instead, he played Re1. After you search e5 and Nc3, you get the same >>position exactly and search no deeper. > >This is exactly the point I don't get. I understand that your PV array is short >at this point. But the 2 ply search should have left this position in the >hashtable ( altough it was supposed to be reached in a different way ) and you >can build the PV from it. Here is how it happens. We are playing a game where we each are averaging about 3 minutes per move. I am expecting you to play Ke6 and my search produces the following PV for a 3 minute search: 43. Ke4 c5 44. Kf4 Ke7 45. Kf5 Kf7 46. e6+ Ke7 47. Ke5 Kd8 48. Kd6 a3 49. bxa3 a4 <more stuff deleted here> However, instead of playing Ke6, after 3 minutes you play c5. When I start searching, I will find that after I play Ke4 and you play Ke6, I have reached the _identical_ position I had already searched during a ponder. That is the position after Ke6 Ke4 c5 is exactly the same as the position after c5 Ke4 Ke6. My PV will look like this: Ke4 Ke6 <HT> Nothing anybody can do about that as that is _exactly_ what we want the hash table to do... > >BTW This cutting short of the pv-array is the reason why I build the pv from >hahtable. It does have a bad side effect. If your opponent plays a different >move, you start search, come to 10 ply immediately and die in ply 11 because you >basicly start an 11 ply search without any knowledge. ( This might be the place >where internal iterative deepening could rescue it ) It will help. When I finish an iteration and discover the <HT> PV, I do go probe the hash table to try to extend the PV. But it often doesn't get the _full_ PV as something was overwritten. If you are getting the PV from the hash table, no wonder you never have a full N ply PV from an N ply search. How could you possible avoid overwriting at least one of those entries? > >Tony > >> >>2. Same as (1) but from the current search. It is possible to reach >>position X in more than one way, and one of those ways could have extended >>the tree deeper than the one you are on now, which will give you a <HT> >>score that is exact. >> >>3. Something left over from an old search. >> >>4. something from position learning if you have that. >> >>If you don't get an EXACT hit on your PV from time to time, as I said before, >>something is wrong. Because _anytime_ you get an EXACT hit, you don't search >>any deeper. How do you fill in the PV below that point? >> >> >> >> >>> >>>> >>>> >>>> >>>>> >>>>>> >>>>>>And you can _still_ turn in your assignment on time. Checkers is perfectly fine >>>>>>to test your hypothesis. :)
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.