Calvin Hayes
September 21, 2005
Period 5

Project Proposal

I. Title
The Use of Genetic Algorithms in Machine Learning; Applications to Othello and Other Games


II. Problem Statement
The project will be to design a program that is capable of playing the board game Othello at a high level. This program will use genetic algorithms to determine weights for specific heuristic values that will decide the machine's line of play.


III. Purpose
Genetic algorithms are becoming more and more popular in the field of artificial intelligence as a way to search many different combinations of settings to find an optimal state. The results of the project can be used to determine how successful this particular algorithm is in setting reasonable heuristic weights that can be used by the computer to play Othello better than a program with these weights set arbitrarily. These results can potentially be generalized to other uses of this algorithm.


IV. Scope of Study
The eventual goal of this project is for the program to play Othello well. At the most basic level, the machine learning from the genetic algorithm should improve upon any arbitrarily set values for the weights of the heuristics. The program, however, would be a true success if it, using these weights and the heuristics that I have set up, could win games against most or all of the other common Othello programs, those that use a simple 'greedy' minimax search or basic weighted board squares. I would be truly satisfied if the program could beat me. To acheive these results, some knowledge of Othello strategy is necesary, to determine useful heuristics to be weighted. Additionally, other AI techniques, such as minimax trees and alpha-beta pruning will be neccesary to help the program run most effectively and efficiently. If I am immediately successful in working with Othello, I hope to extend these algorithms to other, more complicated games, and see the results there.


V. Background and Review of Current Literature/Research in This Area
Clearly the most successful use of artificial intelligence in game playing is Deep Blue, IBM's chess system that plays at the grandmaster level. Deep Blue, however, used data from many hard-coded games played previously by grandmasters to weight its heuristics, rather than 'learning' the optimal values on its own. Machines have also been 'taught' to play Go, Checkers, and Othello, among other games. Artifical Intelligence is also of unique value in modern video games. A genetic algorithm is used to search for an optimal state, composed of an array of individual values used to make decisions. In doing so, it compares the success of each state in acheiving the desired results. Those states that fare the worst are eliminated, and those states that fare the best are morphed together to form new states. Additionally, in a small percentage of cases, these newly formed states are 'mutated' by a small amount by changing one of the values. One can easily see the comparisons to evolution. In effect, this algorithm is simulating the process of Darwinian evolution to build an ideal compilation.


VI. Procedure and Methodology
In order to run the algorithm that I am researching, I will first need to build the environment for which it will run. I will use the Python programming language for these tasks, because it is easiest to code and read. The first environment that I will build to test the genetic algorithm is the 8-queens problem, where the computer will attempt to arrange 8 queens on a chessboard such that none attack each other. This is a good environment for which i can develop a good algorithm and check to see if it is successful. Ideally, I should be able to complete this first testing before November 1, 2005. At this point, I will begin to attack the Othello problem. I will first need to create the Othello environment for the machine to play in. Then I will need to implement the basic machine thinking so that it can play effectively with arbitrarily set heuristic weights. These basic Othello phases should be complete by December 1, 2005. I would now be able to initialize the basic genetic algorithm for testing. I will analyze the results to determine the following: the best form of genetic algorithm for helping the machine to learn the best weights, who or what is best to play against the machine so that it may train itself, and the best way to evaluate the play of each state of heuristic values. This last phase of the plan should be complete by February 15, 2006.


VII. Expected Results and Value to Others
I hope to create a machine that is an excellent player of Othello, by finding the state of heuristic weights that is most successful. Future programmers can learn from my project the potential successfulness of the genetic algorithm for determing optimal heuristic weights in a reasonable amount of time. I do not know at this time how I will track my results, because I do not know how successful my algorithms will be. If my algorithms are successful, I will be able to focus on the more complex aspects of my analysis, the differing forms of the algorithm and the way in which the machine is 'taught'. In my algorithms are unsuccessful, I will need to determine the reasons for their failure. I will chart my progress in a daily log.