Programming a Computer for Playing Chess. Shannon. Philosophical Magazine 1950


I feel myself approaching this paper more as scripture than a scientific paper.
  1. “Although perhaps of no practical importance, the question is of theoretical interest, and it is hoped that a satisfactory solution of this problem will act as a wedge in attacking other problems of a similar  nature and of greater significance.”  He proceeds to list a number of areas that may gain from this research.
  2. “…the proper procedure involves general principles, something of the nature of judgement, and considerable trial and error, rather than a strict, unalterable computing process.”
    1. How the hell did this guy know this back then
  3. <immediately following>”Finally, the solutions of these problems are not merely right or wrong but may have a continuous range of ‘quality’ from best down to worst.  We might be satisfied with a machine that designed good filters even though they were not always the best possible”
  4. Discusses evaluation functions
  5. Discusses brute-force minimax search, and that this is not feasible, and likewise a table lookup for all policies 
  6. Defines a strategy in the same way we do a policy
  7. “Although in chess there is no known simple and exact evaluating function f(P), and probably never will be because of the arbitrary and complicated nature of the rules of the game, it is still possible to perform an approximate evaluation of a position.  Any good chess player must, in fact, be able to perform such a position evaluation.”
  8. Discusses rules of thumb for chess, and how they can be combined to form an evaluation function
  9. Evaluation functions should only be performed for an entire variation (sequence of searches), to fully allow for inclusion of opponent responses
  10. Describes minimax search with cutoffs which use the evaluation function as the function
  11. Its interesting to see how some of the ideas here are totally still relevant today, and other points seem archaic.  For example, he goes to great pains describing how to record a move in a computer program, or check for available moves, which is now taken for granted and considered trivial.
  12. Shannon was able to checkmate a random opponent in 4 or 5 moves, usually
  13. Discusses search methods based on what masters do, which involve doing many plies when simple, but otherwise pruning extensively and only searching a small number of plies ahead
  14. Stochasticity can be introduced so the machine randomly chooses between moves that look nearly the best, in order to make decisions for the opponent more dificult
  15. “The chief weakness is that the machine will not learn by mistakes.  The only way to improve its play is by improving the program.  Some thought has been given to designing a program which is self-improving but, although it appears to be possible, the methods thought of so far do not seem to be very practical.  One possibility is to have a higher level program which changes the terms and coefficients involved in the evaluation function depending on the results of games the machine has played.  Slam variations [Some?-Transcription error? I dont think this is original] might be introduced in these terms and the values selected to give the greatest percentage of ‘wins’.”
  16. Argues that a machine that tries to play based on principles matching board configurations to analogous famous maneuvers “could not be constructed”:
    1. “Although there are various books analyzing combination play and the middle game, they are written for human consumption, not for computing machines.  It is possible to give a person one or two specific examples of a general situation and have him understand and apply they general principles involved.  With a computer an exact and completely explicit characterization of the situation must be given with all limitations, special cases, etc. taken into account.” 
  17. “It is not being suggested that we should design the strategy in our own image.  Rather it should be matched to the capacities and weaknesses of the computer.  The computer is strong in speed and accuracy and weak in analytical abilities and recognition.  Hence, it should make more use of brutal calculations than humans, but with possible variations increasing by a factor of 10^3 every move, a little selection goes a long way forward improving blind trial and error.”
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: