Subject: A few questions and suggestions about/for your Tron game .. (long)

From: [email-masked] (Kai Londenberg)
Date: Mon, 13 Sep 1999 19:16:34 GMT

I wrote a Multiplayer version of the Tron Lightcycle game myself
(MetaTron at www.stud.uni-hannover.de/~klon/metatron.html 

The next project I´m planning is to write a good AI for the Computer
Opponents. And since I´m interested in real AI, not just huge decision
trees, I thought this would be a good point for trying some advanced
techniques like NNs and Reinforcement Learning (Temporal Difference
Learning to be more specific). 
My end-goal is, to let the Computer Opponents not only act in such a
way that they survive as long as possible, but rather I´d like to get
them intelligent enough to act strategically offensive and defensive,
be able to detect traps (like small boxes they drive into), attack
another player by crossing his way in a short distance and so on...

Then someone in a Newsgroup pointed me to your project.. I looked at
the Tron game, and I thought your project to be very interesting.The
sensory input and general principle of your AIs seems to be much like
my first writeup of an AI, just with the differences that I also
provided some random input (so the AIs won´t be absolutely
predictable) and that I did not modify the parameters of the AIs
genetically .. (I just tried a few variations, fiddled around with the
Algorithms a bit until I was satisfied). I also got the idea of
modifying the parameters genetically, but my impression was, that in
whatever way I was modifying them, they could not get past a certain
performance due to the general principles they were built upon. (For
example, you can´t teach them to avoid spiraling inwards if you don´t
build in extra sensors, turn-counters or principles). Humans playing
Tron get much more info, they look upon the whole playfield, know who
their enemies are and so on.

While reading articles about TD Gammon, the book Reinforcement
Learning and another book about NNs, I tried to find a solution for
this. I came up with an idea, yet I don´t know if the idea I had is
suited for this type of problem. Basically it´s about a NN I want to
train to be able to play Tron.  (Clearly nothing you should try in
Java yet, due to it´s execution speed) For special maneuvers I would
then add custom code (for example to that it is able to attack) . The
NN would consist of an input layer, with one neuron of the input layer
corresponding to one pixel in a rectangle around the lightcycle, with
a -1 representing a wall, and either a 0 or a 1 representing free
space. The sensory input would always be provided in such a way that
the lightcycle is in the center and pointing in the same direction.
(So it´s -sort of- from a lightcyle perspective). Then there would be
a hidden layer with various neurons connected in various forms to the
input layer. This hidden layer would be responsible for detecting
structures within the input layer, like connected lines and so on. The
size and complexity of this hidden and input layer is something I have
to experiment with, so that the NN doesn´t evaluate too slow.Then
there would be a output layer consisting of 3 neurons. Each of them
connected to every neuron in the input and hidden layer. The 3 output
neurons would represent the value of driving straight, to the left,
and to the right. This value can take negative and positive values
alike. In another Idea I had, the output layer could also consist of 5
neurons, with the additional 2 neurons representing the value of a 180
degree turn (2 turns following each other in a short  interval) to a
given direction.

Then for the training, I would first intialize the NNs weights in such
a way that it is able to avoid walls (simply speaking). Then I would
let it observe human players, simply by taking snapshots of the state
of the game when they make a decision, and then, later in some free
time, let it evaluate these decisions as being good decisions if the
human performed well. (This could be done by saving the sensory input
the AI would get, along with the decision that was made. Note, that
these Files could be exchanged, so that a huge training base could be
built. Also, it doesn´t hinder performance as much as it would If I
evaluated every decision at once.)
Additionally I would train the NN in a TD Reinforcement Learning style
by letting it play against itself and human players. (Much alike TD
Gammon did. But I would also include humans as smarter opponents)

What I fear is, that such an NN would either be much too complex (and
as such, much too slow for such a fast realtime game) or too simple,
so that it won´t act much better than the usual algorithms. (Which
perform rather poorly if you strip them of the lightning fast
reflexes)

What do you think about this approach ? Do you see any problems or
advantages it could have ? Reading through the presentation of your
paper, I got the impression you are familiar with TD Gammon and NNs,
but additionally you are by now somewhat experts when it comes to Tron
AIs.  Also, I am still not sure how exactly I´d construct and connect
the hidden layer. One idea for a construction I had, was to provide a
neuron for each row and column (Connected with each input neuron of
these). Then some to detect "edges" which could build a cage around
the lightcycle. (I already have an idea how to implement these
efficiently). And of course at least one hidden neuron for each of the
four "Quadrants" in the rectangle.

	thank you if you´ve read so far ;)

		Kai Londenberg

P.S.  .. a Tip for you. If you want to improve the playability of your
game, modify it in such a way that you drive a Lightcycle with just 2
instead of 4 keys. One for a turn to the left, and one for a turn to
the right. I tried both variants, and the 2 key one is much better in
my opinion. Also it will produce better human opponents, you´ll see..