How to implement semi-intelligent opponents for solo-play board game skirmish warfare.
Tabletop gaming has a lot to offer the avid gamer. There's something almost poetic about building a miniature arena with three dimensional figures fighting it out for control. And yet, the requirement for intelligent opponents means playing with a group of others - frequently preferred, but not always possible. You can't play Warhammer 40k by yourself. Dammit.
I believe that you can tailor a board game experience such that you can create at least somewhat intelligent opponents. You see, a computer must go through a process explicitly. You must give it the commands "right turn 90, forward 30". But you can give an instruction to a person like "move towards enemy" and he can fill in the blanks appropriately himself, even if those commands run counter to his goal. So, by collecting complex actions into a single abstract command, you can boil artificial intelligence down to something that can be emulated by what is essentially a flow chart.
Obviously, following a flow chart is never going to create superior opponents to a human mind or even a computer AI, so you'd have to design the game around it. Can't have too many unique charts or have charts that involve too many steps or have too complex processes. But how much AI does a barrel in Donkey Kong require? How much AI does a zombie require? How much AI does a warrior need? Not much. You can compensate for the lack of intelligence through devious level design or innate grouping mechanics (like zombies). This is an approach that must be taken into consider in all aspects of the game design and could probably not be successfully grafted on to existing games.
The following primarily concerns itself with presenting opponents in a skirmish-level game. Something like HeroClix, D&D / Star Wars Miniatures, Heroscape, and what not. It could probably be expanded to squad-based games, or something like that, but keep in mind my goals while reading the following.
Two videogames come to mind immediately (perhaps more if I put some thought into it) of efforts to define AI into a visual, manipulatable concept: Carnage Heart and Final Fantasy XII.
Rather than something like Core Wars or Robot Wars, where one actual programs robots, Carnage Heart has to "programming" robots by creating a sort of flowchart (seen above) by placing chips on a specific sized grid. These chips came in two basic flavors. The first is a single action, where a specific action would be taken and then control would continue on to the next chip in the flow. The second type was a branch, which could move the flow to one of two chips based on the success (or failure) of a specific clause. For instance, the chips with dice on them would do a simple random percentage (like 1 in 30).
Final Fantasy XII had the Gambit system, in which one more or less designed their opponent's AI through a single list of actions based on specific environmental conditions. It's still a flow chart, like Carnage Heart, but with each step, control either continued or stopped. There is no real branching. For instance, if the condition is "Foe:flying", that gambit would be enacted if there was a flying enemy around (casting Aero). If not, control would check the next gambit.
Complex behavior was essentially defined by where in the list a command takes place. In the above image, the character would first try to raise any dead, cure any poison, or heal any ally below 70% - in that order. Failing to do that (as in, no dead, no poisoned, all allies doing fine), then specific enemy actions would be used (flying) with a final default attack against the nearest enemy. Change the order of those gambits and it all breaks down.
A system like this could be easily moved to a boardgame unchanged.
State Machine Flow Chart... With Cards|
Games like Dungeons & Dragons Miniatures already come with cards for each of the units describing things like hitpoints, attacks, special abilities, and what not. I propose that these cards be enlarged and include the AI flow chart on them. The Carnage Heart-style grid flow chart would probably translate quite well, assuming the visual language was appropriately iconic and readable. Basically, each turn, start at the beginning of the flow chart and work your way through it for each unit. It might seem slow at the beginning, but after a few turns, it'll probably be second nature.
As mentioned, commands for these enemies need not be minute and explicit. A human is perfectly capable of interpreting something like "head for closest cover". Likewise, branches like "if unit is near enemy", near probably doesn't require explicitly saying something like "within three squares". Near is near and the player's judgement is probably just fine for a solitaire game. That being said, some people would still probably stretch the definition of rules in their favor, even playing by themselves for fun, so I guess maybe being explicit is required for some states of mind.
One twist I'd add is random branching. Sometimes, you want to vary behavior based on randomness, but if there are several random branches in the chart, it could slow down the game considerably to continually roll dice. Instead, you roll one 20-sided die at the beginning of the unit's turn. Then all random branches are based on that number. For instance, your first branch might be >= 10. Let's say it is 17, so it moves to path A. At that point, you know the number will be between 10 and 20, so if the next random branch is > 15, you have roughly a 50% chance (rather than 25% like it might initially seem). You lose granularity as you go, but design effort should be made towards short, quick charts in the first place.
A second twist is adding states, a classic staple of intelligent behavior. Basically, having multiple flow charts (perhaps printed on the back of the card or on multiple cards) allows different behavior based on which state is active. You might have Fight and Flight states. The Fight state tracks the nearest enemy and engages in combat. If the HP drops below 30%, the Flight state becomes active and the enemy might run away and try to heal.
While most enemies will probably be happy with one or possibly two states, you could create exceedingly complex behavior by increasing the side of the grid and the number of states. A boss-type character may switch between many different states - and since stats would be printed on the state cards themselves, a switch could also represent a change in abilities. For instance, wounding a King Badguy may move him to the Wounded state, which could open up new attacks but also reduce his movement.
This kind of thing should probably be reserved only for boss-type characters since too many battlefield changes could result in a lot of mental bookkeeping. However, state changes themselves (without changes in abilities) probably won't require too much effort seeing as behavior is only relevant during a narrow part of the phase. And since the player's characters have the player instead of a flow chart, only half the units on the board need be done this way.
And of course, the obvious. At the point in which you put explicit reasoning into autonomous units, you've got to let people create their own AI routines. Sharing flow charts that others have created could greatly expand the value and challenge of the game, much like user created maps or units. Simply put, options can be made available for those who like simple enemies to those who want even the smallest grunt to feature a 17 stated 64x64 grid of actions. Give people a way to share these algorithms (and even maps and setups) could allow players to challenge either other without being active participants.
It's a pretty simple idea, and like many of them, it depends heavily on how it is implemented. Make it too complex, or too simple, and the idea fails to deliver. The whole concept of having to learn a dozen or more commands and how the flow chart works on top of the rules of the game already moves this well past simple, but assuming that someone does go to the effort (and there are certainly those who would), hit that sweet spot to make it enjoyable.
I've also got an idea for "automating" another process that has traditionally been done by computers or other players, but it'll have to wait for some other time.