Chess
AI: Introduction
(Up to Chess
AI)
Get Printable Version
Ever since the old days of punch-card computers, people have been
fascinated with chess-playing programs, and no wonder. If they can
create a computer that can outsmart humans in this obviously strategic,
thinking-based game, then it would be a major milestone on the road
to the intelligent computer.
Chess is a game of perfect information.
This means that unlike poker or backgammon, all information specific
to the game is known to both players, and there is neither secrecy
nor chance. Both players can see everything about the position on
the chess board, and they know each other's moves, for the moves
are not played at the same time but rather in order. Thus, chess
is a purely intellectual game, a perfect environment for
testing Artificial Intelligence techniques.
Early on, most researchers concluded that the computer's greatest
asset was its computational speed. Computers would utilize
a variant of the brute-force routine, an algorithm that relies almost purely on how fast the computer can process the board. Chess has a small board: 64 squares and up to 32 pieces to fill them. Even though there are an astounding number of legal chess positions, the researchers relied upon the fact that computers could process more exactly and more quickly than
people, and thus "think" faster than people while playing
the game.
In those days, of course, computers had a ridiculously small
amount of memory (300 K of memory, anyone?) and processing power,
so chess programs were, at best, quite weak. But computers
became faster, and chess programs became stronger and smarter.
With the combined research of many brilliant programmers, the minimax
game tree evolved to become the most major component
of the chess program. Almost all chess programs use the minmax tree
in one form or another. It is by far the most successful
and most popular of all the AI techniques in the history of board
game programming.
Chess AI, of course, seems almost finished. In the middle
of the 1990's, the computer Deep Blue II built by IBM defeated Gary
Kasparov, who was the World Chess Champion at the time.
Chess programming, however, has not lost its usefulness.
There are many other AI techniques that can be implemented
and tried in a Chess program, such as neural networks, genetic algorithms,
and collaborative computing. Chess is a controlled environment
in which the computer is presented with a situation and a goal,
and the computer must find possibilities and make decisions to achieve
that goal. Thus, decision-making algorithms
and other such AI fields can be derived partly from Chess programming.
Chess programming, of course, is also a springboard into the exciting
field of Go programming. In Go,
however, beginning to program and making progress are both very
difficult. Chess programming provides a foundation for developing
more advanced forms of AI that are to be found in Go programs.
Thus Chess programming, although it seems completely explored,
is like a great work of literature: even after it has been
scoured over and over by researchers and programmers, it keeps on
producing more and more treasures. AI benifits much from
it.