June 11, 2008

Interviewing AI Developers

I left Retro Studios a few weeks ago, and I've been talking to a lot of developers in the meantime. It's been a really fun process.

However, it's also reminded me that when it comes to AI development, our industry is all over the map.

So I thought it would be a good idea to make a big list of AI interview questions ... some that I've asked, some that I've been asked, and others that I think are worth asking. I left the answers blank, since plenty of good answers to all of these questions are easily accessible in all sorts of places (and if you're the one giving the interview, you should already know the answers!)

If you think of any good ones I missed, go ahead and add them in the Comments section below.

And if you happen to be interviewing me, of course, feel free to ask me any of these!

AI Developer Interview Questions

Behavioral AI

-What's the difference between a finite state machine (FSM) and a hierarchical finite state machine (HFSM)? Give an example of a hierarchical state machine with functionality that you could not easily replicate in a non-hierarchical FSM.

-What are some of the limitations of state machines? When is the use of state machines appropriate, and when are they insufficient to generate the kinds of behaviors you need in a game?

-What is a decision tree? When would you want to use one? What are its performance characteristics? How can you generate a decision tree automatically from a pre-existing data set? Is it feasible to do this at runtime, and has it been done in a commercial game before? When and why would you want to do this, and how would the data need to be organized to make this possible?

-You're developing a boss encounter in a 3D platformer game, and the boss has 15 different attacks. The game designers have asked you to make sure that the player sees as many of those 15 attacks as possible during the encounter, and that he seldom or never sees the same attack twice in a row. What are some ways you can do this? What does the attack selection algorithm look like in this case? Keep in mind that not all attacks are possible all the time -- for example, the boss has a melee attack that he can only do when the player is very close, and a bombardment attack he can only do when the player is far away.

-In one room in your game, there's an elevator that AIs will need to use to escape from the player. In order to use the elevator, they have to walk over to a special button on the wall, press it to summon the elevator, then walk into the elevator and press another button to tell it to ascend. How would you design a system to make sure AIs can do all of these things in the proper order? If you have 3 AIs in the room, how would you design the system to make sure they can all escape in the elevator at the same time? What happens if one of them dies while they're trying to do this, and how do you make sure the other AIs don't get stuck waiting for that dead AI?

-You're in charge of implementing a stealth game similar to Thief: The Dark Project, and you need guards in your game that have imperfect vision and hearing and inhabit dimly-lit castles, and they can search the area for the player if they think there's an intruder around. How do you model the sensory systems of these guards, and how do you aggregate auditory, visual, and other kinds of stimuli in this system? How do you implement the various alert states for the guards, and why?

-What is planning? How is it used, and what are its advantages? Is it feasible to use planning in real-time games? If so, name any titles where planning has been used for any part of the AI. Describe the architecture of a planning-based AI system for any genre of game.

-You're working on a game that involves enemy wizards dueling each other. Each wizard has at least a dozen different spells at his disposal -- some of them simply inflict damage, while others will temporarily stun or immobilize an enemy, slow him, prevent him from casting spells for a brief duration, teleport the caster a short distance, or give the caster a temporary shield. A wizard can only cast one spell at a time, but each spell has a fixed cooldown (time before it can be cast again) and an associated mana cost (assume no mana regeneration). Describe some ways you might implement a competent AI system for a wizard.

Spatial Reasoning

-Using the example of the Thief-like AI system in the previous section, how do you implement the 'search for player' behavior for the guards, and get them to search an area in a believable fashion? How do you make sure this searching behavior isn't too challenging for players, and ensure that it's usually possible for the player to escape the search if he plays the game well?

-You're tasked with implementing a computer player for a real-time strategy (RTS) game. Assuming that there is no fog-of-war, how do you implement a system to allow the computer player to determine what parts of the map are controlled by enemy players, and which parts are open to easy exploitation? How do you identify the choke points on the map? How do you find the boundary between the parts of the map under your control and the parts of the map controlled by enemy players? How do you detect an impending enemy attack or a change in an enemy's offensive posture?

-You have an AI player in an RTS game that occasionally needs to send scouts out onto the map to perform reconaissance. Designers want each scout to move around semi-randomly, exploring various parts of the map, particularly those that have been seen the least recently. Assume that the game is grid-based and has a fog-of-war feature. Also assume that the scouts are very cheap and dispensable, and it's OK for them to walk into the enemy base or other dangerous areas. How would you implement the system to decide where the scouts should go? What sort of data structure do you need to support this? How can you ensure that the scouts do a good job of exploring the map thoroughly? What are the performance characteristics of your approach? Is there any risk of scouts getting stuck trying to go somewhere that isn't even accessible?

Steering

-How does a flocking-based steering system work? What are the components of a flocking-based steering system, and how are they combined? When does flocking-based steering break down or produce undesirable results? Are there any performance implications of the standard flocking model as described by Craig Reynolds, and if so, what are some ways to address them?

-What are attractors and repulsors? How do they interact with a steering system? When are they useful, and what are their limitations? When can they be used for obstacle avoidance, and when are they insufficient?

-As you're starting work on your game, one of your colleagues suggests avoiding pathfinding completely, and just using potential fields for pathfinding and navigation. He suggests that you just overlay a big 2D grid over the world, with each cell indicating the distance to the nearest obstacle. Is his idea feasible? Why or why not? When would it cause problems? Regardless of the answer to that question, what are some of the other ways that such a system could be used?

-You're implementing a medieval strategy game in which pikemen should always walk in front of archers, and catapults should always be behind the archers. Explain how you could implement the movement system to ensure that you keep pikemen in front and catapults in the rear as much as possible. Explain how your answer might be different depending on whether or not the units simply need to end up in that configuration when they reach that destination, or if they need to maintain that formation while moving.

-You're tasked with implementing a crowd that walks around the streets of a city. Describe some ways you could implement this in a fast and efficient manner. How do you ensure that crowd members don't touch each other while moving? How do you get crowd members to get out of each others way, and ensure that no two crowd members can get stuck trying to get around each other?

-Imagine that you need to extend the previous example so that the crowd runs away when any sort of combat incident occurs. How do you get them to run away from the violence? How do you make sure the crowd doesn't immediately fill in this area again? How do you ensure that the crowd does eventually "forget" about this incident and return to fill the area?

-There's a hovercraft in your game, and the designers want the hovercraft to move along a linear sequence of connected waypoints. It should move to a waypoint, stop, fire at the player for a few seconds, and then randomly move to either the next or previous point in the sequence, taking 4 or 5 seconds to reach the waypoint it's selected. How do you control the movement of the hovercraft to make its movement as natural and believable as possible? Is it necessary to use physics to implement this, and if so, why?

Pathfinding and Navigation

-Explain the A* algorithm. How does it compare to other search algorithms, and why is it usually preferred in real-time games? When does A* give poor performance?

-Name at least 3 different ways of representing a search space so that you can perform pathfinding on it. What are the strengths and weaknesses of these approaches, and when would you want to use each one?

-List as many ways as you can think of to optimize pathfinding without sacrificing the quality of the generated paths. Be sure to explain any additional costs (such as increased memory usage) of each of these optimizations.

-Your pathfinding system was written with a normal human soldier in mind, and it does exactly what's needed for normal human soldiers. Halfway through development, the designers decide to add 3 new units: a 15-foot-tall space alien that can't fit through a lot of the doorways in the game, a very wide hovercraft unit that can't go through tight corridors or small doorways, and a soldier on a motorcycle that can only turn relatively slowly (say, 15 degrees left or right per second at any speed). How do you tweak your AI system to accommodate all of them?

-You have a pathfinding system that does a great job of finding a path across the world, but it does not take dynamic obstacles (such as crates, barrels, vehicles, and other AIs) into account. The player is playing a superhero, and he uses his super-strength to drop a soda machine in the AI's path. The AI doesn't have any way to move or destroy the soda machine. Once the AI sees the soda machine blocking his path, what are some different ways he can pathfind around it while ensuring that he eventually returns to his original path and reaches his initial destination? What happens if the soda machine is on top of his destination? What if the soda machine is right in front of a doorway the AI needs to walk through as part of his initial path?

-You're working on a first-person action game set in a 3D world. The game's pathfinding system is built on a navigation mesh. Suddenly, the designers decide that they want the AIs in the game to be able to use ladders to climb up walls, jump up or down small ledges, and leap across small chasms, and they should be able to use all of thse abilities as part of their normal pathfinding. Explain how you would implement such a system and how it would relate to the existing navigation mesh system. Also describe what sort of tools you would provide to the designers (if any) to add this support.

-You're making a WWII shooter with fighting in the streets of Berlin. Your designer wants to ensure that at certain points during the game, the AI-controlled Nazi units will flank the player, with small squads of Nazis approaching from different directions and side streets and alleyways. We assume that cheating is not allowed (i.e. we may not simply teleport units where we want them to go), and we assume that telling the designers to do it with scripting isn't feasible. Describe at least 2 different ways to implement such a system.

-Your designer just played a game where he saw a squad of AIs "leapfrogging" each other -- in other words, proceeding down a corridor in such a way as to ensure that only 1 AI unit is actually moving forward at a time, with the rest providing cover (i.e. the rear unit always moves forward, presumably to the front). He was very impressed and he wants you to implement the same thing. Describe some ways to implement such a system. How do the AIs know when to move, and where to stop and provide covering fire?

Scripting

-How does scripting fit in with AI development? Under what circumstances should AIs be controlled by scripting rather than AI? When designers use scripting to control AI agents, at what level should the scripting interact with the AI?

-Discuss a few of the different scripting systems you've worked with or seen used in games. What are the advantages and disadvantages of different ways of implementing scripting?

-What are the strengths and weaknesses of scripting in general? When should scripting not be used?

-Pick a sample game, and describe the best way to design a scripting system to allow designers a certain level of control over the AI in that game. Also describe the ideal tools for debugging the scripting system you propose.

General

-How should an AI system interact with an animation system? What are the problems with a 1-to-1 mapping between behaviors and animations? Describe some examples of when AIs need to take explicit control over parts of a character's body beyond simply playing a full-body animation, and describe how you would implement this in each case.

-How should an AI system select animations for playback? In other words, what should the interface for the code and data look like, and how should the data be abstracted to allow the AI system to access the animations as simply as possible? Describe the advantages and disadvantages of various ways of different approaches to describing and accessing the animation data.

-What's the coolest AI system you've seen in a game? What impressed you about it, and how do you think it was implemented? What are the runtime performance implications of that kind of a system?

-What are some uses of machine learning (ML) in games? What problems does ML help you solve? What are the strengths and weakenesses of different approaches? What are the performance characteristics of different ML approaches? Which ML techniques can be executed at runtime, and which are more suited to an offline context? Give some examples of where ML has been used in games, whether or not it was successful, and why.

-You have a game in which 1000 NPCs all have to find their way around a complex game level, and each NPC has its own goals and behavioral system. Assume for the sake of this example that these are enemy soldiers and officers patrolling and guarding a base in a first-person shooter. What are some of the ways you could optimize the AI for your NPCs to improve performance? [Thanks to Ian Millington for this question]

Posted by PaulT at June 11, 2008 11:37 AM
Comments

Come interview at Naughty Dog! :)

