Chess Skill in Man and Machine by Peter W. Frey
Consider the following quotes from the text "Chess Skill in Man
and Machine", 1978 edition, Edited by Peter Frey. [In Frey's book, each chapter is written by a different person or people,
who are referenced here.] Most of the authors looked to their own experience as strong chess players to enhance their research
efforts.
At the time this book was written, there was much dissatisfaction among computer chess researchers
with the rate at which improvements were being made in the performance of the top computer chess programs.
There was a lofty goal of making a computer play chess at an "expert" level, and a curious guess that the "key" to achieving
this was understanding how humans played chess.
Many authors/ researchers were casting about for ideas, looking at how the human mind
works, investigating new algorithms, and speculating about what it would take to make chess programs play at an expert level.
Today's chess programs have now surpassed the performance ratings of the top players, but they play chess
in ways that are much different than how a human plays chess. The style of thinking (of the researchers in 1978) can still
be applied today to the efforts to find new approaches to playing the game of chess.
It seems that the authors of chess playing computer programs should
take a look at how humans play chess, according to Neil Charness:
p.34-35 "Should a computer be more like a man when it comes to playing
chess? ...Perhaps the clinching argument in favour of the first line of thought [a more exact simulation of human chess players
by computers] is that if your goal is to develop a program which can beat the best human player, a guaranteed solution is
to have the program simulate human playing methods almost exactly."
Focusing search efforts on the most promising lines of play seems to be the difference between winning
and losing a chess game. If we could find a better way to focus our search efforts on the most promising lines, we might
be able to play a better game of chess. Of all the concepts discussed in this Proposed Heuristic paper, I think
that this one is the one I would like to emphasize above any other:
p.37"In the final analysis, perception seems to be the key to skill in chess... The difference
between two players [when one defeats the other in a game] is usually that one looks at the promising moves, and the other
spends his time going down blind alleys."
Peter W. Frey thinks that we should write evaluation functions
for our computer chess program that adapt to the position currently on the board:
p.61 "Our general experience in computer chess over the past few
years seems to indicate that future chess programs will probably benefit from evaluation functions that alter as the general
chess environment changes."
Chess programs have evolved over time - it seems that introducing
new ideas to the field of computer chess makes old programs obsolete after only a year, according to Slate and Atkin. It also
seems that these two chess program authors wanted their evaluation function to fill the search tree with positions that were
relevant, interesting, or likely:
p.83 "If there is anything more useless than yesterday's newspaper,
it is last year's chess program... [Chess 3.6, Slate and Atkin's out of date computer program] was an old-fashioned program
that depended on the searching of large trees filled with unlikely positions. It was poorly documented and not very modular.
The instructions that formed the evaluation function were nearly unreadable. Figuring out how our old program worked was like
deciphering hieroglyphics, and adding anything to it was like writing in ancient Sanskrit. One glance at the listing told
us that the program had outlived its usefulness. It had taught us how not to write a chess program."
It seems that organization and structure are helpful when it comes
to modifying a computer chess program:
p.84 "In terms of its organization, CHESS 3.6 was a mess. Not only
was it difficult to modify the evaluation function - it was difficult even to find it in the listing of the program."
The idea for the "future mobility" of chess pieces (in this case,
1 move into the future) and re-using information from previous positions was used by Slate and Atkin in a limited way in their
program CHESS 4.5:
p.85 "Data base [section title] For each position in the look-ahead
tree, CHESS 3.6 maintained certain data related to that position that were useful for evaluation and move generation. The
largest part of this was a table specifying which pieces attacked which squares. This table suffered from two major problems:
it had to be regenerated from scratch for each position in the tree, and it had no clean, simple format that might have more
general utility. In [CHESS] 4.5, we chose a simple data format which could be used for many purposes, including the construction
of attack tables which could be incrementally updated as the tree search stepped from node to node. Incrementally updating
means altering only those aspects of positional information that actually change due to a move on the board. ...much
time is saved if the changes are computed rather than the entire tables."
The CHESS 4.5 evaluation function was primitive and not based on thoroughly rigorous chess principles.
It seemed to work, regardless, and was fast.
p.93-94"The CHESS 4.5 evaluation function... adds several easily computable factors together. The
dominating term is material. The remaining terms are rules of thumb designed to give the program a vague positional sense.
Rather than expressing some theoretically rigorous chess principles, these factors merely improve somewhat over 'aimless'
moves. The design motive for the evaluator appears to be a self-fulfilling prophecy: we knew that it was going to be primitive
and would thus depend heavily on tree searching. To do such deep tree searching would require that the evaluator do its work
quickly, and so it wouldn't have the time to do anything clever, and thus would have to be primitive."
Some of the top-rated commercial chess programs today claim to be able to evaluate several million
positions per second using state-of-the-art hardware. This was the state-of-the-art in the mid 1970's:
p.101"On a CDC 6400 CHESS 4.5 processes from 270 to 600 nodes (calls
to EVALU8) per second."
The Control Data Corporation 6400 central processor was a slower,
less expensive implementation with serial processing
- rather than the 6600s parallel functional units.
All other aspects of the 6400 were identical to
the 6600.
Careful testing of features in the evaluation function seems to
be one of the keys to success:
p.113 "The features of its [CHESS 4.5] evaluation function and tree
search were determined often by the whim of the moment. Certainly they were not the result of a comprehensive, steady, and
coherent research plan designed to exhaust the potential of brute-force tree searching. ... In reality, the program has been
a part-time effort, with long stretches of inactivity punctuated by occasional panicky spurts of attention."
Slate and Atkin had this to say about improving the evaluation function
of a chess playing computer program:
p.115 "We conjecture that the better [the evaluation function] already
is, the more it will benefit from a deeper search. If this is true, then we should work on improving the quality of evaluation
functions, rather than on small increments in search efficiency."
Building more intelligence into a chess program is a proposed route
to a stronger program. The intelligence may take many forms.
p.116-117-118"...two major problems in chess programming: the difficulty
of specifying chess specific knowledge to the program and of representing this knowledge internally... The speculative model
of chess-program evolution sketched above is only one of several possible routes to stronger programs. We believe that
the common element of any such efforts is that they involve the addition of more intelligence to chess programs. This intelligence
may take many different forms... In any case, the whole effort to build more intelligent chess programs is just beginning"
Russell M Church and Kenneth W Church (apparently father and son)
look at the rapid style of chess called "speed chess" and describe their attempt to create a chess program whose goal is to
play chess at a fast time control.
What is interesting is that Church senior and junior
have investigated a way to choose a move in a game of chess without doing any search. The proposed evaluation looks at the
future mobility of the chess pieces, involves looking at which pieces are safe on which squares, and attempts to count how
many moves it would take for the pieces to reach certain squares on the chessboard. What the Church duo seem to be implying
is that the evaluation or estimated winnability of a particular position depends not on the present locations of the pieces
on the board, but instead on the positions that can be forced from this 'starting position'. Traditional searching is one
way this can be determined, while a 'back-of-the-envelope' probing can also be useful. It does not take much imagination to
see that the research performed by the Church team can be extended to apply to concepts involving positional pressure
of the pieces. The Church team seems to get hung up on trying to determine the effectiveness of pins and other tactical traps.
These concepts (whether or not a piece is truly pinned) might only be determined for certain by additional search.
The heuristic proposed in this paper first came to my mind after considering, and then modifying,
a heuristic proposed by the Church team for determining the 'remote power' of chess pieces. The heuristic described
below is effective yet time-consuming to calculate. What is the fastest, most effective way we can estimate
the remote power of chess pieces?
p.153"A somewhat slower but more general routine, fills a board with values representing the minimum
number of moves on an occupied board required by a piece (excluding pawns) to move from a given origin square to any destination
square. This calculation is not continued in a given direction when the piece reaches an occupied square or one on which it
would be en prise."
The authors seem to think that the key to achieving true skill in
machines is understanding how humans play chess. This understanding will produce programs that are goal oriented rather
than a trial-and-error approach. A great concept.
p.156 "It is our belief that the speed and quality of decisions
by people and computer programs are improved when goal-oriented rather than trial-and-error procedures are used... We are
convinced that if one wants to design a computer program to play chess successfully, one must simulate the thought process
of strong players... better programs to play chess can be written if they are based on human thought processes."
The final section in Chess Skill in Man and Machine
was written by Eliot Hearst. The following background information is taken from the biography of Dr. Hearst posted
at chessgames.com. Dr. Hearst was a professor of psychology
at Indiana University for twenty-six years, later held a professorship at Columbia, and now is on the faculty at University
of Arizona in Tucson. He became Marshall Chess Club champion in 1951, while still a teenager, having already become a master
the year before when he won the New York State Championship as an eighteen-year-old. He also holds the distinction of defeating
[former American world champion] Bobby Fischer in the final round of the October 1956 Rosenwald Tournament, just three rounds
after Fischer had played his "Game of the Century" against Donald Byrne. His ideas are still relevant and profound nearly
30 years after first written.
Hearst laments that the academic research field of computer chess suffers from an unusual side
effect not usually found in academia. The commercial computer chess products are in fierce competition with each other for
sales and for boasting rights, and this often prevents a healthy exchange of ideas commonly found in other disciplines:
p.170"There is one feature of computer chess that is less often explicitly mentioned as a goal or
motivation for those working in the field - perhaps because it seems less defensible or noble than the other goals, at least
to programmers working in an academic setting. This aspect concerns the aura of competition that pervades the field. Competition
among the designers of different chess programs is keen, perhaps as keen as among human beings competing in serious tourneys
[tournaments], and this factor may in some cases account for why technological refinements, discoveries, and gimmicks [heuristics?
JLJ] are often not well publicized by their originators... Why should one worker in computer chess have to spend months or
years rediscovering what another group had implemented some time ago?... The publication of a book like the present volume,
composed of contributions from several different groups of workers, may reflect a growing awareness that more cooperation,
rather than more competition, will benefit everyone concerned."
Eliot Hearst contemplates the lack of swift progress in the
improvement of 1970's computer chess programs. He is of the opinion that improving the skill of chess playing computers
requires a new set of ideas:
p.176 "In summary, the past achievements of computer chessplayers
are relatively small... If any success is to occur, a new or different approach appears to be needed."
Hearst argues that studying how humans make chess moves is important
in creating chess playing machines:
p.186 "Most workers in the field of computer chess agree that one
should strive for a program that selects its moves in ways as similar as possible to the manner in which a human being makes
such decisions. For example, Newell, Shaw and Simon [74] argued that 'any information-processing system - a human, a computer,
or any other - that plays chess successfully will use heuristics generically similar to those used by humans.' Botvinnik [18]
stated that we must make the machine 'in our image'; 'the program must be modeled on human thought processes.' "
Hearst declares that something must be done to make the chess playing computer smarter at what it
does, 'in one form or another'.
p.193"I [Eliot Hearst] agree with de Groot's comment that 'incorporating experience into the program,
in one form or another, is not only indispensable but is the very core of the simulation problem,' whether one is involved
with expert-level thinking in chess or in some other field."
Hearst notes that machines need to be encouraged to find good moves when tactical possibilities are
not present. The concept seems to involve long range planning and the measurement and focus on the distant pressure that
the chess pieces are capable of producing, either offensive or defensive in nature.
p.195"Although they will not commit serious blunders, machines rarely are able to produce constructive
moves in positions in which direct threats and tactical possibilities are absent. In such positions, a strong chessplayer
will attempt to reinforce or eliminate his own weak points, and to take aim at his opponent's; long-range planning is the
predominant theme, rather than direct attack. The delicate maneuvers that develop - the 'tacking' for small advantages - may
seem boring to the uninitiated but are a major aspect of competition between strong human chessplayers."
Hearst would favor the re-use of information gained on prior moves:
p.198 "...attempts to transfer information gained on prior moves
for use in subsequent analysis, seem intuitively worthwhile..."
Hearst argues that more human-like qualities should be put into
the software to play better chess, but perhaps it is the man's ability to use heuristics to guide or focus the search
for the best move and to evaluate the strengths and weaknesses of positions:
p. 200 "Perhaps our chances of success in producing a computer chessmaster
in the twentieth or twenty-first century depend on how much more 'man' we can put back into the machine - but this time in
psychological rather than physical form."
