Industrial Applications of Genetic Algorithms:Genetic Algorithms for Game Playing

Previous | Table of Contents | Next

## Chapter 17
Genetic Algorithms for Game Playing

Jiefu Shi

shij@agcs.com

ABSTRACT

This chapter examines genetic algorithms (GA) and machine learning using the game of tic-tac-toe. After “learning” acceptable strategies for playing the game, the GA-driven computer player is able to play a competent game of tic-tac-toe. Results obtained using a GA are compared to results obtained using alternative AI techniques.

INTRODUCTION

Game playing has long been a research favorite of the AI community. AI researchers have developed numerous search methods for game playing. The search methods developed can either be brute force search or a more “intelligent” heuristic search. The current project focuses on the simple game of “Tic-Tac-Toe.” Genetic algorithms are used to develop strategies under different situations, and through a “survival of the fittest” rule, eliminate bad strategies and allow the good strategies to survive.

Even though “Tic-Tac-Toe” is a very simple game, the goal of the current project is to explore game playing strategies using genetic algorithms. Because of the robustness of GAs, the parameters and operators chosen to solve this problem should be applicable to other similar problems in the realm of game playing.

LITERATURE REVIEW

There are many books and papers on game playing, machine learning, and genetic algorithms. The following list contains a few which are related to this problem.

One of the first papers written on game playing and machine learning is Some Studies in Machine Learning Using the Game of Checkers (Samuel, A. L., 1959). In this paper, Samuel examined machine learning and the game of checkers. Samuel developed 26 parameters which he used to determine how “good” a particular board position is. Each parameter has a value associated with it to specify its relative importance. He constructed a polynomial function with these parameters to give each position a value. The polynomial looks like: position value =

His goal was to find the xn values that represent the most effective strategy for playing checkers. He started out by assigning the xn random values and let two strategies play each other, kept the set of values which won the most games, and continued to generate new values. After many games were played, he found that the strategy which survived at the end had effectively “learned” to play the game of checkers.

Unfortunately, as in most situations, this random search can take quite a long time. However, Samuel did produce a good strategy which was able to beat the best human players of his day. The current project is similar to the work of Samuel. Here, the hope is that a search conducted using a GA will allow for the development of more effective strategies in less time.

Another early work on game playing was conducted by Michie (1962). In this paper, Michie examined the process of machine learning and the game of tic-tac-toe. He found around 300 distinct positions that the opening player can be faced with. He then took all the possible moves at each position and assigned a value to represent its relative merit; the higher the value, the better the move. He used a selection process that chose the move that was associated with the highest value. If the move resulted in a win, he increased the value associated with that move. If the move resulted in a loss, he decreased the value. So at first, the game was played randomly. But as the game playing program won and lost games, it learned a little more about the game. After a number of games played, the machine was successfully trained to play the game of tic-tac-toe.

Here, a similar approach is employed. However, in the current effort a GA is used to generate new strategies. These strategies are encoded into strings, and there exist a population pool of more than just one strategy to be considered at each iteration. Michie used his machine to play human players. Here, the GA-generated strategies are pitted in competition against other computer strategies.

A good introductory textbook on AI is Ginsberg’s Essentials of Artificial Intelligence (Ginsberg, 1993). In his book, Ginsberg outlined the different search algorithms and heuristics which are used in the AI community to solve game playing problems. To solve the current problem, the game tree is expanded and a search algorithm is used to traverse the tree in hopes of finding an optimal solution each time a move is to be made. Here, enumeration would result in an optimum solution, but it is time consuming to the point of infeasibility.

There have also been several successful attempts at machine learning using neural networks. A good reference on neural networks and machine earning is Neural Networks - A Comprehensive Foundation (Haykin, 1994). In his book, Haykin discusses neural networks and the different types of learning including supervised learning, unsupervised learning, competitive learning, and others. Certainly, the neural network approach is feasible in a variety of problems (perhaps even here). A neural network tic-tac-toe program would be an outstanding opponent for the GA tic-tac-toe game playing program. Unfortunately, such a comparison is not presented in the current chapter.

The textbook Genetic Algorithms in Search, Optimization & Machine Learning (Goldberg, 1989) serves as a good introduction to GAs. Goldberg covers the basics of GAs along with providing a PASCAL computer code for implementation. Goldberg’s code proved to be very helpful for the current project. Even though the program generated in this effort was written in C, the PASCAL version was used as a reference to the standard GA operators such as crossover and mutation. Goldberg has a rather large section in his book devoted to machine learning via classifier systems. This section of his book also provided several good ideas for the current problem.

An early attempt at machine learning using GAs was done by Bagley on the game of hexapawn. In the paper, The behavior of adaptive systems which employ genetic and correlation algorithms (Bagley, 1967), Bagley examined GA and game playing. He used the game of hexapawn, which is played on a 3 X 3 chessboard with three pawns to each side. He used the basic reproduction, crossover, and mutation operators as well as diploid strings, dominance, and inversion operators. His program performed well after running through a number of generations.

Tic-tac-toe, however, is more complicated than the hexapawn game. Whereas hexapawn has only 52 unique configurations, tic-tac-toe has 612. This makes the current problem much more difficult to solve since there are far more points in the search space.

Previous | Table of Contents | Next

Copyright © CRC Press LLC