Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: The need to unmake move

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.