A House Built on Sand: Engineering Stable and Reliable AI

[Music] let's get the shame out of the way early everybody think of an example of bad a.i you got it okay i think a lot of you are thinking of something like this and the first thing i'd like to convince you of during this talk is that this is not bad ai i mean it's not good but what we're really looking at here is a failure of production of management resourcing because here's the thing if your ai isn't very good you know what you can do you can hide it put these guys on rails because of that bug put disabled grenades in that room stuff like that actual bad ai in a competently developed game doesn't usually directly impact the player experience what it impacts is the overall game quality by sapping the efficiency of everyone else you end up with more pressure on the iterative qa process your level designers spend more time working around quirks in the pathfinder

and less time working on tweaking for balance and fun you spend less time well you spend more time then you eventually end up dialing down your ambitions for like say tactical ai you might cut down some emergent tactics and just move towards something more like on rails shootouts the most sinister thing about bad ai real bad ai is that it doesn't look like bad ai it just looks disappointing it looks like something less than it could have been it looks like the team didn't try hard enough so what i'd like to do with this talk is help you think about ai development in a way that leads to solid and dependable systems this is not going to be an exciting talk because it's not about being creative it's about supporting and enabling creativity it's about building something you can build on the first topic i'll touch on is

layering and the closely related talk topic of interface design now rodney brooks described this idea of a subsumption architecture a bottom approach a bottom-up approach to ai where high-level competencies depend on lower-level skills and we do this in ai without really thinking about it in regards search behavior you'll have something like run to the last place you saw the player but that behavior depends on a lower level locomotion system which might defend on an even lower level pathfinder and what you'll notice when you look at these layers of course is that the creative aspect of ai the content what makes this guard different from that villager is all up in the top layer and as you go down the layers become generic they're services not content and what you want is for the lower levels to be rock solid and boring so you can ignore them and concentrate on the content which is where your game really is well that's the ideal anyway and i think it's useful to look at what happens when layering starts to rot

and there's two ways this can happen and the really bad one is this first one when your creativity and your content starts to leak down into your services the prime symptom of downwards leakage is when your service interface suddenly gets more semantically specific more use case specific when it starts thinking about things that it shouldn't need to think about here's an example you're making a game whose levels include some farms and there's some feral chickens wandering around just you know randomly picking gold points around them and the problem is the chickens keep wandering away from the farm over time because they're just picking random points but you want to keep the chickens tightly clustered there for set dressing so you take your pathfinding system and you add an option to the find path query called is chicken and then your pathfinder if is chicken is set doesn't allow paths that go say more than 20 meters from the nearest farm so now your pathfinder has this concept of a chicken if you want to do

similar things for other characters you'll have to edit the pathfinder again and add more options that 20 meter limit i mentioned is not with the rest of the chicken's behavior it's somewhere deep down in the pathfinding code what it means to be a chicken is no longer local and what it means to find a path has now become more complicated and confusing since previously you are worried about nodes and edges and now you're still worried about nodes and edges and also farms and chickens now that example is trivial to the point of being manifestly unfair i think most of us would would have done it a different way by having the pathfinder say take a call back which filters which faces are allowed or not then the filter for chickens would apply those same limits i talked about but the code for that would be part of the chicken system it would be part of the chicken codebase the pathfinding system sticks to what it's good at finding paths and the extension to its interface just adding this generic filter interface makes a lot of sense but now we have the opposite problem because a piece of code that was

previously concerned with pecking and clocking is now also calculating the distance between points and nav mesh faces it's scanning through the game level to try to find all the farms all this knowledge of the underlying structure is going into the chicken's mind so now say if you want to change how navmesh faces are stored now you need to edit how chickens work so this is the opposite problem with upwards layer leakage because the service refused to give the content what it needed and now service-like code is going into the content this happens when you have a layered system both layers start saying not my job it's not the pathfinder's job to care about chickens and it's certainly not the chicken's job to care about navmesh geometry what you generally end up if you're doing your job correctly is a set of utilities built around the lower level which offer slightly higher level services to the upper level so if you see this sort of pattern where you've got two layers and you can't decide where to put a

