25,161
edits
Changes
no edit summary
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,
and a Ph.D. in AI from [https://en.wikipedia.org/wiki/Walden_University Walden University] in 1992. As part of his M.Sc. researchon [[Alpha-Beta]] performance, he developed the chess playing program , which later evolved to [[HAL]] (Heuristic Associative Linear-algorithm), written in [[Pascal#TurboPascal|Turbo Pascal]] <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>.
=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=
* [[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]: ''Abstract'' <ref>Editor * [[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 Literature Received 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]], pp. 43</ref>: 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 evalution of the algorithm's performance as compared to the unaided [[Minimax]] tree search algorithm.
=Postings=
