Sleep 6: Can A Computer Really Play Winning Chess?

3 July, 2020

ON HIATUS

Computer Chess article from the May-June 1976 edition of the Creative Computing Magazine.

Transcript available
[Music] Helping you fall asleep. I'm John Chidjie. You can follow me on the Fediverse at [email protected], on Twitter at John Chidjie, all one word, or the network at engineered_net. Sleep is supported by you, our listeners. If you'd like to support the show, you can do so via Patreon, with a special thank you to all of our patrons, and a special thank you to our Patreon Silver Producers Mitch Bilger, John Whitlow, Joseph Antonio, Kevin Koch, Oliver Steele, and Shane O'Neill, and an extra special thank you to our Gold Producer known only as R. Visit engineer.network/sleep to learn how you can help. Thank you. So now that that's out of the way, let me talk to you. Just for a few minutes, can a computer really play winning chess? Back in the 50s, when Elvis was making Like a Hound Dog, Victory at Sea was NBC's top prime time hit, and shockly demonstrated the first transistor at Bell Labs. Some optimistic researchers speculated that computers really ought to be able to think. At that time, it was generally accepted that one good measure of thinking was playing a good game of chess. I'm sure that many chess experts and amateurs wouldn't disagree with that view today. Chess is the intellectual game, par excellence. There is no random chance involved, just sheer intellect. In a situation so complex that neither player can hope to understand it completely, but sufficiently structured that each can hope to outthink the other. Even after 200 years of exhaustive play and thorough analysis, the field is still ripe for further exploration and development. Thus, if one could devise a successful chess program, one would seem to have penetrated to the core of human intellectual endeavour. Three researchers in particular delved into this problem with great fervour. They were, of course, Alan Newell and J. C. Shaw at Rand Corporation, along with Herbert Simon at Carnegie Institute of Technology, now Carnegie Mellon University. During their efforts to produce a good chess-playing program, they discovered a number of things. First of all, it's not that easy. Indeed, it may not be possible at all to produce a program that can play at the master level. Why not? First, and the reason that chess-playing programs are so good as a measure of thinking, is that the possible number of moves is on the neighbourhood of infinity, give or take a bit. Actually, Claude Shannon estimated that there are something like 10^120 possibilities, which doesn't help us too much since there are only 10^16 microseconds in a century. Consequently, you can't store all of the possibilities in memory of any kind, nor could you possibly analyse them all. The approach therefore is to teach the computer how to play chess, evaluate possible moves, formulate a playing strategy. To teach a computer, it is probably helpful to first evaluate how a human plays chess. Most players have either learned from experience or been taught by another player or book that beginning game moves are best made following proven approaches. These openings minimize one's vulnerability and hopefully create a strong position for the attack to be launched in the middle part of the game. These relatively few openings, about 20 or so, follow reasonably predictable courses of action for perhaps the first 7-10 moves. Thus, the opening of the game can largely be played from memory, human or computer. The middle part of the game gets a bit hairy. Moves aren't nearly as predictable, and most players adopt a strategy of evaluation of each move by considering its consequences after several more moves on both sides. This is, of course, what separates the men from the boys, so to speak, with the expert player able to accurately evaluate the consequences of a move 12-15 moves later, while most novices are able to look ahead only 2 or 3 moves. Different players put different importance on various pieces and positions, however there seems to be general agreement that at least 5 factors should be considered in evaluating a move – mobility, value of attacked piece, vulnerability and value of attacking piece, king safety, and overall board configuration. Clearly you don't just tell the computer these things and then say "OK, now play". If the middle game is hairy and the end game is downright mind-boggling, when each side has maybe six or seven pieces left, sides of the board have largely lost their meaning and configurations are possible that may never have occurred before, a strong attack can lead to an impossible defence in the span of just eight or nine moves. In short, heuristics and textbook approaches begin to break down and each player tends to develop his or her own individual strategy. What does one do with a computer program at this point? Good question, with as many answers as there are programmers. The ACM and some other groups have been running computer chess tournaments for years. David Levy, an international master, regularly beats the winning computer at the end, although the play is getting awfully good. Many of these can programs are written on big, read gigantic machines of the CDC 6600 class, although some are on minis. I recall a Nova that played extremely well in the 1975 tournament in Minneapolis. Given this background, and the difficulty of the problem, what can we expect from a micro? A year ago, I would have been tempted to say "not much", but Peter Jennings has proven that statement quite wrong. Peter wrote a program called Microchess for the Kim-1. After all, what else can you do with a bare board, not very expandable, microcomputer with only 1K of memory? Only 1K? You must be kidding. But I'm not kidding. Of course, it has a rather powerful 5602 chip at the heart of the system. Peter follows the general outline above. The opening game consists of nine moves on both sides, in which the computer plays from a table if possible. This table occupies about 200 to 300 bytes. From there on, the program looks ahead approximately three moves on both sides and evaluates the possible outcomes from the standpoint of mobility, value of piece under attack and value of pieces open to attack. The program only uses castling in the opening and cannot capture pawns en passant. Minor limitations, in my opinion. Peter has recently converted the program to run on 8080 systems, however it requires 4K of memory. Actually 2K is for I/O, so the equivalent 1K 6502 program occupies 2K on an 8080 system. Interesting. The accompanying manual is quite thorough and includes a description of the program, a sample run and appendix with details of converting the I/O routines to your particular system. is available on cassette for the SOL or on paper tape for other systems. An interesting feature is the ability to reverse the board at any time, which if done continuously lets the computer play against itself. How good is microchess? Well it beat me, but I'm a rank beginner, so that's no measure. Against Dark Horse, the program which won the 6th place in the latest ACM Computer Chess Championship, Microchess was up one piece after 26 moves, but faltered and lost in the endgame. Microchess does not have a separate endgame strategy. I had hoped to have the results of the game between Microchess and Fidelity Electronics Chess Challenger, But that will have to wait until later. Microchess costs $13 for the Kim 1, $18 for 8080 Systems on paper tape, or $20 on Solos cassette. Contact Peter R. Jennings, Microware Ltd, 27 Firstbrook Road, Toronto, Ontario, M4E 2L2, Canada.
Duration 8 minutes and 24 seconds Direct Download

