Article
i/2008/03/monkey1

Does This Mistake Make Your AI Look Smarter?

Dave Mark on March 25, 2008

This week’s developer discussion is based on a topic introduced by Dave Mark, the behavioral mathematics wizard behind Intrinsic Algorithm. Let him know if you find smart mistakes in his post by commenting below!

Monkey Thinking

Since I began writing this column for AiGameDev.com a month ago, Alex and I have occasionally spent an amusingly large amount of time deciding on the titles for the articles. People who have seen my writing before know that I am often inclined to tongue-in-cheek or intentional double-meaning in order to illustrate a point. This column’s title is one such example… and one that I won’t let Alex edit because the question that it asks is very illustrative of a disturbing quandary that AI programmers face.

You may recognize the loaded question that is being parodied by this title: “Does this [clothing] make my [body part] look [good/bad]?” It is a comedy staple due almost entirely to the reaction that it elicits from people (mostly men) as they decide how to split the difference on the equally-damning answers. Is honesty the best policy, however? If he lies to her, isn’t he helping her lie to himself? And if she decides that she does look ridiculous, is she going to hold it against him for not saying so in the first place? We truly feel for the poor sop as he opens his mouth knowing that, no matter how he decides to answer, he’s going to wish that he had chosen the other route (or none at all). And does she really want to hear the answer anyway?

The title question can be thought of in much the similar vein. Instinctively, we want to answer “no”. It’s intuitively wrong. A blatant contradiction contained in one eight word package. After all, since the inception of game AI, we have been trying to have our agents make better decisions, not worse ones. We have been trying to eliminate stupid behaviors, not encourage them. We have been striving for more realism, not less… but wait a minute… Isn’t this where we might be lying to ourselves? And do we really want to hear the answer if it means we have been wrong all along?

A Rational Definition of Rational

John von Neumann was the father of game theory and, in a broader sense, decision theory. Most AI programmers who are familiar with his minimax model also know that one of the requisite premises of applying it is perfect knowledge of the game environment. Given that, the minimax model is spectacular in calculating the best possible move at that moment. Even when faced with uncertainty (i.e. imperfect knowledge) surrounding the game space, there exists an entire arsenal from which we can draw. Bayesian math, for example, helps us to fill in the logical gaps that may occur when we don’t know the whole story. However, this is still one shortcoming that John von Neumann, his writing partner Oskar Morgenstern, and even the legendary game theorist John Nash all acknowledged. All this fancy math to predict decisions based on maximized return is based on the premise that the decision maker is rational — which, much to the dismay of many, is not always the case.

“All this fancy math to predict decisions based on maximized return is based on the premise that the decision maker is rational — which is not always the case.”

The issue that the above-named luminaries were concerned with came to the fore in a roundabout way. Their algorithm had to generate a decision based on what the same algorithm said the other side would do. That is, “if the other player makes his best decision, it will be X, to which I will respond with Y.” However, all of it fell on its face if the other party was not rational — and therefore could not be counted on to make the “best” decision. The point is, humans were not rational — or at least not perceptive and calculating enough to determine what that maximized solution to any given problem may be. (Rational, as used here, is almost a catch-all for omniscient, perfectly calculating, unemotional, and other such non-human traits.)

One common situation would be where the competing options are not significantly different enough from each other so that it is apparent that one is the “best”. A purely mathematical approach may be able to quickly calculate the intricacies and assign a score to the options from which a rank can be determined. For humans, however, this is not always an intuitive process. Let’s face it, there are entire self-help books dedicated to teaching people how to construct a simple “pro/con list” — and that doesn’t even get into the subjectivity that may be involved with assigning values to items on the list. Purely rational — i.e. algorithmic — decision making is just not something we excel at. Often, we have to “go with our gut” — which, if not perfect, may at least lead to a reasonable decision.

But that’s not how we program our AI, is it? As I mentioned above, in modeling our decisions, we have constantly been focused on finding the best that we can accomplish. The A* algorithm finds the best path. We take great comfort in the fact that A* even guarantees that it will find that best path or our money back. We can roll up the n-depth tree search with thousands of leaf nodes into a handful of individually scored decisions, pick the highest ranked one from the pile, and feel quite comfortable that we have selected the “best” possible path. In fact, if our AI is criticized for being not human, we instinctively look for ways to make our best decisions even better! All of this is based on that the same fallacious ideal that haunted John von Neumann — “Humans are always rational; Humans always make the best available decision.”

What is Better Than the Best?

