AI equal cpu usage

At a guess, store the AI's current state and then break off calculation at/after X milliseconds.

Should work for a brute-force method, anyway.

Theoretically that sounds like a solution that would work. But I'm thinking to implement that I would need to save the state of the AI after each line of code in the algorithm for whatever action that AI is trying to perform or compute. This would double the amount of code, and likely more than double the amount of cpu time needed to execute a given algorithm.

Could you throw out some pseudo-code to clarify if I'm missing the mark here?

Though I do like the idea, and that's basically what I'm trying to accomplish, I feel that it is probably not the job of each individual AI to count how long it has been executing an algorithm. I need something like a thread monitor.

Thanks for the response.

AI is my weak point, so not really. However, I don't think you'd need to save the state after each line - Each AI class and function naturally has its own state data; you'd just have to make sure it's stored before breaking off.

This question is one of the reasons why I bought Millington's "AI for Games". Unfortunately, while the book provides good info on various task execution schemes, it was not very forthcoming on the part about getting AI routines to play nice with the time slice, apart from vaguely suggesting that AI routines be implemented in a friendly manner, ie do a bit of computation but return after a while if doing something intensive, storing the intermediate results. This is probably the only way to do it in a single-threaded environment, but it does require you to use timer code in your AI routines. On the other hand, it allows for a kind of "best guess" to be made available that can be immediately acted upon, for instance the direction to move while the pathfinding is working on the full path.

For Java specifically I think you should investigate the possibility of implementing AI routines as Runnable and throwing them into a thread pool (see the Executors factory class). This means that you have to open yourself to the wonderful world of multi-threading, but the Java concurrency facilities provide a lot of cool functionality for you. Whether the Executors pools will spread the love equally among the threads is a question that would need further looking into, however.

To Narf:
This question actually doesn't require extensive knowledge of Artificial Intelligence. It is more of a question relating to concurrent/parallel programming. In the context of AI it is a little bit easier to visualize, though.

Each class does have its own state data, I agree. With Java, we're talking about members of a Java class. But I also need to take into consideration any variables that are in scope when the execution is "broken off".

A quick and dirty example:
for (double i = 0.0; i < 1000000; i += .01) {
this.computeFactorial(i);
}

Ignoring the fact that this example is stupid, I think we can agree that this for-loop will take a while to run... relatively speaking. Let's say the X amount of time originally referred to is reached when the variable, i, is 1000.00. "i" is just a local variable so I'm not quite sure how to store the state of this class, which includes storing the value of "i", without actually putting a method called saveState() in the for-loop too.


To lightbringer:
I will look into the Executors factory class. I am decently familiar with multithreading in C from taking an Operating Systems class. Unfortunately, I also learned in that class that different operating systems don't necessarily implement the fair but equal round-robin scheduling scheme like what would be desirable for this solution. I'll see what I can find after a bit more research.

What you're looking for is known as an "anytime algorithm". Googling that should turn up some useful information.

What is your performance criterion? If your willing to trade off some performance you can run the AIs within an embedded scripting engine (like Lua or Python or Ruby) which gives u fine control of execution. Old games use to do this for NPCs using a cycles budget for each NPC (Grim Fandango for example) and even modern games do this (Eve Online uses stack less Python threads) allowing them to run hundreds of concurrent AIs and tasks within a limited CPU budget.

Good Luck!

-ddn

Sneftel:
That anytime algorithm idea is pretty interesting. That does solve another unmentioned problem which was whether or not any action could be performed at all when the NPC ran out of "thinking" time. If I implement my algorithms in an 'anytime' way then that issue is solved.

I do not believe that solves the main problem though. An anytime algorithm will give me a partial result more or less at any point in time. But anytime algorithms don't help me govern all the NPC's so that each NPC must give me a partial result after a specified maximum amount of time (ie. each turn).

ddn3:
My goal for performance is for a small number of NPC's to run in parallel in near real time. Because I'm limited to a two-core processor, I don't want two NPC's hogging the cpu for complex planning, for example.


I'm curious that this problem doesn't have an obvious answer. There are tons of console games on the market that must have faced this problem before. If you think of a first-person shooter when playing in campaign mode. Most games will have a one hero vs. lots of bad guys plot going on. Or a racing game. One car driving against a dozen opponent cars. All of these agents seem to be thinking all in parallel. How do these commercial games solve that problem?

Thanks again for the responses.

