15 replies to this topic

[Sadness]

Well... i have some problem to figured out a way for making an AI, I dont know if some peoples here know the Koei's games like Romance of the 3 kingdom. I want to make somethings like that but ... i dont really know how

my main idea is to make some rulers doing dyplomacy with some players and making war with others. Some rulers would be more warlike, other might be peacefull, but i want to make them change there "minds" because of some players actions. Like making the rulers#1 attacking a player with the rulers#2

i know this is possibly. but how

[MikeD]

The difficulty here is that you've offered up a problem with a huge scope, many solutions and no real definition.
How much do you know about AI?
Can you define the problem better?
It is much easier to solve a well defined problem. You'll find, in most cases, just understanding what you're asking will offer up a solution by itself.

[Sadness]

Well like you said there's nearly an infinite number of possiblity for this kind of games. And to be true ... i dont really know a lot of thing about AI ... There's a lot of good tutorial . but mostly for "starcraft" games. If you have a very good one i will welcome it

[MikeD]

Okay, what your AI will have to perform is the basis of all artificial intelligence, specifically, decision making.
There are many methods of programming an intelligence to make decisions. Condition Action rules (split into finite and fuzzy state machines), expert systems and neural networks to name the basic ones. Each of these can also be adjusted by adaptive learning or genetic algorithms.
Am I scaring you yet?
Personally, if you're inexperienced, I'd suggest you get your head around condition action rules first. The basic methodology of this (if there is a complex methodology) is identical to the IF THEN statement. Based on a set of criteria, which is basically the current state of the game at any one point in time, the AI cycles through a set of IF THEN clauses until one is triggered. This is a finite state machine, it uses distinct TRUE and FALSE values about a set of facts to determine an answer, everytime you run it with a set of values it gives an identical reasoning.
Fuzzy logic or fuzzy state machines don't work from TRUE/FALSE criteria, instead they weight values from various inputs from the current environment state and make a less distinct decision.
Here's an example to show the difference between finite and fuzzy state machines (often written as FSM and FuSM).
IF 2 * numberOfEnemies < numberOfAllies THEN attack
This would be a FSM making a logical decision which would always fire given the number of it's allies being at least double the number of it's enemies.
For a FuSM example of the same problem
AttackWeighting = ((NumberOfMyTroops * AverageQualityAlly) / (NumberOfEnemyTroops * AverageQualityEnemy)) + (AmountOfLandGained / EstimatedTroopsLost) + HateTowardsEnemy - EstimatedBadFeelingDueToAttack
if (AttackWeighting > 0.75 - aggression) then Attack
It can be as complicated or as simple as you feel necessary.
Most game AI is written as a mixture of FSM and FuSM and it should solve your problem fine.
The main difference is that values in FuSM (such as aggression and HateTowardsEnemy) are constantly changing throughout the game based on past events but FSMs and FuSMs are essentially the same idea.
Any comments?

Mike

[Sadness]

I have only one comment.

Thank ya a lot. You have clear a lot of question i was having. This give me a good example to work with.

Btw, this is not so scary, this is mainly time consuming as i see. i think i will use the if-then statement first.

[Niels]

I've tried this before, but people don't seem to get it, so this time I'll post an example (sorry about the size of it, but it needs a certain size for you to grasp the complexity):

The following is the definition of an array database that describes a common puzzle (some of you might even know it). The idea of the puzzle is, that given a number of people, cars, houses etc. (domains) and descriptions such as "mr.x drives a buick", "mr.y lives in a green house" (relations) you should be able to answer a question such as "who lives in the red house?" without that information being given explicitly.

UBB wouldn't eat the post in one chunk, so the example is available at www.array.dk). The puzzle should be obvious from the comments in the example.

Try to envision a program that given ANY set of input values on any (or all) of the variables can INSTANTLY deduce EACH AND EVERY solution that satisfy the given relations. Now, try to program that using IF THEN statements. No easy task (impossible in fact).

What I am trying to illustrate is that the use of state machines in game AI is perhaps one of the most limiting factors today, simply because there is a limit to how complex problems you can solve with IF THEN statements.

An arraydatabase, on the other hand, is a very efficient binary representation of variables and relations (such as the example above) that is guaranteed to be complete, is VERY small, and allow for VERY fast (table lookup) run-time deductions.

If you want to read more about the math behind this, check out our web site at http://www.array.dk

If you find this interresting and feel like playing around with it, a free evaluation kit will be made available within the next couple of weeks.

/Niels

[This message has been edited by Niels (edited November 09, 1999).]

[MikeD]

Point taken Niels, I totally agree.
Well, actually, I kinda disagree.
I'm one of the believers that any one representation of AI can be represented in any other representation of AI. You can form a set of CA rules out of a neural net or neural net out of an expert system. Normally, due to complexity, one compact form would turn into a hideous huge form in another representation, probably expanding exponentially in size but possible nonetheless.
However, my main point was to get Sadness started with something simple, easy and quick to learn before trying anything complex. I've written simple neural networks and know they can be difficult to debug when they go wrong (bordering on impossible with more than a few dozen nodes) and auto-adapting them in realtime is something most AI programmers shy away from.
So I stuck with simplcity for now...however I will be checking out the URL.
And while we're here, do you have any thoughts on my unresponded topic on Tessalatable AI?

[Niels]

I was not trying to say that FSM or FuSM are dead, just that there are better ways for some of the problems typically solved with SMs. Also, the ADB is NOT fuzzy in nature, and it doesn't learn or mutate in any way, so it should be considered a tool in the toolbox, not an AI engine.

Reg. tessalation: I was going to post an answer, but it ended up as a rather - eh - "muddy" attempt at saying something clever. If I understand you correctly, I generally like the idea, but see some pitfalls (here it comes ):

1) Obviously, the tessalation parameter would have to be something other than the "visibility" of an NPC. Such as "the importance of the NPC at this particular stage in the game". How you determine this I don't know, it could be as simple as a priority list. The problem is that figureing out what NPC are more important is generally an AI exercise in itself.

2) While owners of slow computers would generally accept lower quality gfx for a faster framerate, I'm not sure they would accept dumb AI. (Besides, what will happen with a game that is hard on a 450PII, when it's run on a 1GHz Athlon?)

/Niels

[MikeD]

I believe the only time an FuSM fires a rule randomly is when two or more competing rules have equal weighting and there is no way to determine a better rule heuristically.

Take this example for determining which lane of a road for a car to be in, ripped directly from my code, so somewhat messy.

if(NAV_GetState(car->pilot,NAV_ISPERP))
{
DoubleSwitchLanesWeight = 0.0f; // The higher this is the less likely a car is to try to change two lanes at once
laneWeightThreshold = 150.0f; // The lower this is the more likely a car is to slow behind other traffic
StickToLaneWeight = 20.0f; // The higher this is the more likely a car is to choose it's current lane
SpeedWeightDivider = 1.0f; // The higher this is the less likely a pilot is to change lane for speed
FlightMultiplier = 0.0f; // The higher this is the less likely a pilot is to damage other cars/themselves to get into a lane
OppositeDirectionWeight = -200.0f; // The higher this is the less likely a car will take a lane going in the opposite direction
SideWalkWeight = -200.0f; // The higher this is the less likely a car will use a sidewalk
}
else
{
DoubleSwitchLanesWeight = 30.0f; // The higher this is the less likely a car is to try to change two lanes at once
laneWeightThreshold = 50.0f; //50 // The lower this is the more likely a car is to slow behind other traffic
StickToLaneWeight = 100.0f; //75 // The higher this is the more likely a car is to choose it's current lane
SpeedWeightDivider = 2.0f - car->pilot->agro; // The higher this is the less likely a pilot is to change lane for speed
FlightMultiplier = 1.0f; // The higher this is the less likely a pilot is to damage other cars/themselves to get into a lane
OppositeDirectionWeight = -2000.0f; // The higher this is the less likely a car will take a lane going in the opposite direction
SideWalkWeight = -2000.0f; // The higher this is the less likely a car will use a sidewalk
}

The first instance is for a getaway driver, the second is for a normal car trying to drive legally.

These values are used in a series of computations to determine the following weights

totalWeightFromLane
which is the sum of
weightFromAlreadyBeingInLane
weightFromNextCorner
weightFromLaneDistance
weightFromLaneDisappearing
weightFromForwardObstacle
weightFromRearObstacle weightFromCurveObstacle
weightFromBeingStuck
weightFromLaneBeingIllegal

Each of which represent different factors in driving.

The weights are totalled up and the car switches to the lane with the new highest value.

As the values are all floats and there are so many heuristics involved, in the unlikely event of a tie (I don't think I've ever had one) it is pretty unimportant which lane the car ends up in.

No randomness but certainly not what you would consider an FSM.

The fuzziness comes from an inability for us to see the logic, not the lack of logic itself.

MikeD

[janneyr]

Thought I would add a bit and try clarify a few remarks:

Formally, Fuzzy Logic is an extension of Propositional Logic that allows propositions to have truth values [0..1]. It uses the min function to approximate the 'and' of propositional logic and the 'max' function to approximate the 'or' function of propositional logic ... etc. From my perspective, the FuSM seems to follow the general idea of Fuzzy Logic without any of the formal structure. This seems to be good since there are many problems with Fuzzy Logic, but also bad since there are no formal rules to follow - the structure of each FuSM test must be thought up with little reuse.

If you start talking about random FSM's, then you have an NFA (Nondeterministic Finite Automaton) where alternatives are chosen completely at random or a Markov Model where each alternative has a probability and each transition is chosen stochastically, relative to that probability. This is closest to what mikey was describing, I think.

Markov Models are commonly used for modelling animal (or human) behaviour and in the design of 'rational agent' AI, or Natural Language Processing. They may or may not be necessary for a game system, but because the probability of transitions can be easily parametized or learned from training data(Hidden Markov Models or HMM's), it could
be a valuable tool.

Rob

[Niels]

Just thought I'd mention this: The eval kit IS available now (http://www.array.dk)

/Niels

[MikeD]

Rob, thanks for clearing thsoe precise definitions up, it's been a while since I've been a student and my AI vocabulary has gone a touch *cough* rusty.
In terms of game AI I can honestly say I've never actually used an FuSM or an NFA. The majority of the heuristics I use are comparable to each other and thusly use a -inf to +inf scaling (normally limited to the +/-10000 level).
Generally, I think reducing levels to truth values is rarely a necessity in games and normally kept for academia. I also find using bipolar systems to be a lot better than binary.

Mike