Working NLP on Morrowind dialogues

Jan 21 2019. Written by brainific

Morrowind, the third installment in the Elder Scrolls series by Bethesda Softworks, is an epic fantasy action RPG with an incredibly alien setting and a complex narrative. It includes a sheer amount of in-game content texts, describing past history and current events in minute detail, even including conflicting accounts of critical game events of, really, historical importance. With twelve joinable factions, plus a few better hidden ones, there is a huge number of quests to take, some locking away other choices. What is more interesting, both main and side quests includes lengthy dialogues with different NPCs about a whole range of topics, both quest-centered and background. Maybe its graphics are not as flashy as the latest games, but its story and setting still beats a lot of them by far.

Poor Fargoth lost his stash because of you

During FDG18, we approached Judith van Stegeren, a (now friend of us) researcher interested in text generation in games and well versed in formal methods. It happens that Morrowind is also a favourite of Judith, so we decided to share some common NLP code with her to extract and analyze dialogues in the game. Let’s start with the basics.

Extracting dialogue from Morrowind

Both Fallout and Elder Scrolls games by Bethesda use a format called ESM to bundle the scripts and contents used in the game, as well as a few more. Modders provide new ESM files, often (but not always) created with Bethesda’s own toolkits, that bundles quests, NPCs or terrain features, to name a few categories. In the case of Morrowind, we can use the Creation Kit included (available here for the Steam GOTY edition) to dump all the dialogue lines in the game. After starting the tool, we must load the Morrowind ESM file:

The Object View window allows us to inspect and modify different objects in the game, like ingredients, books or NPCs:

By double-clicking an NPC, we can inspect their dialogue. The Dialogue items are well explained in this article. They are presented in response to topic selection in the dialogue box, according to a list of rules evaluated in order from top to bottom each having up to six slots for functions or conditions. Conditions can check quest progress or PC identity, among others.

But we are, in fact, interested in exporting all of the dialogue. To do this, we use the File menu in the main window, selecting the Export Data option. As you can see, we can export other object classes with dialogue like books. The resulting file contains all the items in the dialogue window separated by tabs.

POS tagging and WordNet analysis

Now we need to get some NLP tool to work with. In this case we will use the widely known NLTK Python package, including Stanford’s CoreNLP Java implementation. First, we will need to install NLTK itself, as shown here, and then load the packages we want into NLTK, as described in this other page. The CoreNLP server starts an HTTP server that will process requests received on a configured port, and NLTK handles the communication for the user.

Using Stanford’s CoreNLP we can perform POS tagging. We will use the grammatical category to select the verbs and cluster them in a tree using the existing categories in WordNet. The idea is to try and analyze the semantics with a double purpose:

  • Separate mechanics from “flavour” verbs. We want our agents to understand and use in-game actions using verbs, like in “I believe that Fargoth will attack you if you find his stash” (a sentence that can be formalized with a slightly more complex logic than Dynamic Epistemic Logic). But, at the same time, we want to add evoking background content that does not tie into mechanics, e.g. describing Fargoth’s family or raising.
  • Find useful mechanics that are described by semantically related words. Verbs like “give”, “take”, “lend”, “buy”, indicate a “property” mechanics, possibly augmented with the possibility of changing the property of an object, maybe in exchange for other goods. The amount of times these verbs appear in the dialogue might also give us an idea of how important they are in terms of mechanics.

But first we need to convert the exported files into a proper Python object. The code we have used for these examples is stored in a git repository for you to use freely. The items are strings separated by tabs, so a simple split will handle the values. The DialogueItem class takes the list of strings from the split and organizes the values for the dialogue item configuration.

def read_items():
reader = MWDialogueReader('csmwinddial.txt')
f = open(reader.fname, 'r')
ditems = []
for line in f:
terms = line.split('\t')[:-1]
for i in range(0,len(terms)):
terms[i] = terms[i].strip('"')

Once we have all the dialogue items, we only need to extract the lines from each one and use a POS (“part-of-speech”) tagger to obtain the grammatical category for each word. In this example, we will focus on verbs, passing them to the next stage.

parser = CoreNLPParser(url=''.join(['http://localhost:', str(nlp_port)]))
lemmatizer = WordNetLemmatizer()
for sentence in parser.parse_text(parag):
postagged = sentence.pos()
for (word, categ) in postagged:
if categ.startswith('V'):
words_per_category[categ].add(lemmatizer.lemmatize(word.lower(), pos='v'))

For each word, we will obtain the WordNet categories associated to that word. WordNet provides a hierarchical semantic classification where the meaning of a word is increasingly narrower in each step. For example, “obtain” (come into possession of) is a specialization of a general “get” meaning (come into the possession of something concrete or abstract), different from, for example, “accept” (receive willingly something given or offered). These meanings will be combined into a tree formed by these specialiations. However, manual intervention would be needed at this point since the specific meaning from the set of possible options is probably difficult to extract automatically. Part of this tree is reproduced as an example.

"accept.v.03": [
"give an affirmative reply to; respond favorably to",
"agree.v.02": [
"consent or assent to a condition, or agree to do something",
"permit.v.01": [
"consent to, give permission",

While avoiding explaining the complete output format, we can see that “agree” and “allow” are present in the game dialogue, possibly with a more specific meaning than the parent term “accept”, also present. It is then up to the designer then decide if these verbs can be tied to a game mechanic, suggesting some kind of negotiation actions whereby a proposal or a piece of information is presented for either allowance or agreement; or is just part of some narrative text presented to the player but not represented in the game mechanics.

We hope that you liked this short introduction to NLP tools for game dialogue analysis. Further articles will delve into mechanics for negotiation and belief for game agents, as well as additional language tools. Stay tuned!

Filed under Uncategorized
Tags: , , ,

Brainific present at EXAG 2017

Oct 24 2017. Written by brainific

Brainific has succeeded in presenting some exciting technologies in the Experimental AI in Games workshop within the AIIDE 2017 conference. We have presented work on our Action Framework (described initially here and here) as a demo, as well as a short paper on Dynamic Epistemic Logic and how it can be used within the design of a game. Our two contributions were broadcast via Twitter:

We expect to continue our collaboration with academia in our goal of successful technology transfer to mid- and small-size studios. Stay tuned!

Filed under Uncategorized

The noncombatant character

Jan 25 2017. Written by brainific

The pilgrim walked down the hill to the entrance of the cave. A couple of bandits with steel shortswords guarded the entrance. One of them unsheathed its weapon after hearing the creaks made by the leather boots. The other followed after a brief moment.

“You vagrant! Get lost before we skewer you and roast you for dinner!”

The pilgrim shrugged and sighed.

“Sorry… I thought I could take a shortcut to the castle. The lady down the road doesn’t want to mingle with dusty pilgrims, either.”

“Lady down the road? What lady?”

“A lady with flashy clothes and shiny bracelets. She was travelling with a bard and a couple of maids.”

The eyes of the bandits opened, and one of them almost dropped his jaw.

“Come on, Krook! Let’s warn the boys and deal with this lady! But lock the cave door first. We don’t want the filthy pilgrim to take our fine jewels, do we?”

The pilgrim waited for some moments after the bandits had run away, and unlocked the door with a whispered spell. He sighed; it was seldom so easy. Lady Bertha and her goblin-summoning spells would prove a match for the rogues, and her tanks in magical disguise would keep her safe. But the band of heroes would be delayed long enough for him to take the spell tome from the bandits and claim the prize all for himself. He just hated the hassle of combat.

Current online games are all about combat, and a not so smart one after all. We have heard long discussions about the holy triad of tank, DPS and healer and how to handle aggro in mobs. It is a pity that role playing games need to restrict themselves so much that these meager concepts are all that is left from the wealth of fantasy and imagination poured on these games.
The paragraph above represents an example of a more interesting and combat-less scenario. The player contacts some bandits who hold a quest object coveted by two parties. In all online games we can think of, the only real choice would be how to execute the bandits. But here at Brainific we think that it should be possible for the players to take other routes, in a similar way as Deus Ex allows. The pilgrim tricks the bandits into choosing another prey, and takes advantage of this situation to take the quest object alone. All this without a single drop of blood (spilled by him, anyway) and a single Open Locks spell. But what wondrous piece of automated logic could possibly enable this scenario?

Natural Language Processing

The first piece in the puzzle is Natural Language Processing. NLP is a very broad area, covering many difficult and complex (as in EXPTIME complexity) problems. Not so recently, IBM’s Watson has cracked quite some nuts dealing with natural language in different areas. Regarding games, restricting the domain may be the answer. After all, we deal mainly with conflict in RPG games, so we can leave out entire language areas. In Brainific we are exploring the content of Morrowind with Stanford’s CoreNLP and NLTK packages to see what subsets are enough for fantasy RPGs.

Natural Language Generation is also a useful technique. Even if the content to deliver is the same in different situations, different phrases, structures and slang can be used to render them unique, akin to “color schemes” in stereotyped characters. This could also provide stereotypes to guide the human player’s actions, in an unfortunate reflection of the real world.

Unfortunately, to be able to say something interesting we need some kind of formal language to which our language can be translated. That is, the listener needs to build a model of what the speaker is saying. Richard Montague tried to tackle this problem using a higher order logic system with modalities and other mechanisms, called Montague semantics. This problem will lead us into the following technical area that we need to tackle.

Modal Logic

The term “modal logic” encompasses whole families of logics that use predicates relating other sets of predicates (at least, in one of its interpretations). Human thought is complex enough to incorporate at least several modalities:

  • Temporal: reasoning about the past, or what could happen in the future.
  • Dynamic: reasoning about what becomes true after performing an action.
  • Doxastic: reasoning about beliefs, that may or may not correspond to the real situation.
  • Multiagent: reasoning about what other people are thinking (yes, this includes what they think we think and what they… well, you sure get the point).
  • Public announcements: reasoning about how one’s knowledge changes after hearing statements from other agents.

These logics often use a “possible world” semantics, where a logic proposition evaluates to true or false if some or all of a number of related “worlds” (those reachable by the modalities’ accessibility relation) hold another proposition. For example, a temporal logic may have a LATER(P) operator that holds true if P is true in the future (which is definitely another “world”). The logic used in these worlds is usually propositional or first-order logic. However, current logic tools (which mainly amount to production systems) in games and other sectors can hardly manage first order logic, let alone modalities.

Agent Communication Languages

Although they were initially designed for machine-to-machine communications, and they are almost 15 years old, the FIPA ACL specifications contains a library of communicative acts that is fairly complete, and contains a semi-formal description of the expected changes in the listener’s mind when certain acts of speech are used. This description can be used to infer the changes in the listener’s minds. For example, we can find a definition for a communicative act of “agree” in <here>:

<i, agree (j, <i, act>, φ))> ≡
<i, inform (j, Ii Done (<i, act>, φ))>
FP: Bi α ∧ ¬Bi (Bifj α ∨ Uifj α)
RE: Bj α
α = Ii Done(<i, act>, φ)

where RE stands for “rational effect” (a sort of desired postconditions) and FP stands for “feasibility preconditions”. The whole definition means that “agent i agrees before j to execute act only if φ is true before”, and that translates into “agent i informs agent j that agent i INTENDS to do action φ

As we can see, the FIPA ACL primitives relate to Searle’s speech acts, and use the BDI logic framework that comprises modalities addressing beliefs and goals. In our opinion, the BDI logic used in the FIPA standards lacks a proper formalization and theoretical support. Also, temporal aspects or dynamic epistemic aspects are not properly modelled in the standard. Lastly, FIPA ACL is oriented at cooperating agents, and so does not cover such “relevant” interactions as threats or manipulation.

Planning Algorithms

In its broadest sense, an exchange of phrases can be thought as a turn game in which each player must maximize the return of their actions. In the described case above, the bandits realize that they gain nothing by staying there and punishing the pilgrim, and instead take the action of running to the travelling lady to relief her of her riches. As we have explained in our previous section, this action becomes “enabled”, or ready for selection, since a new object appears in the bandits’ minds to which the “rob” action can be applied. The use of planning algorithms that maximize a benefit from a certain initial state by selecting the appropriate actions are clearly useful techniques for an exciting and intriguing conversation in a fictional discussion. Some actions (sensing actions) even allow the user to probe its surroundings and further refine their plans. Academics like Thomas Bolander or Jan van Eijk apply modal logics as described above (mainly dynamic epistemic logic) to planning in the hope of devising more powerful planning algorithms.

Planning can also be useful for NLG. Even though many NLG systems use generative grammars, like Tracery, there have been some experiments applying proven planning algorithms to language generation. These algorithms, as opposed as purely generative systems, can keep a “goal” state to guide the language generation.

Fiction or live action?

As promising as the theories and technologies described here may sound, state of the art tools hardly implement any of them. Scripts, chatbots and simple planning are still used or considered top-notch in current games. Here in Brainific we hope to research existing tools and develop new ones to expand the limits of tomorrow’s narrative games. Stay tuned!

Filed under Uncategorized

Twisting your trees

Sep 8 2015. Written by brainific

In the previous post “Introducing the Action Framework”, we presented a separate architecture where behaviours act as reactors to the current state of the game. This allows active behaviours to run synchronously and quickly, moving the more “deliberate” processing to a separate thread or fiber. But how do we select our behaviours? FSMs, trees, planners, as discussed previously?

(UPDATE: the previous post not only owes to the CERA architecture, as we will see later, but also Carle Côté’s article on “Reactivity and Deliberation in Decision-Making Systems” in the Game AI Pro book. Browsing this title has also shown that the choice of title, as well as some inspiration, has been drawn from Bill Merrill’s article, “Building Utility Decisions into Your Existing Behavior Tree”.)

Trees for Funs

In the last, recent developments in behaviour trees arose a number of comments from the attendants about how nodes in a behaviour tree are becoming more similar to functions in a more traditional programming language, and why there was not more general programming support in behaviour trees. After some thinking, we believe that general programming languages are far too complex and varied to be useful as they are. Some sort of constrained, simpler execution model would be much more useful to AI programmers (that can build more powerful tools themselves if need be) and AI authors (that do not need to learn several programming languages to come up with sensible AI). But we also believe that a good model for behaviours need not mimic any of the existing constructs in programming languages. Why and how? Let’s take a look at the current approach.

From Trees to Sprouts

A behaviour tree in many current tools looks like this:

Original behaviour trees

You can see active nodes in green, and non-active nodes in red. This might seem enough at first. However, we have realized that separating the specification data from the runtime data provides much more flexibility at little cost. We can visualize this separation in the following drawing:

Separated behaviour trees

Effectively, we have a specification part, that tells us how new nodes are generated in the runtime part; and a runtime part, that looks suspiciously similar to a function stack (and it works as one, as well; but there are some differences). Note the word “generated”. New runtime nodes are instantiated from the parent node, which is in turn an instantiation of some kind of “prototype” node, or a lambda, or a factory. In our case, a sequence node inserts itself in the runtime tree, and spawns another node as a child.

The important point is that the structure does not need to have a one-to-one correspondence to the runtime node tree. It only generates this runtime tree using some rules. In the following examples we will use mainly Haskell to illustrate these rules and they way we can twist and enrich them, but many of these mechanisms can be implemented in other languages  (albeit much less succintly).

Before jumping to an example, let us be honest: this is not new at all. Whether consciously or by chance, we are replicating the mechanisms sketched by Mateas and Stern in their article “A Behavior Language: Joint Actions and Behavioral Idioms” about the tools used in their game, Façade. The authors even speak about generating appropriate behaviors according to preconditions, so basically they are unifying behavior trees and some kind of hierarchical, no backtracking, contingent planning. One of the differences is that we have separated the behaviour active part from its planning part. Once a behaviour becomes active, it reacts to everything coming from the game world, until the planning layer removes it from play. Even if this means skipping a couple of frames when thinking what to do next, behaviours become simpler to understand: if the state is like this, we do like that. When some conditions are met, then we think for a frame or two what is the next action, change the active behaviors after acting for the frame and off we go again.

But let us be even more honest. Not even the idea of separating a lower and an upper layer is really ours. It bears enough resemblance to Raúl Arrabales and Jorge Muñoz’ CERA-CRANIUM architecture for their award-winning UT bot “Conscious Robots”. We think that our only merit here is to streamline both ideas and use an appropriate tool (Haskell, in this case) to better provide these capabilities to a game programmer.

An Easy Patrol

We will illustrate this separation between specification and runtime parts in an example. Our first task will be to specify a patrol behaviour. With the current state of the art, one would draw a sequence tree, with some kind of “loop” modifier since we need the patrol to run forever. If the patrol fails (by, say, spotting an enemy), then an alternate tree will spawn that activates behaviours for chasing and shooting the target. It would look something like this:

Patrol tree - Mk1

Our first issue is that, after the chase, we want to start the patrol, but not starting in the first point in the specified patrol, but instead in the closest point to the patrol. Repeating the patrol from the farthest end would not look very intelligent, right? So we modify our tree to look something like this:

Patrol tree - Mk2

One issue with this approach is that the runtime view now differs from the specification view: whereas the specification view says “move to the closest point” (and needs to check the blackboard), the runtime view knows the point towards which we are heading, and it will not change. Current behaviour trees can cope with this situation with little changes.

But we want to make our game much more flexible. Take into account that, even if we move to the closest point in the patrol, we need to specify where in the patrol we start. Now our sequence node needs to have some additional list-specific code that modifies the sequence. The separation of specification and runtime views comes in handy at this point.

Instead of moving to a predefined set of points (first go to XaYa, then to XbYb…), we want to specify these points at runtime. As we said, the specification view will handle node spawns (or factories) whereas the runtime view will always handle proper nodes. The specification can say, “this node spawn will take a BlackBoard and issue a Sequence node holding the shortest prefix of the patrol list”. However complicated we want to make the specification, it will nonetheless will be a Sequence node spawning MoveBehaviour nodes at runtime. The specification and runtime views would look something like this.

Patrol tree - Mk3

We will make a function (or a factory, or whatnot) that returns a sequence node using a BlackBoard:

data SeqNode = SeqNode NodeId (forall n. (Node n) => [n])
type seqNodeSpawn = BlackBoard -> SeqNode
patrolPoints = [(0,0), (3,3), (8,8), (10,10)]
prePatrolNodeSpawn = runFromCloserSeqNode "prepatrol" patrolPoints
cycleMoveNodeSpawn = runSeqNode "patrol" $ moveSpawnList $ cycle patrolPoints
patrolNodeSpawn = runSeqNode "complete_patrol" [prePatrolNodeSpawn, cycleMoveNodeSpawn]

You can find all the source code in bitbucket; please take into account that this is WIP, and is appropriately dirty and badly structured for the moment.

(Haskellers out there: the definition of the SeqNode has some complexities that we decided to leave out. For the complete datatype specification, using a “generic node” that holds the specific type of the type class and that performs the polymorphic action, refer to the source code . A profane probably understands it better like this.)

The “runSeqNode” spawn creates a sequence node from a blackboard. It takes an ID and a node spawn list (note that each node spawn will create a node from the data in the blackboard and insert it in the runtime tree under the parent node). One interesting feature in Haskell is that we can easily use and handle infinite lists: the cycle function takes a finite list and repeats it to make it infinite. One drawback is that we can no longer write the list of children, but instead we need to make “event runs” or “event traces” an inspect the runtime trees they create. The auxiliary function “moveSpawnList” takes a list of positions and turns them into Move behaviours for those positions:

moveSpawnList posList = moveBehavioursList
moveId = (++) "move-" . show
moveBehavioursList = map (\x -> runBehNode (moveId x) (moveBehaviour x)) posList

The “runBehNode” spawn, as expected, creates a behaviour node with an ID and an associated low level behaviour (see our previous post and remember that behaviours are properly reactive, always-on actions that produce actions with each frame).

In our second approach, we needed to find the closest point in the patrol list. How would we do this in this “separated” framework? We need a move behaviour spawn that creates a runtime node depending on values of the BlackBoard:

runMoveToCloserNode id posList (mem, bb) | length posList > 0 = (runTree, behaviours)
BlackBoard _ _ _ curPos _ _ _ = bb
    runTree = Node (GenNode $ BehaviourNode id) []
    closeList = [(p, d p curPos) | p <- posList]
    d (x1,y1) (x2,y2) = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)
    (closest, _) = foldl1' (\tmin@(pmin,dmin) t@(p,d) -> if d<dmin then t else tmin) closeList
    behaviours = [moveBehaviour closest]

We fold the values of (un-square-rooted) distances to find out the closest point, and then issue a behaviour move with the right point. Finding out the prefix is somewhat more complex, but equally compact:

runFromCloserSeqNode id posList env@(mem, bb) | length posList > 0 = (runTree, behaviours)
BlackBoard _ _ _ curPos _ _ _ = bb
    d (x1,y1) (x2,y2) = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2)
    pointSubListDistList = unfoldr (\x -> case x of [] -> Nothing; l@(p:xs) -> Just ((p,l,d p curPos),xs)) posList
    (closest, closestSubList, _) = foldl1' (\tmin@(pmin,smin,dmin) t@(p,s,d) -> if d<dmin then t else tmin) pointSubListDistList
    spawnList = moveSpawnList closestSubList
    firstSp = head spawnList
    restSp = tail spawnList
    runTree = Node (GenNode $ SeqNode id restSp) [nextTree]
    (nextTree, behaviours) = firstSp env

