Author: Vincent Diepeveen
Date: 05:39:44 08/07/99
Go up one level in this thread
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.