[Hypothetic babbling] - AI
Moderator: Forum Moderators
Viliam wrote:This idea seems interesting, but difficult to implement. In theory it should be possible.
First, the neural networks could learn by observing the current AI. When they become good enough, we could take the current AI away and replace it by evolution. The neural networks would have random mutations and fight against each other; loser would die, winner would replicate. This would allow neural networks to randomly find some improvements against the current AI.
To add more computing power, it could be possible to download some definitions of neural networks, run the AI vs AI combats on home computer, and then upload the resulting networks to server. As an incentive for donating CPU time, the neural networks could remember names of people who let them train on their computers, and when fighting the internet, they would choose the names of their sponsors for the units.
This set me thinking. Isnt it possible to have the AI based as a multi player challenge based from the internet? That would solve the problem of frequent download/upload.
-
Viliam
- Translator
- Posts: 1341
- Joined: January 30th, 2004, 11:07 am
- Location: Bratislava, Slovakia
- Contact:
You mean something like a program on internet which would join Wesnoth lobby and participate in games (when invited)? Anything is possible. I just doubt many people would like to play against it, until it becomes smart enough.locutus wrote:Isnt it possible to have the AI based as a multi player challenge based from the internet?
(I'm new to the forum, so please go easy on me 
)
Since everything said here, gravitates towards "hybrid-NN-AI" and to let this train against a normal AI, I'd like to contribute my (little) knowledge off NNs to this:
the crucial thing in an NN is to keep the number of free Parameters (Neurons) as low as possible. When having to many Neurons, you run into two Problems:
1) the steps you need for training will explode (i.e. the time needed for training). In a simple Layout with one input, one output, one hidden layer you add (#input-neutrons+#output-neutrons)*2 free Parameters (that need to be fitted) with every neuron in the hidden layer...
2) the so-called overfitting.
When training such a neuronal network you'll notice that it starts to perform extremly well (after training it sufficentily) in the training-situations, but extremly bad on others. This is due to overfitting.
There are methods to get around those two Problems, which efficently reducing the number of free parameters (with training). The downside of those Methods is that you need more training-steps, and that you keep the full need for the calculating-power.
The biggest problem I see is to identify the input and output of such a NN.
The input needs to consist in a list (fixed in length, since you have a fixed #of input neurons) of numbers (usualy between 0 and 1.0, but it should be easy to normalise them to 1.0)
The output consits of a similar list.
)Since everything said here, gravitates towards "hybrid-NN-AI" and to let this train against a normal AI, I'd like to contribute my (little) knowledge off NNs to this:
the crucial thing in an NN is to keep the number of free Parameters (Neurons) as low as possible. When having to many Neurons, you run into two Problems:
1) the steps you need for training will explode (i.e. the time needed for training). In a simple Layout with one input, one output, one hidden layer you add (#input-neutrons+#output-neutrons)*2 free Parameters (that need to be fitted) with every neuron in the hidden layer...
2) the so-called overfitting.
When training such a neuronal network you'll notice that it starts to perform extremly well (after training it sufficentily) in the training-situations, but extremly bad on others. This is due to overfitting.
There are methods to get around those two Problems, which efficently reducing the number of free parameters (with training). The downside of those Methods is that you need more training-steps, and that you keep the full need for the calculating-power.
The biggest problem I see is to identify the input and output of such a NN.
The input needs to consist in a list (fixed in length, since you have a fixed #of input neurons) of numbers (usualy between 0 and 1.0, but it should be easy to normalise them to 1.0)
The output consits of a similar list.
-
Angry Andersen
- Posts: 205
- Joined: September 15th, 2006, 1:22 pm
@Fishion: Good points (... and I'm not saying this just because you are new), I fully agree (see my earlier message!)
Choosing proper inputs and outputs is one of the main decisions and will very much decide how well any such program does. How the actual training is done is probably a lesser problem!
Another important point which has not been considered here yet is what kind of learning algorithm is appropriate: Should the NN-AI learn to emulate a certain player/players/... (i.e. it watches the games and learns to react in the observed ways) OR should it use an error driven learning algorithm, where it plays itself and then adapts the weights according to success?
Choosing proper inputs and outputs is one of the main decisions and will very much decide how well any such program does. How the actual training is done is probably a lesser problem!
Another important point which has not been considered here yet is what kind of learning algorithm is appropriate: Should the NN-AI learn to emulate a certain player/players/... (i.e. it watches the games and learns to react in the observed ways) OR should it use an error driven learning algorithm, where it plays itself and then adapts the weights according to success?
the best way for it to learn would be against/watching the better MP folks
this would help prevent over specialization and give it steeper learning curve
which would benefit its learning process as the variables for failure/success would be learned quicker
as then the NN AI would become better than most players faster
p.s.
the AI could be written and then taught against impressive MP replays
p.s. II
the AI's memory could be kept in SVN somewhere to make it easily available to everyone for download
this would help prevent over specialization and give it steeper learning curve
which would benefit its learning process as the variables for failure/success would be learned quicker
as then the NN AI would become better than most players faster
p.s.
the AI could be written and then taught against impressive MP replays
p.s. II
the AI's memory could be kept in SVN somewhere to make it easily available to everyone for download
happy timezone traveler
When talking about leraning algorythms for a NN which is trained then there only comes the Back-Propagation-Algo to mind (or variations of it for example in a Support Vector Machine). Such a (non-self-learning) NN is often used for pattern-recognition.
So far I've come up with an idea to actually use an NN for an hybrid AI.
The Bruteforce-AI does use an underlying algorythm to assign certain (strategic) values to its own and its enemy units and then acts accordingly (as far as I understood it).
I assume that such an AI needs to know the immediate thread of one of its own units.
So the input would be something like a nxn Matrix (the size should be fixed and about as big as the longest range for a unit, this will unfortunatly rather big, or it does poorly on Maps with alot of horsemen and fast movement). Since terrain also plays a role we need to consider this also...
we already there do get an awful lot of input variables: Range, estimated Dammage and health of unit in Hex (if no unit is on such a Hex this would be 0), and terrain type (don't know really how to encode that).
Plus adding the health of ones own unit.
Leaving the Terrain out, we'd end up with 3*n^2 + 1 Input-Neurons, and by definition (we want a single number to come out for our AI) a single Output-Neuron.
I'm not sure how many neurons in the hidden layer would be advisable.
Training could be done by using Replays. Estimating the Threat to the unit is the % of how often the unit did survive. This is an one-round estimate (therefore "immediate" estimate). So I don't think you'd have a big problem getting training material for it. Since such a huge amount of training material is avaiable for this patter recognition the overfitting problem should easily be counterd by using an "early stopping" method on the back propagation algorythm.
The Error-function is also easly defined ( Erf = estimated thread - measured thread). This seems to be a usable idea (maybe)
One thing I forgot to mention, somehow it would make sense to rotate the nxn Matrix so that up (or another direction) is always the pointing toward the center of mass of the enemy units. This might be necessary since we are using hex and therefore have a 6 time rotational symmetry that the NN would have to fit (i.e. we might end up with 6 seperate NNs which are virtually disconnected from each other that treat only one of the symmetry cases and are otherwise identical).
Something similar could be done to assign enemy units some sort of "value".
So far I've come up with an idea to actually use an NN for an hybrid AI.
The Bruteforce-AI does use an underlying algorythm to assign certain (strategic) values to its own and its enemy units and then acts accordingly (as far as I understood it).
I assume that such an AI needs to know the immediate thread of one of its own units.
So the input would be something like a nxn Matrix (the size should be fixed and about as big as the longest range for a unit, this will unfortunatly rather big, or it does poorly on Maps with alot of horsemen and fast movement). Since terrain also plays a role we need to consider this also...
we already there do get an awful lot of input variables: Range, estimated Dammage and health of unit in Hex (if no unit is on such a Hex this would be 0), and terrain type (don't know really how to encode that).
Plus adding the health of ones own unit.
Leaving the Terrain out, we'd end up with 3*n^2 + 1 Input-Neurons, and by definition (we want a single number to come out for our AI) a single Output-Neuron.
I'm not sure how many neurons in the hidden layer would be advisable.
Training could be done by using Replays. Estimating the Threat to the unit is the % of how often the unit did survive. This is an one-round estimate (therefore "immediate" estimate). So I don't think you'd have a big problem getting training material for it. Since such a huge amount of training material is avaiable for this patter recognition the overfitting problem should easily be counterd by using an "early stopping" method on the back propagation algorythm.
The Error-function is also easly defined ( Erf = estimated thread - measured thread). This seems to be a usable idea (maybe)
One thing I forgot to mention, somehow it would make sense to rotate the nxn Matrix so that up (or another direction) is always the pointing toward the center of mass of the enemy units. This might be necessary since we are using hex and therefore have a 6 time rotational symmetry that the NN would have to fit (i.e. we might end up with 6 seperate NNs which are virtually disconnected from each other that treat only one of the symmetry cases and are otherwise identical).
Something similar could be done to assign enemy units some sort of "value".