Stephen F. Wheeler

Home * People * Stephen F. Wheeler

Stephen Wheeler

Stephen F. Wheeler,
an American computer scientist and senior professor of information systems at the graduate level at DeVry University Irving, Texas campus, with expertise in artificial intelligence and computer games. He holds a Bachelor’s degree in CS and mathematics, as well as a Master's degree in computer science and AI from Texas A&M University in 1985, and a Ph.D. in AI from Walden University in 1992. As part of his M.Sc. research on Alpha-Beta performance, he developed the chess playing program, which later evolved to HAL (Heuristic Associative Linear-algorithm) . Stephen Wheeler was actor in Andrew Bujalski's 2013 feature film Computer Chess .

Alpha-Beta Benchmark

Quote of the abstract of Stephen Wheeler's M.Sc. thesis, as given in the ICCA Journal 1987

Purpose of the Study

The purpose of this research was to provide a performance benchmark of the Alpha-Beta procedure, on depth-first randomly ordered game-trees with non-uniform depth and branching characteristics within the actual game-playing environment of computer chess. Although both theoretical and empirical studies have been performed to evaluate the efficiency of the Alpha-Beta algorithm, this research represents the first of its kind to establish the performance characteristics of the Alpha-Beta procedure within the specific problem domain of this study. 

Procedure

A search of technical literature was performed to determine the research done to date with regard to the Alpha-Beta algorithm, and to ascertain the results obtained.  Modifications were made to the author's chess program to report Alpha-Beta pruning statistics to be used for an empirical evaluation of the algorithm's performance as compared to the unaided Minimax tree search algorithm.

Findings and Conclusions

Research literature indicates that the Alpha-Beta algorithm is asymptotically optimal among all directional algorithms. No algorithm demonstrated better performance than the Alpha-Beta algorithm on uniform perfectly-ordered depth-first game trees.

Chess programs generate non-uniform game trees. This author's research on such trees, generated to a minimum depth of two-ply and a maximum depth of four-ply with random ordering, indicates that the Alpha-Beta procedure provides a three-to one-improvement over the minimax procedure. The author has also demonstrated by empirical research that the number of bottom nodes evaluated by Alpha-Beta on such trees is roughly equal to 2b(3/4)d, where b is the average branching factor and d is the average depth of search, and fits well within the asymptotic upper bound described by Knuth and Moore of (b/log b)d for the size and type of game trees investigated by this research.

Selected Publications

• Stephen F. Wheeler (1985). A performance benchmark of the alpha-beta procedure on randomly ordered non-uniform depth-first game-trees generated by a chess program. M.Sc. thesis, East Texas State University
• Stephen F. Wheeler (1987). A performance benchmark of the alpha-beta procedure on randomly ordered non-uniform depth-first game-trees generated by a chess program. (Literature Received, Abstract) ICCA Journal, Vol. 10, No. 1

Postings

• HAL9000 Levels of Play by Stephen F. Wheeler, Chess.com, May 22, 2010
• HAL9000 Chess Rating? by Stephen F. Wheeler, Chess.com, May 28, 2010

External Links

• Dr. Stephen Wheeler, Ph.D. | LinkedIn
• Stephen Wheeler (sfwheeler) - Chess Profile, Chess.com
• Stephen Wheeler - IMDb

References

Up one level