Alpha-beta is too sequential no body wants to try itpetero2 wrote:Thanks for the link, interesting approach. However, in the paper they used this idea to to implement a distributed IDA* search algorithm. It is not obvious to me how to generalize this to alpha-beta search where you also have to deal with alpha bound updates, cut-offs and propagation of search results to the parent node. The paper just says this is the subject of ongoing research.Daniel Shawul wrote:Not really but I don't expect the 'standard' YBW work stealing procedure will work well. I think a transposition table work driven work scheduling (http://citeseerx.ist.psu.edu/viewdoc/do ... 1&type=pdf) where work is migrated to the processor that has the TT entry is an interesting approach.petero2 wrote:Do you know of any papers describing a tree search algorithm that would scale reasonably well to a huge number of processors in a cluster, such as the IBM Sequoia with 1.5 million cores?
. Some one did try it for two player zero-sum game, however, using MTD(f). http://citeseerx.ist.psu.edu/viewdoc/su ... 1.132.8604I like the TTD approach only because it is radically different from the way we often think of distributing work in parallel search -- which is probably what is needed for a breakthough in massive parallelism of alpha-beta. There is also APHID which is promising (second link Evgeny's post). This is alpha-beta turned into a sort of monte-carlo tree searcher, where we do iterative-deepening on the leaves to get evaluation score and the upper part of the tree is stored in memory. APHID is dynamic in that the shape of the the tree that is stored in memory changes over time (some moves get pruned as more iterations are conducted and evaluation decides the branch is worthless). This is basically an enhancement over the static 'UDABS' approach where f.i you do separate iterative deepening on each of the root moves.
Daniel