Game Development Reference
In-Depth Information
state has a degree of usefulness, or utility, to an agent and that the agent will prefer
states with higher utility.
”
With this definition, you can see that every possible state has a utility value assigned
to it, which is calculated every time a decision needs to be made and is based on how
much happier the agent will be in the new state compared to its current state. Calcu-
lating the utility value is done by taking the current world state and seeing what the
anticipated world state is after performing some action. The delta in happiness
between those two states is the utility of that action. The action with the highest util-
ity is then chosen.
Determining how useful a particular state is or how happy the agent will be in that
state depends on the game. In The Sims, the ideal state is calculated using motives
like hunger, energy, fun, social, and so on. In games like Chess, an analysis of the
board is performed, which could include material, pawn structure, piece positioning,
king safety, and so on. A strategy game might take any number of things into
account, like the safety of the workers, troop strength, and research. Coming up
with a strong utility function is one of the most important steps.
My Favorite Topic
I must admit that the utility theory is one of my favorite topics in AI. That
s
probably why I work on Sims games these days. Whenever I go to the Game
Developer
'
s Conference and meet up with colleagues, there are certain
architectural cliques that people form. Some people love decision trees and
refuse to believe that anything else is better. Others, like me, believe that
utility theory is the way to go. The reality is that none of these sides are
wrong; it
'
'
s just a matter of preference.
The basic algorithm for determining an action is as follows (in pseudocode):
function GetBestAction()
bestUtility = 0
bestAction = none
for action in currentWorldState.GetPossibleActions()
tempWorldState = currentWorldState
tempWorldState.ApplyAction(action)
utility = tempWorldState.Utility()
if utility > bestUtility
bestAction = action
bestUtility = utility
return bestAction
