Ask HN: How does an online game with AIs manage so many AIs? | Hacker News Reader

Ask HN: How does an online game with AIs manage so many AIs?

67 pointsmaruhan249 comments

Each AI should use up a pretty significant resource of the server running the AI. How do the games possibly manage so many of them? Most education on AI is how to make them smarter, not how to make them cheaper. There has to be well known tips and tricks about scaling AI. What are they?

View on HN

It's not 'AI' (what actually is?), but mostly hand-crafted state-machines trying to achieve game-specific goals, which directly inspect the current game state instead of trying to build their own 'world model' (of course with restrictions like fog-of-war, visibility-checks and so on so that the cheating isn't too obvious).

Really no that much different from what the Pacman ghosts did, just developed further from there (especially during the Golden Age of strategy games during the late 90's and early 00's).

With this base, scalability is achieved through fairly traditional performance optimizations (mostly using the right algorithms and data layout, especially for path-finding and 'visibility checks').

Also in strategy games, AI is often layered like a military chain of command, where the "commander AI" only makes high level strategic decisions and only has a very 'sparse' world model, while the lowest level 'soldier' AIs are mostly occupied with pathfinding but only know about their immediate surroundings.

Also, each game genre has their own highly specialised, hand-crafted "AI" algorithms. A first-person-shooter AI is completely different from a car-racing-game or realtime-strategy game.

Exactly this. It's also worth mentioning that 'true AI' would be an absolute nightmare in terms of delivering a game, the QA testing burden would be so enormous for any reasonably large game that it'd be difficult to get it out the door.

I remember working at a games studio years ago and a kid straight out of university joined us after doing a degree in AI - assuming that games used real AI. Nope, it's all smoke and mirrors.

No one has managed to create a real AI (as in strong AI). Machine learning, deep learning is smoke and mirrors too.

I think louthy means something that works more like an agent observing it's environment,learning, strategy etc,

Most entities in games are more like a wall following robot.

...and in games, you actually want smoke and mirrors:

http://www.techradar.com/news/gaming/shouldn-t-our-enemies-b...

If you really had hard and strong AI, a lot of games certainly wouldn't be as much fun to play anymore for casual players (spare some games you want to be frustrating). You want the protagonist to eventually conquer the enemies and win.

Yup. Imagine a boss in a game decides it's not in his best interest to be predictable, or take matters in his own hands and attack the players when they aren't ready. Or any number of things that sounds cool on paper, but would be exceedingly frustrating when actually playing the game.

Imagine a boss in a game tired of fighting every day, and just giving up and not fighting back.

That's essentially the plot of Wreck-It Ralph.

This might be true for FPS and other genres where reflex and speed are the most important factors. However most competitive strategy games will definitely benefit from strong intelligent AIs. For example in Age of Empires, the problem isn't that the AI is too strong (they're not - with enough practice anyone can beat the hardest AI). The problem is that they don't play like a human would, and are exploitable with certain strategies which even a beginner player wouldn't fall for.

Can you expand on this comment? Is there an industry standard definition of real AI? I'm genuinely curious.

Industry standard usually means content-free marketing stuff.

Strong AI is a relatively well estabilished term of art in the field of AI: https://en.wikipedia.org/wiki/Chinese_room#Strong_AI

There's a lot of things hyped/marketed as "AI" that are merely algorithms or applied statistics on large datasets. Things that totally miss the mark on the computer science aspects of what AI is suppose to be.

> It's also worth mentioning that 'true AI' would be an absolute nightmare in terms of delivering a game

An important sentiment I've heard many times on the gamedev.net forums is that machine learning techniques are usually too difficult to tune in order to make the agents behave in the way that the designer wants.

Game AI is about providing an illusion of intelligence and about providing a designer-crafted experience to the player. So it often makes sense to cheat in order to achieve this.

Having said that, some games really do benefit from smarter AI. For example, real time strategy games sometimes do (eg Supreme Commander AI mods, AI War Fleet Command etc) and often first person shooter bots as typical dumb bots are simply not as fun to play against than real humans, although you mostly want the bots to have some high level tactics ability (not perfect aim or such), which is why the game FEAR is often applauded for having fantastic AI (it uses Goal Oriented Action Planning to produce high level tactics such as flanking). But most games don't go very far at all.

