# The Historical Development of Computer Chess and its Impact on Artificial Intelligence

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/the-historical-development-of-computer-chess-and-its-impact-on-artificial-intelligence

- **Authors:** David Heath, Derek Allum
- **Published:** 1997
- **Topic:** Computer Science
- **Original:** https://www.aaai.org/Papers/Workshops/1997/WS-97-04/WS97-04-013.pdf
- **Pages:** 6
- **Annotations:** 13 comments in 13 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/the-historical-development-of-computer-chess-and-its-impact-on-artificial-intelligence

## Annotations

### Annotation 1 (page 1)

Beside the passage: “The Historical Development of Computer Chess and its”

**Annotation** by João Batalha (2016-05-10):

> This paper was published in the late nineties. Right before [Deep Blue beat Kasparov](https://en.wikipedia.org/wiki/Deep_Blue_versus_Garry_Kasparov) - the first time a computer defeated the reigning world chess champion. The advancements in computer chess were seen as a sign that artificial intelligence was catching up to human intelligence.
>
> In this paper the authors give an overview of the history of computer chess, the different approaches to the problem and its significance to the question of to what extent computers ‘think’ or be seen as intelligent.
>
> It’s also interesting to relate this paper to the recent [events in the game of Go](https://en.wikipedia.org/wiki/AlphaGo). How should we interpret the achievements of AlphaGo? How is it different than Deep Blue?
> ![Kasparov](https://www.dropbox.com/s/9hnxz55mp0oopkv/kasparov.jpg?dl=1)
> *Garry Kasparov, Russian Chess Grandmaster*

### Annotation 2 (page 1)

Beside the passage: “The minimax algorithm was first applied in a computer chess context in the landmark paper of Shannon. He also introduced the classification of chess playing programs into either type A or B. Type A are those that search by ’brute force’ alone, while type B programs try and use some considerable selectivity in deciding …”

**Annotation** by João Batalha (2016-05-10):

> ### MiniMax and Alpha-Beta pruning
>
> #### MiniMax
> MiniMax is a decision rule used in decision theory and game theory for minimizing the possible loss for the worst case scenario.
>
> **Example**
>
> Let’s say you are in the middle of a game, where you have 2 possible moves. Let’s also assume you have some way of evaluating how favorable the state of the game is for you at any point. Such algorithm takes in a state of the game and outputs a number from 1 to 10 (10 means you win, 1 means your opponent wins).
>
> Here is the game tree for such game:
> ![game tree](https://www.dropbox.com/s/f7rn3xczpgdf8wg/Screenshot%202016-05-09%2022.43.13.png?dl=1)
> In such tree the **MiniMax** value is $3$. Given that your opponent plays perfectly, that is the best you can do. You would perhaps like to get to node with the $8$, but if you decide to go to the right subtree, in the next move, your opponent will choose to go left (because he wants to get that number to be as low as possible) and you will end up with $2$.
>
> Now that you know the MiniMax value, you know which move to play.
>
> #### Alpha-beta
> [Alpha-beta](https://en.wikipedia.org/wiki/Alpha%E2%80%93beta_pruning) is an algorithm that seeks to decrease the number of nodes you have to evaluate when running the MiniMax algorithm in a search tree.
>
> For instance, in the previous example we evaluated 4 leaf nodes. However, we didn’t really have to evaluate the leaf node all the way to the right. As soon as we saw that the value of the third node was $2$, we knew we would be better off by going left, and therefore we don’t even need to look at that last node.
>
> ![Alpha Beta](https://www.dropbox.com/s/p9b7ay7vrlj0hv9/Screenshot%202016-05-09%2022.59.12.png?dl=1)

### Annotation 3 (page 1)

Beside the passage: “In this paper we review the historical development of computer chess and discuss its impact on the concept of intelligence. With the advent of electronic computers after the Second World War, interest in computer chess was stimulated by the seminal papers of Shannon (1950) and Turing (1953). The influential paper of …”

**Annotation** by João Batalha (2016-05-10):

> ### Chess as a search problem
> You can think of chess as a decision tree. At each turn you have a set of possible legal moves (on average you have 35 legal moves at your disposable).
> ![Chess as a decision tree](https://www.dropbox.com/s/64ezkksh8apr22t/Screenshot%202016-05-09%2021.57.43.png?dl=1)
> Each branch of the tree represents a move (e.g. *move Pawn from c2 to c4*). Each node represents a state of the chess board. Once you decide to go down one branch it’s time for your opponent to play. On average a game of chess has about 80 turns.
>
> Winning a chess game means navigating your way down this decision tree such that you get to a node where you checkmate your opponent (or he quits).

### Annotation 4 (page 1)

Beside the passage: “In this paper we review the historical development of computer chess and discuss its impact on the concept of intelligence. With the advent of electronic computers after the Second World War, interest in computer chess was stimulated by the seminal papers of Shannon (1950) and Turing (1953). The influential paper of …”

**Annotation** by João Batalha (2016-05-10):

> #### How big is the chess game tree?
> On average, the tree has a branching factor of 35 (this is the average number of of legal moves available to a player) and a height of 80 (number of turns in a game).
>
> A tree with such characteristics will have $35^{80}$ or roughly $10^{123}$ leaf nodes. That is a very, very big number. This makes pure brute force search intractable (it is estimated that there are about $10^{82}$atoms in the observable universe). That is the reason why you need *pruning* algorithms like Alpha-beta. These algorithms reduce the size of the tree you have to evaluate in order to make your next move.
>
> Even today, there is no program that can perfectly predict the outcome of any given chess game given the state of the board (assuming both players play perfectly). This means that unlike checkers or tic tac toe, chess remains an “unsolved” game.

### Annotation 5 (page 1)

Beside the passage: “The success of type A ’brute force’ programs using exhaustive search, minimaxing and alphabeta pruning, transposition tables and other search enhancements has had the unfortunate effect of minimising interest in the development of type B programs. The work of Simon and Chase (1973) established that most humans only …”

**Annotation** by João Batalha (2016-05-10):

> In the 1970s Simon and Chase performed a number of very interesting studies with the goal trying to understand how great chess players think.
> In one of their experiments they showed that when chess masters looked at a board for 5 seconds, they could reproduce it with enormous accuracy, while beginners could only recall very few pieces. This difference could not be explained by masters' greater memory, for, in randomized positions, the effect disappeared, with masters and beginners able to reproduce only a few pieces of the board. The conclusion was that Masters seemed to have an easier time recalling plausible board positions.

### Annotation 6 (page 1)

Beside the passage: “Introduction With the advent of computers after the end of the Second World War, interest in the development of chess playing programs was stimulated by two seminal papers in this area. The paper by Shannon (1950) remains even to this day to be central importance while the paper by Turing (I 953) is equally …”

**Annotation** by João Batalha (2016-05-10):

> - [Programming a Computer for Playing Chess by Claude E. Shannon (1950)](http://vision.unipv.it/IA1/aa2009-2010/ProgrammingaComputerforPlayingChess.pdf)
> - [Digital Computers applied to Games by Alan Turing (1953)](https://www.dropbox.com/s/9y75a3otxd46lti/Turing%2C%20Digital%20Computers%20Applied%20to%20Games.pdf?dl=1)

### Annotation 7 (page 2)

Beside the passage: “Turing’s paper (1953) highlighted the importance of only evaluating ’dead positions’ which have no outstanding captures. It is from this paper the term ’Turing dead’ is taken. Most chess programs search to a quiescent position (Turing dead) and then evaluate the position as function of the material balance and other …”

**Annotation** by João Batalha (2016-05-10):

> A *quiescent position / Turing dead position* is a position where there are no more tactical moves (e.g. moves where a piece is captured or there is a promotion) left to be made.
>
> In this context, evaluating a position essentially means giving it a score of how good it is for you.
>
> What this section is essentially saying is that as a general rule if you get to a position where there are still some outstanding moves that could drastically change the balance of the game you should keep searching deeper. This helps you avoid certain blunders that might result from having limits to how deep you can search (due to the size of the tree). For instance, maybe you got down to a position where you just captured a pawn, which could be interpreted as a good outcome, however if in the next move you opponent captures your queen, that might not be such a good outcome after all.

### Annotation 8 (page 2)

Beside the passage: “The historical evolution of computer chess programming techniques and knowledge can be conveniently discussed in three broad eras. Each era is characterised by its own particular developments, some of which can be directly linked to increased processor power, the availability of new hardware devices and others to …”

**Annotation** by João Batalha (2016-05-10):

> ![Computer chess evolution](http://www.frc.ri.cmu.edu/~hpm/book97/ch3/chess.plot.150.jpg)

### Annotation 9 (page 2)

Beside the passage: “Bernstein’s program played at a very elementary level and the first program to attain any recognisable standard of play was that of Greenblatt (1968). For a number of years this remained the most proficient chess program and played at an Elo strength of approximately 1500. It had carefully chosen quiesence rules to …”

**Annotation** by João Batalha (2016-05-10):

> The Elo rating system is a method for calculating the relative skill levels of players in games such as chess. Here are a few Elo ratings:
> - Beginner chess player: < 1400 (this is debatable)
> - Magnus Carlsen (World Chess Champion): 2851
> - Komodo 9 chess engine (one of the most powerful modern chess engines): 3340

### Annotation 10 (page 2)

Beside the passage: “Bernstein’s program played at a very elementary level and the first program to attain any recognisable standard of play was that of Greenblatt (1968). For a number of years this remained the most proficient chess program and played at an Elo strength of approximately 1500. It had carefully chosen quiesence rules to …”

**Annotation** by João Batalha (2016-05-10):

> A transposition table is a set of recently-visited positions in the game. This allows you to save some time by looking up positions in the transposition table instead of having to recompute them.

### Annotation 11 (page 3)

Beside the passage: “The second era of computer chess also saw more emphasis placed on the development of dedicated chess hardware. Typical of such developments was Ken Thompson’s chess machine Belle which won the ACM North American Computer Chess Championship in 1978. The special purpose hardware increased the speed of Belle enabling it …”

**Annotation** by João Batalha (2016-05-10):

> An end game database is a simply a database containing an array of pre analyzed chess endgame positions.
>
> KQKR is an end game position. It means King Queen vs King Rook
>
> ![KQKR](https://www.dropbox.com/s/frpfmoqi7om5exp/Screenshot%202016-05-10%2010.30.09.png?dl=1)

### Annotation 12 (page 3)

Beside the passage: “Iterative deepening is a useful device for allowing moves to be re-ordered prior to the depth being increased as well as providing a method for limiting search depth in response to time constraints. Originally introduced in 1969, it has become standard practice in brute force programs.”

**Annotation** by João Batalha (2016-05-10):

> In iterative deepening the program starts with a one ply search, then increments the search depth and does another search. This process goes on until we run out of time. In case of an unfinished search, the program always has the option to fall back to the move selected in the last iteration of the search.

### Annotation 13 (page 3)

Beside the passage: “The third stage, aptly named algorithmic by Donskoy and Schaeffer (1990), extends onwards from the mid 1980s to the current time. This has seen some considerable activity in the refinement of the basic tree searching algorithms used (see later). It has also seen the emergence of personal computers on a scale …”

**Annotation** by João Batalha (2016-05-10):

> They are referring to the 1996 game between Kasparov and Deep Blue. In 1997, Deep Blue would end up beating Kasparov.

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

The Historical Development of Computer Chess and its [Annotation 1]

Impact on Artificial Intelligence

David Heath and Derek Allum Faculty of Science and Computing,

University of Luton,

Park Square, Luton LU1 3JU United Kingdom david.heath@luton.ac.uk derek.allum@luton.ac.uk

Abstract

In this paper we review the historical development of computer chess and discuss its impact on the concept of intelligence. With the advent of electronic computers after the Second World War, interest in computer chess was stimulated by the seminal papers of Shannon (1950) and Turing (1953). The influential paper of Shannon introduced the classification of chess [Annotation 3] playing programs into either type A (brute force) or type B (selective). Turing’s paper (1953) highlighted the importance of only evaluating ’dead positions’ which have no outstanding captures. The brute force search method is the most popular approach to solving the chess problem today. Search enhancements and pruning techniques developed since that era have ensured the continuing popularity of the type A method. Alpha-beta pruning remains a standard [Annotation 4] technique. Other important developments are surveyed. A popular benchmark test for determining intelligence is the Turing test. In the case of a computer program playing chess the moves are generated algorithmically using rules that have been programmed into the software by a human mind. A key question in the artificial intelligence debate is to what extent computer bytes aided by an arithmetic processing unit can be claimed to ’think’.

Introduction With the advent of computers after the end of the Second World War, interest in the development of chess playing programs was stimulated by two seminal papers in this area. The paper by Shannon (1950) remains even to this day to be [Annotation 6] central importance while the paper by Turing (I 953) is equally influential.

The minimax algorithm was first applied in a [Annotation 2] computer chess context in the landmark paper of Shannon. He also introduced the classification of chess playing programs into either type A or B. Type A are those that search by ’brute force’ alone, while type B programs try and use some considerable selectivity in deciding which branches of the game tree require searching.

Alpha-beta pruning was first formulated by McCarthy at the Dartmouth Summer Research Conference on Artificial Intelligence in 1956. However, at this stage no formal specification of it was given, but it was implemented in game playing programs of the late 1950s. Papers by Knuth and Moore (1975) and Newborn (1977) have analysed the efficiency of the method and it has been proved that the algorithm returns exactly the same move as that obtained by full minimaxing or, alternatively, a move of the same value.

The success of type A ’brute force’ programs using exhaustive search, minimaxing and alphabeta pruning, transposition tables and other search enhancements has had the unfortunate effect of minimising interest in the development of type B programs. The work of Simon and Chase (1973) established that most humans only [Annotation 5] consider a handful of plausible moves. The power and ability of the chess grandmaster resides in his ability to select the correct subset of moves to examine.

In contrast the brute force programs search the entire spectrum of initial moves diverging from some given position referred to as the root. These initial moves fan out, generating a game tree which grows exponentially with depth. Apart from the work of Botvinnik et.al in recent years, there has been no significant progress in developing a type B strategy program which

63

From: AAAI Technical Report WS-97-04. Compilation copyright © 1997, AAAI (www.aaai.org). All rights reserved.

#### Page 2

would reduce the initial span of the search tree. The successful development of algorithms that introduced selectivity into the search engine, so that the program followed similar lines of thought to those of a chess grandmaster, would considerably reduce the amount of searching required.

Turing’s paper (1953) highlighted the importance of only evaluating ’dead positions’ which have no outstanding captures. It is from this paper the term ’Turing dead’ is taken. Most chess programs search to a quiescent position [Annotation 7] (Turing dead) and then evaluate the position as function of the material balance and other features. This evaluation function encapsulates chess-specific knowledge typically relating to pawn structures and king safety.

History

The historical evolution of computer chess programming techniques and knowledge can be conveniently discussed in three broad eras. Each era is characterised by its own particular developments, some of which can be directly linked to increased processor power, the availability of new hardware devices and others [Annotation 8] to algorithmic advances.

The boundary between each era is not always precise as it is sometimes not easy to draw a clear dividing line across a time continuum. Any such process is artificial. However, these broad historical eras are (Donskoy and Schaeffer 1990):

(i) 1st era (1950 - c1975)

(ii) 2ndera(c1975-c1985)

(iii) 3rd era (c1985 onwards)

The first pioneering era as stated above runs from 1950-c1975. Here there is a definite point at which this history commences, marked by the publication of Shannon’s paper and the advent of electronic computers. These computers, although originally regarded as revolutionary and powerful, had but a fraction of the computing power of the current generation of microprocessors. Indeed hardware limitations characterise the first era of computer chess development, requiring highly selective techniques in order to produce moves in an acceptable time. The earliest programs were, therefore, Shannon type B.

The first significant chess playing program was by Bernstein (1957) and ran on an IBM 704 computer, capable of performing approximately 42,000 operations per second. This was not a ’brute force’ program as it only selected the best seven moves for consideration using heuristics based on chess lore. Compared to the sophisticated brute force programs of today which generate the full span of moves at the root, this is a very limited range of moves.

The Bernstein program was built around the strategy of working to a plan. As it was incapable of doing a full width search due to time considerations, it selected its quota of seven moves for deeper analysis by seeking the answer to eight questions. Once the moves were selected, they were analysed to a search depth of 4 ply. The potential replies by the opponent were also selected on the basis of seeking answers to the same set of questions.

Bernstein’s program played at a very elementary level and the first program to attain any recognisable standard of play was that of Greenblatt (1968). For a number of years this remained the most proficient chess program and played at an Elo strength of approximately 1500. [Annotation 9] It had carefully chosen quiesence rules to aid tactical strength and was also the first program to [Annotation 10] use transposition tables to reduce the search space. However, the Greenblatt program also used an initial selection process to minimize the size of the game-tree as the computing hardware of that era was incapable of achieving the computing speeds of today. Again this program, because of its selectivity at the root node, falls into the first era.

The first program to achieve full width search and make ’brute force’ appear a viable possibility was Chess 4.5. This program was developed for entry into the ACM 1973 Computer Chess contest by Slate and Atkin, using the experience they had gained in programming earlier selective search chess programs. The techniques used by Slate and Atkin (1977) are still in use today although they have been refined and improved over the years. These standard techniques initiated what may be classed as the second technology era giving rise to programs typically searching to a fixed depth as fast as possible and then resolving the horizon problem by extending checks at the cutoff depth and considering captures only in a quiescence search.

64

#### Page 3

The second era of computer chess also saw more emphasis placed on the development of dedicated chess hardware. Typical of such developments was Ken Thompson’s chess machine Belle which won the ACM North American Computer Chess Championship in 1978. The special purpose hardware increased the speed of Belle enabling it to analyse 30 million positions in 3 minutes and search exhaustively to 8 or 9 ply in middlegame positions. It also had an extensive opening book. Belle won the 3rd World Computer Chess Championship in 1983, achieving a rating of over 2200 in 1980 and was the first program to receive a Master rating. It was for Belle that Thompson devised his first end game database, solving the KQKR problem and hence partially [Annotation 11] removing the perceived weakness at that time of computers in endgame positions.

In 1975 Hyatt commenced work on Blitz which was then entered in the ACM 1976 North American Computer Chess Championship. Initially Blitz was selective and relied on a local evaluation function to discard moves. However, the availability of the world’s fastest supercomputer, the Cray, enabled the program appropriately renamed Cray Blitz, to use brute force and in 1981 it was searching approximately 3000 nodes per second and consistently achieving six ply searches. This rate of analysis was improved by the use of assembly language and the availability of the Cray XMP computer with multiprocessing facilities, allowing 20,000 - 30,000 nodes to be searched per second in 1983.

The third stage, aptly named algorithmic by Donskoy and Schaeffer (1990), extends onwards from the mid 1980s to the current time. This has seen some considerable activity in the refinement of the basic tree searching algorithms used (see later). It has also seen the emergence of personal computers on a scale originally unenvisaged. The widespread practice of incorporating vast opening books and more cd-roms for end games. This current phase has been most fruitful and seen a considerable increase in the playing strength of chess programs to the point where the top commercial software programs are generally recognised as being superior to humans at speed chess and in sharp tactical positions. Under strict tournament conditions the most highly rated player of all time Kasparov has now lost a game, [Annotation 13] but not the match, against Deep Blue.

Move Ordering Techniques The previous section has outlined the historical development of computer chess. The transition to Shannon B type programs to Shannon A is not solely attributable to increased computing power. It also partly arose out of increased understanding of the alpha-beta algorithm which was subjected to deep analysis by Knuth and Moore (1975). Other techniques for increasing the efficiency of the search and pruning mechanisms also became more prominent at the beginning of the second era.

Producing a cutoff as soon as possible with the alpha-beta algorithm considerably reduces the size of the search tree. Consequently, move ordering is an important aspect of achieving maximum speed since, if we know the best move in a certain situation producing it early rather than late, will have beneficial results. The worst case is where the moves are examined in such an order as to produce no cutoffs, generating the maximum number of nodes to be analysed. This is the maximal tree which grows exponentially with depth, d, so that the number of nodes examined assuming a uniform branching factor, b, is given by b d. The best situation is where the moves are all well-ordered and provide immediate cutoffs, producing the minimal tree which, although it also grows exponentially with depth, is very much reduced in size by the cutoffs. In between these two extremes we have game trees generated by chess programs which, initially are unordered, but become progressivley more ordered as the depth of search increases.

Algorithmic developments and various heuristics are moving the programs closer to the minimal tree. This progressive improvement in reaching closer and closer to the minimal tree is borne out by Belle, which it is estimated came within a factor of 2.2 of the minimal tree, Phoenix within a factor of 1.4 and Zugzwang within an impressive factor of 1.2 (Plaat 1996).

Iterative deepening is a useful device for [Annotation 12] allowing moves to be re-ordered prior to the depth being increased as well as providing a method for limiting search depth in response to time constraints. Originally introduced in 1969, it has become standard practice in brute force programs.

The killer heuristic is another move ordering technique using information from the alpha-beta pruning algorithm to facilitate it. Whenever a certain move causes a cutoff in response to

65

#### Page 4

another move, then it is likely that it is able to refute other moves in a similar position. Such a move is a ’killer move’ and can be stored in a killer table so that it can be tried first in order to cause another cutoff. Captures and mate threats provide the commonest form of such ’killer moves’. In this context the null move can provide a list of the most powerful moves for the opponent and assist in the move ordering process.

The killer heuristic was described in detail by Slate and Atkin (1977) although it had been used in earlier chess programs. However, the benefits of this technique are controversial with Hyatt claiming an 80% reduction while Gillolgly observed no such significant reduction in size (Plaat 1996).

A generalisation of the killer heuristic is the history heuristic introduced by Schaeffer (1989). This extends the ideas of the killer heuristic to include all the interior moves which are ordered on the basis of their cutoff history.

Tree Searching Algorithms

Chess programs have used till now almost exclusively one of a variety of related algorithms to search for the best move. Constant improvements in the search algorithm have been sought to reduce the number of nodes visited, and thus speed up the program.

We now briefly describe a number of variations upon the alpha-beta algorithm. These depend on having some knowledge, albeit imperfect, of what is the most likely principal variation, the series of moves down the tree consisting of the best play.

The usual call to alpha-beta at the root node has an infinite window. In aspiration search some initial estimate of a likely value is made together with a window, or band of values this likely value could lie in. Clearly the success of this algorithm depends on the initial estimates. If a value is returned which lies outside the aspiration search window then a re-search needs to be done with full alpha-beta width. There is thus a trade-off to be made between a greater degree of pruning using the limited window and the amount of re-search which has to be done.

Principal variation search (PVS) is a variation of alpha-beta search where the search at a particular level is ordered according to some evaluation function. The node which is found to be the most likely member of the principal

variation is searched with a full width alpha-beta search, while others are searched with a minimal window where [3 = (x + 1.

With perfect move ordering, all moves outside those estimated to be part of the principal variation will be worse than those estimated to be on it. This is proved when the minimal window search fails low. Should this search fail high, a re-search has to be done with full alphabeta width.

A refinement on PVS is NegaScout. This is very similar to PVS and incorporates the observation that the last two plies of a tree in a fail-soft search always return an exact value.

There have been a number of further derivations of the so-called zero window alphabeta algorithm, which use a zero (actually unity) window at all nodes, unlike PVS which uses zero window only away from the principal variation. One of these is described by Plaat et al. (1996a) and has been given the name MTD(f). It relies on a large memory to hold a transposition table containing records of previous visits to nodes. We recall that in fact games like chess really take the form of graphs rather than trees, so that a particular board position might be visited from many different paths. The memory should be as large as feasible, since it serves to hold as many as possible of the results of visiting nodes.

Since the memory enhanced test algorithms operate with zero window, they, of necessity, need to do many re-searches. It is the use of memory to help speed up the production of results that makes these algorithms competitive in speed. Although Plaat et al. (1996a) claim their version is faster in practice than PVS, R. Hyatt, as he wrote in the rec.games. chess.computer Usenet newsgroup, in April 1997, still uses PVS for his Crafty chess program. The following pseudo-code from Plaat et al. (1996a) illustrates their MTD(f) version.

function MTDF(node-type, f,d)-+

g := f; upperbound := +o0; lowerbound :=-oo; repeat if g = lowerbound then

[3 :=g+ I; else

[3 := g; g:=ABWM(root,[3-1,[3, depth); if g < [3 then

upperbound := g;

66

#### Page 5

else

lowerbound := g; until lowerbound >-- upperbound;

return g;

The algorithm works by calling ABWM a number of times with a zero window search. Each call returns a bound on the minimax value. These bounds are stored in upperbound and lowerbound, forming an interval around the true minimax value for that search depth. When the upper and lower bounds collide, the minimax value is found.

ABWM (AlphaBetaWithMemory) is conventional alpha-beta algorithm which has extra lines to store and retrieve information into and out of a transposition table.

Interest has also been shown in the B* algorithm as well as those involving conspiracy numbers. These are more complex than algorithms involving alpha-beta searches, and seem to get closer to the Shannon B kind of algorithm where some expert knowledge of the game is programmed in to guide the machine.

Impact on AI and Philosophy

In the pioneering era, both computer chess and AI were emerging disciplines. At that early stage computer chess was regarded as a testbed for AI search and problem solving techniques. The early chess programs were primitive but are now much more sophisticated and have achieved spectacular results. However, as recognised by Donskoy and Schaeffer (1990), the dominantion of AI by computer chess has now changed and it is currently viewed as a small part of AI with its methods, identified primarily as brute force, regarded within the AI community as simplistic.

However, the impact of computer chess on AI can be gauged by the number of methods developed within the chess environment that are domain independent and applicable elsewhere. It is, for instance, undeniable that computer chess has made significant contributions to search techniques which find applications in other areas such as theorem proving and problem solving in general. It has also emphasised the development of special hardware to solve the chess problem, a viewpoint which is echoed in other areas of AI (Horacek 1993).

The computer scientists and AI enthusiasts that initiated the pioneering era of computer chess were partly motivated by a desire to investigate

the processes of human reasoning. They argued that if it was possible for computers to solve the chess problem, it must be possible for computers to tackle other difficult problems relating to planning and applications to the economy. This preoccupation with intelligence formed the core of Turing’s work, commencing with the creation of Turing machines and then the formulation of the Turing test which still remains of central importance in the AI debate today.

Turing himself worked in the period 1940-45 at Bletchley Park as an Enigma code-breaker. An indifferent chess player himself, he was, however, in the constant company of the best British chess players of that era, thus creating the environment and ideas for the final phase of his work. The luring test states that if the responses of a computer are indistinguishable from those of a human it possesses intelligence. Consequently, it can be argued that a computer playing chess possesses intelligence as, in many cases, its moves are identical to those of chess experts. This is the strong AI viewpoint.

It was precisely to repudiate these claims of intelligence that Searle (1980) put forward his famous Chinese Room argument against strong AI. Chess programs produce their moves algorithmically. Suppose another human being having no prior knowledge of chess per se, performs the same algorithms, does he also understand the game? The weak AI viewpoint is that computers lack any such intelligence or understanding. This viewpoint is supported by Penrose (1995) who cites an example of position in which Deep Thought blundered because of its lack of understanding of a particular position, despite being capable of deceiving us into thinking that it really has some chess intelligence.

Conclusion The strength of the top chess playing programs is continually increasing. In this paper we have reviewed the main techniques that have enabled programmers to achieve such a spectacular increase in playing strength commencing with the earliest exploratory programs to the sophisticated software of today. During this period, we have seen significant increases in processing power which, despite the prevalent von Neumann architecture of today, is still increasing in power. Consequently, we foresee

67

#### Page 6

the possibility of further increases in playing strength.

Future work will probably refme the traditional Shannon A type algorithms even more. For example, new avenues of research still exist on application-independent techniques of exploiting the fact that computer chess trees are really graphs (Plaat 1996b). However, there is limit on the extent to which this can proceed. The consideration of Shannon B type algorithms is an area requiring further investigation and development.

References

Botvinnik, M.; Cherevik, D.; Vladimirov, V., and Vygodsky, V. 1994. Solving Shannon’s Problem: Ways and Means, Advances in Computer Chess 7, van der Herik H. J, Hersberg I.S, and Uiterwijk, J.W.H.M.(eds) Maastricht, University of Limburg.

Donskoy, M.V and Schaeffer, J. 1990. Perspectives on Falling from Grace, in Computers, Chess and Cognition, Marsland, T and Schaeffer, J. (eds) New York, Springer Verlag.

Horacek, H. 1993. Computer Chess, its Impact on Artificial Intelligence, ICCA Journal 16(1):31-36.

Knuth, D.E, and Moore, R.W. 1975. An analysis of alpha-beta pruning. Artificial Intelligence 6(4):293-326.

Newborn, M.M. 1977. An analysis of alphabeta pruning. Artificial Intelligence 6:137- 153.

Penrose, g. 1995. in Shadows of the Mind, London, Vintage.

Plaat, A.1996. Research Re:Search and Research. Ph.D.diss., Dept. of Computer Science, Erasmus University.

Plaat, A., Schaeffer, J., Pijls, W., and de Bruin, A. 1996a. Best-first fixed-depth minmax algorithms, Artificial Intelligence 87:255-293.

Plaat, A., Schaeffer, J., Pijls, W., and de Bruin, A. 1996b. Exploiting Graph Properties of Game Trees, Proceedings of the 13th National Conference on Artificial Intelligence, Portland, Oregon.

Searle, J.R. 1980. Minds, brains amd programs, in The behavioural and brain sciences, Vol 3. Cambridge, Cambridge University Press.

Schaeffer, J.1989. The history heuristic and alpha-beta search enhancements in practice, IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(1):1203-1212.

Shannon, C.E. 1950. Programming a Computer for Playing Chess. Philosophical Magazine 41(7): 256-275.

Simmon, H.A and Chase, W.G. 1973. Skill in Chess. American Scientist, 6 l, 482-488.

Slate, D and Atkin, L.1977. Chess 4.5:The North Western University Chess Program, in Chess Skill in Man and Machine, P.Frey(ed.), 82-118. New York, Springer Verlag.

Turing, A. M. 1953. Digital computers applied to games, in Faster than Thought, Bowden, B.V.(ed). London, Pitman.

68

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/the-historical-development-of-computer-chess-and-its-impact-on-artificial-intelligence. More annotated papers: https://fermatslibrary.com/llms.txt
