Experimental and theoretical validation of a new search algorithm, with a note on the automatic generation of causal explanation
Abstract
An algorithm is presented for game-tree searching that is
shown under fairly general but formally specifiable
conditions to be more sparing of computational resource
than classical alpha-beta minimax.
The algorithm was programmed in POP-2 and compared
experimentally with alpha-beta searching on randomly
generated trees, and the results are presented.
A machine for solving deep chess combinations was built
from micro-electronic circuits. The general game-tree
searching algorithm was embedded in the machine together
with a chess-specific algorithm.
The chess-specific algorithm and the hardware of the
machine are described.
The results of running the machine on selected chess
positions are presented.
Deficiencies in the performance of the machine are
described and improvements suggested.
The problem of generating human-oriented descriptions of
combinatorial problems was considered using chess tactics
as a domain.
A system is described for finding causal motivations for
moves in a chess game-tree. The chess machine was interfaced to a main-frame computer and programs were
written which ran interactively with the chess machine to
produce humanly understandable explanations of the
combinations solved
The system was tested on selected positions and the
results presented.
Deficiencies in the performance of the system are
analysed and solutions suggested based on extensions of
the underlying algorithm. Applicability of these methods
is discussed to combinatorial problems encountered in
industry and defence.