I'm glad someone referenced the classic AI of a PacMan Ghost ;) Id's Doom from the early 1990s is another deceptively simple yet surprisingly engaging instance:

http://doom.wikia.com/wiki/Monster_behavior

An agent's set of possible actions is conditioned on its environment, other NPCs as well as the players actions. Even for a finite number of variables you can quickly see how the problem becomes computationally expensive for a single agent.

You want to to build unsharded persistent worlds with complex character behaviours and allow millions of online simultaneous players all sharing the same game state? Then you need to take a page from architects building scalable cloud computing infrastructure and applications that serve billions of request per second with low latency.

Companies like improbable.io are abstracting game state and logic with SpatialOS. But I think there is still a lot of room here for some startup to combine "Unreal Engine + AWS". Creating a true "cloud native game engine". Even if its just HTML5 based and targeting games such as Slither.io.

Quest - An iOS "io" Game from Improbable

https://improbable.io/games/blog/quest-an-ios-io-game-from-i...

Most of the work needed for decisions is shared between AI instances using a few tricks:

1. Precomputing information for all agents, like using global shortest path (Bellman-Ford).

2. Abandoning per-unit subjectivity (a lot of units will share same view) or in other words: limiting internal unit state, using a shared state between groups of units.

3. Decoupling expensive algorithms into multiple simple steps. (Like state machine simplifies regular expression.)

4. Using separate AI and visualization thread, and using low amortized cost data structures (priority queues etc.).

You may observe all these three rules by anomalies in unit behaviour. Play http://www.screeps.com to learn a lot about modern RTS AIs :-).

For an online game, an additional trick could be to run the AI code on the users' computers.

"AI" is a ridiculously general term. People use it to talk about everything from line-following robots to machine vision and speech / natural language recognition.

Most game "AI" has nothing to do with the currently trendy "AI" based on linear algebra and neural nets. It's much, much simpler, partly because it has direct access to the game state and doesn't have to do any sensor processing.

"GameAI" tends to be a bag of puppetry tricks. You don't even need the strategic depth of chess, just something that gives you an interesting enough and varied enough move/fire pattern.

I vaguely remember something like an interview where a dev told the story of how by making their bots cleverer the player satisfaction had gone down.

If the relation was monotone, this would mean that playing against real humans is less fun than playing against a stupid AI. Which is not the case, so I guess we have something like an "uncanny valley" here.

So making the bots not a little bit more clever, but really a lot more clever, would improve the game.

In what I remember, they made their bots so clever it wasn't fun because it overpowered any player in their tests. Humans want to win, so losing every time wasn't fun.

I'm trying to find that interview.

  Humans want to win, so losing every time wasn't fun.

This needs to be a bit more qualified.

I personally love games where the skill gap is SO HUGE it seems impossible to win at first. I get my ass kicked for months and years before becoming any good. Go, Quake, Elastomania... Losing doesn't trouble me at all.

On the other hand, "reasonable" games where advancement is assured, the skill curve mostly flat (I can beat top players with a bit of luck or the right items / grind / setup), hold no appeal to me whatsoever. Diablo & co.

Maybe you remember when you started playing go. If you played with strong kyu players (not even dans) you could get all your stones captured. I managed to win a 17 stones handicap game by 80 points as white. It's ok to try it for fun once (we did that for fun) but it's not fun anymore on the second time. I went on explaining all the most common mistakes in that game.

The point is that a game with such a gap as go is fun of you have a ladder of increasingly stronger opponents to play with. 20 kyu, 18 kyu, 16 kyu, etc. If the AI is a dan player, whatever it means in Quake, the gap is probably too wide for many people, especially since games started to be easy to win to retain players.

> Losing is fun ~ Dwarf Fortress Motto

I'm on basically the same boat. One of my biggest frustrations with my gaming friends is that they can't ever lose. Sometimes they can't even win unless they win by enough.

When I play games I'm there to have fun. Trying to win is fun, winning is fun, losing is also fun. It's all fun.