Posted by: cowbs at June 12, 2008 04:50 PM

Awesome! This has given me some food for thought. Thank you very much.

Posted by: Adrir at June 16, 2008 04:11 AM

Wow, this is an awesome list, Paul. A bunch of your questions left me scratching my head and going "uh ... how WOULD I do that...?"

Your decision-tree section reminded me of when I was first interviewing at Bungie: when you apply, the first thing you get is a programming test to do at home and send back to them within a day or two. Question #1 on the test I got (not used any more) was a discrete classification problem.

It was only by the merest luck that, two days before, I had read an article on C4.5 in Game Developer magazine. Since I had, I immediately recognized the problem as a DT one ... and I was able to give Bungie the impression that I knew what I was doing. If I hadn't happened to read that article, who knows where I would be now. Probably in my 9th year of a PhD somewhere...

Posted by: naimad at June 16, 2008 09:50 AM

Re: decision trees: here's an interesting article by Richard Evans of Lionhead on the use of decision trees in the AI of Black & White (yes, I just answered one of my own questions!) :

http://www.gameai.com/blackandwhite.html

Posted by: Paul T at June 16, 2008 11:15 AM

A great list of questions there Paul. I regularly collect programmer interview questions for myself and my students to mull over.

There's nothing like being asked these kind of questions to let you know where you stand. I love to give my finalists C++ interview questions to get them spurred on to really nailing down thier own understanding.