If their algorithms were to accurately model human behavior, the fathers of decision theory had to eventually accept, account for, and try to model the very fact that humans do not always act rationally. This was a daunting task that has only recently been addressed by delving into the realm of psychology. Thankfully, this field is well beyond the scope of this article. (Although I do recommend “A Beautiful Math” for light reading on the subject.) One advantage that we have over von Neumann and Nash, however, is that they were trying to accurately predict human behavior whereas we are only trying to model a sample of it.

Even with that disclaimer in force, the spectre of the imperfection of perfection still looms over us. If the optimal decision isn’t the best one, then what is? Certainly the collection of “good” decisions will tend more towards that optimal one than they will towards a purely random one. Constructing the stochastic equivalent of a blindfolded dart-throw isn’t going to be the answer. In the situation where there are multiple, similarly scored alternatives, picking amongst them could generate a unique collection of behaviors that isn’t precisely deterministic. No matter how we select things, we would want to limit the choices to ones that that are, if not the optimal ones, at least somewhat reasonable. Anything blatantly stupid only makes us just look bad. No amount of explanation of how “we were modeling a form of stress-induced psychosis” will rescue us at that point. Therefore, our “mistakes” (I’m beginning to prefer “inconsistencies” just to avoid the stigma) must be on an order of degrees rather than magnitudes.

Spock Playing Chess

“Your illogical approach to chess does have its advantages on occasion, Captain.”
— Mr. Spock to Captain Kirk in “Charlie X”

So, the Question is…

Again, a proper treatment of this subject would go well beyond the caffeine supply I have in the house tonight — and strays somewhat from the purpose of the column. The quandary that I want to pose here is not a technical one - that is how we could make our agents less than optimal. What I want to ask is more subjective (and therefore bound to be delightfully contriversial). Should we allow (or force) our agents to occasionally not do their best… to sometimes not select the best weapon… to once in a while not dash for the perfect cover… to typically not make impossibly swift analysis and decisions (see last week’s column)… should we allow our agents to make mistakes - and thereby look human? In fact, if our agents ever are going to look more human, don’t they almost have to make mistakes?

Can we seriously walk into a room and ask our designers, producers, publishers, reviewers, and ultimately our players, the loaded question: “Does this mistake make my AI look smarter?” Or maybe it is just better not to tell them that our agents aren’t “perfect”. That we actually designed them to be that way. It may be safer than asking the question. I know that I cringe at the thought of the answer.

One thing is for sure… if we get it wrong, they are not likely to be delicate about their answer. (And do we really want to hear the answer anyway?)

Discussion 10 Comments

Andrew on March 26th, 2008

To be absolutely honest, after you've played against most AI opponents for a matter of a few hours in a game, the flaws do not make it look better - the AI isn't at a level where it is competent enough to [i]make mistakes[/i], which is where the question falls down :) But given a competent AI - of course, mistakes should happen. It could be scripted in any linear game - the AI discussing something, or kicking in the wrong door, or shooting the gas cylinder in the room...things like that add character (and depending on the opponents, could be a core part of silly gameplay). However, there are some that strive for AI which can make mistakes. Might I bring up any Thief game? The entire sensory system is based around the AI not having perfect knowledge. Garret the master thief can hide and hold his breath inches away from the guards, and they can walk on by. They might make mistakes when investigating, or even attacking, allowing Garret to get away scott free. Respawning enemies, such as in Unreal Tournament, while usually not programmed for mistakes, can have them added - I am pretty sure UT2004 has imperfect jumping at most difficulties, which means sometimes it misses a jump, or lands in the wrong place, just like a player would who was running around jumping all the time. You notice it because you play 10+ minute matches with them (or even them as your allies) so it's easy to see. Commanders of armies also can make mistakes. Generally, it's more difficult to program, but I've seen the Total War games do the historical scenarios quite well - falling into the right traps (or not!) making the mistakes (or not!) it becomes less predictable, much more enjoyable, since you can usually see most of the enemy and plan accordingly, and he can do the same against you. This allows back and forth "mistakes". Not many games allow the mistakes mentioned above however - basically; the AI is dumb because it only lives for a minute, or less. How can you make a mistake and get away with it in that amount of time? You simply can't - anything that acts like a mistake (even a blatant one) is usually perceived as simply "dumb" or "a bug". This is rather sad, but not much can be done about it, except if the mechanics of the games were changed. This applies to most of the games having not competent AI - if it were competent, it'd kill the player too often! So, some mistakes? Excellent idea to do, but only if the NPC's are alive for more then a minute. Adds character, and randomness which humans have. For those less then a minute however, most of the time it'd be called buggy, and the AI is imperfect or incomplete for those scenarios anyway (ie; if you keep them alive for more then a minute, they'll do the same thing over...and over...and over...and ...over...). Hope that made sense :D

