Author: Vincent Diepeveen
Date: 08:04:24 04/19/01
Go up one level in this thread
On April 18, 2001 at 23:31:06, Robert Hyatt wrote: >On April 18, 2001 at 08:38:09, Jeremiah Penery wrote: > >>On April 18, 2001 at 05:37:49, Vincent Diepeveen wrote: >> >>>Also i'm splitting hardly near the leaves where all recursive programs >>>keep on splitting near the leaves. That's the b.f. difference! >> >>Is this implying that Diep is using an iterated rather than a recursive search? >>I find that pretty interesting. :) I guess there would be good points for it, >>especially with parallelism, but it is harder to implement than a recursive >>search... > > >The Cray Blitz algorithm is easier to implement with an iterated search, but >it is not essential to make it work. The problem is that we want to look at >_all_ nodes in the current tree, and pick the best place to split. This can >be done pretty easily in an iterated search. But it can be done with a >recursive search. I've just never wanted to introduce the extra complexity >into crafty (yet). But it is definitely doable since even though I am at >ply 18 in the current tree, I can still set things up and start a process >to helping me at ply=4 if I want to... Exactly, it is way easier as i can do with my search whenever i want it to. It works very nice when it works. There is a lot of work involved to get it neatly to work. For DIEP it took from begin 98 to mid 98 before it really worked well and didn't slow me down instead of speed me up (single cpu of course). Not so easy to implement is for example doing a small search first in order to get a PV move (sorry forgot the term something like internal iterative deepening?). The locking of such a linked-list datastructure in parallel search is quite complex, but the advantages are obvious. Let's not forget to mention another advantage that a processor can abort itself when it has searched an entire move list and another processor is still busy searching a position. That is requiring no overhead for me where in parallel search it is mere to unsolvable without big overheads. Of course the chosen plan by Bob is very smart to let the idling processor 'help' the other processor. The disadvantage here is that this increases the number of splits near the leafs. The average splitdepth for diep is very near to the root. Note i do not allow to split in the root. Usually more or less automatically it splits very quick at the second move. Anyway in iterated searching splitting is very cheap anyway.
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.