Show Notes

Course Material:

Other shows on the network:


Episode Gold Producer: 'r'.
Episode Silver Producers: Mitch Biegler, John Whitlow, Joseph Antonio, Kevin Koch, Oliver Steele and Shane O'Neill.
Premium supporters have access to high-quality, early released episodes with a full back-catalogues of previous episodes
SUPPORT SLEEP PATREON APPLE PODCASTS PAYPAL ME
STREAMING VALUE SUPPORT BREEZ PODFRIEND
CONTACT FEEDBACK REDDIT FEDIVERSE TWITTER FACEBOOK
LISTEN RSS PODFRIEND APPLE PODCASTS SPOTIFY GOOGLE PODCASTS INSTAGRAM IHEART RADIO TUNEIN RADIO CASTBOX FM OVERCAST POCKETCASTS CASTRO GAANA JIOSAAVN

Comments

Sleep 6: Can A Computer Really Play Winning Chess? https://engineered.network/sleep/episode-6-computer-chess with @chidgey #Engineered_Net

People


John Chidgey

John Chidgey

John is an Electrical, Instrumentation and Control Systems Engineer, software developer, podcaster, vocal actor and runs TechDistortion and the Engineered Network. John is a Chartered Professional Engineer in both Electrical Engineering and Information, Telecommunications and Electronics Engineering (ITEE) and a semi-regular conference speaker.

John has produced and appeared on many podcasts including Pragmatic and Causality and is available for hire for Vocal Acting or advertising. He has experience and interest in HMI Design, Alarm Management, Cyber-security and Root Cause Analysis.

You can find him on the Fediverse and on Twitter.