Summarize Psychology Article

PSYCHOLOGICAL SCIENCE

Research Report

THE ROLES OF RECOGNITION PROCESSES AND LOOK-AHEAD SEARCH IN TIME-CONSTRAINED EXPERT

PROBLEM SOLVING: Evidence From Grand-Master-Level Chess

Fernand Gobet and Herbert A. Simon Carnegie Mellon University

Abstract—Chess has long served as an important standard task environment for research on human memory and problem- solving abilities and processes. In this article, we report evi- dence on the relative importance of recognition processes and planning (look-ahead) processes in very high level expert per- formance in chess. The data show that the rated skill of a top- level grand master is only slightly lower when he is playing simultaneously against a half-dozen grand-master opponents than under tournament conditions that allow much more time for each move. As simultaneous play allows little time for look- ahead processes, the data indicate that recognition, based on superior chess knowledge, plays a much larger part in high- level skill in this task than does planning by looking ahead.

For the past 20 years, there has been a general consensus, based on extensive laboratory research, that two psychological mechanisms play a principal role in skilled chess-playing per- formance. The first mechanism is recognition of cues in chess positions that evoke information from the expert's memory about possible moves and other implications of recognized pat- tems of pieces. The second mechanism is planning by looking ahead at possible moves, possible responses by the opponent, possible responses to those responses, and so on. The chess- based model of expertise, emphasizing a combination of recog- nition and selective search processes, has been applied widely to the explanation of expertise in other domains involving com- plex specialized skills: medical diagnosis, engineering and ar- chitectural design, and many others (Chamess, 1992; Ericsson & Staszewski, 1989), The validity of this model is consequently of considerable interest and importance for the general under- standing of the nature of expert performance,

TTie role of recognition processes in chess-playing skill was first recognized by De Groot (1946/1978), and studied further by Chase and Simon (1973), Simon and Chase (1973), Goldin (1979), Chamess (1981a, 1981b), Hartston and Wason (1983), Saariluoma (1985, 1989), Lories (1987), Gobet (1993), and oth- ers, A key experimental result is that positions in chess games (with about 25 pieces on the board) can be stored in memory and reconstructed almost perfectly by masters and grand mas- ters after as little as a 5-s view of the board; in contrast, under these same conditions, weak players can recall only some half- dozen pieces. As this superiority of masters over weaker play- ers nearly vanishes if the pieces are placed at random on the board instead of coming from positions in an actual game, it

Address correspondence to Herbert A, Simon, Department of Psy- chology, Carnegie Melton University, Pittsburgh, PA 15213,

appears that the masters are recognizing and storing familiar patterns of pieces, rather than individual pieces (Chase & Si- mon, 1973), From these experiments, one can conclude that the recognition process requires, at most, i to 5 s, in consistency with recognition processes in other tasks.

The significance of recognition is that chess masters, on no- ticing that the board before them contains particular chunks, thereby gain long-term memory access in a matter of seconds to the whole rich body of information that, through previous train- ing and experience, has been associated with, hence is cued by, the chunks (De Groot, 1946/1978), For example, on recognizing that a particular position represents the Dragon variation of the Sicilian defense, a well-known line of play, masters access a template giving the typical locations of a dozen or more pieces in the Dragon and probable locations of other pieces, as well as extensive knowledge of moves and strategies (successful and unsuccessful) that have been tried in similar positions in the past. The recognition mechanism provides a rapid index to the master's chess knowledge and tools of analysis (De Groot, 1946/1978; Gobet & Simon, 1994b), This mechanism has been incorporated in a computer program described by Gobet and Jansen (1994): Patterns of pieces on the board, when recog- nized, suggest potential moves to the program.

The role of search processes in chess has always been ac- knowledged, but De Groot (1946/1978) contribtjted greatly to the understanding of them by demonstrating that even chess grand masters seldom look at more than 100 possible continu- ations of the game before choosing a move. As the number of possible legal moves in a middle-game position averages about 35, the number of legal continuations 3 moves deep for each player is typically about 35*" (1,8 biUion), and the number of legal continuations continues to increase exponentially for greater depths. Thus, look-ahead search is highly selective and closely guided by chess knowledge.

