18
$\begingroup$

I am looking for an efficient algorithm that lets me process the minimax search tree for chess with alpha-beta pruning on a distributed architecture. The algorithms I have found (PVS, YBWC, DTS see below) are all quite old (1990 being the latest). I assume there have been many substantial advancements since then. What is the current standard in this field?

Also please point me to an idiot's explanation of DTS as I can't understand it from the research papers that I have read.

The algorithms mentioned above:

  • PVS: Principle Variation Splitting
  • YBWC: Young Brothers Wait Concept
  • DTS: Dynamic Tree Splitting

are all are discussed here.

$\endgroup$
  • $\begingroup$ Maybe this is an interesting read: chessbase.com/newsdetail.asp?newsid=8047 $\endgroup$ – Alex ten Brink Apr 5 '12 at 10:25
  • 2
    $\begingroup$ Well, this is a problem (parallelizing minimax search or any of its variants) particularly difficult. In a paper to appear this year by Richard Korf entitled "Research Challenges in Combinatorial Search", the following can be read: "[...] minimax search with alpha-beta prunning, have been notoriously difficult to parallelize" I do sincerely doubt there is an algorithm that make it always efficiently ... $\endgroup$ – Carlos Linares López May 1 '12 at 18:54
  • $\begingroup$ So, considering I'm just a very humble 4th semester computer science undergraduate, should I go for a serialized algorithm or I should try expecting some acceptable sub-linear speedup? $\endgroup$ – wirate May 1 '12 at 23:28
  • $\begingroup$ Sorry for the delay in my reply, this passed completely unnoticed in my Inbox. As a matter of fact, I would expect that the final savings do completely depend on the distribution of the scores assigned by your evaluation function to the leafs of the search tree. In general, there are no guarantees that a distributed search algorithm will perform significantly better than a serialized alpha-beta search algorithm. Thus, I would definitely go for a serialized version of it trying as many enhancements as feasible (ordering moves, transposition tables, etc.) $\endgroup$ – Carlos Linares López May 12 '12 at 12:34
  • $\begingroup$ I've had some success with parallel alpha-beta (basically as described on the wiki page you linked to). $\endgroup$ – Jeremy List Dec 27 '12 at 7:59
3
$\begingroup$

yes the theory has advanced significantly and somewhat due to both the chess analysis literature and general parallel programming techniques. here are some newer refs on (chess) alpha beta pruning over distributed clusters/ parallelism. also some of the early distributed computing chess literature predates a lot of basic parallel design patterns and can be conceptualized within that framework.

the basic idea behind DTS is that search trees are distributed among computational nodes based on move/ layout complexity. unused processors that "finish early" can do additional work beyond an initial allocation which can be distributed as evenly as possible initially but will turn out to be uneven. hence its basically a kind of "load balancing" and "producer/ consumer" queue, or also similar to job scheduling.

This idle processor broadcasts (using shared memory) that it is idle, and is available to "help" any other processor finish searching its tree. The busy processors collect the "state of the tree" data, and store it in shared memory for the idle processor to examine. This idle processor analyzes this data, and decides which (if any) of the busy processors seems to have a tree that is complicated enough that it would be efficient to help with the search. If such a position is found, the idle processor informs the processor which owns that node of this and they "join" forces.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.