We create a list of patrol points, with their distance values and suffixes. We find out the closest point, and then generate a list of behaviours that the sequence node spawn will use. When spawned, this sequence node gets inserted in the runtime tree, running the first move spawn node and inserting it underneath it, and holds the rest of spawns. Note that, at each point where a node needs to handle an event (success or failure), the node accesses the blackboard and generates new runtime nodes with this information.

We now how to spawn new nodes in response to events, but the only event we have now is the “start” event. In a following post we will introduce event handling along the runtime tree, including some areas where the behaviour of the system is still undefined. We will also explain how the separation of specification and runtime trees allows us to handle FSMs more naturally using a common framework, and why the usual “function call” abstraction is not powerful enough to implement this framework. Stay tuned!!!!

Filed under Uncategorized

Introducing the Action Framework

Mar 1 2015. Written by brainific

After watching many behaviour tree implementations and GOAP prototypes, we decided that Brainific could build a tool that takes the best from both, and hopefully allows other interesting structures. As we explain in our previous post, there are some common aspects in them, mainly low level reactive behaviours, and some mechanism to find out when an action succeeds or fails and how to select the next action, that could make this approach feasible.

Layered tastes better

DISCLAIMER: As any work in progress, the architecture of the Action Framework is subject to changes. Please comment as much as you want so we can design the kind of engine you really need.

