PROBLEM DESCRIPTION

The Game

The game of “Tic-Tac-Toe” is quite simple; generally thought of as a “kid’s game.” It is played on a 3 × 3 board. Initially, the board contains nothing but blank squares. The two players, X and O, each place X’s and O’s on the board, one at a time, alternately. The player who places three of his pieces in a row either horizontally, vertically, or diagonally wins the game. The game is a tie if nobody has won after the board is filled.

Traditional AI Methods

Traditionally, there are two classes of methods for solving a problem such as playing Tic-Tac-Toe: (1) the brute force method or (2) some sort of heuristic search method.

In solving such a search problem, the decision tree can be searched breadth first, expanding the game playing tree as far as possible, and examining each possible move and its merits. By looking ahead in this fashion, the ramification of each possible move can be examined using a minimax technique which involves computing a function value to evaluate possible solutions and assign a numerical value to each move according to player’s chance of winning the game. The higher the probability of winning the game as a result of making a particular move, the higher the evaluation function value assigned to that particular move. A computer program employing such a strategy would then select the move that results in the maximization of its own score while simultaneously minimizing its opponent’s score.

The problem with the aforementioned approach is that for many games, including tic-tac-toe, the search tree grows too big too quickly. The combinatorial explosion prohibits searching far enough down the decision tree for effective solutions.

As an alternative, any of a number of heuristic search rules can be used to eliminate branches of the search tree from consideration, to prune the tree. This is in effect a depth first search. Such an approach requires a lot of effort on the programmer’s part to carefully choose which branches to discard. For most problems, however, the breadth first search method is still used even though it is much less efficient.

A problem shared by both the breadth first and the depth first methods is the lack of robustness. Once a program is written to play a specific game, it requires a lot of work to change the evaluation function and the search methods to play a different game, even though it might be a slight variation of the original game. Thus, such a program is only as good as the evaluation function, and it does not learn from its mistakes to get any better.

GA and Game Playing

Genetic algorithms are search algorithms based on the principle of natural selection. For game playing, each string in a GA population can represent different strategies for playing the game. Initially, a fixed number of strings are generated randomly. Then, during the selection process, each strategy is required to play a certain number of games against other strategies. A win-loss record is kept for each strategy. The ones that perform badly are discarded while the strategies with the most wins are kept. After selection, crossover, and mutation are performed on those strings to create new strings which form the new population. After this process is repeated a number of times, the population pool will consist of strategies that are fit to survive (i.e., playing a good game of tic-tac-toe).

GA IMPLEMENTATION

Configuration Encoding

To develop a strategy for the game of tic-tac-toe, there exists a desired move for each board configuration. The game of tic-tac-toe is played on a board of nine squares. Each square can either be marked by an “X,” an “O,” or a blank. The total number of possible configurations is 3⁹ or 19683. Here, it is assumed that a ternary string of length nine is used to code each possible configuration. “0” is used to represent a blank, “1” is used to represent an “X,” and “2” is used to represent an “O.” For example, the following board could be represented as shown: