Hi there....i wanted to ask that in games....which technique of AI or i should say branches of AI is mostly used....like Expert Systems, Fuzzy Logic, Deterministic Algorithms etc.....which one is more frequent generally and as well as according to the situation........thnx...

well the A* algorithm is used alot, though it's unclear to me if that was the kind of answer you were looking for.

I hope that helps!

Cheers
Chris

Games AI is generally state machine based.

Firstly, it all depends on the problem you are trying to solve with it. Secondly, just because a technique is used most for a problem does not necessarily mean it's the best technique.

Tools used often in Game AI:

Search algorithms
Finite State Machines
Production Systems (couple with FSMs to produce scripted agents)

and much less frequently:

Predicate (First Order) Logic
Optimisation
Statistical inference and regression
Function approximation

It depends on the game.

RPGs have different requirements than puzzle games.

In case of complicated games/research simulations/or when AI programmer decided he has honor and he would do it as nice as are his skills.

Search algorithms are useless when amount of possibilities is high. Some AIs works best when they have high amount of possibilities (majority of gamers are using just a limited amount of gameplay elements in supposedly efficient combinations, and when these combinations wouldn't work reliably and they must use intuition. Majority of gamers fail, thus smart AI thrives.) My current AI is designed for around 260, and I'd like if amount of different elements rise to 340.

Finite state machines (I often nickname them as a final state machines because after the function returns there is one precisely defined final state.)
ISM (type 1 and 2)

Random functions.
Chains of decisions.
Limited set of fuzzy logic. (It's often not called this way. It's called a reasonable use of "if".)

Flooding algorithm followed by back tracing. (If programmer have one fixed size array that he can reuse for it, it avoids waste of memory by unnecessary allocations, and he can reuse the state if he'd like to do multiple backtracing.)
DASH (dumb and stupid "heuristic") algorithm. (It produces more believable behavior than A sharp algorithm.). And when used backward it could be used for creation of a game story. (If beginning and end of the story is defined.)

Grouping (Aka when you have 1000 lemmings and one of them uses brain, it's solved as a special case, not per every lemming.), flocking. (Thought if you are using grouping, it's much better to use a strut algorithm and detach them as needed, than use pure flocking.)

Some techniques are rarely used because they might need reconstruction of state on the fly (frequently to be of any use), and it could bring any realistic computer to it's knees. Considering the design document recommends it... These are joys of noncommercial freeware.*1

It might be better if OP would use a somewhat longer post if he'd like some details.

*1 Too bad the earth simulator has low bandwidth between cores.

[Edited by - Raghar on November 2, 2006 8:30:40 AM]

Quote: Original post by Raghar
Search algorithms are useless when amount of possibilities is high.

Well that's certainly not true. One might say it were true of brute force search, but then no one in their right mind would ever try and solve a search problem using a brute force approach.

Developing optimal and efficient search algorithms for a broad class of problems has been a very fruitful area of research within AI. Even on countably infinite sets one can still find viable solutions to problems in finite time. So to say that 'search algorithms are useless' for large state spaces is, in my opinion, a misrepresentation of the facts.

Timkin

You are assuming the full search space is known. Also you are assuming evaluation functions are definable, and unchanging. In more complex games this isn't always the case.

Imagine a leader that supported you in a war, he hate you, you don't know about it. He supported you only because he was told to do so by someone you don't know about, and you don't know about that deal. I would think the evaluation function is doomed to give you the bad result in this case.

It's not that bad with "brute force" if used as a verification algorithm, definitelly not into depth. It's quick to implement, so it might be easily used as a security feature when smart AI would go AWOL.

Quote: Original post by Raghar
You are assuming the full search space is known. Also you are assuming evaluation functions are definable, and unchanging. In more complex games this isn't always the case.

Where did I make these statements? Certainly nothing I said could legitimately lead you to this conclusion. You've simply mapped your understanding onto my statements and come to the wrong conclusion.

I've made no assumptions about any particular domain. Perhaps you should read my last post again... specifically...

Quote:
Even on countably infinite sets one can still find viable solutions to problems in finite time

One need not know the extent of the state space. As for an evaluation function, without access to at least some metric of action cost/utility, there is no optimisation problem and therefore no search necessary. As for a dynamic cost function... again, you're making the assumptions, not me. Dynamic cost/utility functions are no more difficult to deal with than static functions. A good example of this is time dependent utility (Eric Horvitz has published some good work in this in the early 90s).

Anyway, this is getting off topic, so I'm going to leave it at that. If the OP needs more info, holler away.

Cheers,

Timkin

Quote: Original post by Timkin
You've simply mapped your understanding onto my statements and come to the wrong conclusion.

Wow, do you mind if I use that in the future. That's a brilliant turn of phrase.