A surprising result in De Groot's study (1946/1978) was that top-level grand masters' do not search reliably deeper than ex- perts. In a direct replication of De Groot's experiment, masters did not differ from somewhat less skilled players in their max- imal depth of search, but searched deeper, on average, than weak amateurs (Class B players; Gobet, 1994). Differences in search have also been reported by Chamess (1981b) and Hold- ing and Reynolds (1982), using experimental positions different from de Groot's (1946/1978), but the increase in depth of aver-

1, Players are ranked by a so-called Elo scale as grand masters (2500 and above), masters (2200-2499), experts (2000-2199), Class A players (1800-1999), Class B players (1600-1799), and so on. The Elo scale is described later in the text.

52 Copyright © 1996 American Psychological Society VOL, 7, NO, 1, JANUARY 1996

PSYCHOLOGICAL SCIENCE

Fernatid Gobet atid Herbert A, Sitnon

age search as a function of skill was relatively small, about 0,5 half-moves for each standard deviation (200 Elo points). Given that the best players in those studies were clearly weaker than De Groot's (1946/1978) grand masters, who did not differ in amount of search from their weaker colleagues, Charness's (1981) proposal that the search algorithms become uniform at high skill levels (perhaps master level) seems valid.

Although the significance of both recognition and search mechanisms is generally accepted, there is not full agreement as to their relative importance. Some researchers (De Groot 1946/ 1978; Simon & Chase, 1973) have proposed that recognition, by allowing knowledge to be accessed rapidly, allows the slower look-ahead search to be greatly abridged or even dispensed with entirely without much loss in quality of play. Holding (1985), by contrast, argued that the main determinant of chess skill is abil- ity to plan ahead by search, rather than reliance on recognition of positional pattems. Specifically, he concluded that

the differences between players at different levels of skill seem to be attributable to differences in the cognitive activities described by the search-and-evaluation theory. The better players show greater compe- tence in every phase ofthe [search] processes, conducting more knowl- edgeable and better planned searches, with more knowledgeable eval- uations, in order to anticipate events on the chessboard, (pp, 255-256)

The data reported in this article test Holding's conclusion. One way to measure the relative importance of recognition

and search is to compare the quality of play of masters and grand masters under normal tournament conditions with the quality of play under the conditions of rapid chess or of simul- taneous play, in which there is little time for extensive look- ahead search. Analysis of masters' and grand masters' rapid and simultaneous games shows that they can play excellent chess even in these difficult conditions. Quantitative accounts of their performance are, however, rare. We have discovered only one published study that bears on this question: Caider- wood, Klein, and Crandall (1988) showed that there was no substantial difference in the quality of moves, as rated by a grand master, between games played under regular conditions (in this experiment, 2.25 min per move, on average) and games played under blitz conditions (5 min for the whole game, or an average of 6 s per move for games 50 moves long).

As this finding depends on a subjective (albeit expert) eval- uation ofthe quality of moves, we have sought a more objective test. We report here our findings of a comparison between reg- ular and simultaneous chess. These findings provide strong sup- port for a dominant role of recognition as compared with search in determining the level of play. The findings are especially interesting in that the simultaneous player involved, Gary Kas- parov, has the world's highest chess rating.

A NATURAL EXPERIMENT

Under typical toumament conditions, the player is allowed, on average, 3 min for each move. Failure to keep within the limit (enforced, e.g., as 20 moves in each hour) forfeits the game. The player may spend a quarter-hour, or more, deliber- ating about a single difficult move, but must then make up the time by making other moves rapidly. In any event, the 3-min

