The Secret History of Chess Engines

Table of Contents

The Method
The Program
The Thinking Machine
The Philosopher
The Match
The Minimax March
Epilogue

Chess was seen as the crème de la crème of human cognition by some artificial intelligence researchers in the 1950's. They were looking at chess because they were using it as a base to test their models of human intelligence. This whole endeavor kicked off during and following WW2, when the U.S. Government subsided massive technology development to establish military and economic dominance. The development of electronics proceeded with the decisions made at the Pentagon.

The side consequence was more funding for AI research. These research papers often have 'sponsored by U.S. Airforce' on the bottom print. Everything that could bear on the question of developing military force was funded, and this included attempts at artificial intelligence, which could be used in the battle field. This funding stimulated the development of artificial intelligence as researchers could have a full ticket to modeling the human mind.

The Method

---

Claude Shannon - pioneer of information theory. By Unknown author - Tekniska Museet of Sweden, Item 43069 via Flickr, CC BY 2.0,

Claude Shannon was a pioneer of formulating how information can be quantified, stored or transmitted. Bits were the basic unit of information. Shannon published a paper in 1950 detailing instructions for creating a chess machine. This involved two suggestions: the minimax algorithm, and heuristics. The minimax algorithm involves assuming the opponent will make the best response to our response. They minimize our advantage, while we maximize our advantage. A evaluation function is used to evaluate the final position of a line. The line with the best evaluation is chosen using the minimax algorithm.

Heuristics involves programming simplifying principles to reduce the search space. Shannon mentioned the possibility of programming patterns into the computer like the Greek Gift Sacrifice. Shannon thought that heuristics would lead to a "much more efficient program". The search space of chess is too large. Shannon was the one who calculated the famous 10^120 number for the estimate of the amount of possible chess games:

Thus a move for White and then one for Black gives about 10^3 possibilities. A typical game lasts about 40 moves to resignation of one party. This is conservative for our calculation since the machine would calculate out to checkmate, not resignation. However, even at this figure there will be 10^120 variations to be calculated from the initial position. A machine operating at the rate of one variation per micro-second would require over 10^90 years to calculate the first move!

The chess problem was simply a stepping stone to bigger things. Shannon considered the problem of building a chess machine to be a "ideal one to start with" as chess is defined exactly and has a discrete structure that fits well with bit operations, that it has just the right difficultly level, and that it could clarify the nature of human thought. Shannon wrote out a shopping list of things he ultimately wanted from AI:

(1) Machines for designing filters, equalizers, etc.
(2) Machines for designing relay and switching circuits.
(3) Machines which will handle routing of telephone calls based on the individual circumstances rather than by fixed patterns.
(4) Machines for performing symbolic (non-numerical) mathematical operations.
(5) Machines capable of translating from one language to another.
(6) Machines for making strategic decisions in simplified military operations.
(7) Machines capable of orchestrating a melody.
(8) Machines capable of logical deduction.

The Program

---

Alan Turing - founder of computer science. By Elliott & Fry, Public Domain.

Alan Turing is the founder of computer science. In 1936, he created the idea of the 'Turing Machine'. It is a model of computation that operates on symbols. It contains a infinitely long tape that is divided into sections which contain one symbol per section. A operator head has the ability to read symbols, write symbols on other empty sections of tape, or replace symbols in a section of the tape. There are fixed rules which govern how the operator reads and manipulates symbols. The Turing Machine can convert an input into an output through a series of read and write operations which are governed by fixed rules. It can solve problems that are written in a symbolic way, e.g. math questions. So if we can rewrite the process of finding chess moves as symbols that can be operated on, then we've got a way to create a chess machine.

Turing and mathematician David Champernowne created the very first chess program called Turochamp in 1948. Turing was interested in the possibility of machines being able to replicate human thinking. Turochamp used minimaxing and had an evaluation function based on various factors like mobility and safety. It calculated a move for the player, and one move for the opponent, with extra moves provided if the position was not yet a 'dead position', meaning that exchanges had not been completed. It never successfully got programmed physically onto a computer as the code was too complex for the computers of the time. It lost a game against computer scientist Alick Glennie in 1952. The program was hand simulated by Turing and Champernowne, meaning that they performed the calculations of the program.