piece of functionality consider whether you need a third layer mapping gameplay concepts to mechanical queries is a type of functionality it's a kind of code itself it deserves to go somewhere it deserves to be recognized as a separate system the other thing to notice about these examples is that the risks differ depending on who's programming what if it's the same programmer in charge of both layers doing both say pathfinding and behaviors you're a particular risk for things leaking through the layers because why not he's an expert in both whereas if it's different people in different layers there's more likely to be separation but it's also more likely that that separation will be in the wrong place because it's more difficult for the two programmers to work together to refactor the layer design so let's change gears a bit you get a bug report where during a cutscene in the middle of the scene a goblin runs in and starts

hitting one of the characters with a stick which rather detracts from the drama of the moment now the background characters the goblins need to keep doing goblin stuff so you can't just turn off their ai during the scene so you try various things various approaches and eventually you find a solution you happen to already have a utility which checks whether a character is playing a scripted animation sequence which is a thing in your animation system so in the target selection system you exclude characters who are currently playing these pre-canned animation systems their sequences and this is a practical solution it's simple and it's straightforward and it happens to actually work and it it feels right like you know you guys know what i mean by feels right because like if a target can't respond to combat if it characters off doing their own thing then they shouldn't be participating in combat including as as a target fast forward the game is released and players start noticing that if they keep sheathing and drawing their broad sword

constantly the player is invisible to enemies because late in the dev cycle the act of drawing or putting away a broadsword got implemented as a scripted animation sequence to work around say some camera issues so if you keep doing the broadsword thing enemies keep ignoring you what happened in this example well what happened is you mistook functionality for intent the attribute you were looking at was called is playing sequence it was not called in a cut scene and it certainly wasn't called in a scripted cutscene where people are talking to each other and everyone else should go do their own thing it worked at that moment in time because at that moment in time nobody was using these canned animation sequences for anything else but it wasn't testing what it wanted to test it was testing a proxy of that in the moment of implementation this felt like a small unimportant fix to a minor bug and what i want to convey

is that little decisions like this can have huge far-reaching future impacts you took the concept of scripted animation and you added to its definition before it was a detail of the animation system now it's a rule of gameplay but it still has to be a detail of the animation system so let's imagine the same scenario a different way because i've known some really good qa testers and constantly drawing their broadsword is exactly the sort of crap they'd try so this never got released it got reported a day after they made the broadsword thing a scripted sequence and the combat programmer says oh i guess we can't use scripted sequences for that because it breaks the ai you the ai programmer just made the animation system worse because you got there first and you imposed definition on something and you did not do a good job of it now this is a particularly egregious example because it involves multiple systems but this sort of thing happens on a smaller scale all the time and it

usually happens in ai because ai has exactly the sort of semantically rich concepts with corner cases that nobody thinks about until the bugs are reported the other thing to take away from these examples is that you should be wary of when something feels right i'm not saying ignore your instincts but what felt right in this example was not just your solution but the whole context in which you imagined the solution existing when there's ambiguity there's a tendency to come to an understanding which is based on your own current needs a sort of wishful thinking repurposing an existing tool to solve a new problem it feels really rewarding because it's clever and being clever is rewarding but when you feel happiness at your own cleverness make sure to feel some worry as well all right so moving on who here has

experienced bugs caused by floating point and precision yeah yeah okay everybody it's sort of a rite of passage right looking at this number and wondering why it isn't one okay so here's an example of a bug so you have an enemy ai for a melee character where the character tries to navigate to be exactly one meter away from the player because that's what the animations are built for and the character measures distance from their own frame of reference which involves you know a number of calculations various additions and multiplications and due to floating point imprecision you find that the character actually ends up navigating to a point 0.99997 meters away that's not a really compelling example it's barely a bug nobody reported this because nobody cared and if you think about it why should floating point imprecision matter in ai because ai is all about uncertainty and fuzziness exact numbers aren't generally important when we tweak our ai we do it through sliders not text boxes

