Games Playing with Computers

Jump To Main Content

Jump Over Banner

Home

Jump Over Left Menu

Chapter 7: Future Developments

Anything that is theoretically possible and desired greatly enough will be achieved in practice. The only reason a machine is not, at this moment, chess champion of the world is because the USA has not spent money and time on such a project.

The problem of prophecy is not what will happen, but how and when and why. The developments to be discussed here will almost certainly be the outcome of military research or application (the why), but (the how and when) is almost certainly unpredictable.

7.1 MORE POWERFUL MACHINES

Over the past twenty years computers have increased their speed of operation a thousand times and their size by a million times. The improvement in game playing programs is almost entirely due to this hardware advance (especially in chess); it is doubtful whether software has realised improvements of even five times, i.e. a modern program could only achieve the same decision in ≥ 20%; of the time of a 20-year-old program on the same machine.

At the moment it seems we can gain another factor of 100 over present day speeds by designing machines which (1) have a great deal of parallel processing, i.e. they try to do as many things as possible at the same time, and (2) can handle strings and arrays very efficiently. The improvement here is that about one-third of a machine's time is spent in decision taking operations. For example,

for i := 1 step 1 until 100 do
  sum[i] : = a[i] + b[i];

is an Algol program to add two arrays (a and b) together and store the result in another array sum. This would normally compile into about 20 instructions which would loop 100 times. On the CDC STAR it is hoped that the compiler will spot this (and other) simple array operations and decompile the program into 1 instruction which, by clever alteration of the variable word length of the machine, could be executed once only.

Another useful advance in the hardware would be a better input/output interface. The ability of computers to handle and manipulate physical objects is only just being developed. One robot (called Butterfingers) has been built at Stanford University. It scans a group of wooden bricks and then builds them into a tower using a prosthetic arm. Such a machine could be connected to a game playing program, and actually move pieces around on a board. The problem at the moment is that Butterfingers is slow and clumsy, not only physically but also mentally. It takes a long time to scan and identify objects in the field of view of its T.V. eye. As such, it could not be linked to a program to play the card game SNAP, or indeed any game which requires fast visual identification of 3-dimensional objects. Also, if such a machine were perfected, it would no doubt be 'usefully' applied to recognising enemy aircraft, tanks, etc. rather than playing cards.

7.2 HOLOGRAPHY

An alternative solution to physically handling objects is for the machine to display the cards, chess pieces, etc. Up till now such displays have been limited to teleprinters (hopeless for bridge because cards played remain in view) and visual display units.

Although V.D.U's are more acceptable they are restricted to a flat screen. An exciting improvement is based on the technique of holography, or photography by wave-front reconstruction, invented by Dennis Gabor (of the Imperial College of Science and Technology) twenty years ago and realised by the invention of the laser. With this technique it is possible to photograph and display a 3-dimensional object to give the illusion of depth and parallax, i.e. the observer can look around the sides of the object by moving his head, and a closer object can obscure objects beyond it.

In an article Photography by Laser by Leith and Upatnieks (Scientific American, June 1965) are a number of example photographs displaying chess pieces on a board from various angles. It is not essential to use a laser; in fact computers have already been used to synthesise holograms from purely numerical specifications (see IBM Journal of Research and Development, vol. 13, No.2, March 1969), and the resulting photographic plate can be displayed in monochromatic light with surprising clarity.

Such displays suffer from the hidden line problem, i.e. the objects are transparent, but the effect of depth leaves no doubt as to the spatial relationships. Coloured holograms have also been made, so it seems that, in the not too distant future, we may be able to sit in front of a 'chess board' on which there are pieces that the machine can move. The illusion would only break if we attempted to move a piece ourselves; this problem has already been solved by a device which can detect where a person is looking (it shines a beam of light onto the eye). We need only look at a man, blink, look at the square we wish to move to, blink again, and the computer makes our move. Such devices are used by helicopter pilots in Vietnam, except that a gun is trained on whatever the pilot is looking at!

Returning to the SNAP machine, Gabor (39) describes how the hologram principle can be adapted to serve as a mechanical translation and recognition device. Basically what could happen is that an object, for example a printed or hand-written character, is photographed in combination with a pattern of point light sources that form a code word which the machine can easily read. Now when the original character (or something sufficiently similar to it) is presented to the hologram with the original illumination, the light pattern appears. Because many images can be recorded on a single photographic plate by changing the angles of the light waves, this technique can be used to record a large number of objects and their variants. Gabor concluded that a single hologram may discriminate between 1000 different characters. Therefore, in physical or imaginary terms, it seems that holography will result in machines giving a much more realistic display of their game playing powers in the next few years.

7.3 GENERAL GAME PLAYERS

The big software problems are as follows.

  1. We want a language which can state easily and naturally as diverse a class of games as possible. This implies sufficient descriptive power to represent the rules of a chosen game and hence generate the moves.
  2. The computer program must be capable of playing the games stateable in the input language. This implies supplying it with tree searching capabilities, a concept of better and worse (31), Monte Carlo tests, formulation as a theorem to be proved in predicate calculus (40), etc.

Efforts to solve the first problem still fall very short of the freedom of expression we are accustomed to when teaching another person how to play a game. This is very largely due to the inability to teach by example, e.g. you move a knight like this. In fact a tape recording of such a lesson would be useless; teaching a blind person would be more analogous.

The second problem has resulted in the General Problem Solver (GPS) (41). The program assumes that the problem exists in a heuristic search paradigm, i.e. it would not solve Snakes and Ladders by the method of Chapter 6.3, but uses constrained and directed suck it and see search. The GPS is quite capable of solving noughts and crosses, the Missionaries and the Cannibals Problem (42), generating magic squares, and many other apparently unrelated problems. Not only can it solve the problem but it can also give an intelligible report of how it does so, an important feature which is often overlooked.

7.4 LEARNING MACHINES

The Barricellian symbioorganisms, described in Chapter 4.3, illustrate an approach which has been attempted many times. The problem is that the learning is very slow and erratic. What is required in this technique is a green fingered program which can oversee the organisms (or automata), detect why some are successful and others are not, and deliberately cross features. Such a program would be a major research project and the author is not aware of any attempts to produce one.