The Role of Chess in Artificial Intelligence Research

Panel:

The Role of Chess in Artificial Intelligence Research

Robert Levinson (Chairperson) Computer and Information Sciences Applied Sciences Building University of California at Santa Cruz Santa Cruz, CA 95064 ( 408)459-2087 ARPANET:levinson@cis. ucsc.edu

FAX:429-0146

Feng-hsiung Hsu

IBM T.J. Watson Research Center PO Box 704 Yorktown Heights NY 10598

T. Anthony Marsland

Computing Science University of Alberta Edmonton Canada T6G 2Hl

Abstract

Our eminent researchers including John McCarthy, Allen Newell, Claude Shannon, Herb Simon, Ken Thompson and Alan 'lUring put significant effort into computer chess research. Now that comput­ ers have reached the grandmaster level, and are beginning to vie for the World Championship, the AI community should pause to evaluate the sig­ nificance of chess in the evolving objectives of AI, evaluate the contributions made to date, and assess what can be expected in the future. Despite the general interest in chess amongst computer scien­ tists and the significant progress in the last twenty years, there seems to be a lack of appreciation for the field in the AI community. On one hand this is the fruit of success (brute force works, why study anything else?), but also the result of a focus on performance above all else in the chess community. Also, chess has proved to be too challenging for many of the AI techniques that have been thrown at it. We wish to promote chess as the fundamen­ tal test bed recognized by our founding researchers and increase awareness of its contribution to date.

Jonathan Schaeffer

Computing Science University of Alberta Edmonton Canada T6G 2Hl

David E. Wilkins SRI International EJ227 333 Ravenswood Ave Menlo Park

CA 94025

Panel Summary

The factors that make chess an excellent domain for AI research include:

• Richness of the problem-solving domain.
• Ability to monitor and record progress accurately through competition and rating, because of its well­ defined structure.
• Chess has been around for centuries - the basics are well-understood internationally, expertise is readily available and is (generally!) beyond proprietary or nationalistic interests. Has been considered a "game of intelligence." Many players of the game feel men­ tally "stretched."
• Detailed psychological studies of chess playing exist. These studies suggest that human players use differ­ ent reasoning modes from those in current chess pro­ grams. Further, the reasoning modes are also used in many other problem-solving domains.
• Excellent test bed for uncertainty management schemes - the basis of most expert problem-solving. The well-definedness and discreteness of the game have led many to ignore this.

The above factors make chess a useful tool regardless of the strength of the current programs. Because of the success of the current methods there remains a vast arena of other methods that have not been explored. The most obvious lack is in the application and develop­ ment of machine learning techniques to chess, but other areas, including knowledge representation and compila­ tion, planning and control, also seem to be applicable. AI researchers should be encouraged to use chess as a test bed for their techniques, with the understanding that chess is not the end in itself. Chess may provide the avenue by which bridges may be built between cog­ nitive science, AI and connectionist modeling.

With the current and future battle for the World Human-Computer Championship the AI community should be made more sensitive to the issues involved and their bearing on intelligence research: Is search sufficient? How much detailed chess knowledge is re­ quired? How is this knowledge implemented and incor­ porated with search? We are fortunate to have a World Champion who promotes creativity over the chess board and is willing to face the challenge from computers head-on.

The members of the panel and the presentations have been designed to address these topics in a way that sup­ ports our objectives to make chess an important and respected AI tool in this new decade. Jonathan Scha­ effer will emphasize those areas of computer chess re­ search that have been ignored, because the approach has been a competitive/engineering one instead of sci­ entific. Feng-hsiung Hsu of the Deep Thought team will discuss the role of knowledge in current chess pro­ gramming and argue that more responsibility for the knowledge should be put on the machines themselves. Tony Marsland will present specific open research issues in computer chess that will require AI solutions. Robert Levinson will describe an alternative model of chess computation, a self-learning pattern-oriented chess pro­ gram ("Morph") whose knowledge is learned incremen­ tally from experience, without many examples being stored (and with little guidance about relevant fea­ tures). David Wilkins will provide balance to the dis­ cussion by pointing out the limitations of chess and claiming that Go is a better domain. He will also de­ scribe a new type of games tournament that prevents the human tailoring of evaluation functions and encour­ ages the use of learning and more robust approaches.

The timing for this panel is particularly good with the current World Championship having completed, a more powerful Deep Thought on the scene, a recent article in Scientific American [Hsu et al., 1990] and new books by Levy and Newborn [1991], and by Marsland and Schaeffer [1990].

Presentations

Computer Chess: Science or Engineering?

Jonathan Schaeffer

University of Alberta

Research into artificial intelligence using chess as the application domain has produced several important contributions to AI:

• The effectiveness of brute-force search. Chess has clearly demonstrated that simple, brute-force ap­ proaches should not be quickly discarded.
• Iterative search. Some of the ideas developed for alpha-beta search, iterative deepening in particular, are applicable to other search domains.
• The inadequacy of conventional AI techniques for re­ altime computation. No competitive computer chess program uses AI languages or knowledge representa­ tion methods. Why? They are too slow for a real­ time, high performance application.

Although these (and other, lesser contributions) have enhanced our knowledge, it is not clear whether the effort expended justifies the results obtained.

It is easy to question the usefulness of computer chess research. It is important to distinguish between com­ puter chess research and research using chess as a test bed. Unfortunately, the latter has evolved into the for­ mer. An entirely new field of "computer chess" has evolved, with the emphasis on chess performance and chess research - not generally of much interest to the AI community. There is a much deserved credibility prob­ lem here. The unfortunate correlation between program speed and performance encourages short-term projects (speeding up a move generator 10%) at the sacrifice of long-term research projects (such as chess programs that learn).

After over 30 years of work on chess programs, where are the scientific advances in:

• knowledge-based search algorithms? There has been some good work in this area, but none has progressed enough to be used in competitive chess programs. Alpha-beta simplifies the programming task, but the exponential search limits what can be achieved.
• knowledge representation and acquisition? These ar­ eas are of considerable importance to chess programs, yet the computer chess community has done embar­ rassing little research in this area.
• error analysis? While extensive error analysis has been done on search algorithms, little has been done to quantify errors in evaluation functions and how they interact with the search.
• tool development? With the right tool, work that might take days could be done in minutes. No tools are being developed to help build chess programs. For example, why isn't someone working on tools for defining chess knowledge?

If the community were committed to research, many of these problems would have been addressed by now. Sadly, much of the work currently being done on com­ puter chess programs is engineering, not science. For example, the engineering of special-purpose VLSI chips to increase the speed of a chess program only underlines the importance chess programmers attach to speed.

In my opinion, conventional computer-chess methods will yield little of further interest to the AI community. I believe they will be inadequate to defeat the human World Champion in a match for a long time to come. It is still very easy to set up a position for which the computer has no idea what is going on - even if you speed up the machine 1000-fold. The current computer chess work will only underscore the need for better ways of adding and manipulating knowledge reliably.

The defeat of the human World Chess Champion sooner rather than later will help artificial intelligence. This will help to re-establish chess as an ideal problem domain for experimenting with the fundamental prob­ lems of artificial intelligence, as elaborated more fully by Donskoy and Schaeffer [1989).

"Expert Inputs" are Sometimes Harmful Feng-hsiung Hsu

IBM T .J. Watson Research Center

Experience from the chess machine Deep Thought sug­ gests that inputs from chess experts, while generally useful , cannot be trusted completely. A good exam­ ple of this is Deep Thought's evaluation function. Sev­ eral changes by capable human chess experts failed to produce significant improvements and occasionally even affected the machine's performance negatively. Here, human experts, along with their expertise, introduced their own prejudices into the program. One way of solv­ ing this problem is to limit the type and the amount of expert inputs allowed into the program; in other words, having an almost "knowledge-free" machine. The avail­ ability of on-line high quality chess game databases makes this an attractive approach. Instead of having the value of, say, an isolated pawn set by human experts either explicitly or in functional form, one can simply tell the program that isolated pawns are important fea­ tures and statistical procedures, with some additional expert inputs, can then be used to decide the functional form and the proper weighting of the features in ques­ tion.

That more responsibility for knowledge should be placed on machines is consistent with recent efforts to handle the knowledge acquisition problem in expert systems and also in memory-based reasoning schemes where knowledge is generated statistically rather than relying on symbolic learning, abstraction or domain modeling.

Open Problems and Lessons for AI T. Anthony Marsland University of Alberta

