Experiments with the M & N tree-searching program
Authors:
Open Access
- 1 March 1970
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 13 (3) , 147-154
Abstract
The M & N procedure is an improvement to the mini-max backing-up procedure widely used in computer programs for game-playing and other purposes. It is based on the principle that it is desirable to have many options when making decisions in the face of uncertainty. The mini-max procedure assigns to a MAX (MIN) node the value of the highest (lowest) valued successor to that node. The M & N procedure assigns to a MAX (MIN) node some function of the M (N) highest (lowest) valued successors. An M & N procedure was written in LISP to play the game of kalah, and it was demonstrated that the M & N procedure is significantly superior to the mini-max procedure. The statistical significance of important conclusions is given. Since information on statistical significance has often been lacking in papers on computer experiments in the artificial intelligence field, these experiments can perhaps serve as a model for future work.Keywords
This publication has 13 references indexed in Scilit:
- Experiments With Some Programs That Search Game TreesJournal of the ACM, 1969
- An adaptive tree pruning system1968
- Experiments With a Multipurpose, Theorem-Proving Heuristic ProgramJournal of the ACM, 1968
- Improving heuristic regression analysis1967
- Experiments with a deductive question-answering programCommunications of the ACM, 1965
- Assembly Line Balancing Using Probabilistic Combinations of HeuristicsManagement Science, 1965
- A Heuristic Program that Solves Symbolic Integration Problems in Freshman CalculusJournal of the ACM, 1963
- LISP 1.5 PROGRAMMER'S MANUAL1962
- Chess-Playing Programs and the Problem of ComplexityIBM Journal of Research and Development, 1958
- Experiments in ChessJournal of the ACM, 1957