APPROACHES TO CHESS by Peter Frey
PART 1 HOW HUMANS PLAY
What does a chess master have that you and I do not have? Many people have been interested in determining the psychological attributes of a chess champion. The strong chess player is often thought of as a formidable calculating machine with incredible memory capacity. Edgar Allen Poe denigrated the game because he thought it involved boring calculations rather than creative thought. Scientist have examined these ideas in a systematic way and have discovered some unexpected answers.
Around the turn of the century, the French psychologist, Alfred Binet, the father of the IQ test, investigated the memory capacity of many of the noted chess players of his time and was surprised to find that their memory span was essentially the same as that of less skilled chess players. Several Russian psychologists examined the IQ scores of their top ranking players in the 1920’s and found that the range of intelligence for this group mirrored the range of intelligence in the general population. Thus, the early systematic investigations indicated that highly skilled chess players are neither especially bright nor gifted with “photographic” memories.
A Dutch psychologist, Adrian deGroot, a skilled player himself, made a detailed study in the 1930’s and 1940’s of the cognitive processes involved in chess play. He traveled around Europe and across the Atlantic with most of the top players of his day. Using a battery of testing procedures, deGroot tried to discover what made the highly skilled player different from average ones. One of his tests involved complicated middle game positions which the chess players studied and then selected the best move. deGroot had his subjects report their thoughts as they worked on these problems. He carefully recorded each verbal protocol and later made a systematic analysis of each player’s thinking process. After several years of data collection, deGroot summarized his findings by presenting average values for several important measures. Top players and average players were very similar in the quantitative aspects of their chess thinking. They considered a similar number of future positions (about 35), had equivalent depths of maximum look-ahead (about 6 and 1/2 plies), looked at an equal number of moves of the first level (about 4), and made the same number of fresh starts (about 3). The top players were not considering hundreds of positions nor were they doing more or deeper analysis than the average player. The only clear difference seemed to be in their choice of what to analyze and their final move selection.
deGroot noted that all of his subjects were silent just after a new position was presented, and no matter how much he urged them to talk, this pause occurred. He surmised that some important nonverbal process was taking place when the player first began his analysis. Later research confirmed this hypothesis. A Russian experiment demonstrated by eye movement analysis that subjects made a global visual inspection of the position when it was first presented. This perceptual processing was apparently the crucial point where the strong and the average players began to diverge. Subsequent research by deGroot indicated that strong players can remember the location of almost all the pieces when they are briefly shown a complicated middle game position while average players remember far less. This advantage disappears if the pieces are randomly placed on the board. The superior memory is therefore chess specific. The most plausible interpretation of this finding is that experienced chess players develop special perceptual skills such that they “see” chess pieces in meaningful patterns. In the memory task, they remember 6 or 7 piece groupings while inexperienced players remember 6 or 7 pieces. Subsequent research in this country has confirmed this interpretation.
The current theory of chess skill is that player develop, through years of practice, a very specific set of perceptual skills in which chess pieces are perceived in meaningful patterns rather than as individual pieces, and they also learn what to do with these patterns to produce winning chess positions. Learning to play chess is like learning to read. For the child, writing consists of many unfamiliar letters mixed in confusing patterns all over the page. For an experienced reader, however, the letters are almost unnoticed. Instead, the page is perceived in terms of words and phrases, with the latter part of each sentence processed only briefly, because the reader had anticipated the general idea in advance from the context of the passage. Research indicates that a very similar process occurs in chess. The experienced player sees a familiar terrain populated by frequently encountered piece groupings. He knows what the patterns connote and what is required for skillful play. Chess skill is a perpetual skill, not a process of computation. Careful move-by-move analysis is used only as a confirmation that the opponent does not have a tactical shot which might refute the intended line of play.
Chess may have arrived in Russia as early as the Eighth century, about a hundred years before it reached Western Europe. That Eighth century Russians traded with the Arabs is not in dispute, and people who traded with the Arabs around that time tended to learn chess. By 1000 A. D., Christianity was established in Russia, and the church there immediately made a concerted and unsuccessful effort to stamp out chess playing. 16th century travelers to Russia reported that people of all classes played chess there. In the rest of Europe, chess playing was confined to the nobility until the 18th century. When the Mongols invaded Russia, they brought their own form of chess with them. The Mongols hat gotten chess via the Eastern route, so they had a number of their own variations. As a result, in certain parts of Russia, the modern rules did not take hold until the 20th century.
PART 2 HOW COMPUTERS PLAY
A computer is a general purpose machine which can manipulate numbers and symbols under the control of various sets of instructions. When computers were first designed they were used t calculate artillery trajectories and for similar military purposes. It was not long, however, before many peace-time uses were developed, including applications in banking, accounting, and bookkeeping. Very few people, however, envisioned that a computer could be more than a fancy calculator. Even fewer people would have taken you seriously if you had suggested that a computer could play a decent game of chess. Much has changed since those early days, and computers are now seen as a powerful tool for aiding humans in complex decision-making tasks. In future years, computer systems may be developed which are sufficiently reliable and “intelligent” to take on important high level roles. Current research on computer chess provides a challenging laboratory for serious work on these developments.
It is not easy to program a computer to play chess. Over the past several decades , techniques have been developed through thoughtful, painstaking effort which have proven to be valuable. Almost all of the modern chess programs are variations on a single theme. The computer represents the playing board as an 8 by 8 array of numbers and represents the pieces by assigning a positive or negative digit to each type of piece. Legal moves can be generated by using a special set of instructions for each piece, which examines the current state of the board and applies appropriate offsets to determine the potential move squares. The details of these procedures vary from one program to another and re often tailored to the special characteristics of each machine to maximize efficiency.
Move selections involves three major modules. One module generates a look-ahead tree of possible continuations. In most programs, the look-ahead is exhaustive. That is, all moves are considered of the first level; every possible reply to each of these is then considered; every counter-reply is examined etc. The number of end points grows exponentially as the depth of the search process increases. For this reason, chess programs, even on huge, million dollar machines, can look ahead only a limited distance. When a computer misses an important continuation in its move planning process, programmers describe the difficulty as a “horizon effect”. Chess programs consider each continuation as far as it is practical in the allotted time and then assign a numerical value to each end position by using the second and third modules.
The second module is called the evaluation function. It applies simple chess ideas to analyze specific board positions. Thus, it considers the relative material for the two sides, their relative mobility, control of the center squares, king safety, pawn structure, etc. and then assigns a value to that position. The more sophisticated the evaluation function is in terms of chess knowledge, the greater the amount of processing time which is required for each end position in the look-ahead search. Therefore, a clear trade-off exists between the number of positions examined and the complexity of the evaluation process.
The third module is called the quiescence function. It considers each end position to determine whether additional captures or checking moves might dramatically influence the evaluation. It uses a complex capture analysis or does further searching to insure that the value assigned is accurate, since it would be foolish to examine a position and assign a value without taking into consideration that the opponent can capture your queen on the very next move. The evaluation function and the quiescence function require efficient program code, since they are executed millions of times during a game. In addition, these tow modules are the real “brains” of the program and therefore reflect the programmers chess sophistication.
The final decision on which move to make is based on an important theoretical idea developed in the 1940’s -- the minimax strategy, in essence, the programs choose that move which minimizes the opponent’s maximum potential gain. In practice terms, the machine assumes that each player will select the move at choice point which maximizes his value at the end points. This is determined by taking the values at each end point and “backing them up” the look-ahead tree. If positive values are good for the machine and negative values are good for the opponent (the usual convention), the machine selects the pathway at even-ply choice points (the opponent’s turn) which leads to the minimum valued end point, while selecting at odd-ply choice points (the machine’s turn) the pathway that leads to the maximum valued end point. By successively maximizing and minimizing the machine can pick a set of future moves which represents best play for both sides and then choose its initial move accordingly.
Over the years, the process described has above has been refined in many ways, especially in terms of how efficiently the computer conducts the search process. Experienced chess programmers talk about alpha-beta algorithm, the killer heuristic, the importance of searching captures first, the iterative search, transposition tables, and many other techniques for improving their programs. To learn about these, however, you will need to visit your bookstore and obtain one of the books that are now available on computer chess. If you come to enjoy your contests against the computer, as we expect you will, a bit of reading about your computer opponent may be fun and rewarding. If you learn more about how the machine thinks, you may be able to use this knowledge against it. Happy hunting.
Excerpt taken from CHESS 7.0 BY LARRY ATKIN User Manual.