AIIDE 2009 - AI Challenges in Sims 3 - Richard Evans
This is the rough dump of my notes from Richard Evans' AIIDE 2009 invited talk on the AI challenges they faced in developing The Sims 3. Some of it was familiar to me as being exactly what he presented as part of our joint lecture at the GDC AI Summit in 2009. Other portions of it were new.
Specifically, I enjoyed seeing more about how they handled some of the LOD options. For example, rather than parsing all the available actions, a sim would decide what lot to go to, then what sim to interact with, and then how to interact. Therefore, the branching factor was significantly more manageable.
Another way they dealt with LOD was in the non-played Sims. Rather than modeling exactly what they were doing when (while off-screen), they made some general assumptions about their need for food, rest, taking a leak, etc. These were modeled as "auto-satisfy" functions. For example, if you met a sim close to dinner time, he would likely be hungry. If you met him a little later, he would present as being full.
Additionally, as you will see below, the entire town had underlying simulation mechanics that balanced how many people were dying and being born, what gender they were (on average), and even where they were moving to and from. They modeled much of this with a very simple geometric interface early on so that they could test their mathematical models. Same with the simple behaviors. He showed video demos of these models in action. This also allowed them to speed up time to ridiculous levels and let the sim run overnight to test for situations that would tip the sim out of balance. Lots of fun!
He also mentioned about how the behavior selection was done. This was important to me in that he showed how they used some of the same techniques that I talk about in my book. Specifically, he uses a utility-based method and selects from the behaviors using weighted randoms of the top n selections. Excellent work, sir!
The following are my raw notes.
AI Challenges in Sims 3
Richard Evans
He mentioned the website dedicated to Alice and Kev. The author simply sat back and watched the Sims do their autonomous behavior and wrote about it.
1. Hierarchical Planning
2. Commodity-Interaction Maps
3. Auto-satisfy curves
4. Story progression
Instead of nesting decisions about which act to perform on which person in which lot, you chose a lot first, then chose a person, then chose an action.
O(P + Q + N) instead of O(P * Q * N)
Data-driven approach so that the venues populate appropriately (e.g. restaurants)
Optimization
If you are full, don’t even consider eating as a possible selection of what to do.
Auto-satisfy curves for LOD. That way you don’t have to simulate the off-screen Sims. Assume that they have eaten at the right times, etc.
Other Sims need to progress through life the same way that your Sim does. Age, marriage, children, career, move, etc. Long-term life-actions are simulated at LOD.
The town has various meta-level desires. (Gender balance so that we don’t have all male or all female.) (Employment rate for the entire town. Some people will be unemployed… peaks at ~80-90%
High-level prototype showing the major life actions (not smaller actions). Simulating the town without simulating the people.
Making Sims looking after themselves
Utility modeling
Highest-scoring
Randomly from the n highest-scoring actions
Randomly using the score distribution as the probably distribution (weighted randoms)
Personality and Traits and Motives
Same that he talked about at AI Summit
Traits -> Actions = massively data-driven system to minimize hard-coded systems.
Kant’s categorical imperatives?!?
Emily Short: "The conversation is an end in itself."
Take Home Actionable items
Data-drive everything!
Take the teime to make good in-game viz. tools
Prove out all simulation ideas using prototypes as soon as possible.
Richard shows excellent 2-D prototype that runs sims without the realistic world!
About a month ago, I was invited to sit down with Adam Templeton of Silicon Prairie News. He wanted to talk to me about Intrinsic Algorithm, my book, the state of game AI, and - more relevant to the purpose of their site - the Omaha Game Developers Association. We had a great chat for about an hour in the library on the campus of the University of Nebraska at Omaha. What resulted was a 20-minute video interview.
I was very pleased to have spoken to SPN about not only my work, but about the possibility of a professional game development community here in Nebraska.
My thanks to Adam for an excellent interview and a pleasant afternoon.
Back on April 5th, Alex Champandard of AIGameDev interviewed me for about 90 minutes for the Members portion of his site. Our topic was how to use behavioral mathematics (such as I cover in my book) to improve the bots in Left 4 Dead. We cover a lot of interesting information in the interview. Some of the examples refer to things I covered in my Post-Play'em columns on the AI in the game.
He has it posted in audio and video formats (although with me rocking back and forth in my office chair, I look like I'm autistic!). I seriously advise that you check it out. (You will need to have access to the members area to view it.) If you are already a member of AIGameDev, you can find the interview here:
In the first chapter of my book, "Behavioral Mathematics for Game AI," I actually use Poker as a sort of "jumping off point" for a discussion on why decision-making in AI is an important part of the game design. I compare it to games such as Tic-Tac-Toe where the only decision is "if you want to not lose, move here," Rock-Paper-Scissors where (for most people) the decision is essentially random, and Blackjack where your opponent (the dealer) has specific rules that he has to play by (i.e. < 17 hit, > 17 stand).
Poker, on the other hand (<- that's a joke), is interesting because your intelligent decisions have to incorporate the simple fact that the other player(s) is making intelligent decisions as well. It's not enough to look at your own hand and your own odds and make a decision from that. You have to take into account what the other player is doing and attempt to ferret out what he might be thinking. Conversely, your opponent must have the same perceptions of you and what it is you might be thinking and, therefore, holding in your hand.
Thankfully, there is no "perfect solution" that a Poker player can follow due to the imperfect information. However, in other games, there are "best options" that can be selected. If our agents always select the best options, not only do we run the risk of making them too difficult ("Boom! Head shot!) but they also all tend to look exactly the same. After all, put 100 people in the exact same complex situation and there will be plenty of different reactions. In fact, very few of them will choose what might be "the best" option. (I cover this extensively in Chapter 6 of my book, "Rational vs. Irrational Behavior."
Our computerized AI algorithms, however, excel greatly at determining "the best" something. Whether it be an angle for a snooker shot (the author's other example), a head shot, or the "shortest path" as determined by A*. After all, that is A*'s selling point... "it is guaranteed to return the shortest path if one exists." Congratulations... you inhumanly perfect. Therefore, as the author points out in his article, generating intelligent-looking mistakes is a necessary challenge. Thankfully, in later chapters of "Behavioral Mathematics..." I propose a number of solutions to this problem that can be easily implemented.
Anyway, I find it an interesting quandary that we have to approach behavior from both sides. That is, how do we make our AI more intelligent... and, how do we make our AI less accurate? Kind of an odd position to be in, isn't it?
It's sometimes interesting the places you can find nuggets that can be applied to game development. The Wall Street Journal has a regular column called "The Numbers Guy". I have often been interested or amused at what appears there. After all, having just finished a book entitled, "Behavioral Mathematics for Game AI", I am obviously sort of a "numbers guy" myself.
Anyway, today's column was titled Scrabble and Other Games -- on Boards, Fields, Courts and Ice -- Have Overvalued Points; Vermont Avenue Is a Steal. For the most part, the author is talking about how, with the addition of more words containing z, x, and q to the Scrabble Dictionary, it has thrown the carefully crafted point balance out of whack. Anyone who has played Scrabble has noticed that there are more of the common letters (e, a...) and only one each of the rare letters. Additionally, the point values are significantly higher for them to reward you for the difficulty in finding words to use them in. However, there are now more of those ostensibly rare words than were originally used... making it easier to use those letters... thereby making it easier to seriously cash in on those high value tiles. The contention by some players is that it has thrown the balance of the game off.
Or has it?
There are others that have pointed out that anyone can use those new words. Therefore, the balance isn't off at all. My follow-up comment would be that the scale of the scoring is different. When I played fairly high-level Scrabble for a while a number of years ago, a good round of 1-on-1 would be up in the 400s. We were using those words such as xi and suq and qat. After all, they are in the Scrabble Dictionary so why not? Now, if we had not been using those words and simply been using... well... simple words. Netting those 400+ points would have been marginally more difficult. The rounds may have been in the 350+ range instead. For both players.
However, this is when we view games as an aggregate. In a single game, reaching into the bag and pulling out the only letter x or the only letter z is, for all intents and purposes, a random event. If you pull out one of those singletons, by definition your opponent cannot. Therefore, the simple (random) act of pulling out a high-value letter gives you a significant advantage.
And that's the rub... novice players who don't know those letters look at the z and q and x as a handicap. ("What am I going to do with this damn thing?!?") Experienced people who fall asleep with the Scrabble Dictionary look at those letters as a fortuitous occurrence... and possibly a clinching one as well. The response is going to be more along the lines of "Ha! I got it and he didn't!"
So... while one could make the claim that it is only the scale of the scores that has increased, the actual result is that it has put more weight on the random factor of what is otherwise not supposed to be a random-centric game. And that I do have a problem with.
Football and Basketball
In other parts of the article, he mentions how other scores and probabilities have change. Football field goals. Basketball 3-point shots, etc. Looking at the latter, if you typically hit 50% on 2-point shots, then all you need to do is hit 33%+ on 3-point shots to make the decision to always go for them. After all, making 1 in 3 3-pointers is the same as 1 in 2 2-point shots. His comment was that, in college basketball especially where the 3-point range was shorter, many players could do that.
This is an interesting item to note as a game developer. If you were designing a game and deciding how far back to place the 3-point arc, you would specifically want to look at those very statistics. That is, at what distance does the probability of success merit increasing the payoff? If it is too close, most people will shoot from beyond it and it will take away the inside game. If it is too far away, no one will bother and will, instead, try to get as close as possible. It's a delicate balance.
Never Mind Boardwalk...
Another quick mention in the article is Monopoly. This one amused me. Back in about 1993, I whipped up a monster spreadsheet that determined that the best bet for buying and building was the light blue properties... the 2nd set on the 1st leg. This article confirmed that some dude did the same math and determined the same thing. Big deal. The difference was, I based mine on the probabilities of landing on various squares, various monopolies, etc., the cost to buy, the cost to build, and the income that you would receive. Apparently this other guy used a Monte Carlo method (32 billion random rolls) to come up with his answer. Wimp. Anyone can run a Monte Carlo simulation and get the right answer. However, you learn a lot more about the "why" of the situation by looking at the relationships of the various components. This is a form of multi-attribute utility theory that I cover extensively in my book.
Anyway, many of us think of game balance in the realm of RTS, TBS, or RPG games. However, even games where every unit is the same (e.g. checkers) can be an excercise in mathematical balancing. How much weight do I put on a given option? How important is it? Especially compared to other types of factors that might not be easily relatable? Again, this is something that I address in great detail in my book. It has always been something that is of interest to me and, thankfully, I seem to have a knack for it.
Go buy the book and you can have a knack for it too! :-)
Well, I guess my book has finally arrived on Amazon's loading dock. They have managed to scan it so that it shows the "look inside" logo and stuff. So those of you who would like to peruse the table of contents, the index and the first 5 or 6 pages may do so. Of course, if you really want to have some fun, you can do the whole "surprise me" bit. Keep at it long enough and you could read the entire book... although it might not make quite as much sense all jumbled up like that!
I also like that you can now see the cover art much better. (I did the cover artwork myself.) Incidentally, the faces on the blocks are, from left to right, Blaise Pascal, John von Neumann, and Jeremy Bentham... all of whom are referenced in the book. A big thanks goes out to my colleague, Richard Evans, for his review blurb that appears on the front cover as well. On the back cover is a blurb by Alex Champandard of AIGameDev.com who was nice enough to provide a review as well.
All in all, I'm quite pleased with how the sales have been going. I've been averaging anywhere between 5th and 15th on the "Hot New Releases of Game Programming" list and have actually been in the top 5 a few times in the past 6 weeks. I've also made it as high as #2 in game programming books overall -- although most of the time I'm in the middle of that very large pack. (e.g. 34th right now)
I'm looking forward to meeting many of you at the Charles River Media booth at GDC next week. (Remember, I charge 25 cents for autographs!)
Alex Champandard over at AIGameDev.com posted a preview of my book last night. He had been waiting for Amazon to get the cover displayed before he did so. Well, AIGameDev has about 3600+ subscribers so it is understandable that a write-up would affect my Amazon sales rank. However, I was not expecting this when I woke up this morning!
As of this hour (9:30AM CST), I jumped up to 16,384 in the overall books category. When you figure that my previous high was 74,604 (after Alex posted a small blurb in his weekly link digest) and that most of my time is spent between 200,000 and 600,000, being around 16k doesn't suck at all!
More importantly, I jumped up to #14 in Game Programming. I had only appeared on that list (100 books) 4 times in the past 2 weeks, no higher than 57th, and usually only for a few hours. Maybe this time I have some staying power.
I am also #2 in the "Hot New Releases of Game Programming. I had been #3 or 4 a few times, but this is a pretty fluid list. Again, however, it will be nice to see how high this climbs.
I figure the next few days should look pretty good as Alex's post is only about 12 hours old. And it probably takes a while for 3600 people to get around to their RSS feeds. Either way, I want to thank Alex for his support and the shout-out on the book.
Well, the cover for my book "Behavioral Mathematics for Game AI" is finally uploaded to Amazon (and I assume other retailers as well). It was odd having that mysterious question mark there for so long. But I suppose when the book is on sale before you have even finished writing it, that's the price you pay. Anyway, it's nice to have it show up properly on the page, the best-sellers lists, and the Amazon ads.
Speaking of rankings lists, I have been floating anywhere between 3 and 20 on the "Hot new releases in 'Game Programming'" list. I've even made a few appearances on the top 100 Game Programming books in the past few weeks. Once, I was as high as 57. It doesn't last long, however. They update those sales figures and rankings every hour so it is very susceptible to fluctuation. I figure that I will do a little better now that I have a pretty cover picture on the sites. (I guess people would be skeptical of a book with no cover.)
For those of you who bounce out to the site, the book description and the bio are still not updated exactly as they are supposed to be. From what I understand, they will changed in the next week or so. They have been pushed out the Amazon, but it takes a while for those sorts of changes to updated. *shrug*
I do want to give a shout out to my colleague, Brian Schwab, who just released his second edition to AI Game Engine Programming in the past few months. I'm looking forward to picking that up soon. He deserves props for being the only new AI book ahead of me (for now!).
Anyway, I need to finish getting the downloads section ready for the book. There will be all sorts of nifty stuff in there. I hope you all find it valuable!
Some of you have asked me questions about my new book, "Behavioral Mathematics for Game AI." The information that is on amazon and other retailers is not up to date. For one, there is no cover picture. There's a good reason for that. The cover is still being laid out and will be uploaded to the resellers soon. In the mean time, here's the cover art that I developed (click for a nicely detailed larger version).
The description text that you see on the resellers' sites is based on what I originally submitted to my publisher when I began the writing process. Things have changed a little bit since then. The following is likely what we are putting on the back of the book and will eventually be updated on Amazon, etc.
Human behavior is never an exact science. As a result, the design and programming of artificial intelligence that seeks to replicate human behavior is already an uphill battle. Usually, the answers can not be found in sterile algorithms that are often the focus of artificial intelligence programming. However, by analyzing why people humans (and other sentient beings) behave the way we do, we can break the process down into increasingly smaller components. We can model many of those individual components in the language of logic and mathematics and then reassemble them into larger, more involved decision-making processes.
Drawing from classical game theory, this book covers both the psychological underpinnings of human decisions and the mathematical modeling techniques that AI designers and programmers can use to replicate them. With examples from both "real life" and game situations, the author explores topics such as the fallacy of "rational behavior," utility, and the inconsistencies and contradictions that human behavior often exhibits. Readers are shown various ways of using statistics, formulas, and algorithms to create believable simulations and to model these dynamic, realistic, and interesting behaviors in video games.
Additionally, the book introduces a number of tools that the reader can use in conjunction with standard AI algorithms to make it easier to utilize the mathematical models. Lastly, the programming examples and mathematical models shown in the book are downloadable, allowing the reader to explore the possibilities in their own creations.
If you have any other questions about the book, feel free to ask! (And yes, it should be available at the Charles River Media booth at the Game Developers Conference next month. I'll be there quite a bit... flag me down!)
For those of you that have been wondering why this blog has been a little quiet in the past 6 months or why I haven't progressed on Airline Traffic Manager, I present to you my excuse...
My new book, Behavioral Mathematics for Game AI, is now available for pre-order on Amazon.com (and dozens of other resellers). Some of the details on the site are incorrect since the book is being finished up. As my publisher (Charles River Media/Cengage/Course PTR) updates their information (including art for a cover that we haven't even designed yet), the information at the resellers will be updated as well.
As it is scheduled now, the book will be available in mid-March. Thankfully, that means that it will also be on the shelf in time for GDC. Considering my role in the inaugural AI Summit, that will make for an exciting week for me.
Rather than the typical AI book which deals with the architecture of state machines and pathfinding, for example, I focus on behavioral AI. That is, what goes into a decision and how can we make those decisions more believable?
I begin by covering a lot of classical game and decision theory and explain how we can relate those examples into the video game world. I cover utility theory and marginal utility, how it manifests in the real world and how we can represent it in our AI agents. There's a healthy dose of technical material as well. There are chapters on constructing mathematical formulas and algorithms to help replicate behavioral patterns. Lastly, I offer solutions to prevent some of the problems that hamstring our AI agents. Throughout all of the book, I tried to make it an easy and even fun read. How often have you read a technical book that would keep you awake chuckling rather than put you to sleep with a headache? After all, we do program games, right?
All in all, it has been an enjoyable project that forced me to re-analyze things that we all often take for granted as AI programmers. I hope that you enjoy it as well.
. I had only appeared on that list (100 books) 4 times in the past 2 weeks, no higher than 57th, and usually only for a few hours. Maybe this time I have some staying power.
in the past few months. I'm looking forward to picking that up soon. He deserves props for being the only new AI book ahead of me (for now!).
, is now available for pre-order on Amazon.com (and dozens of other resellers). Some of the details on the site are incorrect since the book is being finished up. As my publisher (Charles River Media/Cengage/Course PTR) updates their information (including art for a cover that we haven't even designed yet), the information at the resellers will be updated as well.
