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
where
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.
