Artificial Intelligence: Utility builds Character

AI vs AI Debugging

My goal is to simplify some of the pitfalls encountered in dealing with this problem, and distill for you the answers and techniques I used to create the Bulge AI Architecture.  The code is not revolutionary, but implements decision making using Utility Normalization.  Dave Mark covers this concept in depth on his site and articles.  The idea is to be able to score and compare a variety of actions in a way that is intuitive and modular.


This is achieved using a top-down 3 tier approach that focus' on loose coupling, and the end goal of creating an architecture that requires minimal support from the programming team.

Control Yoke (AI Controller) - Interacts with the Interface, requests Decisions

Strategic Brain - Stores, Gathers, and Evaluates Tactical Nodes

Tactical Nodes - Evaluate and Store the Raw Utility values of selecting this Node

Modeling the Player not the Win Condition
Very early on I wanted a concept of an AI Agent as just another player.  "Face-to-Face" games and Solitaire games would be identical experiences.  This calls into question, "What is winning?", and until I can give code access to Tiger Blood, my answer usually starts with the ability to troll players.  Building on that was creating a concept of what types players/strategies would be fun to play against:

Genius - Classic "Best" player, makes all the right moves

Coward - Avoid Confrontation

Psycho - Seeks Confrontation, make Risky Choices

Defender - Cluster Units - Gain and Hold defendable locations

Exploiter - Seek Enemy Weakness

Comedian/Troll - Actively go against normal win conditions, force the player out of their comfort zone.

Many designers start with the "Genius" and quickly run into the wall of it never being good enough, then stop, leaving the player to deal with a sub par opponent, and an architecture hard coded to fail.  These archetypes became springboard to deeper thoughts into what actually goes into playing Bulge.

What it comes down to is by not attempting to define a single "best" move, showed me what moves an Agent COULD make, and what that move could mean to a player.  Focusing on archetypes over win conditions means freedom from overdone difficulty mechanics, and forces loosely coupled Agent design from the first line of code.

Building a Control Yoke

Amusingly the first lines of code had nothing to do with good (cruel) gameplay or strategy.  In deciding to implement the AI as a player, and in the interest of reducing code duplication, the top level was designed to automate a human player's interactions with the interface.  So in essence, the human player's equivalent of the Head and Hands.  If you prefer, it is the AI's controller that allows it to interact with the game.

The Control Yoke was implemented as a Hierarchical Finite State Machine (HFSM) based on game state.  Each game state was broken to a FSM consisting of:

Rising Edge - Initial state prepares AI internals for action this game state

Idle - Gather information about world and game state

Decide Action - Pass Gathered information to decision maker

Commit Action - Perform function that has been decided upon

Wait - Filler state to provide output while waiting for Animations to complete

Not all states were always used.  This allowed for flexibility as features were added or moved.  This structure was also good for recovering from failure.  If an error was encountered at any step, the state could be kicked back to the Rising Edge to ensure the AI was working with clean data.

Bulge Sample HFSM

The next major benefit of abstracting the AI at the player level was that instantiating a second AI Control Yoke was pretty trivial.  Having AI vs AI play not only increased the number of tests per day, but provided the additional stress on the UI to expose some pretty important bugs to fix.

 

Moving Randomly with Purpose

At this point, no smarts have gone in yet.  The "Decide Action" state literally picks a Random Legal Action and executes it.  All is going according to plan.  In order to provide measurable success to stakeholders the following goals were set:

 

Make Random Legal Moves (Random)

Perform Moves with Purpose (Tactical)

AI tries to win (Tactical)

AI prioritizes moves (Strategic)

Externalize Agent that represents the "Genius" Type ( Archetype )

Externalized Agents that challenge the player (Additional Archetypes)

This made for great demos because, the aforementioned AI vs. AI could be set with each new iteration making short work the of the previous.  The real win in being forced to justify each step along the way was keeping the scope the changes in check.

Designing Utility Functions

Utility was the best choice for Bulge because of it's flexibility.  As an asymmetric game, each faction's strategy would need to be vastly different.  Determining if an action led to a win condition was made difficult by complex movement and combat rules that encourage pins and grinding down.

Here's were the Utility function comes in.  Given a certain criteria, it scores how useful an action would be.  This is especially helpful if none of the actions available absolutely lead to a Win State.  By choosing and accumulating actions based on weighted criteria, the Agents can not only track towards their goals, but react to situations as they arise.

The easiest way to think of Utility is with the question, "If I only care about XXX, how do I rate my options?"  XXX can be anything, Moonshine, Vin Diesel Movies, or useful things like bullets and health.  In my example, however, I will be using Apple Pie.

Utility Example 1

The Utility Function has done it's work and returned values of each Action.  Numbers should make sense to the casual observer and be easy to explain.  If it is hard to explain, the function may be doing too much.

Utility Example 2

To reinforce this idea, notice the "plain pie" and "A la mode pie" return the same score.  This is because this is not a test for decadence (where it would score higher), or edibility (I am lactose intolerant), or any other factor that make that one goal better than the other.  It is important that Utility functions tell the Agent one specific thing about the world.  Other utility functions will boost or decrease the utility of this node as they are evaluated.

Yet, how can "Decadence" be compared to "Lactose Intolerance"?  This is done with value Normalization, or making sure the number lies between 0.0 - 1.0.   There are lots of different ways to accomplish this, I'll be using the simplest:

  Node Value - Smallest Value

----------------------------------------------------      or            (Node - Min) / (Max - Min)

 Largest Value   -  Smallest Value

Utility Example 3

All my pre-normalized values are integers to help prevent incorrect mixing of data sources.  This simple function does have pitfalls to be leery of.  The first is range:

Utility Example 4

This happened early in development, where in an attempt to making a certain goal the MOST important, all other values were rendered worthless.  This is a valid design, but make sure it is intended behavior.

Utility Example 5

Another pitfall related to the previous, is creating false positives from equally poor choices.  Having other utility functions, cutoffs, and weights helps reduce the occurrence of this.  Now that all the number are comparable, a weighted sum reveals the best action to take.

At the core, utility breaks down large goals (Win the Game) into small sub goals (Take Enemy ground + Don't die + Win battles).

Ideally, utility functions are created with information from subject matter experts.  Yet this does not have to be the case.  Start with a best guess and work from there. It was really fun to learn how to play Bulge alongside the AI.  Experimentation, observation, and failure built the foundation of my functions, but it was through sharing my failures early that I was able to gain the insight into creating a finished function.

Externalized Agents

Battle of the Bulge ships Dec 13th, 2012, with 8 Agents.  More are planned for future releases.  Each Agent has a personality and distinct strategy that was achieved through tuning an external script file.

Using this architecture, compelling agents can be built quickly, iterated upon, and updated without any input from a programmer.  It is flexible enough to grow as our understanding of the game grows.  And should be able to be carried forward into future projects that use the same basic system.

Pros:

Cons:

Conclusion
There are many different ways to implement and normalize Utility. What matters is the ability to understand that the numbers are meant to map to behaviors. Behaviors can be more than winning, and when reinforced by solid Archetypes, a player can forget the artificiality of their opponent. This moment, where fiction and reality converge, sticks in the minds of players, urging them to discover new facets to their opponent. In seeking more than just "Win State" Artificial Intelligence can create new memorable experiences.

Thanks so much for your support of Bulge, and please drop me a line if you have any questions or want to know more!