Newsgroups: rec.games.programmer
From: jang@ecf.toronto.edu (JANG  HIN LANG)
Subject: AI Learning Algorithms
Date: Wed, 30 Nov 1994 22:45:40 GMT

I do not believe anyone discussed, in detail, on how to apply
basic principles of articificial intelligence, neural computing 
and machine learning into computer games.  In using the
outdated Kohonen Algorithm (explained below) we can simulate
an intelligent computer opponent that can learn from its 
mistakes.
 

For the interested few, here in my treatment on the subject.


---


The least sophisticated of AI algorithms simluates the function
of the biological neuron.  First proposed four decades ago, the
outline of the basic model is as follows



dendrite                   |------------|
(input) -----------------O |            |
                           | cell body  | O---------------
                           |            |          axon (output)
(input) -----------------O |            |
                           |------------|

where O is a synapse.

The synapse is not an actual physical linkage; instead it is a
temporary chemical one that can vary over time.  To represent
these variable connections in our computer model we assign a 
multiplicative weight to each input pathway.  A high weight
term denotes a favourable connection.  The cell body contains
a predefined value known as the threshold.  An output signal
wll be produced if the input to the neuron is greater than
the threshold value.

We now require a mechanism that allows us the simulate learning
in our perceptrons.

In biological systems, the process of learning is thought to 
involve modifications in the effective coupling between neurons.
In our computer model, we make small adjustments to the weights.
To appreciate what this means, consider this learning paradigm:

	- set the weights w and thresholds t of perceptrons to
	  random values

	- present the input x(0), x(1), x(2), ...., x(n-1)

	- calculate the actual output by comparing the threshold
	  value and the weighted sum of the input


			n - 1
			-----
	weighted sum =  \	w(i) * x(i)
			/
			-----
			i = 0

	- alter the weights to reinforce correct decisions and 
	  discourage incorrect decisions.


Adaptation of the learning paradigm lead to the development of 
the Kohonen Network Algorithm, named after Professor T. Kohonen
of the Faculty of Information Sciences at the University of
Helsinki, Finland.  Instead of comparing input values to thresholds,
(as in the case with perceptrons) Kohonen compared the weights of
all output nodes and picked the set of nodes having weights that
closely matched the magnitude of the input signal.


NOTE: --->	the following algorithm may not be appropriate for
		your particular application in terms of space
		and time efficiency.  If you require information
		regarding optimised AI learning algorithms consult
		this reference:

		Kaelbling, Leslie Pack
		Learning in Embedded Systems
		The MIT Press, Cambridge, Massachusetts
		(c) 1993
		ISBN 0-262-11174-8


The self-organising network consists of a matrix of output nodes j
all of which are connected to every input node i.


			----------------
			\  O    O    O	\
			 \		 \
	output nodes j	  \  O    O    O  \
			   \		   \
			    \  O    O    O  \
			     ----------------



	input nodes i		O	O


The algorithm determines the "winning" node j* that closely matches
the expected output as determined by the set of input nodes i.  
Modifying the weights of j* and its neighbours will produce a
set of desired outcomes.

Kohonen successfully implemented this technique for a speech
recognition system in the mid 1980's.

-------------------------
KOHONEN NETWORK ALGORITHM
-------------------------


1. Initialise network
	- define w(ij) (0 <= i <= n-1) to be the weight from input
	  node i to output node j.  Set the weights from the n 
	  inputs to some small values.  Set the initial radius
	  of the neighbourhood around node j, N(j), to some large
	  value.

2. Present input
	- present input x(0), x(1), x(2), .... , x(n-1) where x(i)
	  is the input to node i.

3. Calculate distance
	- compute distance d(j) between input node i and each output
	  node j as in


			n - 1
			-----
		d(j) =  \	(x(i) - w(ij))^2
			/
			-----
			i = 0

4. Select minimum distance and denote output node j with minimum d(j)
   to be j*.

5. Update weights
	- update weight for node j* and its neighbours as defined by
	  the extent of boundary N(j).

	
		w(ij) = w(ij) + M * (x(i) - w(ij))

	The M term is used to control the rate of weight adjustment.
	This value should be set in the range [0.5, 1] and then
	gradually decreased in accordance to a linear function as
	the number of learning cycles increases.

6. If the expected solution set has not been found, repeat the
   learning cycle (steps 2-5).

7. The solution set S of the network is now a counter-strategy tactic
   that a computer opponent can use against the player.

   If, for example, the network consists of 16 output nodes, four input
   nodes and minimum neighbourhood size of four, the Kohonen Algorithm
   can develop 216 (9 * 4!) unique strategy tactics.  Provided that
   the network has been trained well, the computer opponent will be
   rather challenging.



--------------------------------------------------------------------