In the Action Framework, we intend to separate the “planning” aspects of the engine from the “reactive” aspects. Planning can be amortized over several frames and interrupted, even scheduled on a separate core; whereas reactive behaviours need to run very fast and synchronously. So we will fork the “sensory” input when it arrives: one copy will proceed synchronously to the reactive engine and another will be updated in the planning engine. Note that we will sometimes want to act asynchronously on the planning engine, for example to abort the execution of a planning stage that is not necessary anymore. Note also that this separation has been inspired by cognitive architectures.

ActionFW diagram

Apart from a reactive engine and a planning engine, we will add an internal memory that can be accessed by both. This internal memory can be used as a more flexible mechanism where one could use a state machine.

The reactive engine contains two types of reactors: perceptors and behaviours. Behaviours are your bread and butter: they take an input state and output an action, and contain conditions for success and failure. Perceptors, on the other hand, build an abstraction over the purely sensory data, potentially across frames. For example, one can build a “danger” perception that builds up across frames and maxes out when 10 frames pass with health below a 5% threshold. We favor “perceptors” over “sensors” to reflect the structure and high-level function of perception compared to sensation in cognitive psychology. Perceptors can act over internal memory, or send events asynchronously to the planning engine.

The planner engine acts whenever the reactive engine tells it to: either a perceptor detects some kind of “end of action” event (run to point A includes the running behaviour, but also the end condition of reaching point A) or someone adds a goal to be fulfilled (e.g. “remove that soldier”, that can translate into different plans like shooting at him or just distracting him to run somewhere else). The planner comes up with the “best thing to do next” and updates the reactive engine accordingly. A planner could be a utility behaviour selector, a behaviour tree execution, or a planner proper. Its only requirement is to take the external state, the internal memory, the reactive engine state and its own state to come up with a change in the active behaviours. The planner engine will usually work asynchronously, unless the whole current planning stage does not make sense any more. This usually happens when a fundamental behaviour has failed (e.g. when an agent cannot reach point A, the current plan beyond point A is now useless), or there is some more important goal at stake (e.g. throw away flanking plans to come up with a retreat plan when health is low).