The Thinking Machine

---

Herbert Simon and Allen Newell - AI pioneers, 1958, Courtesy of Carnegie Mellon University.

Herbert Simon and Allen Newell were pioneers in the field of AI. Allen Newell was a computer scientist with an interest in cognitive science. He went on to develop the SOAR cognitive architecture to model cognition as a whole. Herbert Simon was a interdisciplinary scholar who worked in a wide range of areas. One was economics, where he created the theory of 'bounded rationality' meaning that people make judgements based on heuristics/principles that are not perfect but are satisfactory.

Computers were known back then as devices that did math fast. After using computers to try to formalize the behavior of officers to warnings in air defense systems, the duo decided to utilize computers more broadly. They decided they could replicate the human mind on a machine. Simon predicted in 1957 that a computer would be the world chess champion by 1967. He reflected that his predictions were wrong in detail but right in principle. He said he wanted to convey the magnitude of what could be done. That computers didn't have to be just for doing math.

This all took place within the context of the Cognitive Revolution. This is a term for the rejection of behaviorism in favor of positing that the mind utilized information processing mechanisms. Behaviorism considered only the body's output as suitable for study and rejected the idea of mental phenomena. An icon of the birth of the cognitive revolution was the 1956 MIT symposium where various researchers from the fields of artificial intelligence, psychology, and linguistics presented their ideas. Noam Chomsky brought the idea of transformational grammar, George Miller the idea of short-term memory. Simon and Newell were also there and presented their Logic Theorist program.

Simon and Newell first started with well structured tasks – theorem proving and chess playing. These tasks were the very beginning. Simon said you don't climb a mountain all at once, you start with first steps. Their goal was to simulate human thought processes, not just create useful machines. They viewed the mind as computational, working like a machine in steps. This was borne out by the general atmosphere of the times. The philosophy of Associationism viewed the mind's operation as composing of elements that were linked in different ways such as time and similarity. A element would automatically cause another associated element to spring into mind.

This was built on a long history of the philosophy of empiricism in western philosophy. Descartes said that ideas were atomic, Kant said that concepts were made up of rules. In 1943, McCulloch and Pitts had proposed that the function of neurons in the human brain could be to implement logic gates. This was the first mathematical model of a neural net.

The NSS program ran on the JOHNNIAC computer built by the RAND corporation. Computer History Museum, California, by Andrew Lih. CC-BY-SA-2.0.

In 1956, Newell, Simon and computer scientist Cliff Shaw developed the Logic Theorist program which was able to prove 32 theorems from the famous Principia Mathematica. They further built on this with the General Problem Solver, a program which used means-end analysis to work towards solving any type of problem with the same problem solving method. It works by applying heuristics to symbols which represent the problem and recursively operating to get the symbol string closer to the goal state. They sought to emulate human thought processes, which they represented through getting college students to record what went through their minds when solving problems.

Newell, Simon and Shaw also created the NSS program. This was a chess engine based on heuristics, which is what Claude Shannon said would be needed for more efficiency, as opposed to purely brute force search. In chess, one heuristic might be counting material points to judge the strength of a position. This is too simple by itself, so more heuristics/goals can be added. The NSS Program used goals like Center Control. The Center Control module proposed central pawn moves and moves which attacked or defended those squares. The goals were organized in value of importance.

In contrast to the other engines of the time, the NSS evaluated positions by assigning values for each goal which gave a vector (e.g. 4,5,1 may represent values for King Safety, Material Balance and Center Control as an example). An acceptable move was found by minimaxing across the vectors, comparing vectors through looking at the goal with the highest priority such as King Safety. If King Safety was equal for two moves then the second most important goal was used as a tiebreaker. Different positions may involve different goals depending on what's possible in the position.

For Simon and Newell, the act of chess is so complicated, a solution must be constrained by the task, not by the idiosyncrasies of the solution method. What this means is that the solution may be similar for both a computer and a human due to how large the search space is.

