Prof. Newborn has studied problems related to search for over 20 years. Search is a fundamental problem in artificial intelligence and is at the heart of designing good programs to solve of a wide variety of problems. Of particular interest has been the subject of chess-playing programs and theorem-proving programs. The basic search strategies used to solve these two apparently different problems are remarkably similar and have evolved over the years.
His research on chess-playing programs has centered around analyses of the efficiency of the alpha-beta algorithm, the correlation between chess program strength and computer speed, the choice of appropriate data structures, and parallel search. The chess program OSTRICH competed in most of the major tournaments for computers from 1972 through 1988. It has to its credit a draw with the former chess championship in Stockholm in 1974. In 1981, OSTRICH became the first chess program to compete in a major tournament using a multiprocessing system, a Data General system consisting of five Nova computers.
In recent years, Prof. Newborn's interest has shifted to developing a theorem-proving program. Many of the search strategies used by OSTRICH and other chess programs carry over the theorem-proving programs. In particular, he has developed a theorem-proving program called The Great Theorem Prover that uses iteratively-deepening depth-first search coupled with the use of a large hash table. It compares favorably with leading theorem-proving programs when tested on standard test sets.
Future research will stress new approaches to theorem proving, attempts to increase the strength of The Great Theorem Prover, and techniques for parallel search.