Article

The Easy Way to Solve Hard AI Problems

Alex J. Champandard on July 5, 2007

Programming generally isn’t easy, but AI algorithms can be particularly difficult. Some that spring to mind are:

  • Exotic neural network training algorithms like RPROP

  • Path-finders in dynamic graphs like D*

In fact, most forums on game AI have posts from students struggling to implement A*, and the #ai channels on IRC regularly witness enthusiasts battling with neural network code.

Sadly, you’ll rarely find what you’re looking for there… not only that, you’re not helping yourself either. Instead, if you can find a solution alone, without relying on an expert, you’ll grow as a programmer.

What’s Really the Problem?

So how do you solve these difficult problems? Look at it this way:

“If you’re having trouble implementing a well known algorithm, then the problem isn’t your code, it’s your methodology!”

Very often, with the pressure to solve a problem, you end up so focused on the end-goal that you cut corners. Most of the time things work out fine. But when you get stuck, try taking a step back and understand that there’s something wrong with your approach.

How do you do that in practice?

Behavior Driven Development

Essentially, BDD is a methodology to help people with any level of experience solve problems like experts, though it might take them a bit longer. In practice, BDD is a rebranding — and slightly improved — version of test-driven development. You can read more about it at behavior-driven.org.

All you have to do is make small but conscious steps towards the goal, and build up your experience incrementally with working code at every stage. Using a test-first approach forces you to break down your problem into chunks you can understand (rather than implementing 1,000 lines of AI code and just praying it turns out ok.)

You write down assumptions as tests, and use a test framework to keep checking them automatically. So, most significantly, BDD helps you make steady progress instead of getting stuck at a certain level of complexity. And that’s ideal for AI algorithms — particularly production code.

No Excuses!

There are a bunch of test frameworks for your C++ code, so you can get started very quickly with test-driven development. All you need to do is make it very easy to create new tests.

#include "TestFramework.h"

TEST(Math, Addition)
{
    int a = 4 + 1;
    ASSERT_EQUAL_MESSAGE(
        "Summing up two integers failed.",
        5, a);
}

Here’s a CppUnitFacade you can use to do this: CppUnitFacade.zip. Just include the header, add to implementation to your project, and link against cppunit.

Going Further…

One particular thought should spike your interest; if a beginner in AI can use better methodologies to achieve the same results as an expert (but slower), then what would happen if experts started using this approach too?

The answer is improvement in quality of the code, better algorithms, and generally a much healthier approach to software development. And this habit is spreading, even in the games industry. (I’ve been using forms of behavior-driven development for three years now and it never ceases to amaze me how things just work out.)

So, do you use tests to implement your AI code?

Discussion 0 Comments

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!