DotA, LoL, etc would be games I'd play a lot if the community weren't the shining example of "can't lose, or even win by less than they `should have`".

This works best when you can see visible progress from one try to the next. Dwarf Fortress is Fun because every loss is different, and you got farther/learned new things every time.

Fighting 13-year-olds in Call of Duty or League of Legends is less fun (provided you don't play much like me), because often you'll drop dead for reasons you can't divine, or anything you try loses the game with no feedback on what worked and what didn't.

(Full disclosure, I'm one of the people who doesn't take losing well.)

If you're a casual player, then playing against humans sometimes isn't fun at all. There are a few shooters that I loved the single player campaign, but very quickly got frustrated by and sick of the multiplayer. Why? Simple - because I wasn't very good and the other players destroyed me. Its just as un-fun as playing against a bot with perfect aim: not at all, its frustrating.

The most fun games I've played are when I'm evenly matched. Being unnaturally overpowered or rolling through noobs isn't really fun.

And like someone said, with "real" AI, players would have a lot less fun.

OpenAI created a bot for the Dota 2 tournament and it makes the professional gamers look like beginners sometimes.

https://openai.com/the-international/

There's a number of tech solutions to scaling mob AI. Most of these are also applicable to non-online games as well:

- Running AI at a different frequency than the game. The network event loop might run at 30Hz (33ms tick delta) but AI doesn't need to make decisions that often, maybe every 100ms or 500ms etc.

- Separate decision making from performance. A cheap execution system can run at a high frequency, while an expensive decision making system runs at a lower one.

- AI LOD. Mobs that are far away run much simpler AI that doesn't try to perform detailed animations etc. Mobs that are in unpopulated areas get frozen, and thawed once somebody enters.

- In instanced dungeons, mobs don't even exist until the players enter, and once players leave, the mobs just get unceremoniously killed.

- Offloading. Mobs are just game agents so in online games it's possible to offload them to other servers that get load balancer as players move about, areas get frozen etc.

Basically the big question is: if nobody is interacting with a mob, does it need to exist? In most online games they do not. And even in sim heavy games, maybe they don't need to run the same high fidelity AI when nobody is watching.

Then the last tip is:

- Make the AI as cheap as possible for the task at hand, but no cheaper. A mob in MMO that is all aggro and easy to kite doesn't need to have complex strategic cognition, and it would probably be a detriment. Everything need a to match it's context.

Source: I make games. :)

Most AI in games are simple.

Either state machines or behaviour trees. So they're designed to be quick to execute by design :)

Also they tend to have manager classes iterating over a list of NPC data, rather than lots of NPC classes and executing "run" methods.

Edit: undo autocorrect typos

And while you're iterating the same code over many NPCs, you could take great advantage of GPUs and gain significant performance by running all those NPCs in parallel.

Two things:

1) Like 'opless wrote, AIs in most games are simple; they're designed to execute in real-time.

2) From the point of view of a networked game, AIs and players are the same - the server(s) only care about inputs. The difference between keyboard input and AI input need not to be relevant, and this suggest a trivial approach - execute AIs on clients, and send their inputs along with players' inputs.

Your (2) opens a networked game to malicious clients manipulating the AI inputs.

I'd suggest digging through old EVE:online devblogs and presentations. They describe server architecture and design points, as well as the process of tuning those with each other and actual community use.

https://community.eveonline.com/news/dev-blogs/ https://www.youtube.com/channel/UCwF3VyalTHzL0L-GDlwtbRw

Regarding (2), there are some MMORPGs that went with this approach, producing hilarious results, obviously - talk about cheat programs allowing players to teleport monsters around etc.

>execute AIs on clients, and send their inputs along with players' inputs

That seems strange, you'd be sending multiple times the same AI's actions to the server, in which case you better be certain that it's deterministic, not to mention the security concerns. It seems far easier to execute the AI on the server and send its actions to each player, especially if it's a trivial AI.

I wonder what you might actually do is execute AIs on both, and send occasional snapshots of the AI state from the server to the clients.

This gives you the benefit of low-latency on the client (don't have to wait for the server to tell it what the AI is doing) but also avoids security and non-determinism worries. (Although the AI might still be non-deterministic, it probably can't diverge too much before the client receives the next snapshot from the server).

