Author: Uri Blass
Date: 02:16:17 08/21/03
Go up one level in this thread
On August 21, 2003 at 04:52:06, Uri Blass wrote:
>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
>
>Why do you think that just counting clock cycles can help more than thinking
>about the chess algorithms?
>
>Gain from all these discussion is only linear speed improvement when the gain
>from better algorithm can be exponential.
>
>How much speed improvement do you get from all of these optimizations about
>unmake move?
>
>How much speed improvement you expect to get from cycle counting in chess tiger?
>
>I think that it is possible that I spend too much time on thinking about speed
>improvement and note that I never think about cycle counting but only about
>the algorithm.
>
>The reason is that movei is a relatively slow searcher and I hate to see my nps
>goes down so when I add more information to use in the future that make movei
>20% slower I look for way to compensate for the loss in speed by other
>optimization before
>trying to use the new information.
>
>I think that it is a mistake from practical point of view and it is better if
>I do not care now about nps but for some non rational reason I do not like to
>see the nps drop and try to look at the source code to see if there are ways to
>get the speed or part of it back(I am talking only about logical optimization
>that are clear without knowledge about cycle counting).
>
>Note that I do not like the idea of saving time by not generating information.
>The problem is that you may do your program faster but it may limit you in
>future developement because if you suddenly think about an idea to use the
>information that you decided not to generate you have a problem.
>
>Uri
As an example for a logical optimization I can give the following example
I had in my program
if a
{
...
}
if b
{
...
}
if c
{
...
}
I payed attention to the fact that b and c can never happen if a does not happen
so I cahnge it to
if a
{
...
if b
{
...
}
if c
{
...
}
}
I am interested to know how much speed programmers earn from optimizations that
are not about the algorithm but about decision like the discussion about make
unmake when it is not clear from algorithm point of view which alternative it
better or decisions to translate something to assembler.
Uri
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.