quote:

---

Original post by MikeD
There can''t possibly be a neural network method that''s best for solving the FPS problem, because FPS isn''t a problem, it''s a game type. Name a problem within the FPS genre that AI has to solve and I''ll give my opinion, which isn''t expert, but it is competent.
One thing I can conjecture is that any form of supervised learning will not work, as supervised learning requires knowing the correct answer to calculate the error to back propogate from. If you know the answer in some numeric form the system can understand then you''ve solved the problem and don''t need the network in the first place.

Beyond that, please tell me what jargon I''m using. I''d like to know where I''ve been flagrantly disregarding explanation and confusing people, instead of merely trying to be specific.

Mike

---

I beg to differ, Mike! The FPS game type incorporates probelms suitable for solution by a neural network (learning the behaviour of players about an environmment and from this, determining the best routes around the environment to maximise the number of frags, or to find power ups). A neural network can exist to solve an FPS problem. If the network is trained with all possible routes through an environment, and given a starting point and an end point, then the net should be able to return one or several possible paths to the end point. This should not be a problem for competitive learning (ignoring the actual complexity of the network), as by its very nature, it is suited to these sorts of problems.

This fulfils the requirement for providing the network with the ''correct answers'' as you mentioned for supervised learning. The only situation where this may fall apart is if you have an environment with an infinite number of paths - which would require such a network to be trained for an infinite amount of time, or trained for a limited amount of time and apply some form of probability theory elsewhere in the code to assess the suitability of a given solution by the network.

I argue that if a problem can be resolved to a finite set of primitives, then a network (irrespective of complexity) exists to solve the problem. The thing to remember here is that we are trying to get the system to be able to identify a problem and return an appropriate solution.

The ''jargon'' I mentioned was to the fact that we have ''AI newbies'' who will not be familiar with gradient decent methods and the like. I am trying to keep it simple.

Regards,
Mathematix.

quote:

---

Original post by Geta

Original post by Mathematix
Okay, you bunch of ''experts''. Let''s see you answer this one.

Assuming that neural nets were the only option for game AI, which category of network would be most suitable for an FPS: back-prop, recurrent or competative? Give reasons for your answer.

Do your really know what all the jargon you mentioned really means??

Regards,
Mathematix.

---

What decision in a FPS do you want to use the ANN for? Pathfinding?

Seriously, the only thing I can think of that an ANN _may_ be a good candiate
for use in a FPS would be in attempting to recognize movement patterns (which
is something you mentioned before). As associators and classifiers, I personally
think ANNs are much to limited to be of much overall use in computer game AI.

Searches, FSMs, Expert Systems and Fuzzy Logic all seem to dominate in use
in computer game AI because they seem to be more general techniques (IMHO).

All that being said, ANN are certainly talked about alot around game boards.

Eric


A well reasoned post… I applaud you.

Regards,
Mathematix.

Geta said..."Ok. So if I understand correctly, you suggest inputs to the ANN being: type of terrain, status of the
tile, nearness of the enemy (and other such data)? Now, would there be a ANN for each tile? Or are
you suggesting a single ANN for all tiles with these inputs? What I am having trouble seeing is how
does this arrive at the best (or a good enough) location to build at?"

My apologies, I reread my post and the thoughts in my head _really_ didn''t make it down to text. Now I''ve had a good 5 hours sleep I''m sure I''ll do a better job *yawn*.

My idea was to have a template, centred on the position for the new building, which is placed over several, or all possible, areas of the map, which gives back a numeric value suggesting the quality of the position for the placement of the building type. For instance, the building it''s trying to place might be (3,3) in size, so the network use could be (7,7). You place the centre point of the template (4,4), at the point where you''d put the origin of the building ((1,1) in building space) and feed the information about each of the squares covered by the template into the network. So if you place the template over world square (18,31) then you''re feeding in information about squares (15-21, 28-34). That''s x * 49 inputs, where x is the number of different aspects of the network you''re feeding it and one output with the value of that space.
You then check an area, centering the template over each central point (possibly for four different orientations per point) to find the position (and orientation) that has the highest value. This is the point your AI places the building.

Possibly expensive computationally before shipping in evolving the net and perhaps expensive during game due to running the network, but if you can get _everything_ running with neural networks then you can go build yourself an accelerator card and you''ll bide fine ;-)

Mike

quote:

---

