BOXES: AN EXPERIMENT IN ADAPTIVE CONTROL
Donald Michie, RAndrew Chambers · 2013
BOXES is the name of a computer program. We shall also use the word boxes to refer to a particular approach to decision-taking under uncertainty which has been used as the basis of a number of computer programs. Fig. 1 shows a photograph of an assemblage of actual boxes—matchboxes to be exact. Although the construction of this Matchbox Educable Noughts and Crosses Engine (Michie 1961, 1963) was undertaken as a 'fun project', there was present a more serious intention to demonstrate the principle that it may be easier to learn to play many easy games than one difficult one. Consequently it may be advantageous to decompose a game into a number of mutually independent sub-games even if much relevant information is put out of reach in the process. The principle is related to the method of subgoals in problem-solving (see Newell et al. 1960) but differs in one fundamental respect: subgoals are linked in series, while sub-games are played in parallel, in a sense which will become apparent. DECOMPOSITION INTO SUB-GAMES The motivation for developing algorithms for small games (by a 'small ' game we mean one with so few board positions that a boxes approach is feasible) needs explanation, since small games are generally too trivial to be of intel-lectual interest in themselves. The task of learning a small game by pure trial and error is, on the other hand, not trivial, and we propose that a good policy for doing this can be made useful as a component of a machine strategy for a large game. The point is that the board states of a large game may be mapped