The group made some rough calculations comparing two previous programs. One was the Los Alamos MANIAC I which performed with a 6x6 board without bishops or moves like castling to reduce computational complexity. It looked 2 ply ahead, 2 moves for White and 2 for Black. This made for approximately 20^4 = 160,000 lines. The program did beat a weak human player in one of the three games it played. The other engine was a full 8x8 created by Alex Bernstein and ran on an IBM 704. It had specialized plausible move generators which contained the sort of heuristics that the NSS had such as development, attacking pieces, king safety etc. That reduces the amount of total lines considered to about 2,500.

They pointed out that heuristics simplify the search space and that humans were found to visit far less than 100 positions in their mind when considering a move. Humans only look at a few candidate moves. So this was the way forward. Make the moves considered more plausible through simplifying principles. If the two engines above were taken to be roughly equal in performance, then "selectivity is a very powerful device and speed a very weak device for improving the performance of complex programs", as Simon wrote in their paper. He said that the right kinds or selectivity could be found by correcting any errors that showed up.

NSS: The history of chess programs is an example of the attempt to conceive and cope with complex mechanisms. Now there might have been a trick - one might have discovered something that was as the wheel to the human leg: a device quite different from humans in its methods, but supremely effective in its way, and perhaps very simple.

Such a device might play excellent chess, but would fail to further our understanding of human intellectual processes. Such a prize, of course, would be worthy of discovery in its own right, but there appears to be nothing of this sort in sight.

The Philosopher

---

Hubert Dreyfus was a philosopher at MIT. He read the works of Heidegger, and considered 'Being and Time' as the most important philosophical work of the 20th century. Heidegger opposed Husserl's view of the world as consisting of a subject with an object presented to it, the Cartesian and representational view of mind which had been the major line of thought in western philosophy headed by Descartes. Heidegger viewed humans as being in the world, their actions caused by dispositions caused by situations instead of passively receiving stimuli which is then rationally thought over.

Dreyfus was hired as a consultant at RAND corporation to advise about AI programs. The corporation was created to co-ordinate operational research and the decisions of research and development. Simon and Newell also worked at the RAND corporation. Dreyfus published his paper 'Alchemy and Artificial Intelligence' in December 1965.

The AI community hated it. They despised this philosopher having the audacity to question the idea that human thought was composed of rules and operations. They also didn't like his tone in the paper.

Hubert Dreyfus (Left). Photographer: John Christian Haugeland II. Copyright holder: Joan Doris Wellman. - CC BY-SA 4.0.

Dreyfus said that the attempts to replicate human intelligence wasn't getting anywhere. He said that the NSS program that Simon, Newell and Shaw created was weak. It got defeated by a 10 year old. He said that they were making ridiculously optimistic forecasts for AI and that they didn't honestly report their lack of progress. Chess players didn't use heuristics. Dreyfus pointed to the verbal report of a player that Simon described. The player noticed that the rook was under attack, and then 'counted out' suggestions, various ways of solving the issue.

Dreyfus wasn't convinced that the reason a player knows that a rook was hanging was due to the player looking at every possible relation between pieces like a computer. He thought it was due to fringe consciousness - elements on the fringe of consciousness framed the conscious experience implicitly. He referred to the vague awareness that we have of other peoples faces when scanning for a friend in the crowd. We are not very aware of them, but they frame our conscious experience by allowing our friend to be recognized. He said the the player 'zeroed in' on the hanging rook, there were no heuristics used, the rook was just noticed. And if rules were used subconsciously to find the rook, then why does the player need to consciously deliberate alternatives for saving the rook. Why does the answer not just pop up in consciousness, having been done subconsciously.

Hubert Dreyfus: In fact, in its few recorded games, the NSS program played poor but legal chess, and in its last official bout (October 1960) was beaten in 35 moves by a ten-year old novice. Fact, however, had ceased to be relevant. Newell, Shaw, and Simon's claims concerning their still bugged program had launched the chess machine into the realm of scientific mythology.

---

While their program was losing its five or six poor games--and the myth they had engendered was holding its own against masters in the middle game--Newell, Shaw, and Simon kept silent. When they speak again, three years later, they do not report their difficulties and disappointment. Rather, as if to take up where the myth had left off, Simon published an article in Behavioral Science announcing a program which will play "highly creative"
chess end games involving "combinations as difficult as any that have been recorded in chess history" [36:429].

