robert zubek / blog

Interesting post by Tadhg Kelly on the everpresence of the slot machine mechanic: http://tadhgkelly.com/post/352475659/ethical-design-are-most-social-games-just-virtual-slot

I definitely sympathize. Games of chance, when used sporadically in an existing game, can make a nice addition, a fun bonus. But when pushed front and center, they don’t stand up nearly as well. Even in Tadhg’s example, where you can stack your card deck to influence the odds – it’s still boils down to a die roll.

But one major point I’ll disagree with – Tadhg conflates slot machine and energy mechanics, as if they were two sides of the same coin. But energy itself can be used in much more interesting, more rewarding ways, than just to feed games of chance. (And by energy, let’s say more precisely: “usable resource that refills over time”. Just to make sure we’re talking about the same thing. )

In a deeper game, energy can be made more interesting. One example: Mafia Wars – you can spend energy to advance along several distinct dimensions – towards leveling up, to improve your combat, to earn money, to unlock loot needed for later on – and since all of those elements have their own consequences later on, you need to choose wisely based on what you’re trying to achieve. Second example: chips in poker – they’re a resource as well, and of course you use them to play the main game. Both are much more than slot machines – and, dare I say, strategic.

That said, energy works well when it’s not the main point of the game. It’s the limited currency that fuels and gates the other mechanics, and forces you to make interesting decisions with limited resources. But the game needs to offer interesting decisions in the first place; a slot machine does not.

(This note is a part of the needs-based AI series)

Action Performance

Having chosen something to do, we push the advertisement’s actions on the agent’s action queue, to be performed in order. Each action would routinely be a complete mini-script. For example, the stove’s “clean” action might be small script that:

• Animates the agent getting out a sponge, scrubbing the stove
• Runs the animation loop, and an animated stove condition meter
• Grants the promised reward

It’s important that the actual reward be granted manually during the action, and not be awarded automatically. This gives us two benefits:

1. Interrupted actions will not be rewarding, and
2. Objects can falsely advertise, and not actually grant the rewards they promised

False advertisement is an especially powerful, but dangerous option. For example, suppose that we have a food item that advertises a hunger reward, but doesn’t actually award it. A hungry agent would be likely to pick that action – but since they got no reward, at the next selection point they would again likely pick, and then again, and again. This quickly leads to very intriguing “addictive” behaviors.

This may seem like a useful way to force agents to perform an action. But it’s just as hard to make them stop once they’ve started. False advertisements create action loops that are very difficult to tune. In practice, forcing an action is easier done by just pushing the desired action on the agent’s action queue.

 

Action Chaining

Performing a complex action such as cooking a meal usually involves several steps (such as prep and cooking), and several objects (a fridge, a cutting board, a stove). This sequence must not be atomic – steps can be interrupted, or they can fail due to some external factors.

Complex sequences are implemented by chaining multiple actions together. For example, the “eat dinner” action might involve several steps:

1. Take a food item from the fridge
2. Prepare food item on a counter
3. Cook food item on the stove
4. Sit down and eat, getting a hunger reward

Of course we don’t want to implement this as an atomic action; there is too much variability in the world for it to always work out perfectly.

We can add dynamism in a couple of ways. The simpler way is to simply represent this as a sequence of small atomic actions, and push each of them on the agent’s queue. This is straightforward, and has the nice effect of interruptability: if something important comes up, we can load it on the front of the queue, and when it’s done, the agent will just get back to whatever it was doing.

Of course these steps can fail, in which case the entire chain should be aborted, potentially with interesting results. For example, a failed “cook food” action, in addition to interrupting cooking, might create a new “burned food” object that needs to be cleaned up.

The second method, more powerful but more difficult, is to implement action chaining by “lazy evaluation.” In this approach, only one action step is created and run at a time, and when it ends, it creates the next action and front-loads it on the queue.

For an example of how that might look, consider the “eat dinner” action again. The advertisement would specify only one action: take food. Once that step is done, it would find the nearest kitchen counter object, ask it for the “prepare food” action, and load that on the queue. Once “prepare food” was done, it would find the nearest stove, ask it for a new “cook food” action, and so on.

