C++ Neural Networks and Fuzzy Logic by Valluru B. Rao M&T Books, IDG Books Worldwide, Inc. ISBN: 1558515526   Pub Date: 06/01/95

Tic-Tac-Toe Anyone?

David Fogel describes evolutionary general problem solving and uses the familiar game of Tic-Tac-Toe as an example. The idea is to come up with optimal strategies in playing this game. The first player’s marker is an X, and the second player’s marker is an O. Whoever gets three of his or her markers in a row or a column or a diagonal before the other player does, wins. Shrewd players manage a draw position, if their equally shrewd opponent thwarts their attempts to win. A draw position is one where neither player has three of his or her markers in a row, or a column, or a diagonal.

The board can be described by a vector of nine components, each of which is a three-valued number. Imagine the squares of the board for the game as taken in sequence row by row from top to bottom. Allow a 1 to show the presence of an X in that square, a 0 to indicate a blank there, and a -1 to correspond to an O. This is an example of a coding for the status of the board. For example, (-1, 0, 1, 0, -1, 0, 1, 1, -1) is a winning position for the second player, because it corresponds to the board looking as below.

 O       X
     O
 X   X   O

A neural network for this problem will have an input layer with nine neurons, as each input pattern has nine components. There would be some hidden layers. But the example is with one hidden layer. The output layer also contains nine neurons, so that one cycle of operation of the network shows what the best configuration of the board is to be, given a particular input. Of course, during this cycle of operation, all that needs to be determined is which blank space, indicated by a 0 in the input, should be changed to 1, if strategy is being worked for player 1. None of the 1’s and -1’s is to be changed.

In this particular example, the neural network architecture itself is dynamic. The network expands or contracts according to some rules, which are described next.

Fogel describes the network as an evolving network in the sense that the number of neurons in the hidden layer changed with a probability of 0.5. A node was equally likely to be added or deleted. Since the number of unmarked squares dwindles after each play, this kind of approach with varying numbers of neurons in the network seems to be reasonable, and interesting.

The initial set of weights is random values between -0.5 and 0.5, inclusive, according to a uniform distribution. Bias and threshold values also come from this distribution. The sigmoid function:

1/(1 + e-x)

is used also, to determine the outputs.

Weights and biases were changed during the network operation training cycles. Thus, the network had a learning phase. (You will read more on learning in Chapter 6.) This network is adaptive, since it changes its architecture. Other forms of adaptation in neural networks are in changing parameter values for a fixed architecture. (See Chapter 6.) The results of the experiment Fogel describes show that you need nine neurons in the hidden layer also, for your network to be the best for this problem. They also purged any strategy that was likely to lose.

Fogel’s emphasis is on the evolutionary aspect of an adaptive process or experiment. Our interest in this example is primarily due to the fact that an adaptive neural network is used.

The choice of Tic-Tac-Toe, while being a simple and all too familiar game, is in the genre of much more complicated games. These games ask a player to place a marker in some position in a given array, and as players take turns doing so, some criterion determines if it is a draw, or who won. Unlike in Tic-Tac-Toe, the criterion by which one wins may not be known to the players.

Stability and Plasticity

We discuss now a few other considerations in neural network modeling by introducing short-term memory and long-term memory concepts. Neural network training is usually done in an iterative way, meaning that the procedure is repeated a certain number of times. These iterations are referred to as cycles. After each cycle, the input used may remain the same or change, or the weights may remain the same or change. Such change is based on the output of a completed cycle. If the number of cycles is not preset, and the network is allowed to go through cycles until some other criterion is met, the question of whether or not the termination of the iterative process occurs eventually, arises naturally.