Jump to content

  • Log In with Google      Sign In   
  • Create Account


Ai for strategies games


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
15 replies to this topic

#1 Sadness   Members   -  Reputation: 172

Like
Likes
Like

Posted 25 November 1999 - 12:22 AM

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



Sponsor:

#2 MikeD   Members   -  Reputation: 158

Like
Likes
Like

Posted 08 November 1999 - 12:29 AM

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.

#3 Sadness   Members   -  Reputation: 172

Like
Likes
Like

Posted 08 November 1999 - 12:39 AM

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

#4 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 08 November 1999 - 12:27 PM

This sounds quite like Game Theory, something I read about in New Scientist once. Basically you have lots of 'players' who can form alliances or start wars, and how they do this depends on what they have to gain.
For instance, attacking a weak enemy would gain quite a lot (you'd win hands down) but attacking a strong enemy would be foolhardy.

I'm not sure how you'd go about it, but you need to identify some form of scoring for war/peace with all other sides in the game and then throw in a little randomness to give your AI some 'personality'.

All constructive criticism welcome.


#5 MikeD   Members   -  Reputation: 158

Like
Likes
Like

Posted 09 November 1999 - 12:07 AM

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


#6 Sadness   Members   -  Reputation: 172

Like
Likes
Like

Posted 09 November 1999 - 01:06 AM

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.


#7 Niels   Members   -  Reputation: 122

Like
Likes
Like

Posted 09 November 1999 - 01:25 AM

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).]


#8 MikeD   Members   -  Reputation: 158

Like
Likes
Like

Posted 09 November 1999 - 02:11 AM

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?

#9 Niels   Members   -  Reputation: 122

Like
Likes
Like

Posted 09 November 1999 - 04:32 AM

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


#10 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 17 November 1999 - 02:57 PM

Actually, one quick clarification:

A finite state machine always goes to a particular next action given the same circumstances.

A Fuzzy state machine, otoh, fires an appropriate but otherwise randomly determined rule given the same circumstances. The randomness can be weighted, as in
c=random(1..100)
if(c>=80)
dostuff;
else if(c>=50)
dootherstuff;
else
doyetotherstuff;
or unweighted,as in
c =random(1..100);
if (c>=(2/3)*100)
dostuff;
else if(c>=(1/3)*100)
dootherstuff;
else
doyetotherstuff;

although weighted usually makes more sense.

Since I'm just a lowly student I'm guessing that that's what the Estimate... bit is used as in an actual implementation. I just didn't get it, so I figured I'd rephrase it.

Anyway,

signing off,
mikey


#11 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 17 November 1999 - 03:19 PM

Bloody hell.

Just to clarify THAT mess:

dostuff, dootherstuff, and doyetotherstuff are all valid responses to the general game conditions, ie unit health, enemies nearby, etc.

In fuzzy theory this is usually pictured as

d.s. d.o.s. d.y.o.s.
/ \ /\ /\
/ / / \
/ / / \
/ / / \
/ / / \
------------------------------------
^
|
here either
function might be fired,
and the weightings are a
matter of how high the
triangles are at this point
(triangle 'height'
being that big expression
that MikeD wrote out)

And since you're just starting out, I might give you this one piece of advice:
Play with anything you make. Fix the numbers as you play. You might learn some interesting stuff, and as I understand it that's the basic production process in the industry anyway, so you'll have a head start.

Anyway.

signing off,
mikey


#12 MikeD   Members   -  Reputation: 158

Like
Likes
Like

Posted 17 November 1999 - 03:59 PM

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


#13 Anonymous Poster_Anonymous Poster_*   Guests   -  Reputation:

Likes

Posted 19 November 1999 - 06:45 AM

As I think I've mentioned, I'm not a working professional. However, what you've written is a finite state machine based on the weights of the lanes, with transitions defined entirely in terms of maximizing lane-state value, ie nextstate = max(states, params)

As I understand it, true fuzzy logic assigns truth values which lie between 1.0 and 0.0. Hence, as it becomes more appropriate for a particular state to be observed to be true, the likelihood of that state being observed to be true increases. However, the actual state is never simply one or another, but several at once. Hence, a truly fuzzy SM will fire a biased-randomly selected rule. Otherwise it would be fairly limited in one of its best game-related applications - providing different outputs to the same input.

Your code is fuzzy in terms of some variables, but it's not fuzzy in terms of lane weights (which can be internally determined). Whether fuzzy and prop logic are truly equivalent is, as far as I know, still an open question.

Anyway,
I am just a student.

signing off,
mikey


#14 janneyr   Members   -  Reputation: 118

Like
Likes
Like

Posted 23 November 1999 - 07:21 PM

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


#15 Niels   Members   -  Reputation: 122

Like
Likes
Like

Posted 24 November 1999 - 10:25 AM

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

/Niels


#16 MikeD   Members   -  Reputation: 158

Like
Likes
Like

Posted 25 November 1999 - 12:22 AM

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





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