Michie, Donald

Coplan, Kevin P.

SRC Studentship in association with a project funded by SRC grant no. GR/A/80327

2013-04-05T11:19:30Z

2013-04-05T11:19:30Z

1984

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.

http://hdl.handle.net/1842/6645

en

The University of Edinburgh

game-tree searching

alpha-beta searching

chess-specific algorithm

chess

Experimental and theoretical validation of a new search algorithm, with a note on the automatic generation of causal explanation

Thesis or Dissertation

Doctoral

PhD Doctor of Philosophy