Home * People * Michael Levin

Michael Levin,
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 ^[1], contains a Theorem by Michael Levin, the well known formula of the number of leaf nodes that need to be examined in Alpha-Beta.

Theorem

Theorem (Levin): 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

• $T = b^n$

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,

• $T = b ^ { \frac {n+1} 2 } + b ^ { \frac {n-1} 2 } - 1$

and for even n,

• $T = 2b ^{ n / 2 } - 1$

which can be reformulated for both cases using ceil and floor functions:

• $T = b^{\lceil { n / 2 } \rceil} + b^{\lfloor { n / 2 } \rfloor} - 1$

Quotes

Alpha-Beta

Quote by John McCarthy from Human-Level AI is harder than it seemed in 1955 ^[2]:

Chess programs catch some of the human chess playing abilities but rely on the limited effective branching of the chess move tree. The ideas that work for chess are inadequate for go. Alpha-beta pruning characterizes human play, but it wasn't noticed by early chess programmers - Turing, Shannon, Pasta and Ulam, and Bernstein. We humans are not very good at identifying the heuristics we ourselves use. Approximations to alpha-beta used by Samuel, Newell and Simon, McCarthy. Proved equivalent to minimax by Hart and Levin, independently by Brudno. Knuth gives details.

LISP

Quote by John McCarthy in From LISP 1 to LISP 1.5 ^[3]:

Many people participated in the initial development of LISP, and I haven't been able to remember all their contributions and must settle, at this writing, for a list of names. I can remember Paul W. Abrahams, Robert Brayton, Daniel Edwards, Patrick Fischer, Phyllis Fox, Saul Goldberg, Timothy Hart, Louis Hodes, Michael Levin, David Luckham, Klim Maling, Marvin Minsky, David Park, Nathaniel Rochester of IBM, and Steve Russell.

See also

• History of Alpha-Beta
• Leaves of Node Types
• Lisp
• Odd-Even Effect

Selected Publications

• John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart and Michael I. Levin (1962) LISP 1.5 Programmer's Manual. The M.I.T. Press, second edition (1985) available as pdf reprint ^[4]
• Michael Levin (1963). Primitive Recursion, AIM-055, reprint available from DSpace at MIT
• Timothy Hart, Michael Levin (1964). LISP Exercises, AIM-064, reprint available from DSpace at MIT
• Michael Levin (1964). Syntax of the New Language, AIM-068, reprint available from DSpace at MIT
• Michael Levin (1964). New Language Storage Conventions, AIM-069, reprint available from DSpace at MIT

References

1. ^ Daniel Edwards and Timothy Hart (1961). The Alpha-Beta Heuristic, AIM-030, reprint available from DSpace at MIT
2. ^ John McCarthy Human-Level AI is harder than it seemed in 1955
3. ^ John McCarthy (1979). History of Lisp, From LISP 1 to LISP 1.5
4. ^ McCarthy et al. LISP 1.5 Programmer's Manual. from The Computer History Museum Software Preservation Group

What links here?

Up one level