Author: Johan de Koning
Date: 23:29:48 08/20/03
Go up one level in this thread
On August 20, 2003 at 13:05:17, Christophe Theron 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. >> >>Copying a struct does take time, and it can easily be pinpointed. Saving and >>restoring and unupdating also takes time, but is harder to identify. Especially >>since the stress on code cache and branch prediction don't show up in a run time >>profile. >> >>... Johan > > > >I'm not surprised by Bob results on this issue, as Crafty has a *lot* of things >to save/restore, and all of them are rather big structures. > >In a non-bitboard program like Chess Tiger, saving/restoring is probably faster. >At least it is in Chess Tiger. > >I do not know if you are using bitboards in The King. Do you? I don't use bitboards-as-we-know-them. I do use 'bitfiles' in the Pawn stuff (as in uchar MapWP[1 + 8 + 1]), but I don't think that counts. >Actually I'm using a mix of undo and restore: I do not save the chessboard >itself because undoing a move involves very few read/write operations. So I undo >the move "manually" on the chessboard but restore with a memcpy a single >structure that holds the rest of the chessboard and a part of the search state. >I seem to remember that this structure is less than 40 bytes big, so restoring >it is really no problem, and as you pointed out most of the time the data to be >restored still lies in the L1 cache. The disadvantage of a mixed approach is that either the data is in several places, or you have to restore the data to it's home (unmake() still required!). Personally I like to have "everything" under 1 pointer. I guess my days on the ARM processor still show. :-) >In any case I cannot imagine that restoring the hash key for the current >position from memory could be slower than computing it again by undoing a >sequence of XORs (at least 2) on a 64 bits integer... Change / size ratio is the first order criterium. Change involves code, possibly with branches, and lookups. Copy goes with raw L1 cache speed. So I'd say that *roughly* anything with C/S > 0.1 is faster by copying. The hash key (or better Zobrist key :-) has a C/S of 1. ... 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.