That the program restricts these end games to dependence on continuing checks, so that the number of relevant moves is greatly reduced, is mentioned but not emphasized. On the contrary, it is misleadingly implied that similar simple heuristics would account for master play even in the middle game. Thus, the article gives the impression that the chess prediction is almost realized.

Dreyfus pointed out that attempts to translate text into different languages failed. The dictionary approach didn't work because ambiguity wasn't accounted for. The machine needed to have human knowledge to resolve sentences like 'The box was in the pen', as pointed out by Bar-Hillel. 'Pen' could refer to an enclosure for children or a writing utensil from a computer's perspective. Computer's also couldn't recognize a common pattern. Letters in presented in different styles could not be recognized through defining letters in terms of lists of features.

Dreyfus said that the General Problem Solver program did not match the thought processes of the students which were recorded by Simon and Newell. One student applied an operation simultaneously, while the machine did it in two steps. Another went back and changed an earlier step while the machine continued in another direction. Redoing the process from a previous stage requires knowing the appropriateness of such an action, otherwise this would result in constantly redoing the process at every stage. The machine did not grasp the problem as a whole. It did not look at it globally.

Hubert Dreyfus: Ironically, research in cognitive simulation is only example of so-called intelligent behavior which proceeds like the GPS. Here one finds the kind of muddling through and ad hoc patching up characteristic of a fascination with surface structure--a sort of tree-climbing with one's eyes on the moon. Perhaps because the field provides no example of insight, some people in cognitive simulation have mistaken the operation of the GPS for intelligent behavior.

It took nine months for Dreyfus' paper criticizing AI to be published.

Simon called it "garbage". He also called it "false pretenses" for Dreyfus to have his paper published under the RAND name, as he "had no technical background".

Hubert Dreyfus: The fears of those who tried to prevent the distribution of the paper were justified. It was the first detailed criticism of work in CS, and it sparked debate all over the world-at Novosibirsk in the USSR, in Japan, and among the top scientists at large companies such as Bell Telephone. But it was not seriously discussed at the principal AI centers such as M.I.T. and Carnegie-Mellon.

Indeed, at M.I.T. the rejection was so total that students and professors working on the robot project dared not to be seen having lunch with me without risking getting into trouble from their superiors. When Joesph Weizenbaum, the only professor who had any doubts, wanted to discuss his concerns with me, we had to meet at his home in the suburbs.

Herbert Simon didn't like what Dreyfus said about their NSS program. He said that Dreyfus said some "really nasty stuff about chess because he was looking at our NSS chess program at RAND and he knew that a ten-year-old had beaten it".

The Match

---

Mac Hack VI was programmed in MIDAS on a PDP-6 computer. Mac Hack VI is playing in a tournament against humans (the moves were sent by teletype to the tournament site a few miles away and vice versa). January 21st, 1967. Credit: MIT and The Computer History Museum.

In 1966, the Mac Hack VI chess engine became operational. It did not go the way of heuristics. It used some algorithmic innovations. It used transposition tables to store results of past calculations which cut the search effort by 50% in some cases. The computer didn't need to redo calculations. It also utilized Alpha-Beta pruning to reduce redundant calculation. Alpha-Beta works by immediately cutting the search in a branch which is found to contain a line that leads to a unavoidable loss if the opponent makes the right move, or vice versa. We assume the opponent will do best play. This is a logical way of programming a computer and is fundamental to how modern chess programs work. It is why a computer sometimes promotes to a rook instead of a queen, because it found the rook promotion first. If the rook promotion is winning it does not bother to calculate the queen promotion line. Mac Hack VI played in a couple of human tournaments, managing to win some games. It obtained a rating of around 1500 USCF.

AI researcher Seymour Papert challenged Dreyfus to play against the computer:

Dreyfus lost.

Then he was mocked for losing.

The Bulletin of the Association of Computing Machinery’s Special Interest Group in AI said 'A Ten Year Old Can Beat the Machine–Dreyfus: But the Machine Can Beat Dreyfus'.

Papert reflected "I organized the famous chess match. That was beautiful".

Dreyfus published a letter about how his comments were taken out of context, he never said that chess computers would never beat a human, only that it hadn't at the time.

Simon then replied in another open letter to him:

Dear Professor Dreyfus, I was a little touched by your recent letter to SIGART, protesting the comment on your defeat by MacHack, Greenblatt’s chess program. A writer who employs the juxtaposition “Alchemy and Artificial Intelligence” can hardly plead ignorance of the uses of rhetoric, or cry “foul” when an editor implies something by juxtaposition of a chess score with a quotation from one of the players. Such writer could not even, in good conscience, protest a return in kind of rhetoric that he began five years ago, and has continued, with escalations, ever since.

What are the facts? A man who exhibited great zest in writing that a “ten-year-old novice” had beaten a particular chess program was himself beaten, and beaten roundly, by MacHack.

---

You see, the real humor in the Dreyfus-MacHack game, as any chessplayer who plays it over will tell you, is not that you were beaten. The humor is that the Greenblatt program exhibited in this game many of the same human failings that you did (failing to see obvious impending mates, for example) and still clobbered you—by the skin of its teeth.

Underneath Simon's letter, the editor of the bulletin attached a message:

(The following is extracted from a set of notes prepared by Prof. Seymour Papert of the MIT Artificial Intelligence Group.)

1.5 Computers Can’t Play Chess.
1.5.1 Nor Can Dreyfus.

The Minimax March

---

But chess computers got stronger not by trying to replicate the human mind, but by searching a vast amount of moves. Simon said that programs should become more selective in their heuristics, and would need less search. But the opposite happened.

The ease and simplicity of the minimax algorithm meant that it was easy for amateur hobbyists to create their own programs. The simulation of the human mind was a forgotten dream at this point. Newborn, Monroe, Scoreboard at the 10th ACM North American Computer Chess Championship in Detroit, Michigan.

Meanwhile computers got better because of greater processing speed. This meant that the minimax algorithm got better with each passing year. Other algorithmic developments took place. Iterative Deepening was introduced in Chess 4.5 in the 70's. This meant that instead of searching to a fixed depth, it would repeat the search incrementally with increasing depths. So first a 1 ply search, then a 2 ply search etc. This may seem odd, but it helps with making the alpha-beta algorithm more effective with its cut offs as the best move selected at a certain ply is often the best move at a later ply.

Quiescence searching made sure that a line was extended if tactical and exchanging moves could still occur. This would help the computer be more tactically aware and get past the horizon effect. In the 90's Fritz implemented the null move algorithm. If the position was still winning if the opponent got a free move, then the computer would look no further. This cut down the lines that needed to be searched, increasing Fritz's efficiency. The evaluation function was refined through experimentation. Different weighing of different factors could be tested to which one worked best.

IBM unveiled Deep Blue which could search 200 million positions a second. Kasparov defeated it in 1996. But Deep Blue got the better of him in the 1997 rematch. Kasparov's defeat to the robotic mind of Deep Blue was hailed as the triumph of the machines.

But humans don't search 200 million positions a second. And they don't numerically value positions or implement sophisticated algorithms.

Ultimately this was a engineering feat. The AI community felt pressure to deliver results during the doldrums period of the 70's and 80's when the attempt to encode human common sense had failed.

So they created some stronger chess engines to look productive. Mikhail Donskoy (Lead developer of 1974 World Computer Chess Champion Kaissa) and Jonathan Schaeffer (Lead developer of 1974 World Checkers Champion Chinook) referred to this time as AI's "fall from grace".

The original purpose of the chess engines were lost. The quest to replicate the human mind had failed.

Epilogue

"Now there might have been a trick - one might have discovered something that was as the wheel to the human leg: a device quite different from humans in its methods, but supremely effective in its way, and perhaps very simple. Such a device might play excellent chess, but would fail to further our understanding of human intellectual processes."

Herbert Simon later proposed that chunked productions were responsible for chess expertise. A particular unit of pieces (a chunk) was stored in memory as a player gained experience. These units had a common link, proximity, defense, attack etc. As a player gained more experience their 'chess vocabulary' would increase. They would have a larger amount of chunks in memory. Each chunk was connected to a production with suggested a move. Players would then evaluate a new position given from these productions, with the amount of chunks held in memory to be around seven plus or minus two - the famous short term memory buffer posited by Miller.

Hubert Dreyfus on the other hand said chunks would require that experts have several moves spring into mind in every position, even though experts can play rapidly without needing to evaluate such a large amount of moves. He also questioned the idea of chunks being functionally significant. The meaning of a configuration of pieces is not rigidly defined, but dependent on the context of the position which is recognized as a whole.

Dreyfus proposed that expertise is a global, holistic process. It is a intuitive way of 'knowing how' that does not use rules. Hubert and Stuart Dreyfus's five stage model of expertise starts with learning abstract rules and ends with intuitive responses to concrete cases. The road to expertise starts with learning context-free rules e.g. move rooks to open files. Then a greater awareness of situational awareness is developed. People then develop a sense of perspective where certain features stand out. Proficiency involves far more situational awareness and intuitive responses, but conscious deliberation is still required. Expertise is intuitive and rapid, without deliberation.

Dreyfus endorsed the philosophy of Merleau-Ponty who did not believe in mental representations. He believed that learning to do things came about by interaction with the world. Stimuli would cause responses. This is known as the intentional arc. The intentional arc involves seeking a maximal grip between the body and the environment - it is a tendency to reduce deviation from an optimal state.

Dreyfus connected this with Walter Freeman's attractor model of neuronal function. Stimuli would create a neural response that seeks a minimum energy state, like a ball rolling down a hill. Dreyfus pointed out that feed-forward neural nets can result in behavioral responses that don't require an internal representation of the world. The input causes changes in the connection of a prior state which has been developed through past experience. Learning 'know-how' is a matter of adjusting behavior to a optimal state, which is not held as an internal representation but is the result of the body-environment interaction. The world can serve as it's own representation. He used the example of an expert hitting a tennis ball. The expert no longer needs to consciously try to figure out what to do, it happens naturally. They return the tennis ball with the right position and angle appropriate to the opponent. This forms a gestalt, a complete whole. This outcome is not represented in the mind, but is a product of a process which reduces deviation from a satisfactory gestalt.

AlphaZero and Maia use neural nets. Does this mean they are intelligent? The answer is no because they do not have bodies. Dreyfus discusses the question of how humans learn to understand the world in similar ways. The answer is due to similar innate brain structure, having bodies which allow affordances/interactions with the world in the same ways, and having similar standards of satisfaction, which are the ways of behaving that humans gravitate towards.

Hubert Dreyfus: All this puts disembodied neural-networks at a serious disadvantage when it comes to learning to cope in the human world. Nothing is more alien to our life-form than a network with no up/down, front/back orientation, no interior/ exterior distinction, no preferred way of moving, such as moving forward more easily than backwards, and no emotional response to its failures and successes.

---

In our world the cards are stacked to enable entities that share our embodied form of life to learn to cope in a way we find intelligent, while leaving disembodied creatures looking to us hopelessly stupid.

Sources

• Programming a Computer for Playing Chess, Claude E. Shannon, March 1950
• Chess-Playing Programs and the Problem of Complexity, Allen Newell, J. C. Shaw, H. A. Simon, October 1958
• Alchemy and Artificial Intelligence, Hubert L. Dreyfus, 1965
• Perception in Chess, William G. Chase, Herbert A. Simon, 1973
• Skill in Chess, Herbert A. Simon, William G. Chase, 1973
• Unedited Interview about History of AI at CMU from 1955-1985, Herbert A. Simon, 1985
• Mind Over Machine, Dreyfus, Hubert L; Dreyfus, Stuart E, 1986
• Perspectives on Falling From Grace, Mikhail Donskoy, Jonathan Schaeffer, 1990
• Robotics' Growing Role in Cognitive Science, Hebert A. Simon, 1998
• Intelligence without representation – Merleau-Ponty’s critique of mental representation, Hubert L. Dreyfus, 2002
• Machines Who Think A Personal Inquiry into the History and Prospects of Artificial Intelligence, Pamela McCorduck.–2nd ed., 2004
• Is Consciousness Entirely Physical?, Hubert L. Dreyfus, Robert Lawrence Kuhn Interview
• Is chess the drosophila of artificial intelligence? A social history of an algorithm, Nathan Ensmenger, 2012
• Optimizing Chess: Philology and Algorithmic Culture, Max Larson, 2018