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.
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.
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.
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.
Most entities in games are more like a wall following robot.
Strong AI is a relatively well estabilished term of art in the field of AI:
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