rule allows time for substantial look-ahead search. Data from chess experiments show that a chess master might examine 100 branches ofthe game tree in 15 min, an average rate of about 9 s per branch. De Groot (1946/1978) found that stronger and weaker players examine nearly the same number of branches, but that the stronger players select more relevant and important branches—again, because of their greater ability to recognize significant features.

In the simultaneous play that we examine, the grand master (the present Professional Chess Association world champion, Gary Kasparov) played against four to eight opponents with a limit of 3 min (on average) for each round—that is, for each four to eight moves. His opponents were allowed an average of 3 min for each move in reply. Hence, Kasparov, in these simul- taneous matches, was allowed only one quarter to one eighth of the normal toumament time for making moves, while his oppo- nents were allowed the full tournament time.

The simultaneous player with only 30 s, say, for a move will have littie time for extensive look-ahead search* at 9 s per branch, and will have to depend primarily on recognition of cues to select the right moves. In fact, this is what grand mas- ters who engage in simultaneous matches report: that they make "standard" (i,e,, familiar) developing moves until they notice a cue that informs them that an opponent has created a weakness in his or her position. Knowledge associated with, and evoked by, the recognized cue then suggests effective moves for exploiting the weakness and creating difficulties for the opponent. Only a few recognized mistakes by the opponent ("mistakes" that the grand master but not the opponent recog- nizes as such) are enough for an easy win.

The skill of chess players is measured by an official scale, devised by Elo (1978), which has been used by the chess world for more than 20 years. On the Elo scale, players with ratings of 2500 and above are called grand masters, and players with rat- ings of 2200 to 2499, masters. At the time he played the games we consider here, Kasparov had a rating of about 2750, A player can usually defeat players whose ratings are 300 or more Elo points lower than his own rating, will draw with them oc- casionally, and will lose to them only rarely.

