Thursday, December 13, 2012

Finite State Machines and ... Miniatures Gaming?

A word of warning: this blog is basically my way of thinking through ideas, even unfinished ones. I find that I do better writing things down rather than just sitting there pondering, and hoping I remember the good bits later. I hope you will bear with me as I sort through my thoughts and hopefully you will find something of interest and use.
The first AI technique discussed in Programming Game AI By Example (see last blog entry for the reference to this book) is a classic: finite state machines (FSM). In the words of the author, the definition of an FSM is:
A finite state machine is a device, or a model of a device, which has a finite number of states it can be in at any given time and can operate on input to either make transitions from one state to another or to cause an output or action to take place. A finite state machine can only be in one state at any moment in time.
The idea being using an FSM is to decompose an object's behavior (in our case, a unit's behavior) into manageable  states. A simple example provided in the book is probably one most of us can understand, that of the "ghost" in the video game Pac Man. The normal state of the ghost is to "chase Pac Man". However, when Pac Man eats the power pill, the ghost switches from "chase" to "evade". The ghost reverts back to chase mode once the timer runs down and the power pill wears off. The rules for the ghost might look something like this:

rule: if in 'Chase Mode' and 'Power Pill Active'
    then switch to 'Evade Mode'
    else continue 'Chase Mode'

rule: if in 'Evade Mode' and not 'Power Pill Active'
    then switch to 'Chase Mode'
    else continue 'Evade Mode'

The same sort of behavior can be encapsulated for units in a game. This is essentially what I was referring to when I discussed creating and using programmed opponents on this blog. What makes a FSM "better" than the rule-based approach I discussed previously is a matter of organization. The rule base mechanic simply lists a set of rules to follow, in a strict order, and to stop evaluating the rules once you find a rule that applies. What makes developing this rule base complex is setting the evaluation order of the rules. It is not usually impossible to determine the correct order, but sometimes it gets so complex that the gamer decides to forego the whole process and just "play each side to the best of my ability", which after awhile can get pretty stale and predictable.

Put another way, a single rule base evaluates a set of conditions in a strict order. An FSM allows you to evaluate conditions in order based upon the state you are currently in. You can essentially have a set of rules associated with every state.

Sample Game
Okay, enough of the theoretical; you can get that from any book. Let's make this concrete. The image to the right shows the start of a skirmish game. The red player (you) have four units: two Warriors (the groups of eight red circles, on the flanks), one Bodyguard unit (the four red circles in the center), and the Warlord (the large red circle in the center). The blue player (represented by a non-player general) also has four units, but they are Warriors (group of eight blue circles on the left), Levy (group of 12 light blue circles in the center, on the hill), the Bodyguard (four dark blue circles on the right), and the Warlord (large blue-in-white circle on the right).

The player's side is oriented towards melee. In fact, all four units have no missile weapons. The non-player side is oriented towards shooting; all four units have missile and melee weapons, but are weaker in melee than their red counter-parts. The basic blue battle plan is to:

  • Use the Levy and Bodyguard to fire upon and weaken the opposite red unit.
  • When the red unit has been weakened sufficiently, the Bodyguard will charge in with the Warlord and finish it off.
  • The Warrior unit will skirmish with the red units, attempting to engage them sufficiently so they do not go support their unit being attacked by the Levy and Bodyguard, but not so heavily engaged that they become overwhelmed.
For now, I am going to ignore the orders of the Levy and Bodyguard and simply focus on the Warriors. Basically, their mission is to tie up one, and hopefully, to three units. There are three basic states (although this may depend upon the rules you use):

  • Neither in missile or melee range.
  • In missile range.
  • In melee range.
There are all sorts of variations or "sub-states", if you prefer to call them that, but I like to think more in terms of conditions. Rather than having a state for "in missile range of the Warriors" and another for "in missile range of the Bodyguard" and maybe yet another for "in missile range of the Warriors and Bodyguard", etc. I simply treat it as the state "in missile range", with conditions indicating which units that applies to. I can then have rules that list the preferable target in order of precedence.

Range Bands
One thing to note about these example states is that you can visualize them as range bands. Consider a unit that moves 6" and has a missile range of 6". The opponent has a movement of 6" also. Technically, if you are in the Melee band, you are also within the Missile and Move bands. This helps us understand that we need to set an precedence order for checking which band, and thus which state we are (or should be) in: Melee, then Missile, then Move.

So, let's think about this, We start the game in the Move band, i.e. outside of both melee (6" move) and missile (6" move plus 6" shoot) range. The first condition to check is whether the enemy moved and we are now at a different range. To keep it simple (for now), let's assume we have the first move, and the situation is as indicated in the map above.

