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.
--------------------------------------------------------------------