Abstract State Machines for Game Rule Specification

Jude has been working on the design of a general board game programming engine. We brainstormed a bit, and I remembered something I had read about a little while ago: Abstract state machines.

An ASM is really nothing more than a formalization of a simultaneous chain of if-then statements. A common example is Conway’s life: given a lattice and a countNeighbors function you could define the rules for Conway’s life as an ASM as follows:

letDie(cell, n) =
  if status(cell) = Alive and (n  3) then
    status(cell) := Dead
letLive(cell, n) =
  if status(cell) = Dead and n = 3 then
    status(cell) := Alive

gameOfLife =
  forall cell in cells do
    letDie(cell, countNeighbors(cell))
    letLive(cell, countNeighbors(cell))

e only thing this is getting us over any type of program specification is the parallelism. But the idea of a list of rules, each of which has a condition and an action, is the right level of abstraction to make a board game engine.

We have to tweak a few things to get it just right. For example, you could have must and may combinators, which specify which moves are available to the player.

Let’s look at Pente. First, we assume a linked-list style lattice, where each cell has eight pointers indexed by direction (they could be abstract or just numbers or whatever), and then a link(direction, n) function gives us the cell in a particular neighbor. Then we could specify pente something like this (Haskellesque syntax now):

move s player =
  if color s == Empty then may $ do
    color s := player
    mapM_ capture directions
  capture d = do
    let oneAway = link d s
    let twoAway = link d oneAway
    let threeAway = link d twoAway
    if color oneAway == color twoAway == otherPlayer player && color threeAway == player then do $
      color oneAway := Empty
      color twoAway := Empty

There are still a few issues to solve as far as expressing “you must do either A or B, then you must do C”. I actually used very little of the ASM model (just one may combinator) in expressing pente. Okay, idea on the backburner, let’s see what else comes.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s