Doing action chaining this way makes it possible to modify the chain based on what objects are available to the agent. For example, a microwave oven might create a different “cook food” action than a stove would, providing more variety and surprise for the player. Second, it makes interesting failures easier. For example, the stove can look up some internal variable (eg. repair level) to determine its failure, and randomly push a “create a kitchen fire” action instead.

In either case, using an action queue provides nice modularity. Sequences of smaller action components are more loosely coupled, and arguably more maintainable, than standard state machines.

 

Action Chain State Saving

When an action chain is interrupted, we might want to be able to save its state somehow, so that it gets picked up later.

Since all actions are done on objects, one way to do this is to mutate the state of the object in question. For example, the progress of “cleaning” can be stored as a separate numeric cleanness value on an object, which gets continuously increased while the action is running.

But sometimes actions involve multiple objects, or the state is more complicated. Another way to implement this is by adding state objects. An intuitive example is food from the original Sims: the action of prepping food creates a “prepped food” object, which cooking then turns into a pot of “cooked food”, which can be plated and turned into a “serving”. The state of preparation is then embedded right in the world: if you interrupt prepping, your cut up food will just sit there, until you pick it up later and put it on the stove.

 

(Go to intro, part 1, part 2, part 3)

• (This note is a part of the needs-based AI series)

Advertisement Scoring

Once we have an object’s advertisement, we need to score it, and stack it against all the other advertisements from this and other objects. We score an advertisement based on the reward it promises (eg. +10 environment), and the agent’s current needs. Of course it’s not strictly necessary that those rewards actually be granted as promised; this is known as false advertising, and can be used with some interesting effects, as described later.

Here are some common scoring functions, from the simplest to the increasingly more sophisticated:

 

a.      Trivial scoring

future value _need = current value _need + advertised delta _need

score = ∑ _{all needs} (future value _need)

Under this model, we go through each need, look up the promised future need value, and add them up. For example, if the agent’s hunger is at 70, an advertisement of +20 hunger means the future value of hunger will be 90; the final score is the sum of all future values.

This model is trivially easy, and has significant drawbacks: it’s only sensitive to the magnitude of changes, and doesn’t differentiate between urgent and non-urgent needs. So increasing hunger from 70 to 90 has the same score as increasing thirst from 10 to 30 – but the latter should be much more important, considering the agent is very thirsty!

 

b.      Attenuated need scoring

Needs at low levels should be much more urgent than those at high levels. To model this, we introduce a non-linear attenuation function for each need. So the score becomes:

                score = ∑ _{all needs} A _need (future value _need)

where A _need is the attenuation function, mapping from a need value to some numeric value. The attenuation function is commonly non-linear and non-increasing: starts out high when the need level is low, then drops quickly as the need level increases.

For example, consider the attenuation function A(x) = 10/x. An action that increases hunger to 90 will score of 1/9, while an action that increases thirst to 30 will have a score of 1/3, so three times higher, because low thirst is much more important to fulfill.

These attenuation functions are a major tuning knob in needs-based AI. We will have more to say about various attenuation functions later.

You might also notice one drawback: under this scheme, improving hunger from 30 to 90 would have the same score as improving it from 50 to 90. Worse yet, worsening hunger from 100 to 90 would have the same score as well! This detail may not be noticeable in a running system, but it’s easy to fix, by examining the need delta as well.

 

c.       Attenuated need-delta scoring

It’s better to eat a filling meal than a snack, especially when you’re hungry, and worse to eat something that leaves you hungrier than before. To model this, we can score based on need level difference:

                score = ∑ _{all needs} (A _need (current value _need) – A _need (future value _need))

For example, let’s consider our attenuation function A(x) = 10/x again. Increasing hunger from 30 to 90 will now score 1/3 – 1/9 = 2/9, while increasing it from 60 to 90 will score 1/6 – 1/9 = 1/18, so only a quarter as high. Also, decreasing hunger from 100 to 90 will have a negative score, so it will not be selected unless there is nothing else to do.

 

Action Selection

Once we know the scores, it’s easy to pick the best one. Several approaches for arbitration are standard: in a winner-takes-all approach, the highest-scoring action gets picked; in a weighed-random approach, we do a weighed random selection from the top n (eg. top 3) high-scoring advertisements; other approaches are easy to imagine, such as a priority-based behavior stack.

