Categories: Post

In The Game of Chess Humanity Has Finally Met Its Match

There is an old fable1–told in more than one country–about the origin of chess. A wise man shows his king a game he developed about the king’s empire. The game depicted the king, his officers, and his foot soldiers battling an enemy army. The king loved the game and wanted to repay the wise man with gold and precious jewels.

The wise man asked for one thing as payment from the king: he wanted wheat, or rice, or grain (it depends on who’s telling the story.) The man requested that the king place one piece of rice on the first square of the chessboard, two pieces on the second, and so on until all the squares were full. The king ordered his servants to fulfill the man’s wishes but they soon found that there wasn’t enough rice in the kingdom! The wise man was clever, having already determined that all the food he requested would be over 18 quintillion pieces of rice! The wise man tricked his king out of his food, and though they didn’t play chess in the story I think the wise man would’ve won, because chess has always been a game about being skillful and smarter than your opponent.

This story is often found in math books. As far as we know it isn’t true. What we do know is that chess has been in existence in some form for over 1500 years. It is an old game with an unknown origin. Despite the mystery behind chess, the game has encouraged prominent advances in both math and computer science since the time of its inception.

Chess has taught us a lot about probability. While a game like poker is highly impacted by probability, it also relies on chance. Chess has no randomness–it is known as a game with “perfect information,2” meaning every move is known to both players and that there is also a perfect next move (a move with no weaknesses that provides advantage.) But chess is extremely complex. There are over 1043 possible positions (that’s over trillions of options!). Because of these facts, “solving” chess became the goal for computer scientists–computer scientists from 1945 until the early 2000s wanted to make a computer that could play a perfect game of chess (and always win).

The first mention of a computer playing chess occurred in 1945 when Alan Turing described what computers might be capable of in the future. Initial chess programs were simple, only capable of a few moves. It wasn’t until 1957 that Alex Bernstein3 wrote a program that could play a full-fledged game of chess against a human. By 1970, the first computer chess competition was held in order to find the best chess playing program, which Northwestern University’s program won. In 1997, a program called “Deep Blue” beat a chess grandmaster4 for the first time. Chess programs have become so advanced that human players are no longer able to beat them. The last time a human player won a game of chess against a computer was 2005!

Once scientists and researchers made a program that couldn’t lose, it became a challenge to develop a program that did not just win outright, but rather played more like a human. Previous chess AIs would analyze entire libraries of chess games to determine the best move, but this isn’t how a human plays the game – the level of information humans have available to them is limited and sometimes, they make risky moves which don’t pan out.

Recently, a collaboration between the University of Toronto, Cornell University, and Microsoft yielded an AI named Maia5, a program which analyzes individual moves made in similarly played games of chess instead of pulling from a library of completed games in order to produce a more human-like play style. When the program predicted moves in a game of chess, she accurately guessed the human players’ next move over 50% of the time. Maia is the first computer with such accuracy, making her as close to a human player as a computer can possibly be. This AI can make honest mistakes despite having the ability to play chess perfectly. Maia is interesting because, unlike most AI, the level of difficulty she plays chess can be adjusted at will. She not only plays like a human, but she can play at several different skill levels, meaning Maia could beat a grandmaster and also lose to a chess newbie.

Chess is an old game. It has been played by humankind for hundreds of years and has taught us a lot about strategy, probability, and programming. Now, chess is giving us great insight into the world of machine learning.

The only question is: how will chess help us next?

Sources