The Best of Creative Computing Volume 2 (published 1977)

Page 35 << PREVIOUS >> NEXT Jump to page:
Go to contents Go to thumbnails
This book is also available for the Kindle

Big Surprise From Small Computers in Chess Matches (Data General Supernova beats IBM System 360/91 in 25 moves)

graphic of page

castle is placed in any of the 36 remaining squares
it appears to control 14 squares 4 of which must
be excluded. Thus the revised computation power
of a castle is
412241136101
6463646364636
and so forth. The remaining computations and further modifications of
definition of checking
power are left to you.

An article discussing chess related recreations
would be incomplete without considering some of
the many "tour" problems, particularly since they
offer interesting programming challenges as well.

There are many different types of tour questions the fewest number of moves to
accomplish a task,
covering all squares once and only once, the minimum distance traveled, ... Here
we'll consider just
three different questions.

First, can you determine a path traveled by a king
such that each square is occupied once and only
once? No, it's not that easy. There's one additional
catch. As the king moves, number each square
consecutively starting with 1. When you've finished,
the squares will each contain one of the integers
1 thru 64. What's the catch? The resulting board
with numbered squares must be an 8X8 magic
square. A solution will be published in a future
issue.

As a second problem, try moving the castle
from one corner of the board to the diagonally opposite corner, again passing
through each square
once and only once. This one isn't quite as easy as
a quick reading suggests, but you should be able
to solve it in a reasonable period of time.

Finally, consider the standard "Knight's Tour"

problem that is considered in so many articles on
recreational chess. A knight must cover the entire
board occupying each square once and only once.

Don't, however attack this one with a knight and a
chessboard-try something different. Write a problem that will find a solution
for you. Kemeny (2)
offers a BASIC program that attempts to find a solution by making random moves.
The small sample
of runs he published doesn't include a complete
solution, in fact not one of 25 runs exceeded 50
squares before no moves were possible. Perhaps
surprisingly, however, in 15 of the 25 runs the tour
did pass thru over half the squares before terminating. Actually, when a
knight's tour is attempted
using only random moves, long tours are quite
common but a complete tour ls very unlikely indeed.

How then can a program help? By adding a little
bit more to the move selection than simply the
choosing of a random number. When selecting a
move, add one additional criteria. Always move to a
square from which the knight will command the
fewest squares that have not been occupied. Fewest
is not a misprint, even if it does contradict your
intuition. If several squares fit this criteria equally
well, then select one of them at random. This additional criteria ls reasonably
implemented in a
program, and although it doesn't guarantee a
successful tour, you are apt to be surprised by the
results!

Bibliography

1) Ball, W.W. Rouse, Mathematical Recreations and
Essays, Macmillan and Co., London 1940

2) Kemeny, J.G. and Kurtz, T.E., BASK Programming Second Edition, John Wiley and
Sons, New
York, 1971

***
Big Surprise From
Small Computers
in Chess Matches

Good things come in small packages-especially
when computers compete in chess matches. In two
matches here and abroad, small computers performed surprisingly well against
giant competitors.

David actually conquered Goliath in an intramural
chess match at Columbia University when a small
Data General Supernova-about the size of an attache case-checkmated an IBM
System 360/91-one
of the largest in the world-in just 25 moves.

The Supernova, owned by Columbia's Department
of Electrical Engineering and Computer Science, had
a memory capacity of 32,768 bytes; the IBM system, part of the university's
computer center, had a
capacity of over 2 million bytes.

The Supernova's chess program was written by
Professor Monroe Newborn of the Electrical Engineering and Computer Science
Department and by
student George Arnold. It is written in assembly
language and uses a technique that determines the
best move by searching between four and eight half-moves ahead, selectively
analyzing about 1,000
terminal positions. A move is determined in about
one minute-well within chess tournament rules.

The game lasted more than 90 minutes, but the
Supernova gained a decided advantage on the sixth
move: the System 360/91, playing white, blundered,
and traded a knight for a pawn. One of the program
authors noted that the computer saw the correct
move (bishop takes bishop) but didn't realize that
exchanging bishops would save the knight. Once the
big computer decided it could not save the knight,
it decided to pick up a pawn.

"Having exclusive use of the smaller computer,
along with running the program on-line, helps offset the greater speed and
capacity of the larger
machines," Professor Newborn said.

In another surprising match, a Computer Automation Naked Mini computer using
only 16,000
words of 16-bit memory came in 12th in stiff competition in the World Computer
Chess Championships held in Stockholm, Sweden.

"I'm no expert at chess; in fact, I'm just an
average amateur, but I love to play with computers.

Even so, I was surprised, indeed," said Bob Prisen,
Interscan Data Systems, Ltd., United Kingdom, who
programmed the Naked Mini. He spent approximately
300 hours in an eight-month period and used BASIC
assembler language.

The first-place winner, by contrast, was a large-scale English-built ICL 4/70
computer entered by the
Moscow Institute of Control Science. The machine
and its programming had been prepared by a team
of 10 fulltime staffers for more than two years. The
computer used a program called KAISSA.

During the Swedish match, the Naked Mini stayed
in England. Communications between Prisen and the
computer were established using international telephone lines and an acoustic
coupler with a Teletype
and an on-line visual display unit.

Prisen said he hopes that a European or British
Chess Computer Championship can be arranged in
the future. "If it occurs, I'm confident the Naked Mini
computer will greatly improve its position in the
Chess Computer League with a bit more core memory and programming effort," he
said.

35

Page 35 << PREVIOUS >> NEXT Jump to page:
Go to contents Go to thumbnails
This book is also available for the Kindle