Review
st-icon

No Ifs, Ands, or Buts: Uncovering the Simplicity of Conditionals

Alex J. Champandard on April 3, 2008

Most days, no matter how productive I’m being with traditional programming languages like C++ or Python, you’ll easily draw me into an argument about how terrible they are as tools for creating decisions or behavior of any kind. In fact, most of my musings on this blog (RSS) and my personal research are pushing me in a direction where visual editors meet planning technology.

Along those lines, it’s always refreshing for me to find researchers that have taken similar thoughts down different paths. The work of Jonathan Edwards from MIT’s CSAI research laboratory on a project called Subtext particularly fascinates me.

Subtext provides schematic tables as a way to express decisions (a.k.a. conditionals) that can be edited visually. The interpreter allows changes to be made in realtime and the appropriate calculations happen on the fly so it’s easy to make changes and add features. That’s the theory at least, read on to find out how this stacks up in practice!

Motivation

This research is driven by the belief that there’s a better way to program conditionals than mainstream programming languages offer. In particular, the following arguments can be made:

  1. Plain text ASCII documents are a poor way to specify many forms of logic, including boolean conditionals.

  2. The syntax of modern programming languages makes programmers jump through hoops to figure out what’s really going on.

  3. As a consequence, it’s very error prone and labor intensive to create logical expressions and conditionals in “code.”

In the context of game AI, conditionals are used at many levels in the hierarchy of scripts or FSM to figure out which sub-behavior to pick. For example, when should a certain attack be used: melee, ranged, with/without cover? When is it appropriate to even enter combat? Being able to specify conditionals effectively makes it much easier to avoid bugs when such decisions are programmed.


Figure 1: A schematic table expresses both computation and decisions.

Contributions

Generally speaking, the innovation of this paper is example centric programming — which helps you create code by specifying what it should do in specific cases. In particular, this involves:

  • Using computers to perform boolean calculations to help visualize, create and manage conditionals.

  • Providing a front-end for programmers to express behavior instead of requiring a text editor.

  • Avoiding editing linear programs (as a bunch of if / then statements) to conditionals.

In practice, this is achieved in the following way:

  1. The basic idea is to use schematic tables, inspired by old-fashion decision tables popular in the 60s, combined with function expressions. These can be used as a functional programming language to calculate any value.

  2. Each column in the table contains a set of values for each variable taken into account in the decision. One and only one column may be true at any time, and the result of the column is used as the result.

  3. In more advanced cases, cells in the table may perform full calculations using a function that can be combined into a visual tree, like most programming languages have under the hood…

The editor itself provides many interesting features, including the ability to debug the program in the very same way it’s visualized (like a live spreadsheet), as well as being able to layout tables in visually pleasing ways. Be sure to watch this video for more information on the subject, including an example of calculating attack damage for a typical game.

Subtext Visual Code Editor


Figure 2: Subtext’s visual editor for schematic tables.

Abstract & References

Here’s the abstract for the paper itself:

“Schematic tables are a new representation for conditionals. Roughly a cross between decision tables and data flow graphs, they represent computation and decision-making orthogonally. They unify the full range of conditional constructs, from if statements through pattern matching to polymorphic predicate dispatch. Program logic is maintained in a declarative canonical form that enforces completeness and disjointness among choices. Schematic tables can be used either as a code specification/generation tool, or as a self-contained diagrammatic programming language. They give program logic the clarity of truth tables, and support high-level direct manipulation of that logic, avoiding much of the mental computation demanded by conventional conditionals.”

You can download the paper from the website:

No Ifs, Ands, or Buts: Uncovering the Simplicity of Conditionals
Jonathan Edwards
OOPSLA 2007.
Download PDF (1.9 MB)

Evaluation

Unlike other papers reviewed so far in this Thursday theory series on AiGameDev.com, this research is pretty much a full programming language. Here’s how I think it would apply to game AI.

Applicability to games: 8/10
Games have many special cases, including custom pieces of logic that need to calculate values based on a set of inputs. Whether you use object-oriented programming or not, these are be a pain to create and maintain correctly. The example of calculating damage is only one of many. This kind of system could help resolve these problems.
Usefulness for character AI: 7/10
While this research helps get decisions right by making it easy to build conditionals, it does not help express sequential behavior — which is arguably even more important to game AI. So the ideas presented here would need complementing with some kind of linear scripting system.
Simplicity to implement: 2/10
The down side of this approach is that it’s still fringe technology. Understanding the ramifications of these ideas, building an editor and the underlying interpreter would take a long time.

Discussion

All these ideas may take a while to find its way into game development, but the implications on object oriented programming are very profound. Anyone who’s tried to maintain large hierarchies of game objects will know how much hassle it can be to maintain the logic scattered in multiple places. Schematic tables could help by hiding the underlying complexity — at the cost of some modularity possibly.

A more practical tip for you today would be to use small tables more often to specify decisions, rather than having to build complex trees of unmaintainable if / then statements in your AI scripts. Do you think this is viable or is this a step backwards?

How useful do you think schematic tables and such visual editors are in practice for AI in games?

Discussion 2 Comments

Jare on April 4th, 2008

Wow what a horrible idea. I may elaborate later but the takeaway is: you gain automated verification of logic coverage and you lose pretty much *everything* else that you would want in a production-level programming language / environment. It's a toy with no hope or desire to scale. Call me when they have used that thing to build a 2-million LOC system with reasonable success in terms of engineering, i.e. controlled cost, maintainable, reusable, modular, etc... It's not going to happen because the fundamental philosophy driving its design is utterly wrong in that context. - Good engineers do not reason in arbitrary terms like (!a && (b || !c)) || (a || ...); they use meaningful names and refactor when a conditional statement has more than 3 boolean operators. - Good engineers make and treat things modularly based on what they are trying to do, rather than merging them into a single and monolithic whole just because they happen to share a common condition. That is exactly why the two separate switch() statements in his later example are a GOOD thing.

Hodgman on April 4th, 2008

I actually really (really) like his idea, however, yes it is still just an experiment and not at all ready for The Real World (tm). I'm sure that eventually, programmers will break out of the world of ASCII text-editing, into something more intuitive and focused on the goal, with less room for totally irrelevant errors (missing a brace is not an error with your design or logic, its simply an error caused by having to input your logic using ASCII!) The video presentation had me hooked until he started demonstrating that his solution to polymorphism was basically to just not use it... Re Jare: "Good engineers ... refactor when a conditional statement has more than 3 boolean operators." The point of tools like this is that you're writing in something even higher than your HLL's, so it can refactor your HLL code for you. I'm imagining that in the future of programming, if you're designing high enough in the problem-space, the IDE/language should be able to recommend to the engineer the appropriate patterns/idioms, and/or be able to implement them for the engineer with minimal guidance. e.g. Decide that your factory pattern itself needs some adjustments? You don't have to refactor any code, just redesign the pattern itself and let the IDE write the appropriate code. However, seeing programmers resisted the idea of compilers writing assembly code for them, it's no wonder we're resisting the idea of a tool writing HLL code for us...

If you'd like to add a comment or question on this page, simply log-in to the site. You can create an account from the sign-up page if necessary... It takes less than a minute!