Enter Haskell

To develop this architecture we need a language that lends itself naturally to the kind of AI mechanisms we want to use. We need both flexibility and as much speed as we can get. In the end the choice was Haskell.

Haskell is a pure, lazy, declarative functional language with a lot of mileage. The language structure itself is deceptively simple, providing a rich and complex type system (the Hindley-Milner type system, with several extensions available) that catches a lot of errors in compile time. Most constructs in Haskell are either type- or function-related. For the newcomers, this might seem a bit like an outdated Scala. The fact is that Scala borrows some of the features from Haskell, making some compromises with uneven results. Haskell also compiles to native code via LLVM, making it appropriate for some applications (e.g. videogames or embedded environments) where a virtual machine’s stats like memory usage may not be appropriate.

Haskell provides a lot of interesting features:

  • Easy concurrency on several mechanisms (our favourites are Channels and STM transactions) with user threads scheduled by the Haskell runtime
  • Performance on the order of x2 related to equivalent hand-tuned C++ for dummy nonsense applications (i.e. the computer language shootout)
  • Multithreaded execution scheduling decoupled user threads (à la Java Executor, but with preemptive user thread scheduling like in Erlang)
  • Monads that encapsulate side effects, making it easy to know which of your functions can execute in which contexts, e.g. inside a transaction, inside an imperative computation…
  • Advanced compilation and runtime system providing small CPU and memory footprint (priceless for computer games)
  • Backends for several architectures, including… OpenCL!
  • A powerful but relatively complex to use Foreign Function Interface (FFI) mechanism, usable in both Linux and Windows (with some small tweaks)