Question for you. How many of those did you actually know? :)

Posted by: Phil Carlisle at June 18, 2008 12:48 AM

I feel that the important focus (which some of your questions address) is not being able to regurgitate algorithms... but that the applicant show that he can think his way out of a box. Show some creativity. We are all going to encounter very project-specific problems that will not be able to be learned in a classroom or garnered from a book. The ability to know how to approach a problem like that is the #1 asset that an employee... especially an AI programmer... can have.

Hey Paul... I want to base my next week's Developer Discussion column at AIGameDev on this post (linked and credited appropriately, of course). Shoot me an email if you would, please.

Posted by: Dave Mark at June 18, 2008 01:03 PM

Oh... one more note: Combine the topic of this post with the prior one, "Game AI U". What would the curriculum directors at purported "game development schools" think about that list? Does their program prepare people to be able to answer any of those questions at all?

Posted by: Dave Mark at June 18, 2008 01:07 PM

> [Phil Carlisle]
> Question for you. How many of those did
> you actually know? :)

All of them ... Most of them come out of problems I've faced at one point or another in my career.

I called them out as fair game for interviewers to ask me at the top of the post, so I certainly have what I believe are satisfactory answers to every question.

Of course, they're fairly broad questions, and I'm sure there are also a lot of good answers beyond the ones I would give.

