Introduction
to Chess Programming and AI
(Original
Essay - Printable Version)
TEST 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. But as the skill level of human competition grows the algorithms for chess programming must likewise grow. 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 benefits much from it.
|