This might be more effort than it's worth, though...

I don't see how this is an issue. Just imagine that client-side AI is just another player that happens to share the same CPU as the human one. From the server's POV, there's not much difference. Client inputs are client inputs, you always want to have some anti-cheating mechanism in place.

> benefit of low-latency

you achieve the benefit by loosening consistency, i.e. the local ai will have to react to local events before those are acknowledged by the server to see any gain, and the server might come to different opinions because it sees a different state of the game considering multiple clients who are constantly out of sync.

That leads to warping. A rocket, to take an example of an extremely simple entity, might fly a few meters on your screen only to explode right in front of your face because the server sent a message that the flight path was blocked by an online enemy that your client didn't predict.

Client-side AI inputs can be trusted no more and no less than player's input; same anti-cheating mechanisms apply.

Sure, if you can execute AI server-side, go ahead. But the GP asked about scaling it up, and this offers a trivial way of doing so.

There are different actions that link to cheating though, so I don't think the same anti-cheating mechanisms will work across the board.

A player remaining still doesn't benefit the player. All the AI enemies nearby standing still does.

A lot of games actually do this: each client has its own AI, and the games just exchange player state. By syncing player state before computing the AI's next action, you ensure that every game instance will have the AI perform the same operation.

Of course, for this, you need a bit of determinism, and some games need to synchronize other parameters, which can lead to "security" concerns: bullet spread, hit detection and such for FPSs, for example.

This can also lead to some hilarious de-sync issues when a player tries to cheat on its local game instance. By altering its local state, the AI is effectively desynchronized, and the players can observe different outcomes on their local instances. This is often used as a punishment for cheating.

The alternative (for serverless, p2p games) is to have a central host, but it might take a lot of computing resources, and the host is then generally free to cheat.

One side effect of having deterministic AIs synced over the lobby is that the code needs to have the exact same behavior, down to the rounding errors. This can dramatically increase the complexity of cross-platform multiplayer games, and usually requires the exact same binary to be used by every client.

I think that Civilization and Sins of a solar empire use this kind of distributed AI scheme (as well as most games that don't have cross platform multiplayer, and those where you can experience de-syncs).

For many games (shooters etc) making a smart AI is relatively easy. What's hard is making an AI that's provides a realistic and interesting challenge. These "AI"s don't use much in the way of machine learning however.

I feel like this isn't what you're getting at though. Perhaps there's a specific example you have in mind?

Most comments here are explaining what's meant by game AI's and how they're not closely related to "AI" as understood in other fields.

There definitely is lots of room for interesting applications of "real" AI in games. Apart from NPCs, learning and building models about the player has lots of potential too.

The interesting-game-ai field is of hard to keep track of, because the search resuls are full of combat AI discussions, which is pretty uninteresting.

Could you provide examples of games? The answer is very different for, say RTS or Shooter, MMO or match-based, etc.

You'd be surprised at how devious some of the tricks are. I'll give you an example from Startopia: visitors want particular services. These have queues. If the queue is too long, the visitor looks for a shorter line. Except... this led to them aimlessly wandering in circles. Oops.

So, instead, when they decide they want a service, they reserve their place there and then and then just walk to their spot. A completely hidden variable, cheap to compute, and the AI now behaves "sensibly".

In general, the AI of the average opponent in a computer game is way less complex than that of a housefly. Primitive communication and responses to external stimuli is about all there is.

> Each AI should use up a pretty significant resource of the server running the AI.

The premise is wrong, in many games AI can be extremely cheap. It's usually not the same "AI" as in other fields. Game dev is a completely different dimension.

I've started playing Destiny 2 and wondered the same thing. There are enemies seen by me and other players at the same time.

So the enemies have to be controlled server side not locally. Also there can be (and will be) a lot of enemies around the "Destiny world" at the same time. What kind of servers do you need for that? That's not just processing HTTP requests and fetching data.

Could there be a not mathematical model of AI

besides the other sensible opinions on the engineering, if those fail, the far simpler answer is to pay for server farms.

Reply on news.ycombinator.com