My basic program is to move towards the closest enemy and get into a position where the unit can fire its missiles, and if possible, move back. If the enemy approaches, the unit is to back off, firing missiles as it retreats. (Note: the basic reason for firing then retreating is because the unit's missile range is 6", the same as the movement distance of the enemy. That means if the unit moves forward to fire, it put itself into Melee range automatically. Thus it wants to back out of Melee range before the enemy unit can react. Your rules may not allow such a maneuver, thus this model will not work for you. The rules I will be testing this with, Saga, do allow this sort of behavior.) One other point might be that where the unit can either move and fire at either the Warriors or Bodyguards unit, it will choose the more valuable unit, the Bodyguards.

As the rules I will be testing this with is Saga, for those unfamiliar with the rules here are the basics you need to know:

  • Each turn the player gets a certain number of dice to roll.
  • Each die rolled indicates what abilities the player can activate during the turn, which includes ordering a unit to take a single action.
  • A unit can be ordered to take more than one action per turn by committing more dice to that unit.
  • The more actions a unit takes in a single turn, the more fatigued the unit becomes.
  • When a unit takes enough fatigue, it is exhausted, and it may not move or shoot until it has rested sufficiently.
This last point brings out another state required in our model: Exhausted. If a unit is exhausted, it can do nothing else before resting. This state will take priority over Melee, Missile, or Move.

Back to our Warrior unit. An ideal turn would be to move forward into missile range (6"), shoot at the enemy, and then retreat back out of the enemy's Melee range (6"), for a total of three actions. As this sequence causes fatigue, a fourth action for resting would make this a truly ideal turn. I can tell you now that committing four actions to a single unit is excessive in most Saga games, so we need to look at the next best option, which is move in, shoot, and move back in one turn, and rest on the alternate turn.

If we put all this into an ordered rule base it might look like:

State: Exhausted

rule: ...

State: In Melee Band (within any enemy unit's movement distance)

rule: ...

State: In Missile Band (movement distance + missile range to an enemy unit)

rule: if not overly fatigued
    then move forward into missile range, shoot the enemy, and retreat out of the enemy's melee range

rule: if overly fatigued
    then rest

State: In Move Band (farther than Melee and Missile bands)

rule: ...

This now covers the basic program of the unit for harassing the enemy with missile fire. We still do not have specifics about how the unit approaches or retreats, or if it fires at the enemy in any specific way (for example, to attempt to kill off a special character like a leader), but we have the basics on how it should act.

As I indicated in the articles on Battle Card Systems and Hand Management, rule bases should be built up over time, rather than trying to do it all up front, at once. I will close this out for now and try and write up the skeleton for the programmed units for this scenario (i.e. all four units) and post them. Maybe then someone else can take them up and play a game with them and provide a critique.

Messing with the rules

40mm wooden Dark Ages Warlord
I have always been an advocate of playing my solo battles "strictly by the rules". In fact, I do not like injecting new game rules in; at best (worst?) I have used dice to apply a personality to the non-player general (NPG) or to determine which course of action to take, but the thought of fudging the numbers in favor of the NPG never crossed my mind.

Recently I started playing Saga, a set of Dark Age skirmish rules (see my review on my Dale's Wargames blog) that have some really interesting game mechanics. As a part of learning rules I typically play a game or two solo, usually by playing the best you can for each side. Probably the absolute worst way to solo game, from an "excitement" viewpoint. It was while playing a learning game yesterday (actually, it is still set up and on-going) that I ran into a situation where I could play a reaction ability against an enemy unit and then I thought "wait a minute, it would be better to react to this other unit". I then realized that the other unit I was going to react to had not declared its action yet; I was reacting to an action my "opponent" (me) had been thinking about, but had not actually done. Put more simply, I was anticipating my moves as the opponent using knowledge I should not have possessed. This is always a problem with solo gaming and "playing the best you can for both sides". This creeps into our solo gaming all the time and usually manifests itself as a bias towards one side or another.

That got me thinking that I need to get back to working on solo gaming mechanics – specifically how to model what the best (?) move your NPG should take – and set aside the campaign ideas for the moment. (Don't worry, I am sure that I will come back to them.) I decided that one way to help me solve this problem was to take a look at what computer programmers are doing for AI in their games. I went out and purchased Programming Game AI By Example, by Mat Buckland.

Solo game with wooden Napoleonic figures
I've just started reading the book, but as I get to the interesting bits I figured I would report it here, and how I might apply the idea to a miniatures gaming AI. Well, it did not take long to hit an interesting bit, which is why I am writing this entry. The author was making the point about academic AI (strong) versus game AI (weak), and that the latter is really about "the illusion of intelligence". The designers of the AI for Halo discovered that their playtesters could be fooled into thinking the game's AI was more intelligent simply by increasing the hit points of the enemy. In one test session they game the enemy low hit points, allowing them to die easily, and 36% of the testers thought that the AI was too easy while 8% thought the AI was very intelligent. After increasing the enemy's hit points, 0% of the testers thought the AI was too easy and 43% thought the AI was very intelligent!

This led me to question my own cardinal rule about changing the game rules for the NPG. In the past, solo gaming had been a vehicle primarily to learn a set of rules or tactics, or to prepare for a tournament (see the work I did on De Bellis Antiquitatis Solus on the Solo DBA Development forum on Yahoo). As my face-to-face opponents wax and wane, especially as I use rules or periods that others are not interested in, I find that solo gaming must become more of an option for personal entertainment. Put another way, game solo or don't game at all. (Well, or game the popular rules, like Warhammer 40K, Warmachine, etc.)

If I did decide to break the rule by altering the rules for the NPG, what might it look like? Would I, for example, give an automatic +1 to the combat roll for the DBA NPG? What would the impact of such an action be? For one thing, it would require that I think and plan my attacks much more carefully. I could not rely as much on "the odds" as they would now be against me. That might certainly sharpen my play and allow a sub-optimal move by the NPG win out. Put another way, it takes the pressure off of making perfect moves for the NPG and allows "good enough" moves to present me with a surprise.

So, what are some of the other ways you can break the rules that lead to a tougher opponent, forcing you to sharpen your game? There are numerous ways to change or add to the rules in the NPG's favor, of course. I am looking for mechanisms that increase toughness, but don't essentially break the game for the player. Increase the challenge, but not the frustration. I would like to hear from you if you have ideas. In the meantime, I am going to keep reading the book and figure out ways to translate the concepts to the tabletop.