Author: Johan de Koning
Date: 22:57:36 08/24/03
Go up one level in this thread
On August 24, 2003 at 21:52:37, Robert Hyatt wrote: >On August 23, 2003 at 02:34:05, Johan de Koning wrote: > >>On August 22, 2003 at 10:45:11, Robert Hyatt wrote: >> >>>On August 22, 2003 at 02:53:06, Johan de Koning wrote: >>> >>>>On August 21, 2003 at 11:29:49, Robert Hyatt wrote: >>>> >>>>>On August 21, 2003 at 03:16:35, Johan de Koning wrote: >>>>> >>>>>>On August 20, 2003 at 14:27:57, Robert Hyatt wrote: >>>>>> >>>>>>>On August 20, 2003 at 03:59:38, Johan de Koning wrote: >>>>>>> >>>>>>>>On August 19, 2003 at 22:11:14, Robert Hyatt wrote: >>>>>>>> >>>>>>>>>On August 19, 2003 at 20:06:58, Mathieu Pagé wrote: >>>>>>>>> >>>>>>>>>>Hi, >>>>>>>>>> >>>>>>>>>>The fact: >>>>>>>>>> >>>>>>>>>>I have this question i read at some place that it is faster to unmake a move >>>>>>>>>>than to save the state of the game before moving then restoring it when we want >>>>>>>>>>to unmake the move. >>>>>>>>>> >>>>>>>>>>For the moment my engines did not implement unmake() (it is still buggy). >>>>>>>>>> >>>>>>>>>>My thougth: >>>>>>>>>> >>>>>>>>>>Since bitboard computation are slow (on 32 hardware) i think that it can be >>>>>>>>>>slower to unmake the move than to save the state. I friend of me that is lot >>>>>>>>>>better than me at optimizing code also think that. >>>>>>>>>> >>>>>>>>>>My questions: >>>>>>>>>> >>>>>>>>>>Are you all using unmake() function or there is some of you that found that >>>>>>>>>>saving the state is better ? >>>>>>>>> >>>>>>>>> >>>>>>>>> >>>>>>>>>read the comments from Crafty in main.c. I started out using what is >>>>>>>>>commonly called "copy/make" as that worked well in Cray Blitz. But it >>>>>>>>>didn't work well in the PC. The PC has very limited memory bandwidth, >>>>>>>>>when you compare the speed of memory to the speed/demands of current >>>>>>>>>processors. If you keep the board in cache, and update it there, it is >>>>>>>>>more efficient than to copy it from real memory to real memory... >>>>>>>> >>>>>>>>I hate to play Vincent here, but real memory is not an issue. >>>>>>>> >>>>>>>>If you manage to keep the deepest few plies worth of position structs in L1 >>>>>>>>cache, then bandwith is pretty decent on the PC. And it has been ever since them >>>>>>>>PCs were endowed with cache. >>>>>>> >>>>>>>Sure, but look at what happens. You copy a couple of hundred bytes. You >>>>>>>update it _once_. Then you copy it again for the next ply. And so on. Not >>>>>>>only are you not re-using what you moved around early, you are displacing good >>>>>>>stuff from the cache as well. >>>>>> >>>>>>You *are* re-using the stuff that you didn't change, by skipping the unmake() >>>>>>while backing up. And yes, you are claiming more cache space. But only the very >>>>>>few most active copies are relevant. >>>>> >>>>>Not quite. I regularly hit 50+ plies deep. By the time I back up to ply >>>>>20, that is long-gone from cache. And it gets re-loaded. >>>> >>>>And this happens quite often. >>>>Particularly if you have a branching factor of 1.01 or something. :-) >>> >>>It doesn't take much. the PIV has 512K L2 cache. 128 bytes per line, >>>which turns into 4096 lines. My bitmap stuff is about 256 bytes, or two >>>lines. 50 plies deep racks up 100 of those cache lines, a big chunk. Of >>>course there are other things that need to be in cache at the same time. >> >>I would be more concerned about L1 cache. >>Especially in 1996, when the Pentia had only 8 kB IIRC. >> >>>However, the q-search is a good case in point. It is easy to zap back and >>>forth for 20 plies with a 1.01 branching factor there... >> >>I was only joking, but if the q-search shows such kind of behavour *regularly*, >>there something fishy going on. >> >>About half of the q-nodes have no children because of rep, mate, eval>=beta, or >>all captures futile (according to a quick test, too lazy to do a decent test). >>This could still mean that most horizon nodes are childless, while some spawn >>very long narrow lines. However, I consider this most unlikely. > >Remember I _only_ do captures and pawn promotions to Q in the q-search. No >reps therefore. If you don't do any checks there should be even less deep and narrow lines. After all, that was your point: deep narrow lines have a hich cache cost per node. My point is that you're right, but is *should* happen very infrequently. > When I make a move, I _must_ go to the next ply, and see if >there are any captures. I do the copy when I do the make to get to the next >ply. It becomes expensive. When you make a move, you *must* be prepared for the next ply to return. :-) >> >>In fact, I would consider it most unwanted. As you like to say: the q-search is >>erroneous anway. Q-nodes with draft -5 and beyond will contribute very little to >>the already small accuracy at draft 0. So if they do claim a large part of the >>search, it's better to prevent them or lose them. SEE can do both. >> >>... Johan
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.