vimes on March 26th, 2008

It definitely makes sense to me :) I've been trying to formulate something along the line of this article for a while and thanks to it, I've managed to organize my thoughts better Well, everything began when I witnessed a weird event in the first Call of Duty : I had attacked a bunker and thought I had killed everybody with the grenade I had thrown in. I was confidently approaching the entrance when a single soldier suddenly jumped out screaming from the shadows inside the bunker and fired at me his last rounds. I got surprised, pulled the trigger and killed him.It lasted less than a second but was a shocking experience : this gave the opponent a human face, casting a different light on a game in which, to this point, only allies seemed capable of human emotions. This reaction was human, however, I wouldn't say it was irrational, and that's were I depart a little from the article and strongly agree with Andrew's comment. What the situation felt like was that the soldier had made a rational decision (i.e. that you could explain logically) based on his knowledge of the situation and its 'internal' (psychological) state. I'm sure this was not how CoD AI works, but the model stands : as Andrew said, the 'misconduct' appeared because the knowledge was partial but even more so, it was analyzed against a filter linked to a certain state of the agent : in another situation, the same knowledge would have been analyzed differently. In the end, the agent still took the best decision but not objectively, subjectively. So, for mistake to have impact on the player experience, the game need to convey the reasons that lead the AI to the decision : in my case, I noticed afterwards that the guy was the sole survivor a massacre, that he had a few bullets left so his decision made sense. From this, I think Andrew's point about short-living AI can be generalized. The psychological states that 'filters' the knowledge should only be modified in ways that fits the character : cannon fodder can go from 'reasonable' to 'freaked-out' because they just saw one of their comrades die, but an elite-super-trooper or a mindless peon of a multitude shouldn't. In any case the 'failability' of AI driven characters seems an underrated mechanisms to me : it gives depth to nameless characters, brings more credibility to the world, enables to the player to study and exploit these shortcomings - feel intelligent afterwards - and be even more amazed when really smart reactions are displayed.

Vicente on March 26th, 2008

While talking with friends, I find that usually gamers don't value in the same way a mistake from a person and a mistake from a computer. For example, in FPS games, it's desirable for the AI players to miss shots (in a believable way) because if the AI always scores a head-shot it becomes frustrating. But if you find a human player that always scores a head-shot, although you find it frustrating, it's more a feeling of "oh my god, that guy is leet" rather than "the dammed computer is cheating on me". But problems in movement (wrong navigation, missed jumps,...) mostly always look silly on AI players, while we are quite forgiving when another human does them. Or that I have found when talking with people that aren't programmers (just gamers). Regards!

zoombapup on March 26th, 2008

I think there is something valuable in this question. I do think that a lot of this will come down to the psychology of players and the internal psychology of the AI's to some extent. What we dont want to see are situationally "dumb" mistakes, like pathing into a wall, or jumping of a ledge thats too high and getting killed, or simply not reacting to a threat thats stood next to you. Once you have these "basics" covered, then I think we're into the realm of creating believable and interesting behavior, which is where the real meat of AI lies and is where its fun for me. Clearly some sort of simplistic internal pyschology would be a useful starting point as its that which drives most human decisions, so modelling it in some way seems natural. So maybe one thing we have to do as AI programmers, is study psychology to learn the two sides: [LIST] [*]How the player percieves the play of the AI [*]How the AI percieves itself and its world view [/LIST] Of course we're getting into the realms of human thought, which is probably quite complex, but even a simplistic model must be able to offer us something useful. I suppose its a lot like the old sims "needs/desires" thing. A set of variables which can be satisfied by actions. They act as an ultra simplistic set of samples that can control a motivational model (sample A is too low, go satisfy that need kind of thing). I wonder what kind of motivations would be useful across a variety of game types.

Dave Mark on March 26th, 2008

