Computer CHESS Programmingby 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.
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.
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.
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.
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.
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!
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.
ODESTA CHESS SOFTWARE
Evanston, IL 60202
SciSys Computer, Inc.
359 East Beach Avenue
Inglewood, CA 90302