Posted by: Paul T at June 18, 2008 03:23 PM

> [Dave Mark]
> Hey Paul... I want to base my next week's
> Developer Discussion column at AIGameDev on
> this post (linked and credited appropriately,
> of course).

Awesome! Looking forward to it. :)

> [Dave Mark]
> What would the curriculum directors at
> purported "game development schools" think
> about that list? Does their program prepare
> people to be able to answer any of those
> questions at all?

Good question! Given the lack of emphasis on AI at most such schools, I doubt they really help aspiring developers with any of these.

But I do think this list sums up a lot of the challenge we face -- and more to the point, they describe problems that we as an industry have already found good solutions for.

Creativity and out-of-the box thinking are important, but those existing solutions should be fundamental knowledge for most devs working in game AI. My own definition of a "game AI developer" is someone who can answer most of the questions in this list.

Posted by: Paul T at June 18, 2008 09:20 PM

Great list! I'll definitely be referring back to it a lot to broaden my own skills.

> [Dave Mark]
> What would the curriculum directors at
> purported "game development schools" think
> about that list? Does their program prepare
> people to be able to answer any of those
> questions at all?

I can't really speak on behalf of other schools, but I know that DigiPen Institute of Technology, www.digipen.edu, does cover a good portion of the techniques you would use to solve these problems, in particular the CS380 - Robotic Intelligence/Game AI and CS381 - Machine Learning courses. I believe Steve Rabin designed the CS380 course; however, I don't think he teaches it anymore.

Posted by: dvertree at June 26, 2008 03:41 PM

For those that are curious, I did indeed use this post as a seed for my Developer Discussion column at AIGameDev. (It also references Damian's post "Game AI U?"

http://aigamedev.com/discussion/industry-knowledge

Posted by: Dave Mark at June 27, 2008 07:39 AM

The performance question at the end sounds like a bit of an afterthought, you could do more with it. How about:

- You have a game in which 100 NPCs all have to find their way around a complex game level, each with their own goals and behavioral system. How would you design system to allow them all do to the processing they need, without exceeding the AI time budget?

Posted by: Ian at June 30, 2008 12:54 PM

Thanks, Ian! Good call; I've gone ahead and added it (with slight modifications).

Oh, and I just picked up your book the other day ... I'm enjoying it quite a bit (despite the lack of references :P ).

Posted by: Paul Tozour at June 30, 2008 05:38 PM