What it Takes to Program a World Champion
by Anthony Emma
The thought of having a computer play on the same level as a master is very difficult to achieve. The first computers were able to play games at very basic levels because they were limited in memory and speed. Today, computers have more memory and processor speed, and yet championship computer programs still use the same techniques as their ancestors. Despite breakthroughs in hardware, there remain games (such as Go) that cannot be played adequately by a computer because of time and space limitations. This paper will examine what it takes to program a championship caliber computer and how today’s technological advancements are being applied to old game playing strategies.
The main problem facing many, if not all, game-playing computers is the Contingency problem.1 The Contingency problem states that a state of the game tree is difficult to assign a value to, and that with each expansion (or move) there are new possible contingencies that arise. The Contingency problem is demonstrated when walking. We see where we want to walk, however new unforeseen problems may arise, and so we keep our eyes open looking for possible contingencies, for example a moving car.
As a result, we are only certain about the goodness of the current board when we have completely expanded it. Unfortunetly, in many games this is far too complicated and massive a structure to deal with. For example, an expanded tree of Chess has about 35100 states,2 which is too many to be analyzed in the time to make a move. Consequently, this is one of the reasons why computers are able to match human play. A computer can now generate more of the tree, and thus provide a more accurate estimation of the "goodness" of a move.
The championship-level computer programs are those that are able to effectively overcome the Contingency problem, and choose their moves with high confidence and correctness. Evaluation procedures (which estimate the value of a node) can be improved in many ways, and those programs with the most accurate evaluations will have confidence in their moves and excel in game play. The following is a presentation of three championship computer programs (Deep Blue, Logistello, and Chinook), and how they have dealt with the Contingency problem in their respective games (Chess, Othello, and Checkers respectively).
Chess
Gaming AI solving Real-World Problems
"The last time I was surprised by the strength of the machine. This time I know what to expect… I mustn’t take the match too lightly"
–Garry Kasparov
By far, the game of Chess has attracted more study than any other area in Gaming Artificial Intelligence. This is largely due to the belief that Chess is thought to require intelligence to play, and that if a program was constructed that could beat any human, it would prove that a computer possesses some form of intelligence. Another attractive feature of Chess is that the state tree is large, but not enormously large. The tree has an average branching factor of 35, and games tend to last 100 moves. This would result in a tree with a total of 35100 nodes. While this may seem large it is not as complicated as many other games, such as Go.
The field of computerized Chess has progressed rapidly due to this overwhelming amount of research. It was said in 1957 that within 10 years computers would beat the human world champion.2 In reality it took 40 years, but eventually a computer was able to defeat the human world champion (Garry Kasparov). The first computer to defeat a grand master in tournament Chess play was Deep Blue, sponsored by IBM.3
Deep Blue solved problems much like any other game-playing program, by creating the game state tree and evaluating board configurations. What makes Deep Blue so successful is the number of different board configurations it can analyze. When Deep Blue beat world champion Garry Kasparov it was able to analyze 200 billion moves per three minutes (the amount of time given to a player to move). Deep Blue is able to generate so many moves because it’s hardware geared toward chess specific functions, and also because it implements parallel computing.
When Deep Blue is asked to make a move it first generates all the possible board configurations to which it can move to, and then sends each board configuration to a computer to analyze and ultimately determine how good the board is. When a computer finishes it’s task it is given a new one, and in this fashion all computers will be using their processing power to break down the overwhelming task of finding the best move. In addition, nodes of the tree that are the most promising will get more attention than those that will clearly hurt Deep Blue. Instead of expanding the tree in a brute-force approach, the computer "intelligently" expands the part of the tree that it feels will contain the optimal move (a concept known as metareasoning, reasoning about reason). Together with 256 processors working in tandem, Deep Blue is able to look 12 moves into the future before selecting a move.
On the surface it may seem wasteful to spend millions of dollars and manpower to solve a problem such as chess. However, behind all the Chess research are practical solutions to billion dollar real-world problems. Deep Blue began back in 1989 at Carnegie Mellon not as a venture in Artificial Intelligence, but instead as an effort to understand how to use parallel processing to solve complex computing problems. Creating a championship Chess player was not the goal of Deep Blue. Instead, Chess was merely a good example of a complex problem that could be better solved using parallel processing to give us insight on it’s effectiveness.
"Well, we’re taking some of the lessons we learned from building this system and applying it to other complex and difficult problems that require a tremendous amount of computational power. The computer that we’ve brought [to the event], Deep Blue, is capable of doing extraordinary amounts of computation in order to choose a good chess move. And, applying and creating a system for other problems would be the ultimate goal of a system like this."
–Murray Campbell, Deep Blue founder
A proposed problem that could be aided by Deep Blue’s computational power is simulating molecular dynamics (the interaction between atoms and molecules). This would allow pharmaceutical companies to predict the behavior of certain drugs before ever testing them in the laboratory. Deep Blue could also be applied to the problem Air Travel companies have with scheduling planes and passengers. For both problems, the millions spent on Deep Blue are minor compared to the possible billions gained in revenue. So while it may seem like a waste to spend money on making Deep Blue faster at chess, it is merely a measuring stick of how efficient parallel computing can solve real-world problems.
Othello
Eliminating the Weak Link, The Experts
"A minute to learn, a lifetime to master"
Othello programs have made great progress over the years, and many, as early as 1980, were able to beat very talented human opponents. However, the progression and evolution of Othello followed a much different path than that of Chess. Deep Blue lost it’s first encounter with Garry Kasparov because Kasparov changed strategies in the middle of the match. As a result the Deep Blue staff worked with Chess Grandmaster Joel Benjamin to add expert information into the program, and as a result the second confrontation was won by Deep Blue (whose programmers warned Kasparov that his strategy will no longer work). Progress in Chess was made in the form of involving an expert into the programming aspect, thereby increasing the accuracy of the evaluation function.
Othello programs of the 70s and 80s were able to expand up to 10-ply, and yet the strongest Othello program, Logistello, only expands 3-ply.4 The difference between the two is that older versions have man-made evaluation functions, whereas Logistello learns its own evaluation function from repeated play. Humans have problems expressing subconscious processes that determine how good a board is, and thus Logistello eliminates the weakest part, the expert.
It is known that the problem of determining an evaluation function for a given state is difficult because of the Contingency problem. A board has different features associated with it, and the difficulty is determining what the features are and determining the importance of those features. Logistello was preprogrammed 11 features to notice on a given board configuration (that can be rotated to form 46 different features), but Logistello’s creator states that while computers are bad at detecting features, they are good at fixing weights. Thus the problem of creating an evaluation function is made easier because a human needs only to identify the features, and the computer will itself determine the weight/importance associated with each feature.5
Logistello is able to automatically adjust its weights by playing itself, learning from mistakes and successes, and ultimatly modifying its evaluation function by altering the weights associated with each features. It converts the 46 programmed features into 100,000 binary features and then attempts to modify the weights for each feature as it plays a series of games. After one month of self-playing and learning Logistello was on the same scale as champion Othello players.
In 1997 Takeshi Murakami (World Othello Champion) challenged Logistello to a tournament style match. The match was overwhelmingly dominated by Logistello, who won 6-0, with only one game coming close to a loss (4-point victory).4 Logistello’s creator, Michael Buro, states the ideas he used were successful, but still desires more research in games with larger complexities:
"After the great success of learning backgammon and Othello programs, it now seems clear that future progress in more complex problems (in which brute-force search is infeasible) – such as Go — also depends on advances in machine learning"5
Logistello’s contribution to Gaming Artificial Intelligence is the idea of eliminating the use of expert players to rank to goodness of features, and instead allow the computer to exercise it’s own heuristic function.
Checkers
Memorizing the Game Tree
"Playing chess is like looking out over a limitless ocean; playing checkers is like looking into a bottomless well"
- Checkers World Champion, Marion Tinsley
While much research was being pursued in the field of computer Chess, little study was given to Checkers. The problem of Checkers had been thought to have been solved in 1975 when a program defeated a master in an informal match. (In reality the game was won because of human error). However, the field of Checkers has received new attention because it is a very good example of how Artificial Intelligence techniques can be applied to a game that is difficult, but easier to manage then Chess.
Chinook is a world championship Checkers program that defeated reigning champion Dr. Marion Tinsley in 1990.6 In actuality creating a championship checkers program was only a stepping stone towards Jonathan Schaeffer’s (Chinook founder) goal of solving the game of checkers. Fortunately Schaeffer was able to use the vast amounts of research done on Chess to his advantage when he implemented Checkers. However, there is a very important distinction between the two games that Schaeffer needed to address to create a world champion computer program.
Game play in Checkers is much more subtle and gradual than in Chess. With just 6 pieces on the board Checkers’ endgames can take as many as 40 moves to win. One classic example in Checkers is known as the "Second Position".
This is a position that has been studied as far back as the 1750s, and it is shown to be a win for white if played correctly. The complexity arises because to win white it must perform a sequence of 40 moves to achieve a victory, and any deviation from this sequence will throw away the win. Even more complicated 4 versus 4 scenarios have sequences of 100 moves to claim a win.6
The one advantage the computer has is that the game of Checkers is much simpler than Chess and thus more of the tree can be expanded. The game of Checkers has an average branching factor of 8, compared to 35 in Chess. This allows Chinook to expand about 1,000 positions per second (about 20 moves into the future). Still, this does not decisively give the advantage to the computer, because in the endgame phase grandmasters’ are also able to look more than 20 moves in the future.
To combat this Chinook introduces an idea used in Chess, but to a greater degree. Chess programs store perfect endgame databases with anywhere from 3 to 5 pieces on the board, but in Chess many games don’t last long enough to reach them. In Checkers a typical search from the root of the tree will result in endgame boards that are 20 levels deep in the tree. Chinook stores its endgames in a database, and then simply queries that database about whether the board is a win, draw, or loss. The advantage is that moves stored in the database have perfect knowledge (so that if the database says it’s a win, it is a guaranteed win). When Chinook competed in the U.S. Open it was able to declare 8 games over before the 10th move.
As in Chess, Checkers was only able to progress due to the evolution of the computer industry. Chinook’s endgame database compressed is roughly six gigabytes. The database contains all board configurations with 8 or fewer pieces. The final result is 444,000,000,000 boards (444 billion).7 This database is what allows Chinook to play effectively, because it can determine whether a given move is guaranteed to be a win, and then all it has to do is merely pick the series of moves that leads to that guaranteed win.
Chinook plays as good as a champion because it is able to "memorize" the results of 444 billion boards. While the program still has flaws, this knowledge is enough to defeat all but a few players in the world. Deep Blue followed the path that increasing processing power is better, but Chinook raises questions as to whether increasing storage space may be an adequate answer for playing championship games.
It may seem that every board game has been developed to a championship caliber. However, there are still many games that just now are starting to be researched. The most notable game that has not been dealt with is called Go. Without describing the rules of the game each player can have up to 300 moves to choose from, and so typical tree searches are infeasible. Current programs that use large rule based knowledge can be easily beaten by an amateur Go players, which means Go is currently where Chess was 40 years ago. Because of this new ideas are being discussed about game play. In addition, research in this field is also sparked by a $2,000,000 prize to the first program to beat a top-level Go player.2 At the time of this paper the reward has yet to be claimed.
The programs discussed in the paper all use the same general strategies to excel in their particular field. The only difference is that particular areas of the intelligence need to be developed differently to suit the difficulty of the game being played. Logistello excelled in Othello because good evaluation functions did not exist, and so the computer calculated its own evaluation function. Deep Blue excelled in Chess because hardware has allowed it to perform a brute-force search to find the next move. Chinook excelled in Checkers because it needs to do better than grandmasters in the endgame phase. Similarly the converse is also true, that Deep Blue does not need an endgame database (since it would be rarely used) nor a "learned" evaluation function (since research has given rise to good evaluation functions). Just like human minds, computer programs need to adapt to the game they are playing to achieve championship quality play.
Bibliography