but playing with curves and fuzziness is only the first half of ai and the second half of ai is about taking these uncertainties and fuzzinesses and probabilities and such and making distinct behavioral decisions based on them there's this related concept in math and computational math of a predicate a predicate is a procedure that takes some data say like the vertices of a polygon and makes a discrete judgment based on that like is that polygon convex based on the real valued vertex positions or like when you take data like how far away is somebody and you make a discreet decision based on that like should i start fighting them both predicates so let's try that bug again you've got a character that wants to be one meter away it does its calculation and it says oh no i'm slightly more than one meter away i'd better get closer so it asks the navigation system please take me to this place i've

calculated that it's exactly one meter away from the player and let me know when i've arrived and the navigation system does its own calculations in a different part of the code base and says good news you've arrived you're one meter away at that goal point you gave me and then the combat system the following frame redoes its calculation system and says oh no i'm 1.002 meters away i'd better get closer i'll get there i'm at my goal etc and from the player's point of view of course what's happening is that the kids just sitting there twitching a little now that feels like a bug right but it's not like a scary bug so okay first of the audience how should i fix this bug anybody add an absolute tolerance yes this was still not a great example this was way too easy to fix let's talk about that tolerance value i heard the word epsilon what should the tolerance be well there's float epsilon which is not

something you should be using for anything unless you fully understand how to do forward error analysis i see this being misused so often this is not a magic value that means two numbers are close enough yeah all right [Applause] we'll call this one centimeter and one centimeter off is going to be fine visually and so you test with one centimeter and it works ship it here's the problem though you tested this in your test level which is maybe 50 meters on the side and your your characters are nearly at the origin now the basic nature of floating point error is that it is mag is relative to the magnitude of the numbers involved when you do math with large numbers particularly when you are subtracting large numbers from each other you end up with an error which is much higher than when all your numbers are small now an example of small numbers is the

coordinates of all the objects in your test level this sets up this tragically common pattern where everything works fine when you test it and then much later you have to fix it again because you tested it so close to the origin and then the game happens far far away it's very tricky to experimentally determine the proper value for tolerance but a good first step is to do your tests as far from the origin as you're going to get so tolerance solved that last problem which is fine that is a good enough solution but i still want to drill into it a little bit more now i was talking about predicates and in this last example we have two predicates now we've got the navigation systems predicate am i one meter away and we've i'm sorry the combat system is predicate and navigation systems predicate is am i at my goal point and the assumption is if navigation says yes i'm at the goal then combat is expected to agree yes i'm ready to start meleeing that's mathematically reasonable but throw in floating point error and

you lose that consistency what we did with the tolerance the reason this was an acceptable solution was that we made this logical con consequence more robust so that when navigation says yes you've arrived combat will definitely say yes i'm approximately one meter away all right so another example squad combat um you've got a squad of two enemies uh let's just say this is a squad and you want to avoid overwhelming the player with two enemies at once so only the closest one engages the player and the other one say waits his turn you know like if you've watched a kung fu action film that sort of thing so each enemy in their behavior measures their own distance to the player and then it measures the other enemies distance to the player and if it's the one that's closer then it attacks and if it isn't then it waits around and tries to look action-packed but now let's say that both enemies are about the same distance to the player and each one does the calculation in a different frame of

