Infsabot Strategy Part 1
OK, so what is this Infsabot? Infsabot is a game I designed for people to write programs to play. Basically, it’s like chess, except where each piece acts independently of each other.
There is a square board where each square is either empty or contains material. The game pieces, robots, require material to stay alive and perform tasks. At each turn, every robot reports which of the following it wants to do:
- Noop: The robot does nothing
- Die: The robot dies
- Dig: The robot digs to try to extract material
- Move: The robot can move in one of the four compass directions
- Fire: The robot can fire a quick-moving projectile (e.g., travel time = 0) in a compass direction
- Message: The robot can send a quick-moving message in a compass direction
- Spawn: The robot can create a new robot with its own initial material and appearance
To decide what to do, a robot has access to two things:
- A picture of the positions around it, to a given distance
- Whether or not the spot contains material
- Whether or not the spot contains a robot, and it’s appearance (not it’s team)
- A snapshot of its own hard drive, which is a massive relational database between Strings and Strings
- A list of all messages received
Crucially, there is no way to tell whether a robot one sees is on one’s own team or not. This must be accomplished through sending an receiving messages.
A robot strategy can be expressed as a type
type RobotProgramResult = (RobotAction, InternalState) type RobotProgram = KnownState -> RobotProgramResult
To create a baseline for human-written strategies, I am going to use an adaptive algorithm to try to generate a strategy. This basic algorithm won’t take into account any of the “human” factors like messages and internal state.
I will reify the concept of a (non-recursive) robot program by representing it as a long expression tree. The basic concept is something like this:
data ActionType = TDie | TNoop | TFire | TDig | TMoveIn | TSpawn data RP = DefaultRepresentation ActionType | ModifyMaterial ExprInt RP | -- Applies to Fire, Spawn ModifyDirection ExprDir RP | -- Applies to Move, Spawn, Fire, Send ModifyAppearance ExprInt RP | -- Applies to Spawn. RGB treated as a single integer. IfRP ExprBool RP RP
DefaultRepresentation describes a default representation of the given
Modify* modifies the given field, if it exists, of the given action. The various
Expr* types represent expression tree types, given below.
data ExprInt = ConstInt Int | RobAppear ExprPath ExprInt | -- Coordinate; Default if no robot MaterialLevel | -- Current material level Age | -- Current Age (:*) ExprInt ExprInt | (:+) ExprInt ExprInt | (:-) ExprInt ExprInt | (:/) ExprInt ExprInt | Mod ExprInt ExprInt | IfInt ExprBool ExprInt ExprInt | SwitchInt ExprDir ExprInt ExprInt ExprInt ExprInt -- Basically [ExprDir] -- Written like this to make the tree more explicit data ExprPath = Here | Offset ExprDir ExprPath data ExprDir = ConstDir RDirection | IfDir ExprBool ExprDir ExprDir data ExprBool = ConstBool Bool | CanSee ExprPath | MaterialAt ExprPath | -- False if can't see that far RobotAt ExprPath | -- False if can't see that far EqualInt ExprInt ExprInt | GreaterInt ExprInt ExprInt | EqualDir RDirection RDirection | Not ExprBool | (:&) ExprBool ExprBool | (:|) ExprBool ExprBool
OK, so that’s a lot of mutually recursive trees. I’m going to skip the boring implementation of
eval for each of these trees, but here’s a simple interface for that purpose:
class Evaluable given from to where eval :: given -> from -> to instance Evaluable KnownState ExprInt Ratio where -- Evaluates to a Ratio, or fraction, for precision reasons. -- Round to get an actual integer ... instance Evaluable KnownState ExprBool Bool where ... instance Evaluable KnownState ExprDir RDirection where ... instance Evaluable KnownState ExprPath [RDirection] where ...
OK, so to construct some trees. Here’s a simple move and dig strategy that tries to maximize the digginess of a given robot.
digStrategy = IfRP (MaterialAt Here) (DefaultRepresentation TDig) (ModifyDirection (IfDir (MaterialAt (Offset (ConstDir N) Here)) (ConstDir N) (IfDir (MaterialAt (Offset (ConstDir E) Here)) (ConstDir E) (IfDir (MaterialAt (Offset (ConstDir S) Here)) (ConstDir S) (ConstDir W)))) (DefaultRepresentation TMoveIn))
That’s some damn good looking Scheme—ahem, Infsabot Strategy DSL!
Anyway, next time I’ll cover how to generate code in the form of this structure. Hopefully, the computer can do most of the heavy lifting!
Note: I made a few corrections to
digStrategy because it wasn’t exactly compiling.