Experiments with the M & N Tree-Searching Program

The M & N procedure is an improvement to the mini-max
backing-up procedure widely used in computer program 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.

CACM March, 1970

Slagle, J. R.
Dixon, J. K.

artificial intelligence, heuristic program, tree searching,
LISP, kalah, game playing, decision theory, 
mini-max backing-up procedure, backing-up procedures

3.60 3.64 3.66

CA700302 JB February 14, 1978  8:34 AM

1515	4	2096
2096	4	2096
2127	4	2096
2210	4	2096
1155	5	2096
2096	5	2096
2096	5	2096
2096	5	2096
2215	5	2096
2096	6	2096