The win of a chess game is assigned the value 1, a loss, 0, and a draw, 1/2, If a simultaneous player won four games against six opponents, lost one, and drew one, he would score 4,5 and his opponents would score 1,5, Thus, the ratio of the player's score to the total score of the opponents would be three to one. If the average Elo rating ofthe opponents was 2450, and the rating of the simultaneous player was 2750, Elo's linear approximation formula yields for the latter a performance rating of 2650 (2450 H- 40O[4,5 - 1.5J/6) under the conditions of si- multaneous play. The level of his simultaneous play would

2, The explanation that Kasparov maintains his strength against several players by suddenly increasing his rate of generating possible moves during search may be discarded at once: If he were able to do so, there is no reason why he would not search at this higher rate in normal competition. Nor can he restore his ability to search deeply by allocat- ing almost all his time to a few critical moves. He still faces the fact that he has only one quarter to one eighth of the normal toumament time in order to do this, and the scope of his searches would therefore be reduced severely.

VOL, 7, NO, 1, JANUARY 1996 53

PSYCHOLOGICAL SCIENCE

Recognition and Search in Simultaneous Chess

Table 1, Kasparov's performance in simultaneous chess against various national teams and the Hamburg team, one ofthe top teams of Germany

Number of Team opponents

Hamburg (Match 1) 8 Hamburg (Match 2) 8 Switzerland 6 United States (junior team) 6 France (Match 1) 6 France (Match 2) 6 Germany 4 Argentina (Match 1) 6 Argentina (Match 2) 6

Date

Dec. 1985 Feb. 1987 May 1987 Feb. 1988 Dec, 1988 June 1989 Jan, 1992 Oct, 1992 Oct, 1992

Opponents' mean Elo

2358 2354 2394 2453 2320'' 2425 2550 2433 2433

Kasparov score

3,5-4.5 7,0-1,0 5,5-0.5 4,5-1,5 4,5-1,5 4,5-1,5 3,0-1,0 4,0-2,0 5.0-1,0

's Kasparov's performance"

2310 2682 2786 2646 2513 2618 2743 2550 2710

Afore, These results, including the games played during these matches, can be retrieved from various publicly available databases, such as ftp://chess,onenet.net/pub/chess/Game-Databases/PGN/PIayers/Kasparov,pgn,gz. we used the lists published biannually by the FIDE (International Chess Federation), 'Median = 2646,

Athens, For the Elo points.

""One opponent was rated at 1850, which biased Kasparov's performance downward. Computed without this opponent, his perfonnance reaches 2564.

then be only 100 Elo points inferior to the level of his play under toumament conditions. An Elo rating of 2650 is very high; even among grand masters, only a half dozen players in the world equal or exceed that level,

RESULTS

We have summarized in Table 1 the scores for a number of matches that Kasparov played against national teams and the strong German team of Hamburg, each comprising leading play- ers with high chess talents. The opposing players, almost with- out exception, were masters or grand masters, Kasparov ob- tained results, rather consistently, close to those described in the previous paragraph. Playing without the opportunity for much look ahead, hence relying primarily on his ability to rec- ognize cues that signaled opponents' mistakes, Kasparov played at the level of a very strong grand master—as a matter of fact, often less than 100 points below his level in toumament play. There was no correlation between the number of oppo- nents (hence the average speed with which Kasparov had to play) and his estimated performance.

Given the strength of the opposition, Kasparov could not rely only on playing normal moves and waiting for opponents' mistakes. Preparation also played an important role in his per- formance (as it does in serious toumament play). In most ofthe encounters, Kasparov required the event's organizers to pro- vide him with about a hundred games of each of his opponents. He then studied these games with the help of a computer chess database program, to identify his opponents' weaknesses and strengths,' During the matches, he might then try to steer the

3, For a detailed description of Kasparov's preparation, as well as of other chess-related aspects of the simultaneous matches, see Kasparov (1993a, 1993b, t993c, 1993d, 1994),

play into types of positions that did not suit a particular oppo- nent, increasing the likelihood of the opponent's making mis- takes.

For example, faced with an opponent who does not like endgames (positions with few pieces remaining on the board), and the choice between a balanced middle game or a balanced (or even slightly worse) endgame, Kasparov would choose the latter altemative. Such knowledge of opponents' preferences allows him to limit his real-time search to particular types of positions, reducing the search space for moves. Two comments can be added. First, before his first match against Hamburg, as compared with the second one, Kasparov did not make as ex- tensive a study of his opponents' styles, which may explain in part his poorer performance, (For similar reasons, his perfor- mance improved in his second matches against the teams of France and Argentina), Second, although his opponents had also studied Kasparov's games, they were not generally able to use their knowledge of his play as effectively, because their own command of chess tactics and strategies was substantially inferior to his.

In view of the slight extent to which the lack of time for search lowered the quality of Kasparov's play in the simulta- neous matches, we conclude that memory and access to mem- ory through the recognition of clues is the predominant basis for his skill, and almost certainly for the skill of the other grand masters of the game.

These findings suggest that in extending knowledge of ex- pertise, it will be important to detennine whether recognition of pattems, based on accumulated knowledge, plays a dominant role (and analysis by search, although indispensable, a second- ary role) in other frequently repeated professional tasks, such as medical diagnosis and engineering design. It will also be important to discover how the balance of recognition and search depends on the severity of real-time limits that constrain the expert in different professional tasks.

54 VOL, 7, NO, 1, JANUARY 1996

PSYCHOLOGICAL SCIENCE

Femand Gobet and Herbert A, Simon

Acknowledgments—This research was supported by the National Science Foundation, Grant No, DBS-9121027; by the Defense Ad- vanced Research Projects Agency, Department of Defense, ARPA Order 3597, monitored by the Air Force Avionics Laboratory under Contract F33615-81-K-1539; and by the Swiss National Science Foundation, Grant No, 8210-30606, Reproduction in whole or in part is permitted for any purpose ofthe U,S, government. Approved for public release; distribution unlimited.

We are grateful to James Altucher, Harald Hofmeister, Stefan Kahrs, and Reinhard Knab for helping us to keep track of Kasp- arov's results, and to Adriaan De Groot and Pertti Saariluoma for helpful comments on an earlier draft.

REFERENCES

Calderwood, B,, Klein, G,A., & CrandaU, B,W, (1988), Time pressure, skill, and move quality in chess, American Journal of Psychoiogy, 101. 481-49J.

Chamess, N. (1981a). Aging and skilled problem solving. Journal of Experimental Psychology: General. UO. 21-38.

Chamess, N, (1981b), Search in chess: Age and skill differences. Journal of Experimental Psychology: Human Perception and Performance, 2. 467- 476.

Chamess, N, (1992), The impact of chess research on cognitive science. Psycho- logical Research, 54, 4—9.

Chase, W.G,, & Simon, H,A. (1973), Perception in chess. Cognitive Psychology. 4. 55-81.

De Groot, A,D, (1978), Thought and choice in chess (2nd ed,). The Hague: Mou- ton. (Original work published 1946)

Eio, A, (1978), The rating of chessplayers, past and present. New York: Arco, Ericsson, K.A,, & Staszewski, J,J. (1989), Skilled memory and expertise: Mech-

anisms of exceptional perfonnance. In D, Klahr & K, Kotovsky (Eds,), Complex information processing: The impact of Herbert A. Simon (pp. 235-267), Hillsdale, NJ: Erlbaum,

Gobet, F, (1993). Les mimoires d'unjoueur d'ichecs (Chess players' memories], Fribourg, Switzerland: Editions tJniversitaires,

Gobet, F. (t994). Has ckess players' rfiiit/ting changed in the last fifty years? Unpublished manuscript, Camegie Mellon University, Pittsburgh, PA.

Gobet,. F., & Jansen, P, (1994), Towards a chess program based on a model of human memory. In H,J, van den Herik, I,S. Herschberg, & J.E. Uiterwgk (Eds,), Advances in computer chess 7 (pp. 3S..60), Maastricht, Belgium: University of Limburg Press,

Gobet, F., & Simon, H, (!994a). Chunks in chess memory: Recall of random and distorted positions (Complex Information Processing Paper No, 518). Pitts- burgh: Carnegie Mellon University, Department of Psychology.

Gobet, F,, & Simon, H, (1994b), Templates in chess memory: A mechanism for recalling several boards (Complex Information Processing Paper No. 513), Pittsburgh: Camegie Mellon University, Department of Psychoiogy,

Goldin, S,E, (1979), Recognition memory for chess positions: Some preliminary research. American Journal of Psychology, 92, 19-31,

Hartston, W,R,, & Wason, P,C. (1983). The psychology of chess. London: Bats- ford,

Holding, D,H, (1985), The psychology of chess skitt. Hillsdale, NJ: Erlbaum. Holding, D,H,, & Reynolds, R.I, (1982). Recall or evriuation of chess positions as

determinants of chess skill. Memory & Cognition, 10, 237-242, Kasparov, G. (1993a, September). Simuls in my life. Chess Life, pp, 732-733. Kasparov, G, (1993b, October). Simuls in my life. Chess Life, pp, 802-803, Kasparov, G, (1993c, November), Simuls in my life. Chess Life, pp, 890-891, Kasparov, G, (1993d, December), Simuls in my lift. Chess Life, pp, 972-973. Kasparov, G, (1994, January), Simuls in my life. Chess Life, pp, 6-^. Lories, G, (1987), Recall of random and non random chess positions in strong and

weak chess players, Psychologica Betgica. 27, 153-159, Saariluoma, P. (1985), Chess players' intake of task-relevant cues. Memory &

Cognition. 13. 385-391. Saariluoma, P, (1989). Chess players' recall of auditorily presented chess posi-

tions. European Journal of Cognitive Psychology, I, 309-320. Simon, H.A,, & Chase, W.G. (1973). SkUl in chess. American Scientist. 61,

393-403.

( R E C E I V E D 11/28/94; A C C E P T E D 2/8/95)

VOL, 7, NO, 1, JANUARY 19% 55