Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Storing the PV in a search routine

Author: Bruce Moreland

Date: 10:59:09 06/10/98

Go up one level in this thread



On June 09, 1998 at 17:04:05, Scott Gasch wrote:

>Thanks a lot, your description was excellent, I've implemented it and it
>works.

I'm glad you could understand it.

I got the technique from Levy's "How Computers Play Chess".  It's the
only place I know where this is written up.

Another thing is that if you fail high at depth zero, you can stick the
move you failed high on in the array, and then just terminate it at
length 1, so you will have return a PV of sorts if you are in a
fail-high state.

Remember also that your array length can be undefined if you fail low.

I actually spend some energy trying to make sure that what's in the
array is something reasonable.

If I fail high on the move that had been the PV up until now, I don't
kill the old PV, I let it sit in there, so I can be sure to search it
first when I re-search.

Also, if I fail low, I keep the old PV around, since it's the best thing
I have.

If I fail high on a new move, then fail low on the re-search, I put the
PV from before the fail high back, but this is a serious decision and
some would argue that this is wrong, and this doesn't pertain directly
to this topic anyway.

>As a followup, you say that the memcpy won't hurt performance much but
>I'm not
>so sure of that... in your experience, is it better to use a 2D array
>for the
>PV or linked lists?  With the prior you have the issue of memcpys
>whereas with
>the latter you have the overhead of a memcpy per ply but can then link
>the
>ply-1 list to the ply list very easily.  Of course then you have to deal
>with
>free calls...

I made a single array, which is sized at max depth squared, plus max
depth, all over two (   (D^2+D)/2   ).

I made an another array of pointers into this array, there are max depth
pointers.

I then initialized the pointers so that the first one points at element
0, the second one points at element D, the third points at element 2D-1,
the fourth points at element 3D-2, etc.

The point is that each of these arrays needs one less element, because
the maximum length of the PV is shorter the deeper you already are.
Levy calls this a triangular array, which seems reasonable to me.

I was being anal about memory at the time.  If you want, you can just
make an array that is D^2 and forget about it, it's not like we have to
worry about blowing RAM much these days, except with hash tables.

If you want to know about how much the memcpy costs, you can check it
yourself, by counting them.  Increment a counter every time you do it,
and display this sometimes, I bet the counter stays pretty small, it did
when I did this.

The memcpy should in-line alright, but any extra code in your search
routine could slow things down by merely existing.

So another thing to try involves running a speed test with this PV code
in, and another one with it commented out.

The use of a memcpy in the search routine should rightly scare you, but
there are some parts of even super-crucial routines like this that
rarely get executed, so you can do more expensive stuff in these parts
and not get too badly burned, as long as you don't add so much code that
the optimizer gets confused or you start screwing up the processor's
cache.

bruce



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.