CHESS
John Krause, Assiant Technical Editor
Try to outwit your com puter with this fast, multilevel chess program whose intelligence routines are written entirely in machine language. There are versions for the Commodore 64; VIC-20 with at least 8K memory expansion; Ataris with at least 32K RAM; and Apples with at least 48K RAM and a disk drive. All versions except Apple require a joystick.
The world was amazed, in the late eighteenth century, by a machine that had the astonishing ability to play a good game of chess. It entertained kings and queens. It defeated Napoleon, a master tactician. Hundreds of people paid to compete against it, but eventually it was revealed that a small man was hidden inside the machine.
A chess-playing machine remained only a dream until the late 1950s when the first computer chess game was played. Now, the World Computer Championship, held every three years since 1974, attracts almost as much publicity as the human championship matches. Why has there been so much interest in machines that play games?
One reason is that chess can be used to measure a computer's intelligence. Chess is easy to play, but difficult to master. So difficult, in fact, that some experts believe that a computer would have to be almost as intelligent as a human to become world champion.
Of course, another reason is that chess is just plain fun, but not if you can't find an opponent. To be an entertaining opponent, a computer chess game should be fast, easy to use, and capable of playing at several different skill levels. "Chess" has all these features and more. Although it's really no match against the best commercial chess games, it has managed to defeat these giants of the microcomputer chess world on rare occasions.
Typing It In
The VIC and 64 versions are in two parts. 64 users should type in Program 1 and save it. Then enter NEW, type in Program 2 and save it with the name CHESS2. The VIC version needs at least 8K of expansion memory. VIC users should substitute the following lines into Program 1 before saving, and then enter NEW, type in Program 3 and save it with the name CHESS2.
5 POKE 56, 60 : POKE 55, 0 : CLR :rem 171 20 IF K < > 79727 THEN PRINT "ERROR IN DATA" : STOP :rem 129 55 POKE 6656, 0 : POKE 44, 26 : NEW :rem85 2080 DATA 11, 173, 20, 145, 205, 127, 63, 144, 18, 141, 127, 63, 140, 128, 63 :rem 19
If you are using tape instead of disk, in line 40 of Program 1 change the 8 to a 1. Make sure that the second part is saved immediately after the first part on the tape. To run either version, run the first part. The second part will load and run automatically.
The Atari version requires at least 32K RAM. Atari users should simply type in Program 4 and save it before running.
Apple users should consult the accompanying Notes for special instructions.
Joystick Input
After running the program, you will be asked to specify several play options. You can choose among five skill levels; start a new game or set up any position; play against the computer or watch it play against itself; or play either the white or black pieces. All of these options will be discussed in greater detail later, but for now, type 1 at each prompt. This puts you in command of the white pieces versus the computer on level one, the easiest level.
The first time the program is run, you need to wait a few seconds while the computer gets its brain in order. Then the board will be displayed with your pieces on the bottom of the screen and the computer's pieces on the top. You should see a frame around the square in the lower-left corner of the board (the VIC version uses a blinking square). This is the cursor which takes the place of your hand to move pieces around the board.
Use the joystick (plugged into port 2 on the 64, port 1 on the Atari) to move the cursor atop the piece you wish to move. Press and release the joystick button. Now move the cursor to the square you want to move to and tap the button again. Your piece moves to the new square, and the computer responds almost instantly with its move.
A Spectacular Blunder
Did you make a foolish move? No problem. One of the most valuable features of Chess is the ability to change the position by adding or deleting pieces. This feature is especially useful for those of us who frequently manage to maneuver into a superior position, only to throw it all away in a single, spectacular blunder.
A piece can be deleted by positioning the cursor on the piece and pressing the space bar. To add a piece or change a piece to a different one, move the cursor to the appropriate square and press P, N, B, R, Q, or K for pawn, knight, bishop, rook, queen, or king, respectively. This will put one of your pieces on the square. To add one of the computer's pieces, hold down the SHIFT key (CONTROL key on the Atari) while pressing one of these editing keys.
To take back a move, use the editing keys to delete your piece and put it back on its original square. Don't forget to take back the computer's move, too.
The editing feature also enables you to make special moves which cannot be made with the joystick alone such as castling and en passant captures. For example, castling can be accomplished by deleting the king and putting it on its new square, and then moving the rook as you normally would with the joystick. Although you can make these special moves, the computer will never castle or capture en passant because, due to their complexity, these moves were not included in its thinking routine.
Strange Chess
Although the computer will always make a legal move, it doesn't check to see that you do the same. You are free to move any of your pieces to any square without so much as a contemptuous buzz from the computer. If you're an experienced player, this shouldn't be a problem. If you're a beginner, however, you may want to familiarize yourself with the basic rules of chess lest you end up playing strange chess, a personal version which bears little resemblance to the real game. On the other hand, if you like to fudge a bit, the computer will make it easy. It will politely acquiesce to your most surreal moves.
When a pawn reaches the other side of the board, it's automatically promoted to a queen. If you would rather have a knight, bishop, or rook, you can easily make the change using the editing keys.
Checkmate
The computer thinks by analyzing thousands of possible moves and countermoves and choosing what it considers to be the best move based on the relative value of the pieces (see "How Chess Thinks"). Most positions don't have just one best move but several which are equally good, in which case the computer chooses among them at random. This random factor insures that every game will be different, and makes for varied and interesting play.
Play continues until one side is either checkmated or stalemated. The computer will then stop play and indicate which side has won.
There are a few quirks in the way the computer determines whether checkmate has occurred. On levels three through five, it announces checkmate prematurely. When this happens, the computer has determined that it's impossible to avoid checkmate on the next move or two, assuming both sides make the best moves.
Also, the computer doesn't know the subtle difference between checkmate and stalemate. Consequently, when stalemate occurs, it will announce checkmate although, in fact, the game is a draw. Since the computer tries as hard as it can to checkmate its opponent, it will also try to achieve stalemate, possibly forcing a draw when it could have won. Fortunately, this rarely happens because the conditions for stalemate exist only in unusual circumstances such as when one side has only the king remaining.
Also, the computer won't give you any hint when your king is in check (not checkmate). So be extra careful that you don't leave your king in check or move into check. Otherwise, your king would be in check during the computer's turn to move—a highly unorthodox if not illegal position. The computer's reply to such a position is unpredictable, but it usually announces checkmate, forcing you to restart the game.
In any case, when the computer announces checkmate, press the joystick button to start a new game. If you want to try out some of the other play options without waiting till checkmate, you can start a new game at any time by pressing RUN/STOP-RESTORE (RESET on the Atari) and running the program again.
Play Options
When you choose the black pieces, the board will revolve so that you still play from the bottom. Since the player with the white pieces always moves first, you must wait for the computer to move before you will be allowed to make your first move.
If you become mentally exhausted after several bouts against the computer, give your brain a rest and watch the computer play itself. When you select this option, just set the joystick aside and sit back and watch the action. Beginners will find this feature an excellent way to learn some good strategies to use against the computer.
You don't have to begin a game from the starting position. If you choose the option to set up a position, an empty board will be displayed and you can use the editing keys to place pieces on the board in any position. When the position is set up, the computer will start thinking after you make your first move.
This feature is especially useful for continuing a previous game or creating a problem for the computer to solve. It also allows you to experiment with hypothetical or downright ridiculous positions. Live out your fantasy by giving yourself ten queens versus the computer's lone king. The position doesn't even have to be a legal one. You could invent your own type of chess by giving each side two kings, for example, although the computer may get confused trying to determine when checkmate has occurred.
How Chess Thinks
You've probably heard that if a monkey sat down at a typewriter and pecked randomly at the keys for a long enough period of time, it would eventually type the complete works of Shakespeare. Theoretically, this is indeed possible—given enough time. There's the rub. At a brisk typing speed of 50 words per minute, it would take that poor monkey billions of years just to type "To be, or not to be." Nevertheless, there is power in trial and error.
The Minimax Algorithm
Substitute the monkey for a high-speed computer, and this technique becomes a practical method of imitating intelligence. In fact, it has been used with great success in the field of artificial intelligence. This program uses a popular trial-and-error technique known as the minimax algorithm.
The computer looks at the present board position and mentally moves the pieces through all the possible combinations of future moves and countermoves up to a certain point, say three moves ahead. For each combination, it calculates a score based on which pieces were captured during the combination. Each piece is worth a certain number of points depending on its general importance: 1 point for a pawn, 3 for a knight or bishop, 5 for a rook, 9 for a queen, and 46 for a king. (Of course, since you lose the game if your king cannot escape capture, the value of a king is actually infinite, but 46 is high enough to convince the computer that it's a bad move.)
When, in a move being examined, the computer captures an opponent's piece, the value of that piece is added to the score. Conversely, when one of the computer's pieces is captured, its value is subtracted from the score. Thus, a high score is considered good for the computer, and a low score is good for its opponent.
The task is to find the combination that represents best play for both sides. This combination is not necessarily the one with the maximum score, because while the computer is trying to maximize the score, its opponent is trying just as hard to minimize it. The best combination gives maximum scores during the computer's moves, and minimum scores during the opponent's moves.
After the best combination has been found, the computer's best move in the present position is simply the first move in the combination. The problem has been reduced from analyzing a chess position to finding the maximum and minimum of a series of numbers, which is much better suited to a computer.
50 Million Combinations On Level 5
Like most algorithms based on trial and error, this one requires sifting through an enormous number of combinations to find the best one. Fortunately, a few tricks can be used to reduce the combinations to a manageable number. This algorithm uses a technique called alpha-beta cutoff. It makes the computer search more intelligently, giving it the seemingly paradoxical ability to find the best move without looking at all the possible combinations. On level 5, for example, instead of having to search through roughly 2 billion combinations, it looks at only 50 million.
Even so, it would take BASIC from now till 1986 to generate that many combinations. That's why the algorithm is programmed in machine language. An advanced programming technique known as recursion (making a subroutine call itself) is used to generate all the possible combinations of moves. Capable of analyzing about 5000 combinations per second, this routine provides a moderate challenge at a reasonable playing speed.
One of the advantages of a computer opponent over a human is that you can tell the computer exactly how hard you want it to try to beat you, and it will obediently play at that level of difficulty. This is important because it's no fun if you always lose or always win effortlessly.
You have five skill levels to choose from. The difference between one level and another is the number of moves ahead that the computer looks. On level 1, for example, it looks two moves ahead (its move and your reply). Each succeeding level looks ahead one more move than the previous level.
Alas, the smarter play on the higher levels doesn't come without a price. The further ahead the computer looks, the more moves it must examine and, hence, the longer it thinks. The thinking time varies greatly depending on the level (about one second per move on level 1; about two hours on level 5).
Here's a rundown of the five levels:
Level 1: Beginner. Thinking time: one second. Look ahead: two moves. Fast but dumb.
Level 2: Intermediate. Thinking time: five seconds. Look ahead: three moves. Provides a reasonable challenge for impatient players.
Level 3: Tournament. Thinking time: two minutes. Look ahead: four moves. Since the usual time limit for tournament play is 40 moves in two hours, an average of three minutes per move, this level is best suited for serious players.
Level 4: Mate in two. Thinking time: 30 minutes. Look ahead: five moves. Capable of solving most mate-in-two problems.
Level 5: Postal chess. Thinking time: two hours. Look ahead: six moves. Simulates postal chess games where there is no time limit. Can avoid checkmate in two moves.
The thinking times given here are average times. The actual time ranges from half to twice the average time depending on the position.
Level 4 can be used to solve mate-in-two problems such as those published in many newspapers. Just select the following options: level 4, set up position, computer versus itself. Enter the position using the editing keys, and then make a do-nothing move by positioning thecursor over a white piece and pressing the joystick button twice. After several minutes of deep thought, the computer should respond by moving one of the white pieces (the solution) and announcing checkmate. The only mate-in-two problems that the computer cannot solve are those which involve castling, en passant captures, or pawn promotion.
If you have a Commodore 64 or VIC and don't want to type in this program, send a blank cassette or formatted disk, a self-addressed, stamped mailer, and $3 to the address below, and I'll make you a copy. Be sure to indicate which computer version you want.
John Krause
402 Monmouth Drive
Greensboro, NC 27410
Apple Notes
The Apple version of "Chess" uses the DATA statements from Program 1. Type in Program 5 and add lines 2000 to 2500 from Program 1 (ignoring the :rem numbers, which are for Commodore owners using the "Automatic Proofreader"). Then substitute line 2080 with the following line and save the program before running it:
2080 DATA 11, 173, 35, 192, 205, 127, 63, 144, 18, 141, 127, 63, 140, 128, 63
Use the A, S, D, and W keys to move the blinking cursor atop the piece you wish to move and press RETURN. Then move the cursor to the square on which you want to set the piece and hit RETURN again.
As in the other versions, the P, N, B, R, Q, and K keys let you add pieces to the board. To add one of the computer's pieces, hold down the CONTROL key while pressing one of these editing keys. Use the space bar to delete a piece.
When the computer announces checkmate, press any key to start a new game. You can start a new game at any time by pressing CONTROL-RESET and rerunning the program.