Journal of Intelligent Learning Systems and Applications, 2011, 3, 37-44
doi:10.4236/jilsa.2011.31005 Published Online February 2011 (http://www.SciRP.org/journal/jilsa)
37
Playing Tic-Tac-Toe Using Genetic Neural
Network with Double Transfer Functions
Sai Ho Ling1, Hak Keung Lam2
1Faculty of Engineering and Information Engineering, University of Technology Sydney, New South Wales, Australia; 2Division of
Engineering, King’s College London, London, UK.
Received October 4th, 2010; revised November 3rd, 2010; accepted January 4th, 2011
ABSTRACT
Computational intelligence is a powerful tool for game development. In th is paper, an algorithm of pla ying the game
Tic-Tac-Toe with computational intelligence is developed. This algorithm is learned by a Neural Network with
Double Transfer functions (NNDTF), which is trained by genetic algorithm (GA). In the NNDTF, the neuron has two
transfer functions and exhibits a node-to-node relationship in the hidden layer that enhances the learning ability of
the network. A Tic-Tac-Toe game is used to show that the NNDTF provide a better performance than the traditional
neural network does.
Keywords: Game, Genetic Algorithm, Neural Network
1. Introduction
Games such as Backgammon, Chess, Checkers, Go,
Othello and Tic-Tac-Toe are widely used platforms for
studying the learning ability of and developing learning
algorithms for machines. By playing games, the machine
intelligence can be revealed. Some techniques of artifi-
cial intelligence, such as the brute-force methods and
knowledge-based methods [1], were reported. Brute-
force methods, e.g. retrograde analysis [2] and enhanced
transposition-table methods, solve the game problems by
constructing databases for the games. For instance, the
database is formed by a terminal position [2]. The best
move is then determined by working backward on the
constructed database. For knowledge-based methods, the
best move is determined by searching a game tree. For
games such as Checkers, the tree spanning is very large.
Tree searching will be time consuming even for a few
plies. Hence, an efficient searching algorithm is an im-
portant issue. Some searching algorithms, which are
classified as knowledge-based methods, are threat-space
search and -search, proof-number search [3], depth-first
proof-number search and pattern search.
It can be seen that the above game-solving methods
depend mainly on the database construction and search-
ing. The problems are solved by forming a possible set of
solutions based on the endgame condition, or searching
for the set of solutions based on the current game condi-
tion. The machine cannot learn to play the games by it-
self. Unlike an evolutionary approach in [1], neural net-
work (NN) was employed to evolve and to learn for
playing Tic-Tac-Toe without the need of a database.
Evolutionary programming was used to design the NN
and link weights. A similar idea has been applied in a
Checkers game [4-7]. Other games such as Backgammon
[8], Othello [9] and Checkers [10] applying NNs or
computational intelligence techniques can also be found.
In this paper, a neural network with double transfer
functions (NNDTF) is proposed to learn the rules of
Tic-tac-toe. Each possible move is evaluated by a pro-
posed algorithm with a score. By maximizing the total
scores (evaluated values), the rules of Tic-Tac-Toe can
be extracted by the NNDTF. Different from the tradi-
tional feed-forward multiple-perception NN, some mod-
ified transfer functions with a node-to-node relationship
are introduced to the proposed NN. The modified transfer
functions are allowed to change the shapes during opera-
tion. Hence, the working domain is larger than that of the
traditional one. By introducing the node-to-node rela-
tionship between hidden nodes, information can be ex-
changed between hidden layers. As a result, the learning
ability is enhanced. A genetic algorithm (GA) [11] is
investigated to train the NNDTF. The trained NNDTF
will then be employed to p lay Tic-Tac-Toe with a human
player as an example.

Playing Tic-Tac-Toe Using Genetic Neural Network with Double Transfer Functio ns 38
This paper is organized as follows. An algorithm to
evaluate each move on playing the Tic-Tac-Toe will be
proposed in section 2. NNDTF will be presented in sec-
tion 3. Genetic Algorithm will be presented in section 4.
Training of the NNDTF using GA to learn the rules of
Tic-Tac-Toe will be presented in section 5. An example
on playing Tic-Tac-Toe will be given in section 6. A
conclusion will be drawn in section 7.
2. Algorithm for Playing Tic-Tac-Toe
The game Tic-tac-toe, also known as naughts and crosses,
is a two-player game. Each player will place a marker,
“X” for the first player and “O” for the second player, in
turn in a three-by-three grid area. The first player takes
the first move. The goal is to place three markers in a line
of any direction on the grid area.
An algorithm is proposed in this section to evaluate the
move on each grid. An “X” and an “O” on a grid are de-
noted by 1 and –1 respectiv ely. An empty grid is denoted
by 0.5. The following procedure is used to evaluate each
possible move.
1) Place an “X” on an empty grid.
2) Corresponding to step 1, sum up all the grid values
for each line in any direction, e.g., for a grid in the corner,
we have three evaluated values because there are three
lines to win or lose.
3) Remove the “X” placed in step 1 and place an “X”
on another empty grid. Evaluate this grid using the algo-
rithm in step 2. Repeat this process till all empty grids
are evaluated.
4) After evaluation, each grid will have been assigned
at least 2 evaluated values for all possible lines, e.g. the
center grid will have 4 ev alu ated valu es, corner g r ids will
have 3 evaluated values and other grids will have 2 eva-
luated values. There are totally 6 possible evaluated val-
ues: 3 (1 + 1 + 1), 2.5 (1 + 1 + 0.5), 2 (1 + 0.5 + 0.5), 1
(–1 + 1 + 1), 0.5 (–1 + 1 + 0.5) and –1 (–1 – 1 + 1). The
most important evaluated value of a grid is 3, which in-
dicts a winning of the game (3 “X”s in a line) if you put
an “X” on that grid. The priority of taking that move is
the highest. The second important evaluated value of a
grid is –1 (2 “O”s and 1 “X” in a line), which indicts that
the opponent should be prevented from winning the game.
The priority of taking that move is the second highest.
Using this rationale, the list of priority in a descending
order is: 3, –1, 2.5, 2, 1, 0.5. Based on these assigned eva-
luated values, a score will be assigned to each possible
move. First, each evaluated value i s assigned a score:
76 54
65 43
371625524,,.,    ,
3
2
13   and 2
1
05 2.  , The chosen scores have
the following properties,
65
4

  (1)
