Language 2: HIPE

My connection with Radical started when I interviewed for employment with them. They made me an offer but I turned them down. Nonetheless, they kept in touch and nearly a year later asked me to write a White Paper on what areas of AI to develop further. They were interested in creating revolutionary new AI to take advantage of the increased horsepower of next generation consoles.

The typical game engine uses explicit scripting and/or finite state machines (FSM) to control its AI.

The disadvantage with scripting is that you must explicitly write out every control transition. That is, if under some conditions you want the AI to do X and other under conditions you want it to do Y, you must write all the ifs and all the thens in one place, creating a long nightmare piece of code. And that assumes that you can know, in advance, the one right way to do things. But situations are rarely that simple. Often times you must generate a solution, try it out hypothetically, discard it if it fails, and try another solution. Scripts are not good for that.

FSM’s improve upon the act of writing scripts by providing orderly areas of understandable code to carry out an activity, with explicit tests to decide when to go to which piece of code next. It’s an improvement in organizing code and the underlying FSM mechanism can become shared code among games. Still, FSM’s have no ability to explore hypothetical paths and you must still explicitly code which piece of code to move to next. When FSM's become complex, they still become a nightmare spaghetti-tangle of control paths.

If you want really interesting AI for a game like Command and Conquer -- if you want a system that can figure how to build the next widget by stringing together mining for materials, manufacturing components, defending the transportation along the way, etc, then what you want is a planner. It’s all about how to do something based on what you have or can do.

So I wrote them a paper which started out: This white paper covers the application of planning, goals, drives, emotion, personality, and historical memory to AI in games. What these all have in common is that they provide one of the three things needed to decide what to do next. They provide the bias in the selection of actions. The other thirds are current sensory input and actual capabilities.

Later I wrote: In the last five to seven years, academic planning systems have evolved significantly. Biennial planning competitions started in 1998 with five programs competing. Consequently, planners have been handling ever larger and more complex problems. The original competitions covered pure “strips-based” planning. They were still working on the blocks world in which all facts are true or false. In 2002, planners were pushed into handling time-based domains and numeric-based domains (ones with constraints on numerically-valued variables) as well. In 2004 they added probabilisitic domains and had 19 competing systems. A quote from the results page of that competition: “For runtime performance, the observations to be made are much more interesting and diverse. Indeed, we were stunned to see the performance that some of the planners achieved in domains that we thought were completely infeasible!!”.

I argued that a planning language would become the next High Order Language for AI. Radical agreed.

Build, Buy, or API?

The features of a real-time planner require tight integration and are not suitable as an API.

Planners are not built to the demands of the video game industry. They are strongly academic, written in LISP, with an obscure syntax. The planner operates in an isolated world environment, where it controls all the actions and the world is completely predictable as a consequence. The planner does not pay attention to memory usage issues, takes all the time it wants, and is not prepared to integrate seamlessly into any game engine. So buy was out of the question.

Radical asked me to design one. After that, they asked me to build it -- HIPE. Another name chosen for its marketability within Radical.

HIPE is a totally ordered Hierarchal Task Network (HTN) planner built for video games. As a totally ordered HTN planner, it can be efficient in backtracking and make good use of existing world state. Built for video games, HIPE also allows the planner to initiate real world action immediately, if desired, even before planning is complete.

HIPE is not the first planner I wrote. I did one for my own use early on at 3DO for a galactic conquest type game. If you told it that to have a ship of a particular class you could either build it, or trade for it, or steal it, and that to build a ship required various materials that could be acquired by mining, trading, scrapping, or stealing, then it could discover for itself that in some situation where it desperately needed a class of ship, it could go steal an enemy ship, scrap it, and build a new one. But that planner could not do lookahead and was designed for a turn-based game. HIPE had to go way beyond that.

A complete plan specification contains three parts: the model, the logic, and the problem.

The model is the definition of the world: what entities the world contains, what acts can be taken, and what effects those acts have. The model is a common shared ground in which acts can take place. It does not specify how or why useful acts arise. The model may either be a complete self-sufficient world (all information can be found within the planner's internal world model) or it can interface to an external world (in which case some information may come about as the result of queries to that external world).

The model consists of these things:

1. user-defined types (categories of objects)
2. objects in the world
3. numeric constants
4. events that can happen asynchronously, arising from the game engine or plans
5. priorities that can be used to reorder plans according to different criteria
6. how objects are described (object attributes and relations among objects)
7. external functions available from the game engine or simulator
8. allowable acts supported by the world (acts change the world)
9. interrupt functions that can respond to events independently of a plan

The logic defines how to reason with the model to accomplish something useful. The logic consists entirely of plans and acts (descriptions of things to do if certain conditions prevail, so as to achieve an effect that will typically take many actions over time).

Acts are atomic actions. Plans are composites of plans and acts.

The problem is the current configuration of the world and the future configuration you want to accomplish and/or the particular goal or goals to achieve.

The initial demo scenario Radical proposed was a “Zookeeper” problem. Given a zoo with a couple of exits, two cages, and some random placement of chickens and foxes, keep as many chickens and foxes alive and within the grounds of the zoo as possible. Animals slowly move toward their nearest exit (if not caged) but if a chicken is within small range of a fox it will back away from the fox and if a fox is in somewhat larger range of a chicken, it will make a beeline to it and eat it. The zookeeper can move next to an animal and pick it up or drop it (including into a cage) or stake it (which temporarily immobilizes it until the animal gnaws through the tie to the stake.

So the zookeeper is given this problem, and must control the game engine and save animals. Then for spice, the HUMAN is allowed to arbitrary teleport any animal anywhere at any time and watch the zookeeper suddenly have to change behavior to still save as many as possible given the new configuration.

Here is a quick illustration of HIPE script to code Zookeeper.

Type declarations define the organization of entities in the world. Entities can be concrete objects or abstract concepts. You can name specific objects and/or name types as being members of your type. Hence in the code below, is a type consisting of two named chickens. is a type consisting of the type (zookeeper) and the type (chicken1 and chicken2 and fox1 and fox2).

TYPE : chicken1 chicken2
TYPE : fox1 fox2
TYPE :
TYPE : zookeeper
TYPE :
TYPE : cage1 cage2
TYPE : exit1 exit2
TYPE : nothing
TYPE : free immobile escaped

Most types are “obvious”. The type includes all the animals and the “nothing” object, so as to be able to represent the zookeeper being empty-handed. The type is an abstract concept type naming conditions of the animals. HIPE also allows you to declare dynamic types, reserving a range of objects to be created on demand at runtime. So you could reserve room for 100 chickens with only a couple of them having current existence.