Thanks, as always, for making the weekly Developer Discussion column into a discussion, folks. As I alluded to the in the article, the mistakes that our agents make would have to be very subtle. In fact, many of them might not be recognizable except as levels of depth. If 3 competing options for a decision score within a few percentage points of each other, is it really a "mistake" to select the 2nd or 3rd rather than the first? However, our algorithms are generally constructed to take the highest ranked one regardless of its margin of victory. To the player, however, the effect is that it reduces the monotonous predictability - "When in situation A with parameters B and C, the AI will always do X." That sort of determinism isn't something you get out of 100 humans (or 1 human 100 consecutive times). If we were to use obvious mistakes, however, there ARE ways that we can "sell them" to our players to show that they are NOT bugs or errors. For example, if an AI agent decides to run for cover, (spinning off of last week's example), it may select a poor cover, get most of the way there and - with frantic animations to support it - say "Damn! That won't work!" and look around for another place to go. How about selecting a less-than-optimal spell to cast? Or weapon to use? The AI can make a comment about how it was the wrong choice. If it lives long enough (good point Andrew) it can perhaps back up to discard the weapon and select another. There are plenty of ways to make our mistakes look intentional (doesn't that just sound odd?). The question is only if we are willing to use those mistakes to create the "humanness" that our AI needs.

Andrew on March 26th, 2008

Those kind of rare occurrences would work excellently for non-combat AI. For instance, if The Sims had characters making mistakes (I've no idea if they do) then you can see over time perhaps learning from the mistakes (ie; cross that off the list of things you can do wrong now). And for reinforced learning, Black and Whites non-combat AI which did mistakes, lots of them, until being told not to do something (and I don't mean eating villagers, which depends on your morality, it can try and eat rocks until you tell it not to!). Works excellently for these models (and the Thief example) due to not having time constraints which combat commonly does. Notably, the example of cover - those NPC's which need cover to survive? The PC would likely kill them before they saw the NPC made a mistake about going to the wrong piece of cover, since it'd be an obvious target - the only way the poor guy would survive is with more health (and thus longer life) or if the player was, say, reloading but looking out from their cover. It's hard to justify the work if it's unseen of course, so in combat, it is possibly the most difficult time to make them more human (unless their your invincible allies or something). As noted; board game AI (or for most computer games, tactical turn based or RTS AI) can have it work with personalities - the mistakes might be intentional (or, in the AI's eyes, none existent).

Vicente on March 27th, 2008

If different AI guys repeats those mistakes "enough times" they will end looking silly even if they try to justify them (specially coming from different entities). And I fear that for a player "enough times" is a really low number (but I don't have anything solid to back up this claim :( ). Also, players tend to make mistakes in different ways, it would help if each AI entity made mistakes in each own ways (giving them personalities as Andrew says). I think it gives more feeling of "real intelligence" having 2 different entities doing 2 different mistakes about the same thing rather than doing the same one. I have just remembered a sentence from a friend game developer from Spain: "in case your AI is not very clever, make the enemies zombies, player won't matter much if they do dumb things, zombies are supposed to be dumb :p". It's fun how changing the visual appearance of the enemy can make the player think differently about how the enemy should react and work (I bet that if F.E.A.R. enemies were zombies they would have seemed too clever). Regards!

zoombapup on March 27th, 2008

On a bit of a tangent, but arent zombies getting a lot faster/smarter these days? Erm, anyway, back on topic. I think there is a good deal of research that needs to be done on player perceptions of AI agents before we can really say what works and what doesnt. Only, you would need to have: An AI expert A psychology expert To do that kind of research. Not sure I know anywhere that has the two together. This is the kind of work that would quite likely help improve the AI development process though. Maybe I'll propose it as an MSc project.

Paolo Maninetti on March 27th, 2008

Just want to give my contribution to the discussion from a bike racer point of view. In this case mistakes are often part of the design. They can easily be one element that characterize a given pilot. The challenge here is more about giving enough control to designers and making them the more realistic than possible. Think there are mainly two different approaches: the first is building an AI enough competent to drive but who may fails. The second is building a perfect AI (maybe cheating a bit) and forcing errors on it. In the first case we'll probably have more realistic mistakes but few control, while in the second case exactly the opposite ...

diegix on March 29th, 2008

The way I see it is that those mistakes are nothing but another feature to add to the character. In the same way as we try to add variety to character by having different animations for the same action, or a whole bunch of different attacks even though there is one that is the more effective and if we want the AI to be optimal it will use always this one. In essence I think that when you are programming an AI a mistake is not a mistake per se, it's just something you consciously put into the system as another behavior to choose from. Any type of variety that we can add to a character will increase its believability. I think we are far away from getting perfect characters in games. I think we will continue adding "mistakes" in the sense of non optimal attacks because it is required for gameplay, but the extra time we have is probably better used in solving all the "programming mistakes" to get flawless characters.

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!