Difference between revisions of "Stephen F. Wheeler"
GerdIsenberg (talk | contribs) (Created page with "'''Home * People * Stephen F. Wheeler''' FILE:StephenWheeler.jpg|border|right|thumb|link=https://www.linkedin.com/in/dr-stephen-wheeler-ph-d-46124a149/| S...") |
GerdIsenberg (talk | contribs) |
||
Line 6: | Line 6: | ||
an American computer scientist and senior professor of information systems at the graduate level at [https://en.wikipedia.org/wiki/DeVry_University DeVry University] [https://en.wikipedia.org/wiki/Irving,_Texas Irving, Texas] campus, | an American computer scientist and senior professor of information systems at the graduate level at [https://en.wikipedia.org/wiki/DeVry_University DeVry University] [https://en.wikipedia.org/wiki/Irving,_Texas Irving, Texas] campus, | ||
with expertise in [[Artificial Intelligence|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 [https://en.wikipedia.org/wiki/Texas_A%26M_University%E2%80%93Commerce Texas A&M University] in 1985, | with expertise in [[Artificial Intelligence|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 [https://en.wikipedia.org/wiki/Texas_A%26M_University%E2%80%93Commerce Texas A&M University] in 1985, | ||
− | and a Ph.D. in AI from [https://en.wikipedia.org/wiki/Walden_University Walden University] in 1992. As part of his M.Sc. research, he developed the chess playing program [[HAL]] (Heuristic Associative Linear-algorithm) | + | and a Ph.D. in AI from [https://en.wikipedia.org/wiki/Walden_University 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) <ref>[http://rybkaforum.net/cgi-bin/rybkaforum/topic_show.pl?tid=17529 HAL 9000] by Master Om, [[Computer Chess Forums|Rybka Forum]], June 10, 2010 (Download)</ref>. |
Stephen Wheeler was actor in [https://en.wikipedia.org/wiki/Andrew_Bujalski Andrew Bujalski's] 2013 feature film [[History#ComputerChess|Computer Chess]] <ref>[https://www.imdb.com/name/nm5421419/ Stephen Wheeler] - [https://en.wikipedia.org/wiki/IMDb IMDb]</ref>. | Stephen Wheeler was actor in [https://en.wikipedia.org/wiki/Andrew_Bujalski Andrew Bujalski's] 2013 feature film [[History#ComputerChess|Computer Chess]] <ref>[https://www.imdb.com/name/nm5421419/ Stephen Wheeler] - [https://en.wikipedia.org/wiki/IMDb IMDb]</ref>. | ||
+ | |||
+ | =Alpha-Beta Benchmark= | ||
+ | Quote of the abstract of Stephen Wheeler's M.Sc. thesis, as given in the [[ICGA Journal#10_1|ICCA Journal]] 1987 <ref>[[Stephen F. Wheeler]] ('''1987'''). ''[https://www.researchgate.net/publication/34381496_A_performance_benchmark_of_the_alpha-beta_procedure_on_randomly_ordered_non-uniform_depth-first_game-trees_generated_by_a_chess_program 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) [[ICGA Journal#10_1|ICCA Journal, Vol. 10, No. 1]]</ref> | ||
+ | ==Purpose of the Study== | ||
+ | The purpose of this research was to provide a performance benchmark of the [[Alpha-Beta]] procedure, on [[Depth-First|depth-first]] randomly ordered game-trees with non-uniform [[Depth|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<span style="vertical-align: super;">(3/4)d</span>, where b is the [[Branching Factor#Average Branching Factor|average branching factor]] and d is the average depth of search, and fits well within the asymptotic upper bound described by [[Donald Knuth|Knuth]] and Moore of (b/log b)<span style="vertical-align: super;">d</span> for the size and type of game trees investigated by this research. | ||
=Selected Publications= | =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, [https://en.wikipedia.org/wiki/Texas_A%26M_University%E2%80%93Commerce East Texas State University] | + | * [[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, [https://en.wikipedia.org/wiki/Texas_A%26M_University%E2%80%93Commerce East Texas State University] |
− | + | * [[Stephen F. Wheeler]] ('''1987'''). ''[https://www.researchgate.net/publication/34381496_A_performance_benchmark_of_the_alpha-beta_procedure_on_randomly_ordered_non-uniform_depth-first_game-trees_generated_by_a_chess_program 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) [[ICGA Journal#10_1|ICCA Journal, Vol. 10, No. 1]] | |
=Postings= | =Postings= |
Revision as of 00:13, 8 January 2020
Home * People * Stephen F. 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) [2].
Stephen Wheeler was actor in Andrew Bujalski's 2013 feature film Computer Chess [3].
Contents
Alpha-Beta Benchmark
Quote of the abstract of Stephen Wheeler's M.Sc. thesis, as given in the ICCA Journal 1987 [4]
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
- ↑ Dr. Stephen Wheeler, Ph.D. | LinkedIn
- ↑ HAL 9000 by Master Om, Rybka Forum, June 10, 2010 (Download)
- ↑ Stephen Wheeler - IMDb
- ↑ 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