Young Brothers Wait Concept

From Chessprogramming wiki
Revision as of 17:02, 29 June 2018 by GerdIsenberg (talk | contribs)
Jump to: navigation, search

Home * Search * Parallel Search * Young Brothers Wait Concept

Young Brothers Wait Concept, (YBWC)
a basic concept for a parallel alpha-beta search coined by Rainer Feldmann et al. in 1986 [2], introduced 1989 to a wider audience in the ICCA Journal paper Distributed Game-Tree Search [3]. Brothers are sibling nodes, the oldest brother is searched first, younger brothers, to be searched in parallel, have to wait until the oldest brother did not yield in a beta-cutoff and did possibly narrow the bounds in case of an alpha increase.

Delay of Parallelism

The Young Brothers Wait Concept, which in some situations delays the use of parallelism until subtrees are available which are relevant for the final result with high probability, prevents processors from searching irrelevant subtrees and reduces the search overhead. The use of the YBWC is possible only in combination with good load balancing possibilities [4].

The eldest son of any node must be completely evaluated before younger brothers of that node may be transmitted. 

Distributed Game-Tree Search

In their introduction, Feldmann et al. mention approaches by several authors to decrease search overhead by various methods. The mandatory-work-first approach first evaluates that part of the game tree that must be searched and then evaluates the rest only if necessary [5]. The Principal Variation Splitting (PVS) algorithm [6] evaluates right sons of game-tree nodes with a minimal window and re-evaluates them only if necessary.

Alternatively, game-tree nodes are evaluated in parallel only if they had acquired an alpha-beta bound before [7]. Yet another approach applies in a distributed chess program running on a hypercube [8]: if the transposition table proposes some move for a game position, then this move is tried first. Parallel evaluation of the other moves is started only of the evaluation of the transposition move yields no cutoff.

Critique

Their 1989 ICCA paper was criticized by Jonathan Schaeffer [9], first on the speedup topic of about eleven on a 16-processor machine not mentioning that parallel speedup is tied to the (in)efficiency of the serial alpha-beta search, and further, on ignoring other work recently done in the field. The YBWC presented was similar to the methods used in the chess programs Cray Blitz [10], Lachex, and Para-Phoenix [11] [12]. In a response, Feldmann et al. agreed that the behavior of a parallelization should be measured relative to the "best" sequential program. However, the speedup depends on many implementation details such as those about the hardware, communication mechanism, load-balancing capabilities, etc., which cannot be described in a short paper. The authors further state that chess programs were not the main research vehicle, but the algorithm, which was the reason for not quoting all the chess specific papers [13].

Quotes

Robert Hyatt on the distinction between ALL- and CUT-nodes [14]:

In CB, I used this extensively, because you never want to split at a CUT node, and want to prefer an ALL node. YBW tries to recognize an ALL node by requiring that at least one move be searched before splitting, since > 90% of CUT nodes are discovered on the first move searched. But waiting on that first move introduces some wait time, and if you knew it was an ALL node from the get-go, you could split before the first move is completed. That was the basic premise behind the iterated search and DTS algorithm in Cray Blitz... 

See also

Publications

1986 ...

1990 ...

2010 ...

Forum Posts

2009

2010 ...

2015 ...

External Links

Jan Garbarek, Rainer Brüninghaus, Eberhard Weber, Marilyn Mazur

References

  1. The Marx Brothers, head-and-shoulders portrait, facing front. Top to bottom: Chico, Harpo, Groucho and Zeppo in 1931, Marx Brothers from Wikipedia
  2. Rainer Feldmann, Peter Mysliwietz, Oliver Vornberger (1986). A Local Area Network Used as a Parallel Architecture. Technical Report 31, Paderborn University
  3. Rainer Feldmann, Burkhard Monien, Peter Mysliwietz, Oliver Vornberger (1989). Distributed Game-Tree Search. ICCA Journal, Vol. 12, No. 2, pp. 65-73
  4. Rainer Feldmann, Burkhard Monien, Peter Mysliwietz, Oliver Vornberger (1989). Distributed Game-Tree Search. ICCA Journal, Vol. 12, No. 2, pp. 65-73
  5. Selim Akl, David T. Barnard, R.J. Doran (1980). Simulation and Analysis in Deriving Time and Storage Requirements for a Parallel Alpha-Beta Pruning Algorithm. IEEE International Conference on Parallel Processing, pp. 231-234
  6. Tony Marsland, Fred Popowich (1985). Parallel Game-Tree Search. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-7, No. 4, pp. 442-452. as 1984 pdf (Draft)
  7. Chris Ferguson, Richard Korf (1988). Distributed Tree Search and its Application to Alpha-Beta Pruning. Proceedings of AAAI-88, Vol. I, pp. 128-132. Saint Paul, MN, pdf
  8. Ed Felten, Steve Otto (1988). Chess on a Hypercube. The Third Conference on Hypercube Concurrent Computers and Applications, Vol. II-Applications (ed. G. Fox), pp. 1329-1341
  9. Jonathan Schaeffer (1989). Comment on `Distributed Game-Tree Search'. ICCA Journal, Vol. 12, No. 4, pp. 216-217
  10. Robert Hyatt (1988). A High-Performance Parallel Algorithm to Search Depth-First Game Trees. Ph.D. Thesis, Department of Computer Science, University of Alabama at Birmingham
  11. Jonathan Schaeffer (1986). Improved Parallel Alpha-Beta Searching. Proceedings ACM/IEEE Fall Joint Computer Conference, pp. 519-527.
  12. Jonathan Schaeffer (1989). Distributed Game-Tree Searching. Journal of Parallel and Distributed Computing, Vol. 6, No. 2, pp. 90-114. ISSN 0743-7315
  13. Rainer Feldmann, Burkhard Monien, Peter Mysliwietz, Oliver Vornberger ('1990). Response to a Comment on 'Distributed Game-Tree Search. ICCA Journal, Vol. 13, No. 1, pp. 20-21
  14. Re: "CUT" vs "ALL" nodes by Robert Hyatt, CCC, March 08, 2011

Up one level