Based on predicted advances in computer technology, particularly the faster speeds and increasing memory of low cost systems, it is reasonable to assume that within the next decade the World Chess Champion will lose an informal game to a computer, and within twenty-five years lose a 12-game match. The early losses will reflect more breaks in concentration at first and later a recog­ nition of the inevitable, as arose when trains started to out-pace runners. Although the defeat of humans by machines will be significant, it will mean neither the destruction of chess as a pastime and learning medium, nor the end of interest in computer chess per se. In­ stead it will focus attention even more sharply on pre­ cisely how and why humans can become so expert at selecting sound (often optimal) variations in seemingly complex situations, without resorting to the exhaustive techniques used by computer programs.

Some fundamental AI questions that will remain are:

• Given a patient and seemingly perfect teacher (that is a superior chess-playing machine), how should one use it to "teach" an AI-based learning program about strategies for playing chess (given that the rules of chess themselves are already perfectly known)?
• A related but perhaps simpler problem comes from the realm of endgame play. Given a perfect N-piece database holding an optimal move for each position (or perhaps only the length of the optimal sequence from that position, or even less, whether the position was won), develop a program that can deduce a sound set of rufes or strategies for playing the endgame per­ fectly (or at least better than any other expert).
• Given endgame positions which cannot be solved by search or databases alone, deduce a plan or playing strategy that will transform the position into a known (win/draw) state. In one class of positions the re­ maining pieces are held to few squares. Progress can only be made by a freein~ move that converts a short-term loss of material (or perhaps position) to the achievement of a later, more significant goal. Consider the Duchess-Chaos game [Frey, 1983, pp. 269-274), which is still thought to be beyond brute force search. Related examples abound, for instance giving up a passed pawn on one side of the board to win a pawn race on the other.
• Given a well-defined threat (for example mate) deep in the tree, identify un-examined moves at an earlier level along the current path that have the potential to deny the threat explicitly. This a form of dynamic re­ ordering of moves, but is also (if no potential denials exist) a good forward pruning criteria - providing evidence to abandon this line of play.

The first two projects rely on perfect domain knowledge and the availability of an un-tiring teacher to whom questions can be posed. The need for convergence to a solution within some arbitrary or unreasonably short time-frame will thus be eliminated. The learning mech­ anisms used will have the benefit of drawing on results obtained by exhaustive means. Even simple rote learn­ ing, for example, has its place in Artificial Intelligence. Scherzer et al. [1990) have shown how to use the moves made during a series of chess games to ensure that a poor move sequence will eventually not be replayed. By holding the computer's memory of played games in a hash table the information can be used to extend the depth of search during later play. In related work, the expert knowledge from an encyclopedia of games has been optically read into a computer which also cor­ rected the typographical computer to play through all known games, identify "losing moves" and by back­ tracking develop "innovations" that correct the flaws. It is not trivial work because it requires making a plausible re-construction from imperfect data, but Ken Thomp­ son has shown the way here [Marsland, 1987) Finally, once errors are found, a backtracking mechanism will be needed to find the best place earlier in the game-tree path to correct (avoid) the flaw that follows. The ap­ proach of recording, correcting and innovating appears to be fundamental to Artificial Intelligence.