After passing the point of maximum slope, advancing in the language was fairly easy. The concurrency constructs are clear and easy to use, user threading works just fine, and the compiler gives mostly useful comments, mainly related to typing. But we need to tackle FFI if we want it to be used in production environments. In the next post we will detail exactly how the Action Framework can be used in a Windows C++ project.

Filed under Uncategorized

Behaviours in Games

Oct 22 2014. Written by brainific

Agents in a virtual world need a brain to provide fun to the players: the smarter the brain, the merrier. However, this smartness is bound by two limits: processing power and algorithms. As the game Republique has shown, processing power is not an issue, once the detail is kept under control. On the algorithmic side, there are several alternatives that are now successfully in use, each one with their pros and cons, of course. These are hierarchical state machines (HFSM), behaviour trees (BT), goal oriented planning (GOAP, a variant of the STRIPS planner) and hierarchical task networks (HTN). Our first intention was to provide a comparison of these approaches to highlight their similarities and differences. However, we found two excellent summaries in AI Game Dev and the Intrinsic Algorithm blog that already fill this gap. So, we would like to take a somewhat more academic approach to try and tackle the problem of a unified approach that could cover all these alternatives.

First, we would like to point to the Open Course Ware provided by Professor Daniel Borrajo’s Planning and Learning Group, at the Carlos III University in Madrid. They contain a comprehensive guide to automated planning and related areas that we will discuss in this post.

Behaviour trees and goal oriented planning are, actually, just two parts of a bigger animal: planning algorithms. GOAP is exactly a small example of such algorithms: if you provide them with a goal and a set of possible actions, then they will provide a plan, a sequence of actions that will finally reach the goal. This is commonly known as classical planning, the simplest form of planning. Each action has some preconditions (conditions to be met before the action can be performed) and some postconditions (conditions that will be true when the action is performed). The agent tries some sort of forward chaining (from current situation to goal) or backward chaining (from goal to the current situation) in its “head” to try and find a path of actions that will lead us to the goal. As we are exploring the implicit graph made of states and actions between states, this can take some time. A useful algorithm called A* is used in GOAP to accelerate this task. It is more commonly known as the main algorithm for navigation in a mesh, but it can be used in any kind of graph as long as we have a useful heuristic, an “optimistic” measurement of the distance between any state and the goal. This heuristic must always be less than or equal to the real distance between a state and a goal. In an environment with obstacles, for example, the straight distance between points can be used since any path avoiding obstacles. Finding a heuristic for an abstract graph of an “state space” with actions is somewhat trickier, but there are alternatives like relaxing intermediate steps. Planning can get much more complex in several dimensions (see slide 4 from this set from Stanford), like rich temporal models, durative and nondeterministic actions, or partial observability of the results of our actions.

Any FPS designer will immediately recognize a couple of limitations in this approach. What if we fail in an action? When do we consider an action as finished? Let us approach each of these aspects separately.

First of all, we have said that actions have a set of postconditions. This is not entirely true; they have a distinct set for each possible outcome of the action. Imagine the action of firing: we could hit the target, or we could miss. The outcome is different in each case, and depending on it we may need to take one action or another, and probabilistic in nature, so that the end state depends on the current state, the action and some random number (it is, formally, a Markov decision process). One possible approach is to find the best sequence of actions in average. Yet another approach is to provide contingent planning: instead of finding a sequence of actions, we compute, at least for some paths, corrective actions in case our actions fail. That leaves us with a tree of actions to execute when the main actions fail. That rings a bell, right?

Exactly, a behaviour tree can be considered exactly this: a plan with additional contingent plans on several levels. Of course, we are missing the whole pre- and postconditions parts that enable us to reason about plans. This prevents us from adapting our actions in the tree or discarding branches that we may know will fail. Maybe if we added pre- and post- to the actions and separated the tree declaration from its execution we could unify the approaches. But we will try that out in a later post.

And what about FSMs and HTNs? FSMs are a way of specifying traces of actions with mechanisms that are hard to build into behaviour trees, like recursion. Imagine switching from the alert to the relaxed state and viceversa in a behaviour tree. One of the states must be the parent of the other; adding a third state will further confuse things because we will need to work out an artificial hierarchy among them. We might use sequence and loop nodes to organize actions, but state switching as described here can be hard to express in a behaviour tree.

Regarding HTNs, they also come from the planning domain, as a sort of “hint” to alleviate the computational burden on the planner by specifying some conditions that need to be reached at some steps. Instead of leaving the planner explore all the state space, the designer will mark some spots that the agent has to reach: We do not fix actions in this way, but rather subgoals. If we want to buy meat, we first need to go to the butcher, and then get the meat. The agent can go to the butcher walking, taking a taxi or driving the car, and fulfill these subgoals with different actions (like building a car or hiring a driver to drive the taxi). The specific actions selected for the subgoal may depend on some metric, like probability of success or a utility measurement (e.g. being “green” instead of being fast). HTNs are probably a good middle ground among behaviour trees, GOAP and utility based actions.

In a future post we will try to find some middle ground among all these. Warning! It may include Haskell, graph algorithms and cognitive architectures…

Filed under Uncategorized

Evidence Based Medicine Made Dead Easy – Part II

Mar 2 2012. Written by brainific

The following post describes the specific architectural and software design issues in our EBM demo, framed in the scenario described previously in Evidence Based Medicine Made Dead Easy – Part I. We hope health IT people out there will enjoy this small demo.

Requirements and Architecture

