Search in Game AI

In my experience search has had very limited use in game AI.  For the most part it's used for navigation and for the rare special case action/point selection situation.  This strikes me as not nearly enough.  As an AI developer how are we supposed to avoid the local maximum that is the current state of game AI if we throw one of our most powerful tools out the window.

I think we should flip the situation entirely.  Our default setup should be built around search.  Everything in the AI should be hooked up with search in mind.  Action selection, animation selection, dialog selection, target selection, and so on should all be setup as searches. 

I can already hear my colleagues screaming.  "Search is too slow!"  "It uses too much memory!"  "Don't search if you already know the path!"  And of course all of those statements are perfectly correct.  My contention is that even with this in mind we should still be using search.  Essentially I think if we develop the 'craft' of using search we will find that we can mitigate many of the problems of search while gaining most of the benefits.

When I say craft of search I'm trying to describe how you use and implement search.  If you naively implement search then the time space behavior of search will be prohibitive.  Instead you need to architect your search to work in a real time environment.  To do this we need to do four things.

1. Pick the right algorithm
2. Constrain the search space
3. Expand the solution space
4. Guide the search

Picking the right search algorithm is the most important step.  Can you beam it?  Is A* a possibility?  Can you use ends means analysis?  Your particular situation will require careful thought and consideration about what type of search you need. 

Constraining the search space means that we limit the number of possible states that we consider.  How much you constrain the space is dependent on your problem.   The craft/trick/magic is constraining your search space without excluding your solution from the remaining search space.  In the general case this can't be done.  In most game situations I think this can absolutely be done. 

Expanding the solution space means accepting more possible solutions.  This has the same effect as constraining the search space.  So instead of looking for one possible end state you need consider a range or the best available.

Guiding the search will speed up the search in the general case.  A heuristic or hard coded expert knowledge is perfect for most game situations.  If before you were able to explicitly path the AI to the desired action now you can guide the search to the same exact results.

Given there is some overhead to using search that would not exist in a non search environment you might ask what do we gain for all this hard work.  You might also be thinking "I'm not a dumbass I know all this already and you're still wrong".  In either case let me explain what I think the benefits are/could be to take a more search oriented approach.

AI would be smarter
AI would be more robust
AI would be easier to develop

The AI would be smarter because it would consider more of the state space than you could ever hope to explicitly encode.  The best example I can think of is considering future actions.  It is hard enough to encode all the responses to current state without having to encode responses to future state.  Searching would trade some runtime cycles to explore this space to find better smarter solutions.

The AI would be more robust because it could find solutions to situations we have not explicitly encoded.  We might have a rule for jumping on turtle heads but what if those turtles have wings?  Searching would allow us to find solutions to problems we haven't planned for.  It would also enable us to escape the local minimum.  The AI could get stuck in the valley never able to escape because the tuned thresholds don't account for the fact that turning around just hits the same threshold on the other side.  Searching allows us to get past this issue into the state space of correct solutions.

Search is easier to develop because it requires the AI developer to have less expert knowledge.  You don't have to add as many tuning parameters and better yet you don't have to tune those parameters.  Instead of the AI developer heuristic of we should jump at velocity X, height Y, and Time T we can search and find the optimal best point to jump without the AI programmer ever spending any time trying to figure out good strategies and tuning values for when to jump.

There you go.  That's my manifesto on why we should be using search in games.  I've done hacky one off search stuff but never anything on the scale I'm proposing.  I do have the architecture ready to go though if ever I get something close to a sure lets try it out on project X.

As a follow up I found this article today.  I'm not totally alone.

https://www.skatgame.net/mburo/ps/aiide12-combat.pdf

Game AI Behavior

I'm just going to list out things I think will improve game AI from a behavior standpoint.  I'm going to ignore all the nitty gritty details.  For example I don't think it matters how your AI decides what to do.  I think some  mechanisms are more powerful than others and will help empower you as the developer to make the AI better but ultimately it matters what the AI decides to do and not how it makes that decision. 

AI's should always be purposeful.

• Don't use random 
• Don't use wander
• Don't use idle

Start your model as close to reality as possible

• If you want an airplane to look like an airplane it helps to start with the basic mechanics of airplane flight. 

Don't model bullshit

• Bullshit doesn't scale.  Trying to tune a bunch of AI's to look natural by giving them some half assed model of human intentions is never going to work.  You are far better off just telling them to do what you want to achieve your desired effect rather than tuning some goofy model. 

Respond to everything

• Car wrecks, gun shots, staring, you name it and your AI should respond.

Foreshadow everthing

• Everything the AI does should be signaled. The AI is leaving cover to get a better vantage point. Don't just fucking do it. Signal the player that your doing it and why. It should be clear at all times why an AI is doing something

Execution is king

• Doesn't matter how smart your decision maker is if the AI looks like shit doing it then don't bother

Flicker is the devil

• Once your AI decides to do something it's better to continue doing it long after whatever reasonable reason for doing it has passed then it is to stop doing it then decide to start again in a short period of time.

Spatial hacks are good.

• Allow the world to be annotated to tune specific behavior

Global hacks are bad

• Don't let the AI's be universally tuned

Don't randomly select behaviors

• Don't 50% of the time attack and 50% retreat.  See the first point.  Be purposeful!

Ok I'm out of pearls of wisdom/bs on AI behavior design.  As more come to me I might come back and update this post or repost it etc.  Not sure what works better from a blog perspective. 

Economics is bunk

What does this survey mean?  To me this complete lack of consensus on fairly basic issue means that either the entire field of economics is fundamentally rubbish or it's fundamentally corrupt.  My tendency is to lean towards the corruption side but I don't think that is the truth.  There are no boogeymen just people being people.  That means that the profession is bunk.  The inability to test models or reproduce results means all models are equally accurate or inaccurate.  Krugman and Schiff have equal predictive power. 

As someone who strives to be rational I'm forced to admit that my strong economics views can only be bias based and irrational.