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.