2011 VIRTUAL SCIENCE FAIR ENTRY
Purpose
The purpose of this project was to determine the best algorithm for strategy games.
Type
Computer Science
Grade
9^{th} Grade
Difficulty of the Project
Requires technical knowledge
Cost
There are no costs associated with this project.
Safety Issues
There are no safety hazards associated with this project.
Time Taken to Complete the Project
The total time taken to complete this project is as follows:
 Programming: 147 hours
 Board Construction: 4 hours
 Written Report: 18 hours
Objective
The purpose of this project was to determine the best algorithm for strategy games.
Materials and Equipment
 A simple text editor such as notepad
 A computer (Windows 7 Ultimate 64bit, 4GB RAM, Intel Core 2 Duo 3.00 GHz)
 Google Chrome (8.0.552.237)
Introduction & Terms and Concepts for Background Research
The goal of endowing humanlike intelligence to inanimate objects has a long history. Modern computers can perform millions of calculations per second, but even with all of this remarkable speed, true logic has yet to be achieved. Every year that passes, computers come closer and closer to achieving this goal, or at least mimicking true logic. Game strategy is one of the most common applications of artificial intelligence. Algorithms are a set of instructions a computer follows to achieve a task or goal. There are three main types of algorithms for intelligence in games: Alphabeta, learning, and hybrids. Chess was one of the first games to implement artificial intelligence with the discovery of the Alphabeta algorithm in 1958 by scientists at CarnegieMellon University (Friedel, n.d.). The Alphabeta algorithm was the first feasible algorithm that could be used for strategy in games. As artificial intelligence in games evolved and became more complex, a more modern “learning” approach has been adopted. Even though there have been major advancements in both “learning” style algorithms and Alphabeta algorithms; a hybrid utilizing elements of both algorithms results in a stronger, more efficient, and faster program. On the forefront of the quest for artificial intelligence, these algorithms are playing vastly important roles.
The Alphabeta algorithm has a long history of success. The first use of the algorithm in a game was in the 70’s and 80’s by the “Belle” computer. Belle remained the champion of computer chess until being superseded by the Cray supercomputer (Friedel, n.d.). Belle was the first computer to be successful using the early forms of the Alphabeta algorithm. Deep Blue later used the algorithm in order to defeat chess grandmaster Garry Kasparov; this was a major development for the artificial intelligence community as it was the first time in history a computer had beaten a chess grandmaster in a standard match. Over time, the algorithm has been revised, updated, and modified to the point where several versions of the algorithm exist that all use the same core principles.
The Alphabeta algorithm uses bruteforce calculations (thousands every second) to make decisions. The Alphabeta algorithm uses the minimax principle (one player tries to maximize their score while the other tries to minimize it) and efficient evaluation techniques in order to achieve its logic. Alphabeta is a “game tree searcher,” or in other words, it forms a hierarchy of possible moves down to a defined level (i.e. six moves). In some variations, eliminating symmetries and rotations is used to reduce the size of the game tree (Lin, 2003). After the tree is formed the algorithm then proceeds to evaluate each position in the tree based on a set of rules intended to make the computer play stronger, this is called heuristics. The reason why Alphabeta is fast, yet strong is that it ignores portions of the game board (Lin, 2003). It decides which portions to ignore based on finding the best move per level (or move) and ignoring all the moves that aren’t the best and the moves under them. Alphabeta can calculate two levels of moves with 900 positions in 0.018 seconds, three levels of moves with 27,000 positions in 0.54 seconds, four levels of moves with 810,000 positions in 16.2 seconds, and so on. These efficiencyimproving techniques are responsible for the small calculation times and improved game strategy that the algorithm provides.
Learning style algorithms are another popular type of algorithm for game use. Learning style algorithms aren’t necessarily a recent creation. They have been in use for approximately thirty years, but have been met with limited success until recently. In this approach, an algorithm uses its own experiences, or a large database of preplayed games to determine the best moves. Unfortunately, learning algorithms have also incorporated the “bad” strategies utilized by novice players. Over time, improvements have been made so that an algorithm can be a threat to intermediate players in most action games; however, learning algorithms are often unsuccessful in games requiring strategic play. The Chinook program uses the most notable learning algorithm. The program spent eighteen years calculating every possible move for the game of checkers. But the Chinook’s algorithm is considered by some not to be a “true” learning algorithm since it already knows all of the possible outcomes for every move (Chang, 2007). Chinook, however, does adjust its playing style for each player’s strategy; this is where its element of learning comes into play (Chang, 2007). Learning algorithms are considered closer to true intelligence than other algorithms that use bruteforce calculations such as Alphabeta. Compared to pure calculation algorithms, they play games more like humans and even show very limited aspects of creativity and selfformed strategy.
A hybrid algorithm combines the bruteforce style of the Alphabeta algorithm with the flexibility of the learning style algorithm. This method insures that the full ability of the computer is used while it is free to adapt to each player’s individual game style. Chinook successfully utilized this technique to make a program that is literally unbeatable. Because of the Chinook program, the game of checkers has been “solved.” No matter how well an opponent plays, the best they can do is end in a draw (Chang 2007).
Other champion programs have used just one style of algorithm in order to win. As a result, no particular algorithm has been measured or proven to be dominant. Game developers choose which algorithm to use based largely on personal preferences and on a lack of consensus from the artificial intelligence community as to which algorithm is superior. There are weaknesses that can be used to determine which algorithm will prove to be inferior. For example, the Alphabeta algorithm does not generate all possible moves from the current condition of the game. Alphabeta assumes that the opponent will make the best possible move available. If a player makes a move that is not in their best interest, the algorithm will not know how to respond because that move’s game tree has not been calculated. The opponent can trick the algorithm by making suppar moves, and forcing it to recalculate. It is also important to note that the Alphabeta algorithm can use tremendous amounts of time when calculating more than a couple of moves. The learning algorithm has its flaws, too. If it encounters an unknown strategy, the algorithm will be helpless against its opponent’s moves. The most likely way to minimize these flaws is to combine these algorithms into a hybrid. If the hybrid encounters an unknown strategy, it can then use the Alphabeta style game tree to determine the possible moves from that point. Likewise, if the opponent uses a move not calculated by the bruteforce method, it can then use learned strategies to defend itself. The hybrid algorithm will be faster and have better winning strategies than either the Alphabeta, or the learning style algorithms.

1
 2