In everyday implementation, weighted-average is a good compromise between having some predictability about what will happen, and not having the agent look unpleasantly deterministic.

 

Action Selection Additions

The model described above can be extended in many directions, to add more flexibility or nuance. Here are a few additions that I’ve used in the past, and how they have fared:

 

Attenuating score based on distance

Given two objects with identical advertisements, an agent should tend to pick the one closer to them. We can do this by attenuating each object’s score based on distance or containment:

score = D ( ∑ _{all needs} ( … ) )

where D is some distance-based attenuation function, commonly a non-increasing one, such as the physically-inspired D(x) = x / |distance|^2

However, distance attenuation can be difficult to tune, because a distant object’s advertisement will be lowered not just compared to other object of this type, but also compared to all other advertisements. This may lead to a “bird in hand” kind of behavior, where the agent prefers a much worse action nearby rather than a better one further away.

 

Filtering advertisements before scoring

It’s useful to add pre-requisites to advertisements: for example, kids should not be able to operate stoves, so the stove should not advertise the “cook” action to them. This can be implemented in several ways, from simple attribute tests, to a full expressive language for Boolean predicates.

From personal experience, I would recommend starting out with something simple, because complex prerequisites are more difficult to debug when there are many agents running around. An easy prerequisites system could be as simple as setting Boolean attributes on characters (eg. is-adult, etc.), and adding an attribute mask on each advertisement; action selection would only consider advertisements whose mask matches up against the agent’s attributes.

 

Attenuation function tuning

Attenuation functions map from low need levels to high scores. Each need can be attenuated differently, since some needs are more urgent than others. As such, they are a major tuning knob in games, but a delicate one because their effects are global, affecting all agents. This requires good design iterations; but analytic functions (eg. A(x) = 10/x) are not easy to tweak by designers or reason about.

I have found the happiest medium by defining attenuation functions using piecewise-linear functions (ie. point pairs, rather than analytic formulas) in a spreadsheet file, and loading them during the game.

 

Tuning need decay

 Agents’ need levels should decay over time; this causes agents to change their priorities over time. We can tweak this system by modifying how quickly those needs decay. For example, if an agent’s hunger doesn’t decay as quickly, they will not need to eat as often, and will have more time for other pursuits.

We can use this to model a very bare-bones personality profile, eg. whether someone needs to eat/drink/entertain themselves more or less often. It can also be used for difficulty tuning: agents whose needs decay more quickly are harder to please.

 

Tuning advertisement scores

The scoring function can also simulate simple personality types directly, by tuning down particular advertisement scores. To do this, we would have each agent contain a set of tuning parameters, one for each need, which modify that need’s score:

                new score _{agent, need} = old score _{agent, need} * tuning _{agent, need}

For example, by tuning down the +hunger advertisement’s score, we’ll get an agent that has a stronger preference for high-quality food; tuning up a +thirst advertisement will produce an agent that will opt for less satisfying drinks, and so on.

(Go to intro, part 1, part 2, part 3)

(This note is a part of the needs-based AI series)

Main AI Loop

Let’s get right to the meat of the matter: the main AI loop. There are many ways to drive an agent; many games use finite-state machines, or behavior trees, or other approaches. Needs-based AI is an alternative that works as follows.

To pick something to do, the agent looks around the world, and figures out what various things can be done, based on what’s in the area. The agent makes a list of what activities are possible, and scores how beneficial they are. Finally, it picks a good one based on the score, finds what actions make it up, and pushes them onto its action queue.

The highest-level AI loop looks like this:

Main AI loop:

• While there are actions in the queue, pop the next one off, perform it, and get the reward
• If you run out of actions, perform action selection based on current needs, to find more actions
• If you still have nothing to do, do some fallback actions

That second step, the action selection point, is where the actual choice happens. It decomposes as follows.

Need-based action selection:

1. Examine objects around you, and find out what they advertise
2. Score each advertisement based on your current needs
3. Pick the best advertisement, get its action sequence
4. Push the action sequence on your queue

The following sections will delve more deeply into each of those steps.

 

Needs

Needs correspond to individual behavior drivers; for example, the need to eat, drink, rest, and so on. The choice of needs depends very much on the game. A simulator of everyday people such as the Sims borrowed heavily from Maslow’s hierarchy, and ended up with a mix of biological and emotional drivers. A different game should include a more specific set of drivers.