Original post by MikeD
Geta said..."Ok. So if I understand correctly, you suggest inputs to the ANN being: type of terrain, status of the
tile, nearness of the enemy (and other such data)? Now, would there be a ANN for each tile? Or are
you suggesting a single ANN for all tiles with these inputs? What I am having trouble seeing is how
does this arrive at the best (or a good enough) location to build at?"

My apologies, I reread my post and the thoughts in my head _really_ didn''t make it down to text. Now I''ve had a good 5 hours sleep I''m sure I''ll do a better job *yawn*.

My idea was to have a template, centred on the position for the new building, which is placed over several, or all possible, areas of the map, which gives back a numeric value suggesting the quality of the position for the placement of the building type. For instance, the building it''s trying to place might be (3,3) in size, so the network use could be (7,7). You place the centre point of the template (4,4), at the point where you''d put the origin of the building ((1,1) in building space) and feed the information about each of the squares covered by the template into the network. So if you place the template over world square (18,31) then you''re feeding in information about squares (15-21, 28-34). That''s x * 49 inputs, where x is the number of different aspects of the network you''re feeding it and one output with the value of that space.
You then check an area, centering the template over each central point (possibly for four different orientations per point) to find the position (and orientation) that has the highest value. This is the point your AI places the building.

Possibly expensive computationally before shipping in evolving the net and perhaps expensive during game due to running the network, but if you can get _everything_ running with neural networks then you can go build yourself an accelerator card and you''ll bide fine ;-)

Mike

---

Ok, let me see if I get it this time? Each tile (or cell) of the map that exists within the building type template
(based on size and shape of building) provides ''x'' number of inputs to the network. Is this the ANN you are
describing in the above?

Influence Maps are often used to solve this problem in a non-ANN manner. [shameless plug alert] For those
who are not familar with IMs, there will be some articles in the upcoming Game Programming Gems 2
book that go into great detail about them. [end shamless plug] In the meantime, I''ll just mention that they
are a technique that allows one to graph the influences of various considerations across an area. In our
"pick a construction site" example, each cell is assigned a value based on the positive (near necessary
resources, defensible, close to related buildings, etc.) influences around it minus the negative (near the
enemy, bad for defensie, no resources, ontop of another building, etc.) influences around it. These
influences are game specific, just as they are in the ANN example Mike offered. And like in Mike''s ANN
approach, we want to look at the map through a template of cells (or tiles) that matches the size and
shape of the building we are interested in constructing. We look at that map, using a "wave front search"
that begins at the center of our base, and propogates outward. From that point we can allow the search
to process all the cells seeking the cell (that fits our template) with the highest influence value or we
can set a threshhold and stop the search when that threshhold is passed (and thus select a site that
is "good enough").

Using IMs is not computationally expense (no accellerator card needed) and does not require training,
and since the influence values can be stored in the map tiles (or cells) there is little additional memory
overhead, and finally by using a threshhold, various levels of AI difficulty can be easily accomodated.

For those of us who do not know what a "wave front search" is, think of dropping a pebble in a pond,
and seeing the wave crest propogate out from the impact spot of the dropped pebble.

