The properties of chess which make it especially suitable for computer-based approaches to such questions are that the domain can be fully and exactly defined; it overextends the best human intellects; it demands calculation, learning, concept manipulation, analogical thinking, and long-term judgement. Moreover master skill at chess is measurable on a universal scale, and over the centuries players and scholars have built a vast incremental literature of chess knowledge, as apprehended and improved by each generation.
In the theory of games chess is a two-person game with perfect information: both players have full sight of the board and of every move made. It is also zero-sum, i.e. what is good for one player is bad in precisely equal measure for the other. Further, the rule which declares a draw when 50 moves have passed without castling, captures, or pawn moves ensures that the game is finite. The space of legal positions is, however, rather large, having been estimated as exceeding 10 to the power of 46.
The fraction of these which a chess master would regard as capable of occurrence in serious play, and hence meaningful, is infinitesimal. Yet the number of distinct positions contained in that infinitesimal fraction has been estimated as exceeding 10 to the power of 23. This is still many billion times too many for complete solution by computer search and enumeration. Such an enterprise would also require mechanizable representations of chess meaning, in a language whose most primitive expressions would denote basic features from which the master builds his mental picture of a chess position.
Only a few descriptive clichés of the hypothesized language have been uncovered to date. The 'chunks' involve such relations as mutual defence between pieces, cooperation in attacking a common target, certain types of pawn chain, characteristic castled-king patterns, and the like. Relevant investigations began a century ago with Alfred Binet's studies of chess memory in simultaneous blindfold chess, and were extended in the 1940s by Adriaan de Groot's analyses of players of varying strengths, including former world champions, 'thinking aloud' about given positions. More recent work by Herbert Simon and by Jorg Nievergeldt has yielded in addition estimates of the number of chunks, or basic patterns, stored by a master in long-term memory. This number, thought to lie between 30,000 and 50,000, corresponds to the size of the vocabulary employed by the hypothesized language. Little use has so far been made of studies of chess cognition by the mechanizers, who have mainly been content to apply brute force along lines mapped out, although not particularly recommended, by Claude Shannon in 1950. Current high-water marks are reviewed below.
1. Brute force: tournament play
2. Brute force: endgame analysis
3. Automation of chess knowledge
1. Brute force: tournament play
The first world computer chess championship in 1974 was won by a program authored by M. Donskoy and V. L. Arlazarov of the USSR. It performed at the level of mediocre club play. Programs for playing under tournament conditions have concentrated on wringing the most out of the concurrent rapid advance of computing technology together with the use of short-cut tricks of programming technique (such as 'alpha-beta' — see below). The Shannon paradigm of searching large trees of possibilities, guided by simplistic but fast means of evaluating each possibility as it is thrown up, has dominated.The principle of machine search resembles the strenuous 'thinking ahead' of an ambitious beginner, enhanced with miraculous speed, completeness, and accuracy. Tens, or even hundreds, of thousands of variations per second are scored for features generally correlated with a position's strength, such as piece scores, mobility, control of centre, king safety, and pawn structure. From the positions located along the furthermost boundary of the forward search, position values are assessed up the levels of the look-ahead tree, by a method known as minimaxing, until the immediate successors of the position under consideration have received backed-up values. Choice of the highest scoring of these determines the machine move. A refinement of minimax known as alpha-beta pruning almost doubles the depth of analysis obtainable for given computational cost: modern tournament programs regularly search three to four moves ahead (six to eight 'ply'), pursuing capture–recapture or other unstable-looking sequences to as much as twice this depth.
As early established by de Groot, the chess mind follows a diametrically opposite regime. When asked how many moves ahead he looked, the great grandmaster and theorist Richard Reti replied, 'One, the right one.' Even in correspondence chess forward calculations are highly selective, pruned and guided by criteria of strategic meaning not yet seriously addressed by the mechanizers.
In 1985 the strongest programs had reached the borderline of international master strength, as judged by their showing in regular human tournaments. When, however, obliged to play the same opponent repeatedly, they tend to fall to the human's ability to learn his enemy's weak points and exploit them. No tournament program of today has the power to learn from experience. Yet the final of the 1985 North American computer chess championship, in which Hans Berliner's 'Hitech' defeated Robert Hyatt's 'Cray Blitz', was recognizably master level. Both programs searched 20–30 million look-ahead positions per move. The equivalent figure for de Groot's grandmasters was 20–30 positions.
Further annual tournaments led to the creation in 1988 of Deep Thought by a team of Carnegie Mellon University graduate students including Feng-Hsiung Hsu and Murray Campbell. In that same year the program became the first to defeat a grandmaster in a tournament. In the following year, IBM's T. J. Watson Research Center recruited the team's two key members.
The reconstituted team, backed by powerful chess-specific ultra-parallel hardware from IBM, over a period of years developed Deep Blue, Deep Thought's successor. Thousandfold gains of calculating power allowed up to 100 billion positions per move to be evaluated in look-ahead. Additionally a database was incorporated that held the grandmaster games of the past 100 years together with billions of specific endgame scenarios.
In February 1996 Deep Blue met the World Champion Garry Kasparov in the international Association for Computing Machines' six-game Chess Challenge held in Philadelphia, USA. Kasparov was victorious with three wins, one loss and two draws.
The rematch came in May 1997. After a win by each side followed by three draws, all hung on the sixth and final game. To the astonishment of the chess world, Kasparov played a well-known opening blunder and was lost, resigning after the game's nineteenth move. The generally accepted explanation lies in the blow to morale in Game 2, which Kasparov mistakenly resigned in a position that subsequent ultra-deep analysis showed to have been technically drawn.
Well satisfied with the result's public impact, IBM declined Kasparov's immediate request for a rematch, dissolving its winning team and discontinuing significant computer chess work. It was to be five years before his next public opportunity for a challenge match against a reigning world computer champion.
Meanwhile a growing website of chess programs, openings, endgame databases, and computer analyses of past games became accessible at www.chessbase.com. Chessbase has enabled grandmasters not only to train ever harder for combat in human tournaments but also to study the peculiarities and vulnerabilities of computer play. The latter has also strengthened, not least through decreasing costs and increasing speeds of microcircuitry.
2. Brute force: endgame analysis
Given today's fast processors and large computer memories, exhaustive computation can be performed so as fully to solve and tabulate subgames of chess which are not understood by grandmasters, or even (a taller order) by endgame specialists. The first such feat, by T. Strohlein in 1970, fully analysed the four-piece ending king and rook versus king and knight, thought until then to be in the general case a drawn game. Of the 1,347,906 legal rook's-side-to-move positions (neglecting positions equivalent under rotations and reflections of the board), almost half (651,492) turn out to be winnable by correct (though for the most part protracted) play. The two longest wins are represented by positions 27 moves from checkmate or knight capture. Aided by knowledge that it could be done and by samples of the computer-generated material itself, the leading endgame scholar A. J. Roycroft was able to acquire and demonstrate complete mastery of optimal play of positions won for the rook's side (contrast the KBBKN case, below).Kenneth Thompson has completed exhaustive databases for all the interesting four-piece and five-piece pawnless endings. Of his factual discoveries one of the most spectacular has been the status of king and two bishops versus king and knight (KBBKN), previously believed to be drawable provided that the knight's side can attain the 'Kling & Horwitz' position (Fig. 1a). The position dates from 1851. The verdict that the defending side can draw positions like this (based on the placing of the two black men and largely ignoring the white placement) is repeated in all relevant chess endgame textbooks. In 1983 Thompson's exhaustive solution demonstrated the general win of this endgame in at most 66 moves, and the particular win in Kling & Horwitz positions in about 40–45 moves. Cases of this kind have led to a growing number of ad hoc modifications by the World Chess Federation of the 50-move drawing rule.
Not only does the Thompson database, comprising some 200 million legal positions, show that the bishops' side can win from all but a few freak starting positions, but its manner of doing so passes the comprehension of the ending's dedicated human students. The critical fourth stage of a five-stage win from the starting position shown in Fig. 1b involves a procedure 'not to be found in any book and characterized by excruciating slowness and mystery' (Roycroft). Moreover, following a year's study by Roycroft and others, involving availability of a variety of computer aids, it seems that human mastery (as opposed to machine mastery) of this ending may never be attainable.
Databases generated in this style can also be searched for positions which a master or endgame scholar would recognize as 'studies' or 'compositions'. Here a unique winning (or in appropriate cases drawing) line of play must exist, coupled with properties of elegance, surprise, didactic value, and even wit, not easy to define in programming terms. M. R. B. Clarke has conducted selective trawls with some success: two of his discoveries for king-pawn–king-pawn (KPKP) are shown as Fig. 2a and 2b.
Fig. 1a. Either side to move.
Fig. 1b. White to move.
Fig. 2a. White to win.
Fig. 2b. White to win. Two computer-assisted study compositions in the KPKP domain. The natural-looking Pd4 for Fig. 2a, and Kg6 for Fig. 2b, fail. Correct are Kc3 and Pd5 respectively.
3. Automation of chess knowledge
In addition to purely factual discoveries, computer programs could help the chess expert fill the gaps of which codified chess knowledge is now seen mainly to consist. Knowledge-directed programs can support his endeavours to outline the missing framework and by semi-automatic generation of descriptions from expert-supplied examples to fill empty slots in the framework as it takes shape. Using a technique of Alen Shapiro and Timothy Niblett known as 'structured induction', Shapiro was able to generate a complete human-readable codification for adjudicating positions in the king-pawn–king-rook ending (pawn's side to move, pawn on a7) where none pre-existed. A side benefit subsequently extracted from this phenomenon was endowment of the program with the ability to document its own adjudications on demand with explanatory notes.In the above-mentioned work the induction process was fuelled by hand-supplied examples. In some other cases success has been reported where the examples have been quarried by the program itself from large pre-computed databases. A recent de novo synthesis of knowledge in clinical cardiology by Ivan Bratko and colleagues employed just such an alternation between
(i) exhaustive derivation of brute facts from a logical model and
(ii) induction from these of an operational theory.
Sparked initially by the chess work, application is beginning to place emphasis on factual compilations as raw materials for automating the codification of new knowledge as a commercial product. The need to better understand the cognitive invariants with which the designer of codification languages must now come to terms is also leading to closer involvement of professional students of mind.
(Published 2004)
— Donald Michie
- Bibliography
- Binet, A. (1894). Psychologie des grands calculateurs et des joueurs d'echecs.
- Chase, W. G., and Simon, H. A. (1973). 'Perception in chess'. Cognitive Psychology, 4.
- de Groot, A. (1965). Thought and Choice in Chess (rev. edn.). (For mental representations of chess masters.)
- Hayes, J. E., and Levy, D. (1976). The World Computer Chess Championship, Stockholm 1974. (For an introduction to chess cognition in relation to artificial intelligence.)
- Michie, D., and Shapiro, A. (1986). Several articles in Advances in Computer Chess, 4. (For the knowledge-synthesis approach.)
- Shannon, C. (1950). 'Programming a computer for playing chess'. Philosophical Magazine, 41.
- Simon, H. A., and Gilmartin, K. (1973). 'A simulation memory for chess positions'. Cognitive Psychology, 5.
- Thompson, K. (1986). 'Programs that generate endgame data bases'. End Game, 83.
