Author: Robert Hyatt
Date: 08:34:23 08/25/03
Go up one level in this thread
On August 25, 2003 at 01:57:36, Johan de Koning wrote: >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. The q-search as an unusual animal. With queens on the board, it is amazing how the two queens can infiltrate and "eat" away on the other's material, for many plies. :) 10 plies is trivial. > >> 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. :-)\ That was the point I think. There are so many copies, of an array, that (for Crafty) it was significantly faster to avoid the copy and keep the bitmaps in cache. > >>> >>>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.