Thursday, May 12, 2016

Simulating Human Geographical Knowledge With Neo4j

TriadCity uses multiple AI architectures to model human behavior in different contexts. Even the simplest is pretty sophisticated: the subsumption architecture for in-game automata does a great job of keeping the City vibrant, where AI-driven characters have homes to go to, jobs to be employed at, hobbies to cultivate, and relationships to explore. At the higher end of the spectrum, we use external bots which log in to the game world just as human players do, mimicking human decision-making and in a very limited way mimicking human speech.

There's a trade-off which might not be immediately intuitive between in-game and external AI. While external AI has access to greater compute resources, in-game AI has access to the database. Think of movement. An AI-driven in-game character finds its way around the world by querying a weighted directed graph which the game server keeps in memory. The model goes like this: in-game AI are residents of the city, they've been there a while, and they know their way around. External AI face a different problem. If we want to model human behaviors, they can't simply query the database to ask how to get to point B. Like humans they must explore the world, building their own mental representation of its geography analogous to the paper or Visio maps drawn by players.

Here's a practical problem external AI characters must solve to survive. "My canteen's empty; I'm thirsty. Where is that fountain I passed a while back?" A human will probably use ordinary geospatial reasoning to reckon a reasonable path. A naive AI can walk back through a history of its moves. A more sophisticated, human-like AI needs an internal representation of where it's been, what it's found there, and how to navigate the most reasonable path back.

I've recently enhanced our external bots to build persistent knowledge maps of the world as they explore, using the excellent open-source graph database Neo4j. This is the same technology the TriadCity game server uses. The server's use case is extremely simple. At boot, once the game world is loaded into memory, a Neo4j graph of all of the Rooms and their relationships is made, with properties describing path attributes. At runtime, AI characters simply query the graph for a path and off they go. The database isn't persisted, it's re-created at each boot, and is updated on the fly as World Builders add or delete Rooms. The external AI use case is more nuanced, where the bot must build a persisted graph room-by-room as it explores. Fortunately the Neo4j code is again very simple.

Each time the bot enters a Room, it asks the graph if that Room is already present. If no, it creates the new Node, populating its properties with information it may want later: is there a water source here, a food source, a shop, a skill teacher? Along with the new Node, it adds a Relationship from the originating Node to the new one. A single simple LEADS_TO RelationshipType is all that's needed. If yes — the Room was already present in the graph — it adds the Relationship linking the origin and destination Nodes. With a little work we can add the cost of the move to the new Relationship: cache the bot’s energy before the move and compare it to when the move is complete; make that cost a property of the Relationship. The robot now has a comprehensive map of all the Rooms it's visited, the paths between them, and their costs. Finding the closest Room with a water source is a simple shortest-weighted-path traversal.

Movement behavior is now more intelligent. Bots already knew not to re-enter the Room they previously left. Now they can prioritize directions they haven't yet explored. If a Room has Exits north, south and west, and the bot's previously explored north and west, next time it'll go south. The resulting behavior is less random, more like the way a systematic human would do things. Also, the bot can take the least expensive path back to a water source; that is, it'll get onto the trail rather than blundering through thickets. Nice.

Survival skills are improved. The bot now knows the comparative distances to multiple water and food sources, and can compare their relative merits. It keeps a catalog of shops with their Item types and can return to buy something useful to it once it has the necessary scratch. It retains the locations of hidden treasures it can revisit if its current strategy is wealth acquisition, and it knows where the ATMs are so it can deposit its loot. It can potentially assist human players with directions, or bring them food or water if they're without — I'm thinking of implementing an Alpine Rescue Dog who can bring supplies to stranded players and guide them out of mazes. Yes, it'll have a barrel around its neck. The barrel was previously doable — now the rescue is, too.

There are some nuances to manage. One obvious one is that in TriadCity, Room Relationships aren't 100% reciprocal. Certain mazes are especially problematic, where if you enter a Room from the East, returning to the East doesn't necessarily take you back to the Room you originated from. Sneaky us. So there’s an impedance mismatch, where Neo4j Relationships are reciprocal by definition, but TriadCity reality isn't always so. Also, of course, the mazes change. The solution we've implemented for now is to simply not persist maze graphs, although that's not particularly satisfying. More thought required. A perhaps less obvious problem is closed doors. If the bot finds an exit West, and tries to move through it, but the door is closed, we have to parse the failure message — "Perhaps you should open the <thing> first?" — and delete the Relationship. The ugly problem is that "Perhaps you should open the <thing> first" can apply to either doors or containers: "Perhaps you should open the refrigerator first?" We can try to disambiguate by keeping a cache of the last several commands, doing our best to figure out whether a move succeeded or not. But Threads are our enemy here, where events and messages are pushed to us from the server, and the Thread driving bot behaviors doesn't stop for 'net lag. The danger is that the graph could become garbled if the bot fails to recognize that while it intended to move, it in fact did not. We address this today by periodically walking the bot to a known location; if that traversal fails to arrive at the expected Room, we delete the portions of the graph that were added since the most recent successful walk-back, and begin graphing again from wherever we happen to be, with the hope that before long we'll meet up with Rooms we already know, and can link the new graph segment to the old. Not entirely pretty, and we're open to suggestion.

None of that is Neo4j's fault. The graph db is a stellar addition to our external AI. It lets the robots "think" similarly to the ways humans do.

Here's how one of our bots thinks of Sanctuary Island, the exact geographical center of the City. Experienced TriadCity players will note that its north and south poles are reversed. But that doesn't matter at all from the bot's POV. The point is that it can now easily return to the Temple of the King to level, or the Fountain to refill a canteen, and so on. This image was generated by Neo4j's built-in graph visualizer, which is pretty spiffy:

Embedding Neo4j this way was again extremely simple. One class, a few dozen lines of code, easy-peasy. My one complaint is that Cypher, the Neo4j query language, has been a moving target. The change which tripped me up is related to revised indexing schemes which first deprecated, then eliminated Cypher constructs such as "START". The first edition of O'Reilly's Graph Databases is out of date; the one I've linked to should be current. These syntax changes cost me some Internet research. Time to buy the new edition.

I'll close by noting an interesting possible future enhancement, now that we have Neo4j embedded with the robot code. Seems the perfect platform for implementing decision trees. The bots I’ve been describing are rules-based, via Drools. Enhancing their decision-making realism via decision trees is attractive — I've long planned to explore this idea for modelling addiction in-game. Perhaps our external bots will be the prototype platform for this type of AI. Watch this space.

[Addendum 2016.05.21: view of Sanctuary Island and part of the Northwest Third from space. Doesn't this graph look like a three-dimensional sphere — a universe?]

Neo4J graph