Game playing

Chess players: familiar to all as the Chess Challenger, etc. A lot of progress from big programs: Belle in 1983 got US Master status; Deep Thought in 1989 got a US Chess Federation rating of 2500, aspiring Grand Master status. See article on Computer Chess in the Encyclopaedia of AI.

Backgammon: Hans Berliner's program defeated the world champion Villa in 1979. There have been a lot of improvements since. See Computer Backgammon by Berliner, in the June 1980 Scientific American.

Go: more intelligent than chess programs. The latter rely on brute-force search and fast computers. Most chess programs search the tree of possible moves to five or six levels deep. Eventually, the branching factor will overwhelm them: an example of combinatorial explosion. But Go has many more possible alternative moves from any position - perhaps 150-200 options as against 25 for typical mid-game chess. So Go programs can only search one level deep. This means that they must consider alternative moves, and evaluate each in terms of global strategy. Hence - say many Go players - a successful Go program will probably ``see'' the board in terms of eyes and other patterns, and react to these as an expert would.

As Berliner points out, the same applies to backgammon, and his article is a nice introduction to the subject of intelligent searching.

So how do humans play games? Concerns AI-as-engineering because game-playing machines sell (and the methods might apply to other kinds of problem); concerns AI-as-psychology just for the intrinsic interest of knowing the mechanism.

De Groot: one of the earliest to ask this question. Chess masters and weaker players differ in performance - what's the difference in mechanism? Difference in search methods perhaps: depth of search, or number of alternatives considered for each move? Experimental evidence suggests not: de Groot found these the same for masters and weaker players.

But although masters and weaker players consider the same number of moves, masters consider better moves! Also, masters are better at remembering (correct) chess positions. Instead of perceiving them as collections of individual pieces, they appear to work in larger chunks, such as pawn chains, castled-King positions. These units are probably strategically significant, and may serve to trigger suitable moves for further consideration. See article on Human Chess Skill by Neil Charness in Chess Skills in Man and Machine edited by Frey (2nd ed 1984; PSY KH:F 089).

Several important themes of AI arise from this:

• The interplay between the engineering and cognitive modelling sides of AI.

• Combinatorial explosion. Search is expensive. It takes time to do, and space to store the alternatives. In most problems, it will be forever impossible to build computers that are fast enough to search through all possible alternatives.

• Evaluation functions. In search, whether we consider all alternatives, or only some, we have to know when one is good enough. This involves trying to evaluate it against other alternatives. The evaluation must be done quickly, and may only be approximate.

• AI as productive laziness. A slogan from Computers and Thought, by M Sharples, D Hogg, C Hutchison, S Torrance, and D Young (MIT 1989; PSY KH:S531; RSL M92.E00068; Hooke).

  How can an agent apply its knowledge to cut down the number of possibilities it must search through? What's the best way to store that knowledge? Can clever indexing methods reduce the time taken to find items?

• The paradox of the expert. Surely as the amount of knowledge increases, the time taken to find an item should take longer. Not in people! Perhaps this is because we can reconfigure our representations, e.g. by changing the size and type of chunk (going from letters to words, or chess pieces to positional features). As yet, we have very little idea of how to make a program do this, or of how humans avoid the paradox.