The described system may sit alongside the EHR system. Of course, it will need some integration in the EHR interface so that the doctor does not need to start yet another application. It will further need to understand the data model used in the EHR, to be able to allow the health professional to select the patient info to include in the tests. Finally, it must also provide libraries for numerical analysis, also including parallel, concurrent and distributed capabilities to some extent. A preliminary architecture is shown below.

We have decided to use Python as the programming language in this demo as it is suitable both for prototyping and for deployment in a web server like Django, many connector modules for different databases are available, is relatively easy to use for newcomers, and also includes libraries for numerical calculus and distributed processing. Note that we have not addressed the messaging interface (the dotted box in the architecture).


In the following sections, we will describe the components included in the architecture. We will not, however, address the integration with openEHR’s UI, as it is not the focus of these posts.

Data Retrieval

First of all, we need a way to obtain the patient data from the EHR. In our case, we chose PatientOS as explained in our previous post. In this aspect, the boon and curse of PatientOS is its flexibility. All forms, records and record items are not specified in code, but rather described in rows of different tables and the relations among them. So, we will have to find out which record item stores the information we want.

In our case, let’s assume we store the weight records as procedures in the patient’s medical history. The procedure we will use is 2001F “WEIGHT RECORDED” in CPT, with a freeform string value of “XX kg”, where XX is the weight in kilograms. It seemed a natural place to put this data; however, doctors might decide to use less structured data records to store the visit information. In this case we could think about using natural language processing techniques using e.g. NLTK.

After some research, we can obtain the query that gets the procedures we want for the user we want:

SELECT p.first_name, p.last_name, f.title, fr.value_string, t.term_name, t.description FROM refs, forms f, patients p, form_records fr, terms t WHERE p.last_name='Cave' AND fr.patient_id=p.patient_id AND fr.form_id=f.form_id AND refs.ref_id=fr.record_item_ref_id AND refs.ref_key='PROCEDUREDESCRIPTION' AND t.abbreviation='2001F WEIGHT RECORD' AND fr.term_id=t.term_id ORDER BY fr.record_dt;

We will run this query from Python using Psycopg2 to connect to the PostgreSQL DB used by PatientOS.:

import psycopg2
conn = psycopg2.connect("dbname='patientos_db' user='patientos_user' host='localhost' password='patientos_user'")
cur = conn.cursor()
cur.execute("""select p.first_name, p.last_name, f.title, fr.value_string, t.term_name, t.description from refs, forms f, patients p, form_records fr, terms t where
p.last_name='Cave' and fr.patient_id=p.patient_id and fr.form_id=f.form_id and refs.ref_id=fr.record_item_ref_id and refs.ref_key='PROCEDUREDESCRIPTION' and t.abbreviation='2001F WEIGHT RECORD' and fr.term_id=t.term_id order by fr.record_dt;""")
patients = cur.fetchall()
weights = []
for patient in patients:
    weight = int(patient[3].split()[0])
print "Weight: ",weight
print weights

Data Analysis

Once we have the data in place, we could use any statistical program to analyze them, such as SAS, SPSS, R, Matlab or, in our case, Scipy. Scipy is a Python package that includes many numerical methods. It even allows us to use optimized libraries like ATLAS, BLAS and LAPACK, or distribute our calculations with MPI (e.g. using mpi4Py).

Let’s suppose we have retrieved the weight of two groups of 30 patients at two points in time, before and after the prescription of a drug, which may alter the patient’s weight. One of the groups will be a control group that will not take it, but otherwise (and ideally) have all other independent variables controlled. We will simulate both groups using the following piece of code, which generates two populations with different means for the difference of pre-and post-drug conditions:

import numpy.random
randn = numpy.random.randn
floor = numpy.floor
ttest = scipy.stats.ttest_ind
group1_pre = floor(randn(30,1)*10 + 65)
group2_pre = floor(randn(30,1)*10 + 65)
print group1_pre.T
print group2_pre.T
group1_post = floor(randn(30,1)*3 + group1_pre)
group2_post = floor(randn(30,1)*3 + group2_pre*0.95)
print group1_post.T
print group2_post.T
group1_diff = group1_post - group1_pre
group2_diff = group2_post - group2_pre

Now we will just apply a Student t-test to both populations, and check whether both groups have a different distribution:

(t, p) = ttest(group1_diff, group2_diff)
# Remember we have aliased ttest before...
print (t, p)

As simple as this. Our obtained p is 0.00386893, so it passes a 1% test.

There are many more statistical tests we can use in Scipy: ANOVA, Kolmogorov-Smirnoff… But, furthermore, there are many Python packages that can provide other data mining methods, like Orange or SciKit-learn. Even if you want to write your own, as we may want our statistician to do, Python is as good a language as, say, Matlab, for a quick implementation (and able to run fast too if you use an optimized numerical library).

Filed under medical
Tags: ,

Evidence Based Medicine Made Dead Easy – Part I

Jan 16 2012. Written by brainific


Okay, so it will not be dead easy. We’ll see later the full list of tricks and obstacles we find when trying to deploy an evidence based medicine system in an EHR system in a later post. But hopefully this one will help you realize that data analysis modules can and should be installed alongside an EHR to make clinical research much more agile.

What’s EBM anyway?