The remaining problems are linked closely to formal or probabilistic pruning methods. Computer chess is computationally expensive enough that one can afford to expend considerable time eliminating parts of the search space by deduction. Over the years humans have developed techniques that allow them to reduce the search space through judicious use of forward prun­ ine; (that is, by temporarily abandoning certain vari­ atiOns) and either deducing by analogy that further consideration would be irrelevant, or (upon questioning the validity of the pruning) force reconsideration of the omitted lines. Pruning by analogy is a powerful general­ purpose tool and if developed satisfactorily for a per­ fect information game like chess would almost certainly be applicable to related decision-tree searches. The in­ tent is to be more selective about variations that are to be expanded fully. Methods like the null-move heuris­ tic [Beal, 1989], conspiracy number search and singular extensions [Anantharama.n et al., 1988] all do this by e:J~:panding non-quiescent lines of play. On the other hand, the more formal probabilistic methods [Palay, 1985] attempt to limit the width of search at any node by estimating the probability that a. better move exists in the moves that remain to be searched (Kozdrowicki and Cooper's [1973] so called "Fischer Set"). In effect this problem requires looking again a.t the method of analogies [Adelson-Velsky et al., 1975]. It is remark­ able that no significant improvement has been made to that method, despite the passage of 15 years. Not even attempts to implement simple forms of the idea in se­ rious chess programs. The fundamental work here is to determine how best to make the method of analogies pay for itself. In this era. of faster processors and par­ allel computation this must be a topic that is ripe for xploitation.

One important lesson for the AI community is the im­ portance of competitive testing and performance com­ parison of algorithms. In a. sense 20 years of computer chess championships have provided a. long-running se­ ries of experiments proving conclusively that progress has been made, identifying clearly those methods that have been effective and making a direct comparison from year to year possible. In principle theorem proving programs could be tested the same way, as indeed could language translation systems. These forms of compari­ son are standard for pattern recognition systems, why not for natural language understanding? In conclusion AI would benefit if more of its work were done on a direct competitive basis to identify more sharply those methods that are truly generally applicable.

Morph: An Adaptive, Pattern-Oriented Chess System

Robert Levinson University of California

Although chess computers now are competitive at master and grandmaster levels, that is where their re­ semblance to human players ends. Psychological evi­ dence indicates that human chess players search very few positions, and base their positional assessments on structural/perceptual patterns learned through experi­ ence. Morph is a computer chess program that has been developed to be more consistent with the cogni­ tive models.

The main objectives of the project are to demonstrate capacity of the system to learn, to deepen our under­ standing of the interaction of knowledge and search, and to build bridges in this area between AI and cognitive science.

The current model of chess programming came into its own in the 70's and early 80's and has been refined ever since [Slate and Atkin, 19771. The main character­ istic of the model is the use of brute-force alpha-beta minimax search with selective extensions for special sit­ uations such as forcing variations. This has been further enhanced by special purpose hardware. This model has been so successful that little else has been tried.

The alternative AI approaches have not fared well, perhaps because of the expense in applying the "knowl­ edge" that had been supplied to the system. When chess has been used as a test bed [Flann and Diet­ terich, 1989; Minton, 1984; Pitrat, 1976; Quinlan, 1983; Wilkins, 19821 only a small sub-domain of the game was used, so that fundamental efficiency issues that AI must grapple with have been largely unaddressed. However, we feel that there is a third approach that relies nei­ ther on search nor on the symbolic computation ap­ proach of knowledge-oriented AI. In what we shall call the "pattern-oriented approach," configurations of in­ teraction between squares and pieces are stored along with their significance. A uniform (and hence efficient method) is used to combine the significance in a given position to reach a final evaluation for that position. That such an approach is possible is evidenced by psy­ chological models of human chess play [de Groot, 1965; Pfleger and Treppner, 1987] .

Morph 1 is a. system developed over the past 3 years that implements the pattern oriented approach [Levin­ son, 1989; Levinson and Snyder, 1991] . It is not con­ ceivable that the detailed knowledge required to evalu­ ate positions in this way could be supplied directly to the system, thus learning is required.

To strengthen the connections with the cognitive lit­ erature the system's knowledge is to come from its own playing experience, no sets of pre-classified examples are given and beyond its chess pattern representation scheme little chess knowledge such as the fact that hav­ ing pieces is valuable (leave alone their values) has been provided to the system. Further, the system is limited to using only 1-ply of search. 2

System Design Morph makes a move by generating all legal successors of the current position, evaluating each position using the current pattern database and choosing the position that is considered least favorable to the opponent. After each game patterns are cre­ ated, deleted and generalized and weights are changed to make its evaluations more accurate, based on the outcome of the game. A more detailed summary of the design has recently appeared [Levinson and Synder, 1991].

1 The name "Morph" comes from the Greek morph mean­ ing form and the chess great, Paul Morphy.

2 Though nothing in the method except perhaps effi­ ciency, prevents deeper search.

Morph stores two types of pattern: Graph patterns which represent attacks and defends relationships be­ tween pieces and squares and Material patterns that are vectors giving the relative material difference be­ tween the players, e.g. "up 2 pawns and down 1 rook," "even material," and so on. Along with each pattern is stored a weight that reflects the significance of the pattern. The weight is a real number in [0,1] that is an estimate of the expected true minmax evaluation of states that satisfy the pattern.

Results with Morph There have been many encour­ aging signs in the three months since Morph was fully implemented, and some preliminary results have been published [Levinson and Snyder, 1991].

Relationship of Morph to other approaches The chess system combines threads of a variety of machine­ learning techniques that have been successful in other settings. It is this combination, and exactly what is done to achieve it, that is the basis for Morph's con­ tributions. The learning-method areas and their in­ volvement in Morph include genetic algorithms [Gold­ berg, 19891, neural nets (weight updating), temporal­ difference learning, explanation-based generalization (EBG), and similarity-based learning. To combine these methods some design constraints usually associ­ ated with these methods are relaxed. With genetic al­ gorithms, structured patterns rather than bit strings are used. In contrast to neural networks the nodes in Morph 's hierarchy are assigned particular seman­ tic/structural values. Temporal-difference learning is usually applied to methods with fixed evaluation func­ tion forms (in which the features are known but not their weights) but here the features change and the hi­ erarchical database organization produce atypical dis­ continuities in the function.

Once a chess graph is constructed from a game board, the semantics of the nodes and edges in the graphs are unknown to the system. The only information a pat­ tern contains as far as the system is concerned is the significance (weight) that has been attached to the pat­ tern , in no place after pattern creation do we special case pieces or edges. Such a syntactic approach to the learning of search knowledge is substantially different from many of the traditional symbolic AI approaches to chess and to the learning of control knowledge.

In summary, in addition to a unique combination of methods, what distinguishes Morph is:

• A uniform representation of search knowledge.
• A syntactic approach to playing and learning.
• An attempt to play a complete game of chess rather than a small subdomain.
• Rejection of a learning-by-examples framework for an experiential framework that is more cognitively­ inspired.
• Responsibility for feature discovery given to the sys­ tem.
• Non-reliance on search (though at some point small guided search may be incorporated, bringing us even closer to the cognitive model).

Chess Was Good for AI Research. David E. Wilkins

SRI International

Over the years, chess has proven to be a fertile ground for ideas and techniques that have spread to other areas of AI. These include database enumeration techniques [Bratko 1 1978], chunking [Campbell, 1988], search tech­ niques ~minimax, alpha-beta, iterative deepenin~), and the utility of information [Good, 1977] . Cons1dering the lack of funding for chess, it is significant that it has produced so many results.

Chess has been fertile because it provides a complex reasoning problem from a simple domain with a built­ in performance criteria. The simple domain permits research to progress with little initial overhead. Having a hostile opponent adds complexity to the reasoning. In many domains (natural language understanding comes to mind), progress can be hindered by lack of perfor­ mance criteria - it can be hard to tell whether the lat­ est thesis is an improvement on the current state of the art . Chess provides precise answers to performance questions.

However, hardware advances have made chess a less fertile ground for addressing the basic issues of AI. The game is small enough that brute-force search techniques have dominated competitive computer chess, and I see little AI interest in squeezing out the last few hundred points on the chess ratings, except for the psychological impact of having a computer beat the human world champion.

Obviously, many basic issues in AI are not naturally addressed in a game-playing environment and should be explored in other domains. These include commu­ nication, forming models of one's environment, sensor analysis and integration, and (perhaps) reasoning about uncertainty. In addition, real-world domains force AI researchers to address issues such as economy of scale, noise, realtime response, failed actions, novel phenom­ ena, and multiple agents - issues that can be ignored in chess.

Of the AI areas well-suited to a game-playing do­ main, there are better domains than chess. In partic­ ular, Go has all the advantages of chess but provides more complex reasoning and an even simpler domain. A successful symbolic Go program would have to plan, would have to use goal-directed search, would encourage machine learning, and would promote visual reasoning - all basic AI research issues that are now ignored in competitive computer chess.

Even better than Go, Barney Pell [1991] has proposed an event where programs compete against each other, but are only given a description of the game to be played at the beginning of the match. Chess is particularly well suited to this adaptation. One could, for example, have a competition using a chess board and pieces, where the match begins by giving the programs a declarative statement of how the pieces move, how they capture, the initial position, and what the objective of the game is. The programs would have to play this newly de­ fined game under time constraints. A longish series of games could be required. This would require machine learning and a robust symbolic problem-solving capa-

• bility that is not tailored to a specific game. For each new game, the programs would have to learn evaluation functions (if needed), learn what goals are advantageous to attempt, and learn heuristics or features for selecting moves. Brute force techniques would be disadvantaged by the lack of opportunity to fine tune both an evalu­ ation function and a quiescence search for the game at hand.