54
4

  (2)
43
4

  (3)
32
4

  (4)
21
4

  (5)
The sum of the scores of a grid is the final score. The
final scores will be used to determine the priorities of the
possible move. A higher final score of a grid indicates a
higher priority of that move. The reasons for choosing
the scores in this way with the properties of (1) to (5) are
as follows. As the evaluated value of 3 indicates a win-
ning of the game (3 “X”s in a line), the score of 6

must be the highest. There are at most four evaluated
values for a grid. Hence, 6

must be greater than 4
times the second largest evaluated values, i.e. 5 4

.
Consequently, the priority of a grid having an evaluated
score with a higher priority will not be affected by other
lower evaluated scores. For instance, consider a grid
having evaluated values of 3 and 0.5, and another grid
having evaluated values of 1, 2.5, 2 and 0.5. The final
score of the former grid (77 + 22) is bigger than and latter
grid (77 + 22 and 66 + 55 + 4 4 + 22). Thus, the “X” should
be place at the grid having an evaluated value of 3 to win
the game.
Take the game as shown in Figure 1 as an example,
we have 3 “X”s and 3 “O”s. The next move will be to
place an “X”. After assigning an empty grid to be 0.5, an
“X” to be 1, an “O” to be –1, Figure 1(b) is obtained.
Following Step 1 to Step 3, we obtain the evaluated val-
ues as shown in Figure 1(c). Based on Step 4, Figure
1(d) shows the final scores for the empty grids. As the
highest score is 873324, the most appropriate move is to
put an “X” on the bottom right corner. This move not
0.5 0.51
11-1
-1-1 0.5
-1, 2.5,
2.52.5,152906 3152
873324 3, -1,
2.5
(a) (b)
(d) (c)
Figure 1. Evaluation process.

