Sign in to follow this  
Thunder0ne

First order logic in videogames

Recommended Posts

I was wandering if first order logic http://en.wikipedia.org/wiki/First-order_logic is used in videogames. There are c/c++ prolog libraries that could be useful to handle complex knowledge bases, so I would like to know if currently anybody has thought of using it to model complex AIs.

Share this post


Link to post
Share on other sites
No it's not. If it is used, it's very rare. Games generally use a simple statemachine for behaviour, and that's about it. It's argued all the time that game AI should "evolve" into something more advanced, but it looks like we're stuck at a local minimum that's difficult to get out of.

Share this post


Link to post
Share on other sites
Quote:

It's argued all the time that game AI should "evolve" into something more advanced, but it looks like we're stuck at a local minimum that's difficult to get out of.


That might be true. But 99% of the time people don't really want smarter AI. They want AI that does less dumb things, but not more smart things.

More smart things and the AI becomes better than the player. People always say "the AI cheats". Well it has to cheat somewhat just to work. But usually they refer to cheating due to personification. If the AI makes a decision and the player can't personalize the decision then the AI cheated. The simplest cases are when the AI knows where the player is, sometimes people get frustrated with the thought "how did he know i was here?". Other, more subtle cases are caused by reaction time. It takes you a moment to identify an object, tell if it is friend or foe, and then click fire. The AI can, in theory, just shoot the instant the line-of-sight is clear and get a headshot. People expect the AI to have similar, or slower, reaction time and similar to worse aim.

Less dumb things is where AI is at. F.E.A.R. was touted as having great AI at release. A lot of this came down to the fact that it sounded like the AI was thinking and reacting to the player. When the AI screwed up and got stuck it would yell things like "I got no place to go!". When you left the navigation or engagement area of the enemy they'd say "I lost him". This hides the "dumb" aspects of the AI fairly well, since you hear a reasonable decision to cover up the fact that the AI really is just out of options. It is those out-of-options states that really bug people: AI walking into walls, AI being confined to a particular area, etc.

People also tend to have more problems with friendly AI than enemy AI. In movies, books, TV, and games people have come to expect some level of stupidity from the evil enemies. At the same time they expect that an AI buddy should be just as good as a human co-op partner. Problem is they are bugged by similar AI issues: AI having poor threat assesment(ie attacking X when you expect it to attack Y), AI having poor controllablility (player can't tell it what to think), etc. Left4Dead manages good voiceovers too. Simple things like saying "I'll be right there" indicate that the AI has some sensor to determine if you are down, even if their state machine assesses "melee zombie" as more important, thus getting you killed. That is enough to help most people forgive the AI. They still yell that it is stupid, but they treat the faults as faults of the entity and not the programmer.

Triming down on the dumb things the AI does means more to almost any player than having the AI be "smarter" in the same sense you'd call a person smarter. And in reality the AI being "dumb" is less about the limits the AI has and more about not conveying those limits to the player. Convey those limits and people are much more forgiving of the AI and the programmer. People tend to easily see what is bad, but can never place their finger on what is good.

Share this post


Link to post
Share on other sites
you make some great points, i never thought about it but you are right. Good AI programming doesnt make the AI smarter (well unless we are talking about a chess game or something) but rather making it less dumb. Thanks for that insight.

Share this post


Link to post
Share on other sites
Thanks for your interesting information.
It appears to me, then, that it is a question of how the AI behaves in a game rather than a performance problem.
A chess game or a simulator of a complex behaviour, such as a turn based complex (civilization and so forth) game, would use this kind of advanced techniques, but "usual" videogames actually do not use much more than a state machine, randomising and sometimes cheating :-)

Share this post


Link to post
Share on other sites
I see a lot of room for fancy AI, but not necessarily in the direction of better planning. There is also the possibility of more social AI, which could open up new genres of video games. There are all sorts of subjects that movies can deal with and video games can't until we develop socially aware agents. For instance, we should be able to have video games where you investigate a murder case, or "chick video games" about romantic relationships, but you won't get anywhere if the agents don't understand what an interrogation is, or what a date is.

Share this post


Link to post
Share on other sites
I just got home (an hour late) from E3 and I'm shot... but I wanted to toss something out here. In a panel at the AI Summit at GDC, I spoke about how AI is in the middle of a pipeline where we are getting throttled at both ends. On the output side of things, it doesn't matter how much we do with the AI - if the animation can't express it (an expensive proposition), then it doesn't matter how many shades of behavior we come up with.

On the input side, we are limited by the world model and knowledge representation. If it doesn't exist in the world model (technically) we can't reason about it. This is where the first order logic comes in. First order logic often deals with definitions of relationships between entities - physical or conceptual. By utilizing it (and other things like it) we increase our resolution on the knowledge available to process our decisions with. This can be used to either make smarter AI or - as has been proposed above - to make "less dumb" AI.

Therefore, first order logic DOES have a place in making better game AI... it's just tricky to figure out how.

Share this post


Link to post
Share on other sites
As far as I understood,
something using a first order logic based Knowledge Base could be useful if the programmer does not want or cannot define all of the state of a state machine that can decide what action a AI to perform based on current conditions.

So with this technology an AI could infer what is true and false without somebody having written it in a state machine or in a "if - else chain".
I cannot think of something really interesting in videogames right now (well, that was basically the initial question :) ), but I tend to agree that such things would improve AI or at least AI engineering a lot.
The thing I am worried about is performance: a state machine determines the required action immediately, but requires thorough designing, whilst an inference engine would need to "think" about it, that is to think what is true and false in order to decide what to do.
I will try and study deeper it (if only I had more spare time.. sigh...) and implement some very simple example.
I guess I will use Russel and Norgiv as reference which appears to me to have a good theoretical approach. Do you know any other book or web reference that maybe has some example already implemented?

What about implementing a simple AI using automatic reasoning to play Windows minefield (or minesweeper I forgot the name of that game)?
Would that be a good starting point, even if a very simple one?
How would you implement an AI playing minefield without using an inference engine?
Does anybody know about other examples that could be interesting to understand when it is better using automatic reasoning rather than a state machine?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this