Your criterion are quite different than what normal game developers have. The requirement that each AI don't share state (ie each AI has it's own algorithm and correspondingly state) and you want to give each AI equal amount of CPU time (implying some sort of preemptive threading model where each AI's running process can be halted).

Most AI's in games share state, that is they share some cached path information, spatial checks, shared visibility, etc.. to reduce redundant computation. Also most AI's have the exact same fundamental algorithms with a few tweaks to add some variety and are optimized for this. So you can run 100's of them per frame within the alloted CPU time.

2nd requirement of exact CPU usage per AI, that's almost never done in games since it's never needed. The entire AI system usually get a fixed time slice per frame of the CPU and must work within that bounds. It's unimportant how much each AI gets as long as it performs adequately within that criterion and they usually all run on the same thread so there isn't any need for multithread coding (ie rsrc locks, etc..) techniques.

A language like Java or C++ or C# doesn't offer fine grain execution control (unless there is some API for preempting threads on the microsecond which I'm unaware of). So many games implement a scripting language for their AIs which they can control the execution context of the AI's down to the number of instructions executed per frame (instruction of the scripting language not assembly) with some loss of performance (generally scripts will run about 10x slower than C) but you do gain alot of flexibility.

These scripts are usually some high level language like Python, Lua, Scheme or some custom language invented just for that project, and thats pretty much how commercial developers do it.

Good Luck!

-ddn

One of the problems can be -- will the decision be outdated by the time it is made (if its finalization is delayed too much). Depending on the game/mechanics the situation may change too much, invalidating much of the planning computation. Usually you would need an event processor that would evaluate them to gauge if the situation change is past a threshold. (Ive before used an object tracking mechanism with conditionals and event priorities and accumulated/cached object data/evaluations and the AI gets filtered alerts when the tracker determines a significant change).

The changes then can be applied to the planner to redo only certain branches of the options being evaluated (or if major priority shift happens to dump everything and restart with the new reality).

If your game macro decisions move slowly and generalizations can be made to be able to calculate strategy, more specific tactics code can then take over which
computes the narrower/simpler problem space.

But then, real AI (planner level in environment with many options or even temporal requirements or the bigger buggaboo of uncertainty) will cost alot of CPU, to where moron level intelligence will be taking more CPU resources than the glitzy graphics do (probably by magnitudes). Its just the cost of having to compute/evaluate so many options and constantly throwing out the results and redo it all.

One of the reasons I'm trying to do this the seemingly difficult way is because software has always been losing in the arms race with hardware. Software is written in a certain way because it is limited by hardware speeds. When hardware speeds increase, software is then written to take full advantage of those speeds. I don't believe that artificial intelligence fits that model yet, not with current hardware speeds. If it does fit the model with current hardware, then it isn't artificial intelligence, it's behavior that simulates intelligence.

It may sound like I've just defined AI, but I've defined the spin-off definition people have been using so far. I am not looking to simulate intelligence. Simulated intelligence is not intelligence. It is trickery to fool the person behind the controller. I am looking to create actual intelligence (within a small scope). And by that I mean an NPC should be able to solve problems within its domain. If programming intelligence the way we problem solve can be done with an NPC that can still only solve complex problems 1000 times slower than a person could, that would be great. That would be actual intelligence and soon enough hardware will come along to speed that up to real time performance.

Going back to my original post I better reiterate the word "simulation". I'm not looking to create a fun massively multi-player game. I'm looking to practice programming real intelligence. Not cheating intelligence (shared state, enemies always know where you are, opponent cars behind you get a speed boost to make it a competitive race, etc.)

Real time parallel execution of real, not simulated, intelligence is the goal here. The more I think about this and read new responses the more it looks like I've set the bar way too high. In that case, I still would like to shoot for real intelligence that performs at a slower speed for this simulation. And the original problem mentioned in my first post is still the main problem.

Quote:

Original post by chuck22 I'm looking to practice programming real intelligence. Not cheating intelligence (shared state, enemies always know where you are, opponent cars behind you get a speed boost to make it a competitive race, etc.)

"Real" intelligence, eh? Good luck :)

It used to be that AI got to cheat by knowing the whole state of the board, but today in many games the inputs an AI gets from its environment are limited to pretty much the same as what the player gets. Both sound and sight can already be satisfactorily simulated in real-time, for instance (think Thief, Metal Gear Solid, Uncharted, Assassin's Creed).

I'm not convinced that you can make your NPCs think no matter how advanced the hardware gets. At the end of the day they are still going to follow the programming you wrote. What I think you are (or maybe ought to be) looking for is what is known as emergent behavior, which appears in systems that are sufficiently complex and looks like "thinking" AI doing clever things.

Innovative programming does not happen by admitting defeat at the beginning. I do appreciate you keeping my self-expectations in check. One thing I'm certain of is if this idea is unsuccessful, it's something I will find out the hard way.

I'd still like to keep this on topic for any of those who have read responses down to this point. I am still up for suggestions on fair, parallel processing of multiple NPCs.

Actually we have alot of hardware power these days (and memory too) for much smarter AI.

The real limimitation is building the AI logic (problem specific logic rather than the AI engine which is trivial by comparison -- even much more capable ones).
'Teaching' the AI the proplem logic is the chokepoint and mostly involves 'teaching time' done by real people to form the 'good/correct' thinking and correct or cull out the 'bad/wrong' thinking. Automatic learning systems can help alot but even with them doing the grunt work, a human has to shape the AI
and organize the 'lessons' used as examples in the problem space. Complex systems (simulation/game complexity) has horrendous numbers of endcases which an automatic system has to be exposed to and the 'correctness' of tried solutions cant always be determined/discovered automaticly.

It really doesnt do much good running the same simplistic AI logic faster...

Quote:

Original post by wodinoneeye It really doesnt do much good running the same simplistic AI logic faster...

Well that depends on what the AI logic is doing. If the AI logic is solving a problem, the problem is solved faster. If the AI logic is learning and gaining knowledge, similar to how you mention a human has to teach the AI 'lessons', then that is done faster too.