According to Wikipedia (and, in turn, to Timmermann and Mauck) evidence-based medicine is about “apply[ing] the best available evidence gained from the scientific method to clinical decision making”. We all thought this was already true, given the amount of clinical magazines out there. However, evidence is not so easy to gather, and leaving out the doctor’s instinct out of the diagnosis is rarely a good idea. Now that EHRs are widespread, we at Brainific think that it is easy and convenient to deploy analysis systems that provide the kind of evidence EBM needs, and present it in a way that doctors can readily work with.

We will use PatientOS as the starting EHR on which to build our decision support demo. PatientOS follows the OpenEHR standard, an open specification for a health information model. An information model specification is more generic and flexible than a data model specification and more concerned about semantics. For these reasons, an information model tends to be more difficult to implement. All the data we handle in PatientOS falls in some Entry category, as specified in the OpenEHR architecture overview. OpenEHR is flexible enough to allow different processes on data, but it does not dig into the issue of how these data can be handled automatically. In our case, we would take Observations and Actions as inputs, and produce Assessments that will be reviewed by health professionals.

This series of posts will explain the use case, architecture, design and conclusions for a simple prototype, showing how a few open source products will allow us to quickly obtain evidence from our own clinical data.

The Scenario

Suppose we have already deployed PatientOS in our health center. We would like to relieve the statistician of so many doctors asking about simple tests, and instead have him focused on researching more robust and avanced ones. So we want our application to automatically retrieve the data the doctors need, and perform some standard test on it that the statistician will have already coded.

One such test will be whether one drug affects the patient’s weight after its prescription. We will use a Student t-test, where we will compare the difference in weight before and after the prescription for prescribed patients against the same measurements in a control group. The null hypothesis says that both groups will have zero difference, that is, that the mean in weight will be the same before and after the prescription. Note that there are thousands datasets in a clinical environment to which the Student t-test can be applied.

The statistician already knows how to code such a test. The IT staff can help him out with the code needed to interface the clinical data. We may use any data that follow its rules, so the statistician only needs to code the test once, and then the IT staff will access the data the doctors need in each specific case. Once the statistician has made its code available, exactly the same process can be applied to any specific dataset.

In turn, apart from all the billing, prescription and data record solutions, doctors may use a small window to interface this application and create a Student t-test. There they can select the data for each patient they want to analyze, as long as it is suitable for the test. The data of any patient can then be included in this experiment as soon as they come to the doctor’s office with a couple of clicks, so a new analysis can be done on the fly after enough new evidence has arrived. It can also be automated so that it runs in the background every nth patient, or even perform tests on other variables the doctor has not thought of, just in case.

The following post will illustrate how such a data analysis server would interface with the EHR system to retrieve the data and perform our statistical tests. We will perform a small proof of concept on a toy PatientOS installation including data collection from PatientOS and statistical analysis.

Filed under Uncategorized

Applications of Artificial Intelligence in Interactive Content

Jul 13 2011. Written by brainific

Brainific aims to provide leading innovative artificial intelligence and machine learning solutions. We strongly think there are different fields that would obtain benefits from their applications. For example, we are aware that fields such as on-demand content, advertisement, streaming media and interactive software are not taking advantage of what artificial intelligence and machine learning can offer.

Due to this reason, here in Brainific we decided to write a position paper in order to create and lead a work group inside eNEM platform.
eNEM is the Spanish Technology Platform dedicated to Networked Electronic Media that takes the European NEM platform as a reference.

We have titled our paper “Aplicaciones de la inteligencia artificil en contenidos interactivos” (Applications of Artificial Intelligence in Interactive Content).
This paper has been accepted and published on the eNEM site for being studied by the eNEM members. We hope that this initiative will attract other eNEM members so a work group can be formed.

Note: the paper is unfortunately available only in Spanish; however it will be translated shortly.

Filed under Uncategorized
Tags: , , , , ,

How to install PatientOS on Ubuntu server

Jul 11 2011. Written by brainific

Here in Brainific we are interested in the applications of machine learning and artificial intelligence in very diverse fields. Our current goal is to find out how these techniques have evolved in e-health since Mycin, and what would be the needs addressed by them. For the sake of experimentation, we decided to test an open source Health Information System (HIS).

We chose PatientOS, developed and maintained by PatientOS, Inc. It is an open source HIS that appealed to us due to several features. First of all, PatientOS relies on well-known open source technologies like PostgreSQL, JBoss or Mirth. This means that both the code and, more important, the interfaces are open, subject to inspection and extenal connections. PatientOS it also seems to be actively pushed in different fora, and supported by a company with a strong background in EMR and HIS. Finally, it follows the openEHR information model, which we think will be important in the future of health IT systems.

As we had some problems to solve in order to install this software in our servers (using Ubuntu), we want to share the installation steps we finally followed. We hope you find it useful.

1. Download PatientOS software


2. Install PostgreSQL

sudo apt-get install postgresql postgresql-8.4 php5-pgsql

change the password of system user created by PostgreSQL (“postgres”)

sudo passwd postgres

Connect to the database and change the password of the admin user, also called “postgres”

su postgres

3. Create a postgre user to be used by PatientOS

It has to be a super user

createuser -P -h localhost -U postgres patientos_user

4. Create the PatientOS data base

createdb -E UTF8 -h localhost -U postgres patientos_db

5. Grant privileges

psql -h localhost -U postgres
postgres# GRANT ALL ON DATABASE patientos_db TO patientos_user;

On next posts we will describe how to configure the PatientOS client to access our server.

Filed under Uncategorized
Tags: , , , , ,