Author: Robert Hyatt
Date: 06:28:15 02/04/99
Go up one level in this thread
On February 04, 1999 at 00:34:51, Don Dailey wrote: >On February 04, 1999 at 00:27:46, Robert Hyatt wrote: > >>On February 03, 1999 at 23:23:39, Don Dailey wrote: >> >>>On February 01, 1999 at 10:17:40, Robert Hyatt wrote: >>> >>>>On February 01, 1999 at 00:51:40, Don Dailey wrote: >>>> >>>>>>>Testing the move is like adding 2 or 3 bits (I'm guessing, but it's >>>>>>>some small number of bits) to the hash key. It's a really good way >>>>>>>to measure false matches in the hash table. If you can spare about 3 >>>>>>>bits or so, you can pick up the majority of conflicts in the hash table. >>>>>>>With 3 bits, you will identify a false match almost 90% of the time. >>>>>>>It's a neat trick and testing the move is pretty much the same >>>>>>>idea, except you get the bits for free since you store the move >>>>>>>anyway. But it turns out that I don't test the move, I generate >>>>>>>all the moves and push this one to the front if I run across it, >>>>>>>similar to how one might do the killers. I could trivially do >>>>>>>your test though and probably should. Technically, I should probably >>>>>>>try the hash move before doing any work but I never found this to be >>>>>>>worth anything for me. Is this what you do? I think it's because >>>>>>>there is rarely a hash move near enough to the end nodes to do you >>>>>>>much good. >>>>>>> >>>>>> >>>>>> >>>>>>I _must_ validate the move... because I search this move before generating >>>>>>moves. And if it isn't valid, my program 'blows up'. Because making a bad >>>>>>move will corrupt the board, and I make/unmake which means I might _really_ >>>>>>corrupt it on the unmake (ie if I try O-O where it isn't legal, the board is >>>>>>_gone_ because the MakeMove() gives me a new king and rook, and the UnMake >>>>>>won't fix it... >>>>> >>>>>My program will also crash and burn if an illegal move is attempted. >>>>>But I will never make an illegal move, even if it is in the hash >>>>>table. Essentially, the validation process is to sort it to the >>>>>top IF it is already in the list. Since you try the move first >>>>>of course you have to validate it. But do you find that this >>>>>speeds things up in a measurable way? I don't do this because >>>>>I never noticed a speedup. >>>> >>>>if you don't get a speedup, your 'hash-move' stuff sounds like it isn't >>>>working. Because shouldn't that move cause an instant fail-high in a >>>>reasonable percentage of the cases? And in those cases, I do _no_ move >>>>generation at all, and save that time. >>>> >>>>I haven't tried measuring this in Crafty, but in Cray Blitz, we didn't >>>>generate any moves in about 1/3 of the positions we searched, normally, >>>>although in endgames this went _way_ up... >>> >>>My hash-move stuff works fine. I have done a lot of tests on this and >>>about half of the benefit in the middle game is due to keeping the >>>best move and trying it first. I am astounded that you only have to >>>generate moves 2/3 of the time. This means you are getting a hit >>>a lot more than 2/3 of the time. I will do some measurements and >>>see what percentage of the time I actually get a cutoff from a hash >>>move. >>> >>>- Don >> >>I typically get decent hit rates, when hit == signature match, rather than >>getting a useful score/bound. With a 40% hit rate, if 30% cause cutoffs, then >>that is the 1/3 I mentioned. Notice that at fail low nodes there is _no_ best >>move stored, so this doesn't help at all... >> >>and since I started generating moves in two passes (captures by themselves >>and then (later) the non-captures) this probably doesn't help as much as it >>did in CB where we generated all moves at once because it was easier/faster >>due to the vectorized move generator... >> >>But I'm more interested in why/how you can get away with allowing a hash entry >>to be stored in 'chunks' but non-atomically. Because that killed us even on the >>early 2 cpu XMP. And on my quad xeon I can turn it off and produce a continual >>barrage of 'bad move from hash table' messages... > >I'll try to do the test tomorrow. The test will be to count the number >of hash table moves that do not correspond to a legal move right? I'll >try it on one of the 4 processor alphas and if I get time I'll see if it >changes on one of the 8 processor suns. > >- Don That's about all I know how to test. It culls about 1/2 the problems, however, because on 'fail low' nodes you don't have a best move, but you can get two cpus to access the same position at the same time, one storing, one loading, and the 'loader' can get something bogus. And it will go undetected. Another test might be to store the hash signature, the score/draft, followed by the true board position (*big* hash entry). Then check the signature, grab the score/ etc, then check the 'position' to see if it still matches... and even that has a race condition that will miss errors...
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.