History of AI Applied to Chess

Chess is widely recognized as a game that requires intellect, and many early computing experts believed that a machine capable of playing chess would signify true artificial intelligence. While the Turing Test presents a significant challenge for determining machine intelligence, chess has also been a valuable pursuit for AI researchers, who have developed programs that can compete with, and sometimes even surpass, the world’s top chess players. However, even the most advanced chess-playing machines do not truly comprehend the game’s concepts and instead rely on brute force methods to play.

Origins of computer-Chess

Chess has long been associated with intelligence. In fact, it was even included as a valid question during Turing’s Turning Test. People have long imagined machines that could play chess, but it was Claude Shannon who wrote the first paper on developing a chess playing program.

In Shannon’s paper, there were two methods proposed for computer chess. The first approach, Type-A, involved using brute force by analyzing thousands of moves through a min-max search algorithm. On the other hand, Type-B programs utilized specialized heuristics and ‘strategic’ AI to examine only a few critical moves. 

During the 50s and 60s, Type-B (strategic) programs were preferred over Type-A (brute force) ones because of the limited computing resources available at that time. In 1973, the creators of the ‘Chess’ program series, which had previously won the ACM computer chess championship from 1970 to 1972, made the decision to switch their program to Type-A. The resulting program, known as ‘Chess 4.0’, went on to win several future ACM computer chess titles, dealing a blow to those who had hoped to gain a better understanding of chess through the development of Type-B programs.

There were a few crucial reasons for transitioning from a Type-B program, which is arguably more intelligent in design, to a less intelligent Type-A program. The first factor was simplicity. A Type-A program’s speed is directly related to its ability, so with machines getting faster every year, it’s easier to write a robust Type-A program and enhance it by providing more power through parallelization or specialized hardware. In contrast, a Type-B program would require being taught new rules and strategies, regardless of the amount of new power being supplied to it. Furthermore, predictability was a significant factor. The creators of the game ‘Chess’ have expressed their anxiety during tournaments because their Type-B program would behave unpredictably in response to different hard-coded rules.

Currently, Type-A (brute force) programs remain the most powerful applications in existence. Type-B programs with advanced intelligence do exist, but due to the simplicity of writing Type-A programs, exceptional gameplay can easily be achieved solely through computer speed. Despite ongoing research to better understand and abstract the game of chess into additional rules and heuristics, Grandmaster-level Type-B programs have yet to be developed.

Realization

IBM’s Deep Blue program is widely recognized as the most prominent Type-A program. In 1997, it challenged and defeated the reigning world chess champion, Gary Kasparov, with a 3.5/2.5 match win. Although the victory wasn’t entirely one-sided, the increasing power of machines suggests that this match was only a glimpse of what’s yet to come.

It’s not surprising that a computer was able to beat a world chess champion. According to scientist David G Stoke, people aren’t too concerned about this because it’s similar to a motorcycle beating an Olympic sprinter – it’s expected. Deep Blue, the computer that won, was a Type-A program that could evaluate around 200 million positions per second and search up to 12 ply depths, or even 40 under certain conditions. Humans, on the other hand, typically examine around 50 moves to various depths. I agree, the victory of Deep Blue would have been even more impressive if it had been a Type-B program. It just goes to show how far machine intelligence has come and how much potential it has for the future.

It is worth noting that IBM profited greatly from Deep Blue’s victory in the chess match. Experts have estimated that the win resulted in approximately $500 million worth of free advertising for IBM Super computers. Furthermore, the match also caused IBM’s stock price to increase by $10, reaching an all-time high at the time.

Go as the next border.

The development of computer chess is ongoing, with the goal of creating more powerful machines that require less specialized hardware. However, there is currently limited interest in Type-B programs that aim to capture the raw knowledge of human chess players. As chess has been “solved” by many, attention has shifted to other games where computers have yet to challenge humans. One such game is the ancient Asian game of Go, which is now seen as the next frontier of game-based AI research.

Go is a game that differs from chess in its computing power. While chess has a branching factor of around 40, Go has a branching factor of 200, which means there are many more valid moves a player can make at any given point. Another unique aspect of Go is that there is no clear victory condition like in chess, where the goal is to achieve a checkmate. In Go, both players must agree on the end-game determination, and it requires intensive search to determine if the board position is terminal. Even after extensive research, there is currently no definite algorithm to determine whether a cluster of stones is alive or dead, which is a crucial aspect of the game. Even with a $1,000,000 prize offered to create a program that can defeat a strong amateur Go player (the Ing prize), the best programs cannot defeat a weak club-level player.

Programs for playing Go are gradually making progress, particularly in the field of ‘Type-B’. One example is mathematical morphology, a branch of image processing that has helped computers quickly analyze board positions in a similar way to humans [Bouzy03]. It has been discovered that the strength of computer-Go programs can only be moderately improved through massive parallelization, which is unfortunate.

Conclusion

While chess-playing machines have undoubtedly made impressive strides, some individuals remain skeptical regarding their true intelligence. One common argument against their intelligence is the “Chinese Room Argument,” which posits that analyzing billions of board positions to make a single move may not necessarily be considered a highly intelligent approach. Despite this, these machines consistently demonstrate exceptional gameplay. However, as games become more complex in the future, it is possible that new abstractions will need to be developed that have a more direct connection to general artificial intelligence, rather than solely relying on specialized search algorithms.

Picture of Hoa
Hoa

Leave a Comment