Computer CHESS Programming
by MICHAEL CIRAOLO, Antic Associate Editor"You don't seem to be playing your usual game today, Dave." -HAL 9000, from 2001
Computers that play chess have fascinated
both the public and programmers ever since a large IBM 704 played two legal
but bumbling games at a 1957 Dartmouth Conference on Artificial Intelligence.
(For more about designing intelligent games, see "Slide" in this issue.)
In this article, we examine the current state of computer
chess programming-as represented by the Odesta Chess software for
Atari (Odesta Corp., $69.95) and the Turbostar 432, an expert-level
dedicated chess computer (SciSys, $350) which uses the same 6502 microchip
as the Atari.
During our research, we discovered that Atari computers
play a more than passable game of chess. We matched the Odesta program
against the Turbostar at levels ranging from easiest to hardest. The more
expensive Turbostar consistently won, but the Odesta gave it a tough battle
each time. And both play chess well beyond the skill of most non-competition
human players.
PLAYING GAMES
The basic approach to designing intelligent computer games is not hard
to understand, although the programming itself isn't easy. So says Larry
Atkin, who programmed Odesta Chess and helped write the ground-breaking
CHESS program at Northwestern University. Successive versions of CHESS
held the Computer Chess Championship throughout the 1970s.
Atkin said that most chess programs represent variations
of a "tree" search pattern.
The computer "sees" the board as an 8 x 8 array of numbers,
with the pieces represented as a positive or negative number.
Move selection involves three modules-a move generator,
an evaluation function and a quiescence function.
The first module produces a look-ahead tree of possible
moves starting from a given position and lists all situations that could
possibly "branch" from a move.
CHESS MODULES
The program then develops a second generation of possible branches,
and so on. Obviously, with millions of possible chessboard situations,
even a Cray XMP supercomputer would run out of processing space quickly.
That's why game design requires additional modules.
The second module is called the evaluation function. It
is here that knowledge of chess strategy and concepts is put into an algorithm-a
series of steps by which a computer can solve a given problem.
An evaluation function program might compare the two opponents
material forces, mobility, pawn strength, king safety, control of central
squares, and so on. This function looks at each "node" (possibility) on
the tree to analyse specific board positions.
The more chess sophistication you put into the evaluation
function, the more processing time the program takes. So there is a trade-off
between the number of nodes that can be examined and the complexity of
the evaluation module.
Because most of the nodes on a tree aren't optimum positions,
the program also needs a section to evaluate the end position of the various
branches and determine what branches are worth pursuing. This module is
the quiescence function-it "prunes branches" (eliminates possible moves)
that aren't promising, thus freeing computer memory.
This complex process results in the computer making a
move, and then developing a strategy for the situation created by the move.
Most dedicated machines currently use the same chip as
the Atari, the 6502 microprocessor. Software is compiled into assembly
language from C or Pascal. "C keeps you closer to assembly language, Pascal
protects you from too many of assembly language's tricks," said Julio Kaplan,
president of Heuristic Software in Berkeley, California. Kaplan programmed
the Turbostar for SciSys.
NEW APPROACH
Although "brute force" is the proven approach to programming chess
and other games, the philosophy is changing, according to Kaplan. He favors
a "selective search" instead.
"You rely on special knowledge for evaluating each node,"
Kaplan said. That is, the computer starts playing more like a grandmaster
and less like a computer. The search is narrower, but the "thinking" about
various positions is more intensive.
Kaplan brings considerable "special knowledge" to chess
programming- the last time he checked, he was ranked "about 73rd in the
world." He was World Junior Chess Champion as well as a National Master.
Active as a professional chess player for five years, Kaplan also holds
a master's degree from U.C. Berkeley in computer science.
MOVING UP
Chess computer advances are coming quickly in both hardware and software,
believes Kaplan.
There was a quantum leap between the previous SciSys Superstar
machine and the current Turbostar, Kaplan contends. The Turbostar is much
faster.
Kaplan said there's been considerable improvement in designing
efficient search trees, with improved pruning. "It's a leaner program,"
Kaplan said.
Kaplan has improved the end game, an area traditionally
weak in machine play because the consequences of any move went beyond the
ability of the search tree, and those consequences are greater in the end
game than in the opening.
To improve a chess program, you evaluate the game the
program is playing. Kaplan thinks about what pieces of knowledge are missing
for the computer's evaluation of a certain situation node.
That information then must be expressed in an algorithm.
But that algorithm can't just be added onto the program. Kaplan must understand
how all the elements of the program affect each other.
Finally, he must analyse the impact of the added algorithm
on the speed of the program, which is frequently measured in nodes per
second-how many situations can the program evaluate in one second.
THE FUTURE
With the dropping price of ROM (Read Only Memory) chips which store
the game program, larger programs for the high-end machines will be available
at lower prices, Kaplan predicted. In the $60-80 range, machines are much
smarter than they were three years ago.
The software area is especially improvable, Kaplan believes.
Of the four leading companies, two are using brute force exhaustive search-ideal
for finding tactical mates in, say, four moves.
The other companies, including SciSys, are using selective
searches, which play some positions very well, but still make embarassing
moves on others.
"I think there will be a master-level microcomputer based
chess program within two years," Kaplan predicted.
"I'd like to see these machines provide entertainment,
user interest and education." Ideally, the machine should tell you more
about its own thought process and coach you on your game. Playing a computer
chess program will be like playing HAL in 2001-it can tell you when
your game is off. . . and why.
"A brute force machine can't explain its thought process.
Only a selective search can. This makes it more interesting as a chess
player," Kaplan said.
The better micro programs currently beat the mediocre
mainframe programs, Kaplan said. The day is not far when there will be
"upsets" between micros and mainframes-by the end of 1986.
The next generation of Turbostar, which should be available
by the end of this year, will have a tactical knowledge that surpasses
the ability the brute force programs are likely to have by year's end.
And new machines will be upgradeable with plug-in chips!
RECOMMENDED READING
Computer Gamesmanship, by David Levy. $12.95. 272 pages, paper-bound. 1983. Simon and Schuster.
Chess Skill in Man and Machine, by Peter Frey. $18.95. 335 pages, 1984. Springer Verlag.
How to Get the Most from Your Chess Computer, by Julio Kaplan. $9.95. 1983. RHM.
MANUFACTURERS
ODESTA CHESS SOFTWARE
Odesta Corporation
930 Pitner
Evanston, IL 60202
(312) 498-5615
48K disk
$69.95
TURBOSTAR
SciSys Computer, Inc.
359 East Beach Avenue
Inglewood, CA 90302
(213) 673-9500
$350