Finally, I recall there is a IM Discussion thread archieved on Ferretman''s site (http://www.gameai.com).

Eric

Sounds like a similar idea to me, the ANN approach being a more abstracted, perhaps less human understandable method. The only time that training enters into it is if you want to find some way of optimising the heuristics to the problem (if my understanding of IMs is correct), which means that training will be just as complex for IMs as for ANNs. Either you choose the values or find a training method that I shouldn''t think would be dis-similar for each.
The one possible advantage of a neural network is that you can place hidden layers in with more interactive effect on the output. Stop me if I''ve grabbed the wrong end of the stick anywhere but IMs seem to be heuristic driven calculators no different from an ANN with no hidden layers. Each input value (distance from base, nearness of enemy troops) is multiplied out by a multiplier based on its importance, to gain an overall value for the choice of position. Is that the way the values are used in an IM? Anyway, using hidden layers in a network you can have more interesting effects, where the existance of one factor can make another factor worth more or less (excitation or inhibition via the hidden layer), i.e. if you have a,b and c then just sum them for value, if you have a,b,c and d then d makes a worthless but makes b twice as important as it was. Is that kind of consideration easy to do in IM''s? Probably. Either way I think one is just an abstraction of the other.

Mike

quote:

---

Original post by MikeD
Sounds like a similar idea to me, the ANN approach being a more abstracted, perhaps less human understandable method. The only time that training enters into it is if you want to find some way of optimising the heuristics to the problem (if my understanding of IMs is correct), which means that training will be just as complex for IMs as for ANNs. Either you choose the values or find a training method that I shouldn''t think would be dis-similar for each.
The one possible advantage of a neural network is that you can place hidden layers in with more interactive effect on the output. Stop me if I''ve grabbed the wrong end of the stick anywhere but IMs seem to be heuristic driven calculators no different from an ANN with no hidden layers. Each input value (distance from base, nearness of enemy troops) is multiplied out by a multiplier based on its importance, to gain an overall value for the choice of position. Is that the way the values are used in an IM? Anyway, using hidden layers in a network you can have more interesting effects, where the existance of one factor can make another factor worth more or less (excitation or inhibition via the hidden layer), i.e. if you have a,b and c then just sum them for value, if you have a,b,c and d then d makes a worthless but makes b twice as important as it was. Is that kind of consideration easy to do in IM''s? Probably. Either way I think one is just an abstraction of the other.

Mike

---

Yes, I quite agree, in this example ANNs and IMs sound very similar. And I also agree that
training an IM could be just as complex as training an ANN.

Your point about "hidden layers in with more interactive effect on the output" is interesting.

quote:

---

"Each input value (distance from base, nearness of enemy troops) is multiplied out by a multiplier based on its importance, to gain an overall value for the choice of position. Is that the way the values are used in an IM?"

---

Yes, and with heuristics, one can have a factor influence (excite or inhibit) another as in the
hidden layer effect of the ANN.

IMs also have other map related uses. When used in conjunction with an A* they can effect
how a pathfinding algorithm finds a path. And obviously, in a wargame or RTS, they can be
used to suggest the best (and worst) places to attack.

I hope anyone reading this comparison of ANNs and IMs to be of use and will give both a
try in their current or next project.

If we have exhausted discussion about finding a place to build a building, then let''s move
on to another AI decision. In FPS death match play, "camping" is a tactic often deployed
by human players. If we want to have our ''bot camp, then how would we use an ANN to
decide "where to camp"?

Eric

quote:

---

Original post by Mathematix

My experience comes from the academic world; developing nets to dianose medical conditions and the like.

---

Do you have any references to published articles from your research team Mathematix? I would be interested to read of the application of ANNs to medical diagnosis as I work in the field of Bayesian Networks which are another popular technique for diagnosis problems (and have been used widely in medical diagnosis). In particular, I would like to see how the problem is tackled with an ANN and compare the differences between ANNs and BNs on the problem... particularly performance wise.

Cheers,

Timkin

quote:

---

Original post by Geta
Influence Maps are often used to solve this problem in a non-ANN manner. [...] In the meantime, I'll just mention that they
are a technique that allows one to graph the influences of various considerations across an area.

---

This sounds like a discretised version of a potential field search. Yes? No?

Timkin



Edited by - Timkin on August 20, 2001 3:09:11 AM

quote:

---

Original post by Geta
If we have exhausted discussion about finding a place to build a building, then let''s move
on to another AI decision. In FPS death match play, "camping" is a tactic often deployed
by human players. If we want to have our ''bot camp, then how would we use an ANN to
decide "where to camp"?

Eric

---

I''ve got a feeling that the majority of the ways I''d use an ANN would be quite similar to the ways an IM would be implemented in the same situation. Like with any AI, you take a set of information about the environment to develop a solution to a question. If IMs are a comparative quality mechanism for positional placing of a task (handled by other AI) then my answer is the same for the camping question as it is for the building placement question. Take the inputs from the agent state (health, weaponry, armour etc.) and the current state of the world and decide upon a course of action. If it''s decided that camping for health or a weapon or something else is necessitated then use the IM or ANN on each node of the world to find the quality of camping for that item. The polling system will give you the best node and you camp it until you get what you want or your/the world state changes for some other reason.

Sound simple enough?

Mike

quote:

---

Original post by Timkin

Original post by Geta
Influence Maps are often used to solve this problem in a non-ANN manner. […] In the meantime, I''ll just mention that they
are a technique that allows one to graph the influences of various considerations across an area.

---

This sounds like a discretised version of a potential field search. Yes? No?

Timkin



Could be. I looked at potential fields years ago (maybe 10?) and do not rightly
recall all their properties and capabilities. If you are looking for a definitive
answer, I know there are descriptions of IMs on the web, that are more
detailed than I''m going into here.

Eric