Playing Tic-Tac-Toe Using Genetic Neural Network with Double Transfer Functio ns 39
only lines up 3 “X”s to win a game, but also prevents the
opponent to line up 3 “O”s. The second appropriate
move, indicted by the final score of 52906, can gain a
chance to win by lining up 2 “X”s, and prevent the op-
ponent to win.
3. Neural Network with Double Transfer
Functions (NNDTF)
NN was proved to be a universal approximator [12]. A
3-layer feed-forward NN can approximate any nonlinear
continuous function to an arbitrary accuracy. NNs are
widely applied in areas such as prediction, system mod-
eling and control [12]. Owing to its particular structure, a
NN is good in learning [2] using some learning algo-
rithms such as GA [1] and back propagation [2]. In gen-
eral, the processing of a traditional feed-forward NN is
done in a layer-by-layer manner. In this paper, by intro-
ducing a node-to-node relationship in the hidden layer of
the NN, a better performance can be obtaine d.
Figure 2 shows the proposed neuron. It has two acti-
vation transfer functions to govern the input-output rela-
tionships of the neuron: static transfer function (STF) and
dynamic transfer function (DTF). For the STF, the para-
meters are fixed and its output depends on the inputs of
the neuron. For the DTF, the parameters of the activation
transfer function depend on the outputs of other neurons
and its STF. With this proposed neuron, the connection
of the proposed NN is shown in Figure 3, which is a
three-layer NN. A node-to-node relationship is intro-
duced in the hidden layer. Comparing with the traditional
feed-forward NN [12], it was reported in [13] that the
proposed NN can offer a better performance and need
fewer hidden nodes. The details of the NNDTF are pre-
sented as follows.
3.1. The Neuron Models
We consider the STF first. Let ij v be the synaptic con-
nection weight from the i-th input component i
x
to the
j-th neuron. The output
j
 of the j-th neuron’s STF is
