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

Some time ago I found a fascinating paper on the history of Erlang, written by one of its main creators:

http://www.cs.chalmers.se/Cs/Grundutb/Kurser/ppxt/HT2007/general/languages/armstrong-erlang_history.pdf

It showed up on programming.reddit for about a day, and then disappeared right back into the deep waters – which is too bad, because the paper is illuminating.

Erlang is a language with strong built-in support for concurrency based on message passing. As the author describes it:

Erlang was designed for writing concurrent programs that “run forever.” Erlang uses concurrent processes to structure the program. These processes have no shared memory and communicate by asynchronous message passing. Erlang processes are lightweight and belong to the language, not the operating system.

Reading the paper, I had several delightful “aha!” moments, where the details of Erlang design just clicked together. And I don’t mean the mundane issues, like single-assignment variables (hello, Prolog!), or interactively modifiable code (hello, Lisp!). Rather, the history put some architectural bits in perspective.

At a certain level, I always knew that Erlang was designed for programming telephone exchanges. But this paper really conveys the feel for what that means: huge collections of loosely coupled finite-state machines, all running in parallel, doing little bits of protocol validation here and there, but mostly staying dormant.

Typically, the software for call control is modeled using finite state machines that undergo state transitions in response to protocol messages. From the software point of view, the system behaves as a very large collection of parallel processes. At any point in time, most of the processes are waiting for an event caused by the reception of a message or the triggering of a timer. When an event occurs, the process does a small amount of computation, changes state, possibly sends messages to other processes and then waits for the next event. The amount of computation involved is very small.

Which definitely explains a number of their implementation choices which, without this motivation, look highly unusual. Let me highlight just three of them.

Continue Reading »

(Edit: Welcome reddit readers. The following is a howto on setting up an embedded Jetty server in Clojure, and writing a minimal servlet that serves up dynamic content.)

Last week I discovered a very nice language named Clojure. It’s based on Lisp, but hosted on the Java platform, and running inside the JVM. It has some lovely features, like native support for Java collections, and a clean API that ditches a lot of the old ANSI CL library cruft.

But the best part for me was language interop: Clojure can effortlessly load and use any external Java library. And there is a ton of good ones out there, including a rich set that comes with the Java platform. (This may seem like a minor point, but most free Lisps lack good libraries; only the non-free Allegro CL has really extensive, cross-platform ones.)

So I decided to take the language for a spin, especially exercising the language interop bit. For example, by building a little web server to serve up some dynamic content. You know, web development 101 kind of stuff. This turns out to be really easy to do.

Since Clojure is backed by Java, we can use an existing server library to do the heavy lifting for us. Several high-quality ones are available - I went with Jetty, a servlet-based engine that’s really easy to embed in custom applications. Using a servlet container will take care of all the mundane bookkeeping for us.

In the following posting, I’m reproducing the steps required to get a Clojure-based web server up and running, in much less than 100 lines of code. Hope you find it interesting!

Continue Reading »

Game logic often gets split into “time-sensitive” and “blocking” parts. When dealing with I/O-bound components, we often want to let them run separately from the main game loop. This way they won’t block the whole game as they’re waiting for their data.

The typical example is reading from disk, or accessing a database. Disk operations are orders of magnitude slower than operations on memory. If the data we need is already loaded and in memory, that’s great, we can use it immediately – but if it isn’t, we’ll have to load it first. And we wouldn’t want to put the whole game on hold, while we wait for the drive to seek to the appropriate sector on the disk.

The standard solution is to split the work into multiple threads: the fast main thread, which handles time-sensitive processing, and a worker thread (or a pool of threads), which will handle anything that could potentially block. But how to implement this?

Continue Reading »

Here are my steps for setting up SBCL (Steel Bank Common Lisp) and Slime (Emacs Lisp mode) to work under Windows Vista.

It’s mostly straightforward, except for dealing with spaces in path names. It turns out that slime.el uses the (split-string) function to pull apart the Lisp command line, which won’t work with the default “c:\program files\…” location. Here’s how to fix that, using symbolic links (yes, Windows supports them too!).

The following was tested on a Vista box, SBCL 1.0.13, and Slime 2.0 on Emacs 22.2.1.

Installing SBCL:

1. Download and install SBCL. By default, it will install to c:\Program Files\Steel Bank Common Lisp\1.0.13
2. Run cmd.exe as Administrator (required for symbolic links)
3. Set up a link from SBCL install directory, to some location without spaces. Note that the syntax is an inverse of the Unix ‘ln’ command.
   

   C:\Users\Rob\Documents>ver
   Microsoft Windows [Version 6.0.6000]

   C:\Users\Rob\Documents>mklink /d SBCL “c:\Program Files\Steel Bank Common Lisp\1.0.13″
   symbolic link created for SBCL <<===>> c:\Program Files\Steel Bank Common Lisp\1.0.13

   C:\Users\Rob\Documents>dir sbcl*
   …
   04/09/2008 09:07 PM <SYMLINKD> SBCL [c:\Program Files\Steel Bank Common Lisp\1.0.13]

Installing Emacs and Slime:

1. Download Emacs, unzip it to any location (eg. c:\Program Files\emacs). If desired, run the emacs\bin\addpm.exe program to add a link to the start menu.
2. Download Slime, and unzip it under your emacs/site-lisp directory.
3. Add the following to your ~/.emacs file:
   

   (setq inferior-lisp-program “c:/users/rob/documents/sbcl/sbcl.exe –core c:/users/rob/documents/sbcl/sbcl.core”)
   (require ’slime)
   (slime-setup) 

4. Restart Emacs, and then run M-x run-lisp to test whether Lisp starts up.
5. Start slime with M-x slime. Happy hacking!

Here’s what I’ve been working on all this time: Whirled is now in public beta!

Below is a live view into my room – stop by and say hello!

Launch the full version of Whirled