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.