Jump to content

  • Log In with Google      Sign In   
  • Create Account

Any help required?


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
49 replies to this topic

#21 ButchDean   Members   -  Reputation: 110

Like
Likes
Like

Posted 16 August 2001 - 02:29 PM

What have I done! I have spawned a heavily opinionated debate!

This could go on forever. I personally believe that you really cannot accuratly predict the performance of any of the AI methodologies until they have been tried and tested. Bringing in discussions of genetic algorithms and fuzzy logic systems does little to resolve the debate on which is best to use. Personal experience is valuable; analysis better. The relative performance of these methodologies is not only dependant on their architectures, but also on the specifics of the game being designed: one person''s FPS may perform better with a neural net., while another with A*. Who''s to know?

Regards,
Mathematix.


Regards,
Mathematix.

Sponsor:

#22 MikeD   Members   -  Reputation: 158

Like
Likes
Like

Posted 16 August 2001 - 10:18 PM

In absence of information, postulation.

Isn''t that the gamedev way? ;-)

Mike

#23 Geta   Members   -  Reputation: 136

Like
Likes
Like

Posted 17 August 2001 - 01:33 AM

quote:
Original post by Mathematix
What have I done! I have spawned a heavily opinionated debate!

This could go on forever. I personally believe that you really cannot accuratly predict the performance of any of the AI methodologies until they have been tried and tested. Bringing in discussions of genetic algorithms and fuzzy logic systems does little to resolve the debate on which is best to use. Personal experience is valuable; analysis better. The relative performance of these methodologies is not only dependant on their architectures, but also on the specifics of the game being designed: one person''s FPS may perform better with a neural net., while another with A*. Who''s to know?

Regards,
Mathematix.


Regards,
Mathematix.


I was actually hoping that any opinions offered, were coming from an experience of
having implemented (or at least tried to implement) ANNs to handle similar decisions.

I also agree with you, in that it takes implementation to determine the success or
failure of any technique. My posting history mentions that often.

So, with using MikeD''s suggestion, how about if we give this another go?

Eric


#24 Geta   Members   -  Reputation: 136

Like
Likes
Like

Posted 17 August 2001 - 01:41 AM

quote:
Original post by MikeD

It might be useful to discuss what exactly forms the problems of an FPS game and why an ANN system should/shouldn''t be used to try to solve those problems.




Excellent idea. Unfortunately, I''m sorely pressed for time this AM so I can''t offer much this
session. However, I will be back later or tommorrow. In the meantime, you have made an
excellent start with your points about pathfinding and avoiding getting blocked. Perhaps it
would be handy to try to think in terms of specific questions that an AI must get answered
in order to make its next move on the current frame? Like what do I research next? What
should I build next? Where should I camp? Should I camp? etc.

Eric


#25 MikeD   Members   -  Reputation: 158

Like
Likes
Like

Posted 17 August 2001 - 04:17 AM

Okay, let''s dive into picking construction sites for an RTS (seeing as your suggestions were drifting away from just FPS games).
I think in general it seems that there''s no supervised training method feasible for this kind of application. There''s no way of saying what is the right thing to do in a situation, only relaitvely good solutions compared to relatively bad. Otherwise you''d be training an ANN based either on human defined metrics by visual means or writing some logical rules to define the quality of a choice. If you do the latter then just use that as the decision making mechanism and forget the ANN''s ;-).

Okay, so you have a pseudo-blocks world in a typical tile-based RTS. This means you have details about a discrete number of tiles and their status (rocks, buildable land, trees). These factors could be the inputs of a neural net, with several inputs per tile defining key information. The number of tiles searched around a central point would define the size of the networks inputs, with a single numeric value output describing the quality of any given site.
By evolving the networks, using repeated battles as the fitness quotient, you could end up with a good network for deciding the quality of any given site for particular buildings. A similar polling system for what to build next could take into account all the buildings already built (on yours and the enemies sides) and decide on the best building to construct next in a similar manner.

I know this is fairly vague, but we are talking general principles.

Mike

#26 ButchDean   Members   -  Reputation: 110

Like
Likes
Like

Posted 17 August 2001 - 06:09 AM

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.

#27 ButchDean   Members   -  Reputation: 110

Like
Likes
Like

Posted 17 August 2001 - 06:19 AM

quote:
Original post by Geta


I was actually hoping that any opinions offered, were coming from an experience of
having implemented (or at least tried to implement) ANNs to handle similar decisions.

I also agree with you, in that it takes implementation to determine the success or
failure of any technique. My posting history mentions that often.

So, with using MikeD''s suggestion, how about if we give this another go?

Eric



My experience comes from the academic world; developing nets to dianose medical conditions and the like. I am new to game development and am currently coding my own with OpenGL and C++. I have coded many neural nets, and have come up against many problems encountered by newbies.

Regards,
Mathematix.

#28 MikeD   Members   -  Reputation: 158

Like
Likes
Like

Posted 17 August 2001 - 07:59 AM

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

#29 Geta   Members   -  Reputation: 136

Like
Likes
Like

Posted 17 August 2001 - 01:46 PM

quote:
Original post by MikeD
Okay, let''s dive into picking construction sites for an RTS (seeing as your suggestions were drifting away from just FPS games).
I think in general it seems that there''s no supervised training method feasible for this kind of application. There''s no way of saying what is the right thing to do in a situation, only relaitvely good solutions compared to relatively bad. Otherwise you''d be training an ANN based either on human defined metrics by visual means or writing some logical rules to define the quality of a choice. If you do the latter then just use that as the decision making mechanism and forget the ANN''s ;-).

Okay, so you have a pseudo-blocks world in a typical tile-based RTS. This means you have details about a discrete number of tiles and their status (rocks, buildable land, trees). These factors could be the inputs of a neural net, with several inputs per tile defining key information. The number of tiles searched around a central point would define the size of the networks inputs, with a single numeric value output describing the quality of any given site.
By evolving the networks, using repeated battles as the fitness quotient, you could end up with a good network for deciding the quality of any given site for particular buildings. A similar polling system for what to build next could take into account all the buildings already built (on yours and the enemies sides) and decide on the best building to construct next in a similar manner.

I know this is fairly vague, but we are talking general principles.

Mike


How does one achieve several quoted sections within a response? Every time I try to do so,
I end up with the first section quoted and all the others not. Anyway ....

Actually, my "camping" question was relative to "camping in a FPS", but I think your choice of
finding a construction site in an RTS is a good place to start.

Some givens to start with. The approach must be map independent so that it can work just as well
with random or user-created maps. We will assume the AI has already decided what type of building
it needs to build. The map is tile based (although we could consider polygon based maps).

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?

And additional question, how would you use an ANN to decide "what to build next"? And, do you think
an ANN is the better technique to use for this decision?

Eric


#30 Geta   Members   -  Reputation: 136

Like
Likes
Like

Posted 17 August 2001 - 01:53 PM

quote:
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


#31 ButchDean   Members   -  Reputation: 110

Like
Likes
Like

Posted 17 August 2001 - 02:08 PM

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.

#32 ButchDean   Members   -  Reputation: 110

Like
Likes
Like

Posted 17 August 2001 - 02:25 PM

quote:
Original post by Geta
[quote]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.

#33 MikeD   Members   -  Reputation: 158

Like
Likes
Like

Posted 17 August 2001 - 08:22 PM

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

#34 Geta   Members   -  Reputation: 136

Like
Likes
Like

Posted 18 August 2001 - 04:12 AM

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


#35 MikeD   Members   -  Reputation: 158

Like
Likes
Like

Posted 18 August 2001 - 05:23 AM

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

#36 Geta   Members   -  Reputation: 136

Like
Likes
Like

Posted 19 August 2001 - 03:17 AM

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


#37 Timkin   Members   -  Reputation: 864

Like
Likes
Like

Posted 19 August 2001 - 07:33 PM

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



#38 Timkin   Members   -  Reputation: 864

Like
Likes
Like

Posted 19 August 2001 - 08:00 PM

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

#39 MikeD   Members   -  Reputation: 158

Like
Likes
Like

Posted 19 August 2001 - 10:42 PM

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



#40 Geta   Members   -  Reputation: 136

Like
Likes
Like

Posted 20 August 2001 - 02:03 AM

quote:
Original post by 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



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





Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS