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.

The subjects of perfect information games, machine learning and computational intelligence combine in an experiment that investigates a method to build the skill of a game-playing agent from zero game knowledge. The skill of a playing agent is determined by two aspects, the first is the quantity and quality of the knowledge it uses and the second aspect is its search capacity. This thesis introduces a novel representation language that combines symbols and numeric elements to capture game knowledge. Insofar search is concerned; an extension to an existing knowledge-based search method is developed. Empirical tests show an improvement over alpha-beta, especially in learning conditions where the knowledge may be weak. Current machine learning techniques as applied to game agents is reviewed. From these techniques a learning framework is established. The data-mining algorithm, ID3, and the computational intelligence technique, Particle Swarm Optimisation (PSO), form the key learning components of this framework. The classification trees produced by ID3 are subjected to new post-pruning processes specifically defined for the mentioned representation language. Different combinations of these pruning processes are tested and a dominant combination is chosen for use in the learning framework. As an extension to PSO, tournaments are introduced as a relative fitness function. A variety of alternative tournament methods are described and some experiments are conducted to evaluate these. The final design decisions are incorporated into the learning frame-work configuration, and learning experiments are conducted on Checkers and some variations of Checkers. These experiments show that learning has occurred, but also highlights the need for further development and experimentation. Some ideas in this regard conclude the thesis. / Dissertation (MSc)--University of Pretoria, 2007. / Computer Science / MSc / Unrestricted