defined as,
jth neuron
)(
j
s
net

)(
j
d
net
1
x
2
x
in
n
xj

jj
p,1
jj
p,1
1j
z
1j
z
j
v1
j
v2
jnin
v
j
z
STF
DTF
Figure 2. Model of the proposed neuron.
1
x
2
x
in
n
x
1

2

h
n

1
y
21
p12
p
2
h
n
ph
n
p2
1
h
n
p
h
n
p1
11
v
12
v
h
n
v1
hin nn
v
2
in
n
v
1
in
n
v
11
w
21
w
1
h
n
w
1
z
2
z
h
n
z
out
n
w1
out
n
y
out
n
w2
outhnn
w
h
n
p11
h
n
p
Figure 3. Connection of the NNDTF.
1
in
n
j
j
siij
i
netx v 




 (6)
where 12i,,

, in n, 12j,,

, h n;in ndenotes the
number of in put and


j
s
net

is a static activation trans-
fer function. The activation transfer function is defined
as,
2
1
2
2
1
2
2
1
1
2
1
1
nin j
iij s
iin
j
s
in
nin j
iij s
i
j
s
xv mn
niij s
ji
siij
ixv m
e if xvm
netx v
eotherwise





 




 
















(7)
where j
s
mand j
s

are the static mean and static stan-
dard deviation for the j-th STF respectively. The para-
meters (j
s
mand j
s

) are fixed after the training
processing. Thus, the activation transfer function is static.
The output of the STF depends on the inputs of the neu-
ron only. From (7), the output value is ranged from –1 to
1. The shape of the proposed activation transfer function
is shown in Figure 4 and Figure 5. It can be observed
from these 2 figures that

1net fas f and


1net f as f.
Considering the DTF, the neuron output
j
z of the
j-th neuron is defined as,


j
jj
j
djdd
znet ,m,   (8)
where


j
d
net

is the DTF defined as follows,



2
2
2
2
2
2
1
1
j
jd
j
d
j
jd
j
d
m
j
j
d jjj
djdd m
eif m
net,m,
eotherwise















(9)

Playing Tic-Tac-Toe Using Genetic Neural Network with Double Transfer Functio ns 40
-1-0.8 -0.6 -0.4 -0.200.2 0.40.6 0.81
-1
-0.8
-0.6
-0.4
-0.2
0
0.2
0.4
0.6
0.8
1
net
f
m=-0.4 m=-0.2
m=0
m=0.2
m=0.4
Figure 4. Sample transfer functions of the proposed neuron
(

= 0.2).
-1-0.8 -0.6-0.4 -0.200.2 0.40.6 0.81
-1
-0.8
-0.6
-0.4
-0.2
0
0.2
0.4
0.6
0.8
1
f
net




Figure 5. Sample transfer functions of the proposed neuron
(m = 0).
where
11
j
dj,jj
mp z


 (10)
11
j
dj,jj
pz 

 (11)
j
d
mand j
d

are the dynamic mean and dynamic standard
deviation for the j-th DTF. 1
j
z

and 1
j
z represent the
output of the1j-th and 1-thj neurons respectively.
1
j
,j
p denotes the weight of the link between the
1-thj node and the j-th node and 1
j
,j
p denotes the
weight of the link between the 1-thj node and the
-thj node. It should be noted that if 1j, 1
j
,j
pis
equal to h
n,j
pand if h jn, 1
j
,j
p is equal to 1,j p. In
this DTF, unlike the STF, the activation transfer function
is dynamic as the parameters of its activation transfer
function depend on the outputs of the 1-thj and
1-thj neurons. Referring to (14), the input-output
relationship of the proposed neuron is as follows,
1
in
n
j
jjj
jds iijdd
i
znetnet xv,m,









 (12)
3.2. Connection of the NNDTF
As shown in Figure 3, the NNDTF has three layers with
in
n nodes in the input layer, h nnodes in the hidden
layer, and out n nodes in the output layer. In the hidden
layer, the neuron model presented in the previous section
is employed. The output value of the hidden node de-
pends on the neighboring nodes and input nodes. In the
output layer, a static activation transfer function is em-
ployed. Considering an input-output pair ),( yx , the
output of the -thj node of the hidden layer is given by
1
in
n
jj
jds iij
i
znetnet xv








 (13)
The output of the NNDTF is defined as,
1
out
n
l
lojjl
l
ynet zw,




12l, , , out
n (14)
11
out in
nn
ljj
odsi ijjl
li
netnetnetxvw













(15)
where
j
l
w denotes the weight of the link between the
-thj hidden and the -thl output nodes;


l
o
net

denotes the activation transfer function of the output
neuron. The transfer function of the output node is de-
fined as follows,



2
2
2
2
2
2
1
1
l
ko
l
o
l
ko
l
o
zm
l
ko
l
oj zm
eif zm
net z
eotherwise











(16)
where l
o
mand l
o

are the mean and the standard devia-
tion of the output node activation transfer function re-
spectively. The parameters of the NNDTF can be trained
by GA [11].
4. Genetic Algorithm
Genetic algorithms (GAs) are powerful searching algo-
rithms. The traditional GA process [14-16] is shown in
Figure 6. First, a population of chromosomes is created.
Second, the chromosomes are evaluated by a defined
fitness function. Third, some of the chromosomes are
selected for performing genetic operations. Forth, genetic
operations of crossover and mutation are performed. The
produced offspring replace their parents in the initial
population. This GA process repeats until a user-defined
criterion is reached. In this paper, the traditional GA is
modified and new genetic operators [11] are introduced
to improve its performance. The modified GA process is
shown in Figure 7. Its details will be given as follows.
4.1. Initial Population
The initial population is a potential solution set P. The

Playing Tic-Tac-Toe Using Genetic Neural Network with Double Transfer Functio ns 41
Figure 6. Procedure of simple GA.
Figure 7. Procedure of the modified GA.
first set of population is usually generated randomly.

12 pop _size
P, , , pp p (17)
12 jno_vars
iii i i
pp p p

 p , 12i, ,,
12pop_size;j, ,,no_vars (18)
j
j
j
min imax
parap para (19)
where pop_size denotes the population size; no_vars
denotes the number of variables to be tuned; j
i
p,
12i, ,,

 pop_size; 12j, ,,

 no_vars, are the
parameters to be tuned;
j
min
para and
j
max
para are the
minimum and maximum values of the parameter j
i
p
for all i. It can be seen from (17) to (19) that the poten-
tial solution set P contains some candidate solutions i p
(chromosomes). The chromosome i p contains some
variables i p (genes).
4.2. Evaluation
Each chromosome in the populati on will be evaluated by
a defined fitness function. The better chromosomes will
return higher values in this process. The fitness function
to evaluate a chromosome in the population can be writ-
ten as,

i
fitness fp (20)
The form of the fitness function depends on the appli-
cation.
4.3. Selection
Two chromosomes in the population will be selected to
undergo genetic operations for reproduction by the me-
thod of spinning the roulette wheel [16]. It is believed
that high potential parents will produce better offspring
(survival of the best ones). The chromosome having a
higher fitness value should therefore have a higher
chance to be selected. The selection can be done by as-
signing a probability i q to the chromosome i p:



1
i
ipop _ size
j
j
f
q
f



p
p
, 12i, ,, pop _ size (21)
The cumulative probability i
ˆ
q for the chromosome
i
p is defined as,
1
i
ij
j
ˆ
qq

 (22)
The selection process starts by randomly generating a
nonzero floating-point number,


01d. Then, the
chromosome i
p is chosen if 1ii
ˆˆ
qdq
, 12i, ,,


pop_size, and 0
ˆ0

q. It can be observed from this se-
lection process that a chromosome having a larger


i
fp will have a higher chance to be selected. Conse-
quently, the best chromosomes will get more offspring,
the average will stay and the worst will die off. In the
selection process, only two chromosomes will be se-
lected to undergo the genetic operations.
4.4. Genetic Operations
The genetic operations are to generate some new chro-
mosomes (offspring) from their parents after the selec-
tion process. They include the crossover and the mutation
operations.
Procedure of the simple GA
begin
 0 //  : iteration generation
initialize P(
 ) //P(  ): population for iteration t
evaluate f(P(
 )) // f(P(  )):fitness function
while (not termination condition) do
begin
   +1
select 2 parents p1 and p2 from P(
 -1)
perform genetic operations (crossover and
mutation)
reproduce a new P(
 )
evaluate f(P(  ))
end
end
end
Procedure of the improved GA
begin
 0 //  : iteration
initialize P(  ) //P(  ): populati o n for iteration t
evaluate f(P(  )) // f(P(  )):fitness f u n ction
while (not termination condition) do
begin
   +1
select 2 parents p1 and p2 from P(  -1)
perform crossover operation according (23) to (28)
perform mutation operation according to (30) to three
offspring nos1, nos2 and nos3
// reproduce a new P(  )
if random number < pa
The one among nos1, nos2 and nos3 with the largest fitness
value replaces the chromosome with the smallest fitness
value in the population
else if f(nos1) > smallest fitness val ue in the P(  -1)
nos1 replac es the chromosome with the smallest fitness
value
if f(nos2) > smallest fitne ss value in the updated P(  -1)
nos2 replaces the chromosome with the smallest fitness
value
if f(nos3) > smallest fitne ss value in the updated P(  -1)
nos3 replaces the chromosome with the smallest fitness
value
end
end
evaluate P(
 )
end
end

Playing Tic-Tac-Toe Using Genetic Neural Network with Double Transfer Functio ns 42
4.4.1. Cros s ov er
The crossover operation is mainly for exchanging infor-
mation from the two parents, chromosomes 1 p and 2 p,
obtained in the selection process. The two parents will
produce one offspring. First, four chromosomes will be
generated according to the following mechanisms,
111 112
12 2 cno_vars
os osos



pp
os  (23)
 
222 2
12
max1 2
1max
c no_vars
os osos
w,w




os
ppp
 (24)
 
3333
12
min1 2
1min
cno_vars
os osos
w,w
 


os
ppp
 (25)

444 4
12
maxmin1 2
1
2
c no_vars
os osos
ww




os
pppp (26)
12
maxmax maxmax
no _ vars
para parapara

 p (27)
12
minmin minmin
no _ vars
para parapara

 p (28)
where


01w denotes a weight to be determined by
users,

12
max ,pp denotes a vector with each element
obtained by taking the maximum among the correspond-
ing element of 1 p and 2 p. For instance,







max12 32 312 33,. Similarly,

12
min ,pp gives a vector by taking the minimum val-
ue. For instance,





min 123231,


121. Among 1
c
os to 4
c
os , the one with the
largest fitness value is used as the offspring of the cros-
sover operation. The offspring is defined as,
12
ios
no _ var sc
os osos



os os (29)
where os i denotes the index i which gives a maximum
value of

i
c
fos , 1234i,,,.
If the cro ssov er op era tio n can prov id e a good off spr ing,
a higher fitness value can be reached in less iteration. As
seen from (23) to (26), the offspring spreads over the
domain: (23) and (26) will move the offspring near cen-
tre region of the concerned domain (as w in (26) ap-
proaches 1, 4
c
os approaches 12
2
pp
), and (24) and (25)
will move the offspring near the domain boundary (as w
in (24) and (25) approaches 1, 2
c
os and 3
c
os approach-
es max p and min p respectively). The chance of getting
a good offspring is thus enhanced.
4.4.2. Mutatio n
The offspring (30) will then undergo the mutation opera-
tion. The mutation operation is to change the genes of the
chromosomes. Consequently, the features of the chro-
mosomes inherited from their parents can be changed.
Three new offspring will be generated by the mutation
operation:
12
112 2
jno_vars
no _var sno _var s
os osos
b nosbnosbnos








nos 

(30)
where 12
i
b,i, ,,no_vars

, can only take the value
of 0 or 1; i nos

, 12 i, ,

, no_vars, are randomly
generated numbers such that ij
min ii
para os nos  
i
max
para. The first new offspring ( 1j) is obtained
according to (30) with that only one i b (i being ran-
domly generated within the range) is allowed to be 1 and
all the others are zeros. The second new offspring is ob-
tained according to (30) with that some randomly chosen
bi are set to be 1 and others are zero. The third new
offspring is obtained according to (30) with all 1
i
b

.
These three new offspring will then be evaluated using
the fitness function of (21). A real number will be gener-
ated randomly and compared with a user-defined number


01
a
p. If the real number is smaller than pa, the
one with the largest fitness value l
f
among the three
new offspring will replace the chromosome with the
smallest fitness
f
in the population (even when
lss
f
f

.) If the real number is larger than pa, the first
offspring will replace the chromosome with the smallest
fitness value
s
f
in the population if ls
f
f; the
second and the third offspring will do the same. pa is
effectively the probability of accepting a bad offspring in
order to reduce the chance of converging to a local opti-
mum. Hence, the possibility of reaching the global opti-
mum i s ke pt.
We have three offspring generated in the mutation
process. From (30), the first mutation ( 1j) is in fact a
uniform mutation. The second mutation allows some
randomly selected genes to change simultaneously. The
third mutation changes all genes simultaneously. The
second and the third mutations allow multiple genes to be
changed. Hence, the domain to be searched is larger as
compared with a domain characterized by changing a
single gene. As three offspring are produced in each
generation, the genes will have a larger space for im-
proving the fitness value when the fitness value is small.
When the fitness values are large and nearly steady,
changing the value of a single gene (the first mutation)
may be enough as some genes may hav e reached the op-
timal values.
After the operation of selection, crossover, and muta-
tion, a new population is generated. This new population
will repeat the same process. Such an iterative process
can be terminated when the result reaches a defined con-
dition, e.g. a defined number of iterations have been

Playing Tic-Tac-Toe Using Genetic Neural Network with Double Transfer Functio ns 43
reached.
5. Training of the NNDTF
In this section, the GA will be employed to train the pa-
rameters of the NNDTF to play Tic-Tac-Toe based on
the gaming algorithm in Section 2. The NNDTF with 9
inputs and 1 outpu t is employed. The grids are numbered
from 1 to 9 from right to left and from top to bottom.
An “X” on the grid is deno ted by 1, an “O” is denoted b y
–1, and an empty grid is denoted by 0.5. The grid pattern
represented by numerical values will be used as the input
of the NNDTF. The output of the NNDTF (

y
t which
a floating point number ranged from 1 to 9) represents
the position of the marker that should be placed on. In
order to have a legal move (place a marker on an empty
grid), the marker is placed on an empty grid that has its
grid number closest to the output of the network.
To perform the training, we have to determine the pa-
rameters to be trained and the fitness function describing
the problem’s objective. The parameters of the modified
network to be turned is
11
j
jll
ijssj, jj, jjloo
vmpp wm





for all i, j,l, which will be chosen as the chromosome
for the GA. 100 different training patterns (obtained
based on the proposed gaming algorithm stated in Sec-
tion 2) are used to feed into the NNDTF for training. The
fitness functions is designed as follows,
  
 
100
1100
1
m
i
max
i
Syt,t
fitness
St




x
x
(31)
where

y
t denotes the output of the NNDTF with the
t-th training pattern

txas the input,





m
Syt,tx
denotes the final score for grid

y
t and the t-th train-
ing pattern

tx based on the gaming algorithm.
 
max
Stx denotes the maximum final score value
among all the empty grids for the t-th training pattern

tx. The GA is to maximize the fitness value (ranged
from 0 to 1) so as to force the output of the NNDTF to
the grid number having the largest final score to ensure
the best move.
6. Example
In this session, a 9-input-1-output NNDTF is used for
training. The number of hidden nodes is chosen to be 8.
100 training patterns are used for training with 50000
iterations. The population size, probability of acceptance,
and w are chosen to be 10, 0.5 and 0.1, respectively.
After training, the fitness value obtained is 0.9605. The
upper and lower bounds of each parameter are 1 and –1,
Table 1. Results of the proposed NN playing Tic-Tac-Toe
against with the traditional NN for 50 games.
Proposed NN
Wins: Draws: Loses
Proposed approach moves
first 18: 3: 4
Traditional approach
moves first 13: 4: 8
respectively. The initial values of the parameters are gen-
erated randomly.
For comparison purposes, a traditional 3-layer feed-
forward NN [17] trained by GA with arithmetic crossov-
er and non-uniform mutation [17] is also applied under
the same conditions to learn the gaming strategy in Sec-
tion 2. The probabilities of crossover and mutation are
selected to be 0.8 and 0.1, respectively. The shape para-
meter of the traditional GA for non-uniform mutation [17]
is selected to be 5. These parameters are selected by trial
and error for the best performance. After training for
50000 iterations, the fitness value obtained is 0 .9456.
To test the performance of our proposed method, our
trained NN plays Tic-Tac-Toe with the trained traditional
NN for 50 games is carried out. The first 25 grid patterns,
which are generated randomly with 2 “O”s and 2 “X”s,
are the same as the next 25 grid patterns. For the first 25
games, the proposed approach moves first. For the
second 25 games, the traditional approach moves first.
The results are tabulated in Table 1. It can be seen that
the proposed approach performs better. The number of
wins is 18 by using NNDTF while only 13 by using the
tradition NN.
7. Conclusions
A neural network with double transfer functions and
trained with genetic algorithm has been proposed. An
algorithm of playing Tic-Tac-Toe has been presented. A
new transfer function of the neuron with a node-to-node
relationship has been proposed. The proposed neural
network is trained by genetic algorithm to learn the algo-
rithm of playing Tic-tac-toe. As a co mparison, the t rain ed
NN has played against the traditional NN trained by the
traditional GA. The result has shown that the proposed
approach performs better.
REFERENCES
[1] H. J. V. D. Herik, J. W. H. M. Uiterwijk and J. V. Rijs-
wijck, “Games Solved: Now and in the Future,” Artificial
Intelligence, Vol. 134, No. 1-2, 2002, pp. 277-311. doi:10.
1016/S0004-3702(01)00152-7
[2] H. J. V. D. Herik and I. S. Hersch ber g, “The C onstr uct ion
of an Omniscient Endgame Data Base,” ICCA Journal,
Vol. 8, No. 2, 1985, pp. 66-87.

Playing Tic-Tac-Toe Using Genetic Neural Network with Double Transfer Functio ns 44
[3] L. V. Allis, M. V. D. Meulen and. V. D. Herik, “Proof-
Number Search,” Artificial Intelligence, Vol. 66, No.1,
1994, pp. 91-124. doi:10.1016/0004-3702(94)90004-3
[4] D. B. Fogel and K. Chellapilla, “Verifying Anaconda’s
Expert Rating by Competing against Chinook: Experi-
ments in Co-Evolving a Neural Checkers Player,” Neur-
computing, Vol. 42, No. 1-4, 2002, pp. 69-86. doi:10.10
16/S0925-2312(01)00594-X
[5] K. Chellapilla and D. B. Fogel, “Evolving Neural Net-
works to Play Checkers without Relying on Expert
Knowledge,” IEEE Transactions on Neural Networks,
Vol. 10, No. 6, 1999, pp. 1382-1391. doi:10.1109/72.80
9083
[6] K. Chellapilla and D. B. Fogel, “Evolving an Expert
Checkers Playing Program without Using Human Exper-
tise,” IEEE Transactions on Evolutionary Computation,
Vol. 5, No. 4, 2001, pp. 422-428. doi:10.1109/4235.94
2536
[7] K. Chellapilla and D. B. Fogel, “Autonomous Evolution
of Topographic Regularities in Artificial Neural Net-
works,” Neural Computation, Vol. 22, No. 7, 2010, pp.
1860-1898. doi:10.1162/neco.2010.06-09-1042
[8] G. Tesauro, “Programming Backgammon Using Self-
Teaching Neural Nets,” Artificial Intelligence, Vol. 134,
No. 1-2, 2002, pp. 181-199. doi:10.1016/S0004-3702(01)
00110-2
[9] S. Y. Chong, M. K. Tan and J. D. White, “Observing the
Evolution of Neural Networks Learning to Play the Game
of Othello,” IEEE Transactions on Evolutionary Compu-
tation, Vol. 9, No. 3, 2005, pp. 422-428. doi:10.1109/TE-
VC.2005.843750
[10] D. E. Beal and M. C. Smith, “Random Evolutions in
Chess,” ICCA Journal, Vol. 17, No. 1, 1994, pp. 3-9.
[11] F. H. F. Leung, H. K. Lam, S. H. Ling a nd P. K. S. Tam,
“Tuning of the Structure and Parameters of Neural Net-
work Using an Improved Genetic Algorithm,” IEEE Trans-
actions on Neural Networks, Vol.14, No. 1, 2003, pp. 79-
88. doi:10.1109/TNN.2002.804317
[12] M. Brown and C. Harris, “Neuralfuzzy Adaptive Model-
ing and Control,” Prentice Hall, Upper Saddle River,
1994.
[13] S. H. Ling, F. H. F. Leung, H. K. Lam, Y. S. Lee and P.
K. S. Tam, “A Novel GA-Based Neural Network for
Short-Term Load Forecasting,” IEEE Transactions on
Industrial Electronics, Vol. 50, No. 4, 2003, pp. 793-799.
doi:10.1109/TIE.2003.814869
[14] J. H. Holland, “Adaptation in Natural and Artificial Sys-
tems,” University of Michigan Press, Ann Arbor, 1975.
[15] D. T. Pham and D. Karaboga, “Intelligent Optimization
Techniques, Genetic Algorithms, Tabu Search, Simulated
Annealing and Neural Networks,” Springer-Verlag, New
York, 2000.
[16] Z. Michalewicz, “Genetic Algorithm + Data Structures =
Evolution Programs,” 2nd Edition, Springer-Verlag, New
York, 1994.
[17] S. Haykin, “Neural networks: A Comprehensive Founda-
tion,” 2nd Edition, Prentice Hall, Upper Saddle River,
1999.