robison@eosp1.UUCP (Tobias D. Robison) (07/04/84)
References:
Some of us are currently playing correspondence chess with the
"Phoenix" computer program, and some of us have other experience
playing against computers, or interest in the subject. I wonder
if some of us would enjoy discussing the question of what a really
strong chess computer program will be like?
There was a chess match about 2 years ago between 4 candidate masters
and 4 of the best computer programs. There was much hope for the
programs, but they only scored about 6 out of 16 points.
The match was reported in Chess Life/Review, along with speculation
that a stronger group of chess players was at last starting to
probe for weaknesses in the computer programs, with inevitable results.
Current chess programs have opening libraries, and otherwise
analyze primarily by brute force. I believe that there is also a
tendency for programs to extra-analyze certain capture situations
and other concerns, such as passed pawns, that can cause the
"horizon effect". ("Horizon effect" refers to a situation where the
computer ignores, say, the opponent's threat to queen a pawn because
it can postpone the threat just one move beyond the depth that it
analyzes.)
Here are some of my feelings about what strong chess programs need to
do:
(1) They do need good opening book lines, but care is necessary to
limit the book to lines that the computer feels comfortable in.
(Example -- Phoenix is playing the French defense, which leads to
cramped positions that are hard for a computer to evaluate; I don't
a computer should play 1. ... P-K3.)
(2) Computers should never be ready to repeat a game exactly in
tournament play. In tournamement play, any good master is ready to
replay, from memory, a loss by the computer in a previous round.
(One player actually did this in the match described above.)
Correspondence players can exchange games easily. Therefore a
chess program playing correspondence should be careful to avoid
repetition (or at least make that unlikely) in simultaneous or
sequential correspondence games.
(3) Because (as far as I have seen) computers do better in open
positions, they should have a strong preference for opening up
positions, even to the extent of making some speculative sacrifices
of small amounts of material or positional values. Therefore
if a computer does give extra analysis to exchange possibilities,
it should give the same extra analysis to possible sacrifices against
pawn chains.
(4) Chess programs should vary the depth that they analyze positions.
It is possible to get a feeling for awhile about how deeply a
computer is routinely analyzing. It is much harder to do this for
humans. It may be that the best programs already do this, but it seems
to me that the programs can safely vary their rules for deciding
how to spend time in a position so that it is much harder for a
human opponent to feel safe about a particular horizon.
In particular, chess programs should be able to do something that
humans do fairly easily -- analyze long forcing and semi-forcing lines.
If I receive private mail on this subject, I will summarize for the
net.
- Toby Robison (not Robinson!)
allegra!eosp1!robison
decvax!ittvax!eosp1!robisonrjnoe@ihlts.UUCP (Roger Noe) (07/04/84)
> what a really strong chess computer program will be like? > . . . chess programs should be able to do something that > humans do fairly easily -- analyze long forcing and semi-forcing lines. > - Toby Robison (not Robinson!) That's part of what current chess-playing machines really lack. Virtually all such successful machines have quite good tactics but no strategy what- soever. They're all just like novice players with prodigious memories and blinding speed. What they lack is the learned ability of the grandmaster. Sure, you can say that it is possible for a machine to play a perfect game given sufficient speed and storage. But that's impractical. Current tech- niques (basically full-width searches with alpha-beta pruning and evaluation algorithms which have become rather sophisticated) have pretty much reached their limit, barring significant advances in hardware technology. What is most needed (and I know this is not a new idea in the slightest) is to be able to program the ability of the expert to select moves that look promising and reject irrelevant continuations without generating and evaluating posi- tions several ply down. Easy to say, hard to do. -- Roger Noe ihnp4!ihlts!rjnoe
jonathan@alberta.UUCP (Jonathan Schaeffer) (07/05/84)
Here are a few comments on Tobias Robison's remarks on what it takes to have a really good chess program with emphasis on how it applies to my program, Phoenix: 1) Opening book. Agreed. One cannot ignore a century of extensive analysis of the openings. But from the programing point of view, opening analysis is purely mechanical - I get a friend to type in the latest analysis from the latest chess journals. Phoenix does not have an extensive opening book (a shortage of friends who have the patience to type all that junk in). On the other hand, Ken Thompson typed in approximately 350,000 moves from ECO for his chess machine Belle. One can envision in the near future chess opening book databases in which ALL the latest theory will be available in machine readable form. 2) Determinism. Chess programs should not be deterministic, but regrettably, most are. In most programs (including Phoenix), non- determinism comes from two sources. First, we can randomly select our opening line. This offers some variety, but there is still the danger of repeating a game. Second is the clock. In tournament play, even if two games follow the exact same move sequence, the times on the clock will never be identical. Differing times may mean the program will search more/less and possible result in a different move. There is actually a third form of non-determinism. Rarely does a tour- nament game go by when I do not detect an inaccuracy in Phoenix and fix it before the next round. In that case, the next opponent is playing a slightly different program which will possibly make different moves. 3) Regarding open positions. It is true that most programs play open positions well. Blocked positions require more chess skill to play correctly. However, with enough chess knowledge, there is no reason why programs cannot play such positions well. Phoenix runs on a VAX and therefor has considerable difficulty being competitive with a Belle or Cray-Blitz, both of which run on much faster hardware. Phoenix uses knowledge to compensate for depth. In fact, Phoenix avoids open games and prefers closed ones, contrary to most chess programs. I noticed Robison criticized Phoenix for playing a French defence, but the fact is that Phoenix has never lost the black side of a French in tournament play. 4) Variable depth. Almost all brute-force chess programs I know search to variable depths. For example, most programs extend the search tree an extra ply for every check encountered along a line of analysis. It is true that the program is still brute-force and not selective (such as the chess program Awit). Given that you want to search 5 ply, Phoenix will search a line for a minimum of 4 and a maximum of 8 ply (plus extensions for capture sequences) depending on what "features" of the position it sees during its analysis. Phoenix does have the advantage of variable depth and the advantages of brute-force search- ing (along with some of the disadvantages too I'm afraid). In summary, I think your points are too general. I can argue that all the deficiencies you see in computer chess programs today do not really exist for many programs. As to what it will take to have a really strong program, well thats another article...