Author: Robert Hyatt
Date: 08:33:08 08/21/03
Go up one level in this thread
On August 20, 2003 at 20:00:12, Christophe Theron wrote: >On August 20, 2003 at 14:30:47, Robert Hyatt wrote: > >>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? >>> >>>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. >>> >>>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... >>> >>> >>> >>> Christophe >> >> >>I just checked. I think my previous 168 was wrong. I think a complete >>"structure" would now contain about 256 bytes which would have to be copied >>for each copy/make cycle. >> >>In Cray Blitz, without the bitmap stuff, we did a combination. We didn't copy >>the chess board, we did make/unmake there. But we did copy things like hash >>signatures and incrementally updated stuff (number of pawns on a file, open >>files, etc) so that we didn't have to unmake those. > > > >Yes that's exactly what I do. The structure I'm talking about contains exactly >that: hash key, incremental score, the last computed part of the dynamical >score, king safety information, pawn structure information, last move, last >captured piece, ... > >But I understand that if you have a bigger structure that saves various >bitboards at some point saving/restoring might be too costly because of memory >wait states. > >That's a part I do not like much: when the hidden (internal) architecture of the >machine starts to have such a variable impact on the program's design. I mean >from one computer to another, and depending on the processor/memory/mainboard >manufacturer, one should completely redesign the program to get the best >performances. > >I don't like the idea that someone just counting clock cycles could improve more >a chess program than someone thinking about the chess algorithms themselves. > >As a matter of facts I had to do cycle-counting myself in Chess Tiger, and I >hate that. > > > > Christophe I hadn't thought about the timing until I saw Bo's comment. But think about this. I search about 2.4M nodes per second on my dual xeon. That is about 400ns per node. For each node, I have to make a move and then go to the next ply to see if there is anything to do there. That includes one of those "copy" operations. Copying 256 bytes every 400ns is a killer, obviously. The PC is going to have a hard time maintaining that, in addition to fetching normal instructions and data.
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.