25,161
edits
Changes
m
no edit summary
[[FILE:Img2725NodeTypes.gif|border|right|thumb|440px|link=http://www.netlib.org/utk/lsi/pcwLSI/text/node351.html|Node Types <ref>[http://www.netlib.org/utk/lsi/pcwLSI/text/node351.html Analysis of Alpha-Beta Pruning] from the [http://www.netlib.org/utk/lsi/pcwLSI/text/BOOK.html Parallel Computing Works] ebook</ref> ]]
'''Node Types''' are classifications of [[Node|nodes]] as expected inside a [[Search Tree#MinimalGameTree|minimal alpha-beta tree]], or as determined by the search. These types were first formulated by [[Donald Knuth]] and Ronald Moore when describing the [[Alpha-Beta|alpha-beta algorithm]] <ref>[[Donald Knuth|Donald E. Knuth]] and , [http://www.informatik.uni-trier.de/~ley/pers/hd/m/Moore:Ronald_W= Ronald W. Moore ] ('''1975'''). ''[http://www.scribd.com/doc/28194932/An-Analysis-of-Alpha-Beta-Pruning An analysis of alpha-beta pruning].'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6:, No. 4, pp 293–326, 1975. Reprinted in [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/%7Eknuth~uno/aa.html Selected Papers on Analysis of Algorithms] by Donald E''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN. Knuth, Published 2000shtml CSLI lecture notes series] 102, by Addison-Wesley ISBN: 1-5758557586-211212-53</ref> and further analyzed by [[Judea Pearl]] <ref>[[Judea Pearl]] ('''1982'''). ''The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality''. [[ACM#Communications|Communications of the ACM]], Vol. 25, No. 8, pp. 559-564</ref>. While Knuth used the terms Type 1, 2, and 3, [[Tony Marsland]] and [[Fred Popowich]] introduced the more descriptive terms '''PV-''', '''Cut-''' and '''All-nodes''' <ref>[[Mark Winands]], [[Jaap van den Herik]], [[Jos Uiterwijk]], [[Erik van der Werf]] ('''2003'''). ''Enhanced forward pruning.'' [http://www.personeel.unimaas.nl/m-winands/documents/Enhanced%20forward%20pruning.pdf pdf]</ref> <ref>[[Tony Marsland]], [[Fred Popowich]] ('''1985'''). ''Parallel Game-Tree Search.'' [[IEEE#TPAMI|IEEE Transactions on Pattern Analysis and Machine Intelligence]], Vol. 7, No. 4, pp. 442-452. [http://webdocs.cs.ualberta.ca/~tony/OldPapers/parallel.pdf 1984 pdf] (Draft)</ref>.
Node types as established by the search are stored inside the [[Transposition Table|transposition table]], indicating whether the [[Score|score]] is either [[Exact Score|exact]], [[Lower Bound|lower]] or [[Upper Bound|upper bounded]]. Expected node types, as determined by tree topology, probing the transposition table, or comparing scores of a [[Evaluation|static evaluation]] considering threats, or even a reduced search or [[Quiescence Search|quiescence search]], with the [[Bound|bounds]], may be considered by various ([[Parallel Search|parallel]]) search algorithms and in decisions concerning [[Selectivity|selectivity]].
=Selected Publications=
* [[Donald Knuth|Donald E. Knuth]] and , [http://www.informatik.uni-trier.de/~ley/pers/hd/m/Moore:Ronald_W= Ronald W. Moore ] ('''1975'''). ''[http://www.scribd.com/doc/28194932/An-Analysis-of-Alpha-Beta-Pruning An analysis of alpha-beta pruning].'' [https://en.wikipedia.org/wiki/Artificial_Intelligence_%28journal%29 Artificial Intelligence], Vol. 6:, No. 4, pp 293–326, 1975. Reprinted in [[Donald Knuth]] ('''2000'''). ''[http://www-cs-faculty.stanford.edu/%7Eknuth~uno/aa.html Selected Papers on Analysis of Algorithms] by Donald E''. [http://web.stanford.edu/group/cslipublications/cslipublications/site/CSIN. Knuth, Published 2000shtml CSLI lecture notes series] 102, by Addison-Wesley ISBN: 1-5758557586-211212-53
* [[Igor Roizen]] ('''1981'''). ''On the Average Number of Terminal Nodes examined by Alpha-Beta''. Technical Report UCLA-ENG-CSL-8108, [https://en.wikipedia.org/wiki/University_of_California,_Los_Angeles University of California at Los Angeles], Cognitive Systems Laboratory
* [[Judea Pearl]] ('''1982'''). ''The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and its Optimality''. [[ACM#Communications|Communications of the ACM]], Vol. 25, No. 8, pp. 559-564
