Author: Brian McKinley
Date: 14:52:17 08/07/99
Go up one level in this thread
On August 07, 1999 at 08:39:44, Vincent Diepeveen wrote: >On August 06, 1999 at 13:47:35, Brian McKinley wrote: > >>I am implementing a parallel search, and I have 2 questions for those who have >>gone before me. >> >>1. If my parent thread has searched all moves at a ply and a child thread is >>still searching, should the parent thread wait for the child thread to return, >>or should it abort the search in the child thread and re-search the move from >>the parent? This would allow the child thread to be placed back in the pool so >>that both threads are working again. I am assuming that the re-search would be >>fast to the point where there child was stopped. > >My program is not using recursion, but iteration. >Therefore there is no thing such as parent/child relation. > >Assume i have 2 processors (which is the maximum i allow at a single >position and that works great for machines with say 4 processors) >at a position X. Assume P0 is ready while P1 is still busy, >then P0 aborts itselve, writes in datastructure some things, >and goes looking for a new job. > >I can do this because DIEP is not using recursion for it's search. >I consider this a major speedup for a program that's parallel, as >the only alternatives are: > - writing something cruel where processor P1 is part of too and > P0 is gonna unmake a bunch of iterations first and P1 is gonna make > all iterations. > - easiest solution: just let P0 idle till P1 finishes > - let P0 split within the search tree of P1, so that it > kind of helps it (see msg from Bob about this) > >I consider all alternatives poor, speedupwise. > >>2. If a score comes back that is greater than alpha and less than beta and there >>is a child thread searching another move for this ply, should I update beta in >>the child thread? Am I correct in assuming that this is not an issue for MTDf? > >It's not an issue for MTD indeed. >updating alpha to the other process isn't very smart, because that >messes up a lot of alfa and beta values and best moves. > >After some testing i found it not necessary to handle this. > >I just search on. Chance is too small that the improvement of >alpha is major as we would otherwise get a cutoff. > >So in fact i waste some nodes on this phenomena, but with a resolution >of 1/1000 pawn it's not really a big concern. of course the next >move that i get in that position i use the correct alfa and beta values >already. > >The intuitive thing to do here is to abort search for the processors >that are searching with the wrong alfa and beta values and research with >correct alfa and beta values. This means however a research of search space >already searched, and i consider that a waste of nodes actually! > >Greetings, >Vincent > >>-- Brian McKinley
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.