Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: The need to unmake move

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.