reference and each one thinks my squad mate is a little closer and waits its turn and the result is much the same as with the last example two enemies standing around checking their watches so let's try adding some tolerance to that so let's say if an enemy calculates that he's 10 percent closer than the squad mate he says yes i'm definitely closer if he's 10 percent farther away he says yes i'm definitely farther in those two cases if he's definitely closer he attacks definitely farther he waits and what about if it's in between what then we're seeing a different kind of tolerance here in the goal reached case it was simply identifying the region in which it was good enough here we're using to a tolerance to express that in this zone the predicate might not be giving the correct answer but we still need an answer right because the enemy still has to attack or not attack we still have to make this binary decision

what if we added a tie breaker that applied just in that error zone if he's definitely closer he attacks he's definitely farther he waits in the middle he say he'll fall back on a tie breaker select look at your object id and your squadmates object id if yours is lower you are closer you get to attack and you know this is obviously consistent so does this work no you have just moved the bug over you've just made it more complex to reproduce now there's a situation where one enemy thinks i'm definitely farther so i'll wait just outside that tolerance and the other one calculates i'm in the error zone and my id is higher so i'll wait so they both wait you cannot use tolerance and a tiebreaker you cannot use this sort of escalation of uh um complexity to fix floating point problems that are caused by inconsistent predicates it doesn't work

this is a real life problem by the way this is not just games so here's another example two cars come to a four-way stop now the law says at least in california that the driver on the right goes first but if i'm sorry the driver who gets there first goes first but if two drivers get there at the same time the driver on the right goes first which i'm sure they had the best of intentions when they made this law but it doesn't help anything because now instead of wondering whether you whether you were there first or second you're wondering whether you were there at the same enough time so you get exactly the same problems this is another bug caused by inconsistent predicates so let's revert all that uh enough with tolerances two enemies the closer one attacks and there's a much cleaner solution right so they can just both measure from the same frame of reference right because then they're both asking consistent questions so of course they'll get consistent answers they might get the wrong answer

they might say that a is slightly closer when really truly b was slightly closer but that's that's the sort of bug we don't care about that's a 0.99997 meters away sort of bug once we have this consistency in fact if we detect a tie then we can fall back on the tiebreaker because it'll only apply in the actual case of exact ties of course we can make the solution even cleaner don't make the enemies make the decision separately have a squad behavior which handles this and again we're restoring consistency in this example not by having two consistent predicates but by chopping the number of predicates down to one now i want to disabuse you of the idea that floating point math is the only source of inconsistent predicates it happens at stop signs for instance it's a common one with floating point math simply because we have all these intuitions about how math is supposed to work which actually can kind of go out the window but there's a danger

of inconsistent predicates whenever you are making decisions based on multiple concepts whose relationship might be a little more complicated than it first seemed all right so changing gears a bit let's talk about documentation which is a huge topic and it's not necessarily ai specific but i think there is an ai specific bit of this because i want to go back to something i touched on earlier i mentioned in an earlier slide about this is the one with the cutscene thing with the goblin i said that the source of the bug was that the programmer confused functionality with intent there's various kinds of documentation there's different reasons that you might need to document something but one crucial reason for ai is to document intent all right take a look at this function

i will keep you in suspense anybody know what this is this is bubble sort if ever there was self-documenting code it's this all right so keep that one in mind here's another function yes that is identical code no these are not the same function they have the same functionality but they have different intent this first function is intended to sort any array of characters by the character's age it has a bug if the array has length 0 it reads out of bounds and probably crashes this second function is an intent is intended to sort any non-empty array of characters by their age it's only used when the array is not empty it does not have a bug and the only difference is the intent this is why the most crucial documentation is documenting intent because nothing else indicates intent this code is self documenting for most things everything except the intent imagine that you saw that function crash

read out of bounds of memory well where is the problem is the bug here in this function or is the bug in whatever code produced an empty array of characters which is never supposed to happen and if the bug is here if empty arrays are reasonable where did it come from why did this code use not equals instead of less than was the programmer not paying attention is there some subtlety maybe there's a range issue with signed integers maybe there's it's designed for a platform where that's faster is this code stupid or smart for that matter speaking of stupid or smart why bubble sort n squared time why not use quick sort but maybe the programmer doesn't know about quicksort or maybe they do but they wanted a stable sort which quicksort is not but then maybe they should have used merge sort maybe not maybe they're worried about branch prediction maybe they tuned this very specifically for the use case who knows you know what this code is it is uncooperative it refuses to tell you what you need to know and through that refusal

