25,161
edits
Changes
m
'''Theorem''' (Levin): <br/>Let '''''n''''' be the number of plies in a tree, and let '''''b''''' be the number of branches a every branch point. Then the number of terminal points on the tree is
no edit summary
'''[[Main Page|Home]] * [[People]] * Michael Levin'''
'''Michael Levin''',<br/>
an American computer scientist, in the 60s affiliated with [[Massachusetts Institute of Technology]], and involved in the initial development of [[Lisp]] within the group of [[John McCarthy]]. The 1961 memo on [[Alpha-Beta]] by [[Daniel Edwards]] and [[Timothy Hart]] <ref>[[Daniel Edwards]] and [[Timothy Hart]] ('''1961'''). ''The Alpha-Beta Heuristic'', AIM-030, reprint available from [http://dspace.mit.edu/handle/1721.1/6098 DSpace] at [[Massachusetts Institute of Technology|MIT]]</ref>, contains a Theorem by Michael Levin, the well known formula of the number of [[Leaf Node|leaf nodes]] that need to be examined in Alpha-Beta.
=Theorem=
T = b<span style="vertical-align: super;">n</span>
However, if the best possible advantage is take of the alpha-beta heuristic then the number of terminal points that need to be examined is for odd ''n'',