Inside the engine, needs are routinely represented as simple numeric values, which decay over time. In this discussion we use the range of [0, 100]. Depending on the context, we use the term ‘need’ to describe both the driver itself (eg. hunger), or its numeric value (eg. 50).

Needs routinely have the semantics of “lower is worse and more urgent”, so that hunger=30 means “I’m pretty hungry,” while hunger=90 means “I’m satiated.” Performing an action then “refills” the need to a higher value.

To simulate needs getting worse and more urgent over time, their values also decay at some rate. For example, decreasing the hunger value over time simulates the agent getting hungry if they don’t eat. Performing the “eat” action would then refill it, and it would be less important.

 

Advertisements and Discovery/Selection Decoupling

When the time comes to pick a new set of actions, the agent looks at what can be done in the environment around them, and evaluates the effect.

Each object in the world advertises a set of action/reward tuples – some actions to be taken, with a promise that they will refill some needs by some amount. For example, a fridge might advertise a “prepare food” action with a reward of +30 hunger, and “clean” with the reward of +10 environment. I will write these as tuples: < “prepare food”, +30 hunger > or < “clean”, +10 environment >, respectively. 

To pick an action, the agent examines the various objects around them, and finds out what they advertise. Once we know what advertisements are available, each of them gets scored, as described in the next section. The agent then picks the best advertisement using the score, and adds its actions to their pending action queue.

Please notice that the discovery of what actions are available is decoupled from choosing among them: the agent “asks” each object what it advertises, and only then scores what’s available. The object completely controls what it advertises as available, so it’s easy to enable or disable actions based on object state. This provides great flexibility, for example, a working fridge might advertise “prepare food” by default; once it’s been used several times it also starts advertising “clean me”; finally, once it breaks, it stops advertising anything other than “fix me” until it’s repaired.

Without this decoupling, imagine coding all those choices and possibilities into the agent itself, not just for the fridge but also for all the possible objects in the world – it would be a disaster, and impossible to maintain.

 

(Go to intro, part 1, part 2, part 3)

These notes describe a needs-based AI for action selection and performance in game characters. It’s a very flexible and intuitive method for building moderately-complex autonomous agents, which are nevertheless simple and highly efficient.

In short: needs-based AI is based on agents having a set of needs, and performing actions that fulfill them. These needs represent independent, often conflicting motivations, such as hunger, thirst, or boredom. The agent’s action selection is driven by wanting to fulfill these needs – but one always comes at the cost of the others.

My own exposure to needs-based AI came first from the Sims (first at Northwestern University, and later at EA/Maxis). I have since re-implemented variations on this approach in two games: a very popular web game, and an RPG. I found the technique to be extremely useful, even across such a range of genres and platforms. But unfortunately, it’s not widely known.

In terms of its historical context, needs-based AI is a younger relative of behavior-with-activation-level action selection methods, common in autonomous robotics [1]. However, it seems to have been independently rediscovered in the gaming context, with great results. Sims was perhaps the best known game based on this model. A particularly interesting contribution of the Sims was also a new action representation, where the behavior/activation data is distributed “in the world” in the game, and therefore very easily configurable.

Unfortunately, very few resources about the original Sims AI remain available; of those, only a set of course notes by Ken Forbus [2] and a Sims 2 presentation by Jake Simpson [3] are freely downloadable on the web. My goal in this set of notes is to present some of this knowledge to a wider audience, based on both what I learned about the original Sims AI, but also my experience building such systems from scratch for other games.

This will come in three parts:

1. Needs and the Main AI loop
2. Advertisements and Scoring
3. Action Performance

Enjoy!

 

[1] for an overview, see Arkin’s Behavior Based Robotics, p. 141 and on.
[2] http://www.cs.northwestern.edu/~forbus/c95-gd/lectures/The_Sims_Under_the_Hood_files/frame.htm
[3] https://www.cmpevents.com/Sessions/GD/ScriptingAndSims2.ppt

Casual games are fun to play and fun to make, but can a developer make a living from them? Funding the casual business was one of the prominent questions at this year’s GDC. I want back and forth between the Casual Games and Worlds in Motion summits, and managed to gather a few interesting tidbits. Here are my impressions.

The popular funding models are: 

• Indirect ad sales – ad rotator networks, etc., which let people participate in a larger pool of ad space providers
• Direct ad sales – such as doing a deal with a specific client, for banner or in-game ads
• Shareware model – aka try-and-buy, typically with a content lock (e.g. first level free) or a time lock (first hour free)
• Subscription – the standard MMO approach, pay per month
• Virtual goods model – aka free to play, pay for items

Of these, advertising is the most popular entry-level option, but it has its pros and cons.

Indirect ads are the easiest to get into – just sign up with AdSense or one of the other ad networks, and watch the money come flowing in! Except apparently it’s not that much money. People were mentioning ad revenue figures on the order of a few cents per thousand impressions. ¹ 

Direct ad sales seem to fare better, since you can deal with clients who want to target specific demographics. In their Worlds in Motion session, the WarBook devs praised this model. But they also admitted to 700 million pageviews per month (across all of their games), and their access to players’ demographic info makes them very appealing to advertisers. A brand new project won’t be able to play in that league.

The other popular model is shareware – downloadable games with free trial versions, and full versions available for purchase. It’s a classic model (Doom and Quake come to mind), with the trial version typically limited in content (e.g. first level or chapter free) or game time (e.g. first hour free).

This model was the focus of much discussion, since it’s the primary model for the established players. It’s clear that it can do wonders for hit games, especially since the full game price is customarily set at $10 or $20. But standard games don’t fare as well. Only ~1% of players end up buying the full version, and even then, distributors take a significant chunk. Additionally, most downloadable games get their players from portals, which exhibit significant churn due to a large number of very similar games being created – so differentiation and getting to the top of listings are both difficult.

The other two models are subscriptions, and “free to play, pay for items.” The latter has worked very well for us, while the former works for others, including the 800-pound gorilla of MMOs. Both systems have a significant optimal case, however – they’re best for games where players are compelled to keep coming back to the game, over and over again. Fitting this against ”consumable” games is non-trivial.

So the dominant model is still content-limited shareware, but it’s not an optimal case: budgets can be brutal unless your game becomes a huge hit. But banking on blockbusters is a classic hit-driven studio funding scheme, with familiar drawbacks, only recapitulated on a smaller scale. A more stable model is something like subscriptions or virtual items, which scale nicely, but they require a larger, continuous kind of a game.

---

1. This roughly fits with announcements I’ve seen elsewhere, e.g. MSN Games offering developers 10% of ad revenue from the games they publish.

Viral Coefficient and Growth

The viral coefficient is a measure of how many new users are brought in by each existing user. It’s a quick and easy way to measure growth: if the coefficient is 1.0, the site grows linearly, and if it’s less than that, it will slow down. And if the coefficent is higher than 1.0, you have superlinear growth of a runaway hit.

In an invite-only situation (e.g. gmail closed beta), it’s easiest to calculate this directly, based on how many people are being invited by each new user, and how many of the invitees create new accounts themselves. The viral coefficient is simply:

v = new user invites accepted / new users
   = accepts_t / δp_t-1

where δp_t denote the number of new users who join in time slice t (ie, the increase in population between p_t-1 and p_t). 

But most sites have an open account creation policy. For those, we’ll have to estimate population acceleration from raw population deltas. Let’s assume that each accepted invite is quivalent to creating a new account at the next time slice. Then we can estimate virability as:

v ≈ δp_t / δp_t-1
   = (p_t – p_t-1) / (p_t-1 – p_t-2)

which is an acceleration metric, easy to compute from historical data. 
 

Population Forecasting 

Viral estimate calculated as momentary acceleration will fluctuate over time. But we can use it for some short term forecasting.

To calculate expected future population p_t some t steps in the future, given the viral coefficient and present population p₀, we first invert the above:

δp_t = v δp_t-1 = … = v^t δp₀

and plug this right back in:

p_t = δp_t + p_t-1
    = Σ_k≤t  δp_k + p₀
    = Σ_k≤t  v^k δp₀ + p₀

This describes a geometric series. When v ≠ 1, p_t  = δp₀ (1 – v^t+1) / (1 – v) + p₀ 

AIIDE starts tomorrow at Stanford. We have a very impressive array of speakers this year, and an intriguing collection of papers. Hope to see you there!