it refuses to change this is code that you leave alone if you are not absolutely forced to not leave it alone because if you touch it something might break the other reason to document intent is to standardize it let's say your character has an is alive method what does alive mean here suppose you add a death animation while the death animation is playing should isalive return true or false the documentation of is alive helps you answer that question by telling you what it's meant to be used for because the process of documenting a concept involves exploring that concept defining that shape maybe assuming we thought of that when we were making the documentation but suppose we didn't think about it because we didn't even think of the aspect of something somebody being neither alive nor dead that's still an example of a reason to document your intent even if we have to go back and fix the documentation

because when you fix the documentation when you change the intent or clarify it which is a kind of change you're potentially cutting off certain usages the update to the documentation forces you to think about that action you're taking it forces you to think about all the use cases you might be ruining all the uh all the future use cases even ones not currently using this function that you might be cutting off now documenting your intent isn't just about writing essays think about an architectural drawing you know this this is not a single picture it's multiple pictures you get redundant overlapping information to resolve ambiguities in a single diagram similarly if long comments are one view another view is tests and assertions now i'm not going to talk very much about tests and assertions because i don't think i'm the right person to do it other people have thought about it a lot more than i have but i will say that one of the most

useful aspects of tests for me is as a form of documentation they document what you are thinking about what you are worried about they highlight the difficult or underspecified cases they help someone understand why you had to make the decisions you made though while we're at it if we're making an automated test maybe we should document the intent of that test is this something that you never think will happen but you just put it in just in case is it the common case is it an edge case is it why you didn't use quicksort now a corollary of tests and document of tests and assertions being a kind of documentation is that they don't have to break in order to be useful i will often use assertions that i know will never ever ever fail for two reasons first of all sometimes they fail secondly an assertion is inherently reliable look at this comment x will never be zero well says you but the reason i'm even looking at this code is because there's a bug so someone's wrong about something

but if it's an assertion well okay you're right it's not zero the princess is in another castle otherwise this assertion would have fired and because it's an assertion and not a comma comment i don't have to spend any time any brainpower second guessing it it's documentation you can believe in i don't think document your code is a very controversial opinion but it's one of those ideals we sometimes opt out from like we try to eat healthy get plenty of vegetables and then we see a burger and some steamed carrots and we don't really feel like the steamed carrots and what feels like in the moment good to do is not documenting your code maybe maybe what you feel like doing is writing the code because ai programming what feels good is getting stuff done not to mention in a situation where you're experimenting and iterating and redesigning if you document something

while you're doing all that it feels like you're trying to paint an oil painting of a football game while the football game is still going on so documentation is often done as a post pass the good thing about documentation as a post pass is you don't need to redo it the bad thing about it is that it feels like such a chore because you already did what you wanted to do you fixed the bug you got everything done and now you have to go back and write a book report sorts the characters by age there documented i want to advise you how to write good documentation and i think to do that i need to advise you how to want to write good documentation because there's no objective metric of documentation quality if you just want to get it out of the way you can do that you can convince yourself that you documented everything you needed to so here's my advice in the moment want to share that moment if you did something clever want to tell other people about it not not to brag but to share your joy if something was a huge pain to write tell them about it tell them about the journey that it took you through tell them why you were

forced into this weird solution explain to them the dilemmas you faced document to share sometimes that'll happen while you're writing the code sometimes it'll happen afterwards but always with the same intent which is to help your team because the goal of your process is to help your team i want to have some big inspiring conclusion for this talk but i think that would be a little dishonest you're still going to write some bugs i hope i've helped you write fewer thank you