Our pre-PAX East coverage continues with another of the games made during the Summer 2009 session at the Singapore-MIT GAMBIT Game Lab. Dearth was an ambitious project for the lab, an attempt to create a two-player co-operative action-puzzler which could be played with either two human players or one human player and one computer-controlled character using an artificial intelligence method that does not require a programmer to create AI behavior by hand, but rather a separate program creates the AI behavior based on the game's rules.

The game plays a lot like the old Daleks/Robots game, but with two players instead of one. Each player traverses a maze. They goad the enemy characters into following them, but when two of the enemies are lead into occupying the same square on the maze, they burst, destroying themselves. Or, to use the 'back of the box' language:

Play as the tribal shamans. Force the mysterious water-sucking creatures to smash into each other, allowing stolen water to gush from their engorged bodies and be returned to the land. Plan movements with your partner carefully or be ready to make split-second decisions if things don't go according to plan. The future of the Tribal Lands will depend on how well you work together!

The artificial intelligence method used, a Markov Decision Process (MDP) problem solver, is not new, but until its use in Dearth it was largely untested in the domain of video games. Researchers Leslie Pack Kaebling and Tomas Lozano-Perez from MIT's Computer Science and Artificial Intelligence Lab (CSAIL) and Lee Wee Sun from the National University of Singapore, along with GAMBIT Embedded Staff Andrew Grant met before the student team was formed to discuss exactly what kind of problems an MDP could solve. It was up to the nine-person student team to take this advice and apply it to a video game. Early on it was decided that the game would be the starting point for research into how to use an MDP to solve the kinds of complex problems an AI sidekick would be confronted with.

Without getting too dry on details, an MDP works by taking as input every conceivable state of the world of the game. Meaning for each level, it needs a coordinate representation of where each player and enemy could be. Based on this, the MDP calculates a probability table whereby each possible action is given a score based on how much the action would help the other player (part of the description of the game given the MDP is what actions are helpful). When a human player plays with the AI sidekick, the AI is calculating what move it by looking up on the probability table what action it should take based on where the other player is and where the enemies are. To the human player, they're playing a game in real-time, but if you look at the game from the AI sidekick's point of view, it's a discrete set of moves (turn-based, like chess) but played very rapidly. The difference between this and most AI methods is that the programmers did not code behavior for the AI. The AI character behaviors were created automatically purely by examining the game rules and applying the MDP method onto them. The resulting sidekick AI behavior is unusual, in that it models several strategies that the player could be using, and tries to determine which one is most like the strategy that the player is using.

In the current version of the game, there are four levels that have been tuned to work for single-person (AI sidekick) play. The real meat of the game is in the two-player version, where there are 20 levels available to play with a human partner. The second life of the game is to use the two-player levels to continue to refine the MDP problem solver to solve more and more complex challenges.

As part of our Game of the Week video series, Embedded Staff Andrew Grant gives an explanation and insight into the games' development:

This video is available to watch via YouTube.

Dearth was selected to be in this years' Boston Indie Showcase at PAX East. If you drop by our kiosk at the Boston Indie Showcase booth (#117), you'll be able to see Lead Programmer Alec Thomson impress with his one player, two-handed approach to the two-player game!

Come by the GAMBIT Game Lab's booth (#1119) and bring a friend to play two-player as it was meant to be played: side-by-side on a full-size arcade game cabinet!

You can play this game today, online for free (by yourself or with a friend!):

Tomorrow: Shadow Shoppe!