Looking Out To Sea

This is written with the inspiration of Simon Peyton Jones’ talk about pudding combinators. (He may also have mentioned financial contracts.)

Imagine we have a board game, with two opposing sides. To make things easy, this board game only has one type of piece on each side — there are no rooks and bishops and cuddies.

A Strategy is a mapping from the circumstances you find your players in to a move you can make.

type Strategy = Situation -> Direction
type Situation = (Location, [Location], [Location])

The situation for any one piece is its location, the location of the pieces on its side and the location of pieces on the opposing side.

The base Strategy is to not move at all. This is no way to win, so we need to improvise a few strategies. We could move all of our pieces towards the enemy in a mindless deathmarch:

attractfoes :: Strategy
attractfoes (me, _, foes) = attraction me foes

We can do the same for friends (so that pieces can clump together) and with repulsion (so pieces avoid their team-mates, for example).

repelfriends :: Strategy
repelfriends (me, friends, _) = repulsion me friends

Brief diversion: Attraction and Repulsion

So far I’ve assumed the existence of a few things. Some of them you can guess at (eg, Location is just a tuple of x and y co-ordinates). The functions attraction and repulsion need some more explanation. From the given type signatures we can infer that their type is:

attraction, repulsion :: Location -> [Location] -> Direction

The first argument is the piece under study and the second argument is all the pieces it is attracted to/repelled from. Between each pair of locations (pieces) there is a force — either toward or away:

attract, repel :: Location -> Location -> Direction

It seems to me that these should be the “primitives” of this system. (In a sense they are, but not in any formal way. That’s just what these strategies ultimately rely on.) Maybe working up from these functions would reveal a nicer system. (I say “these functions” but really there is only one: each is the negation of the other, so either could be implemented in terms of the other.)

Now where was I? Combining strategies

Assuming we have four simple strategies (attracted to and repelled from both friends and foes) we probably want to combine them. The simplest means is by addition:

(<+>) :: Strategy -> Strategy -> Strategy
s1 <+> s2 = \x -> s1 x + s2 x

Let’s say that s1 is attracted towards enemy pieces but s2 is repelled from them. (This is a silly example, but instructive.) The combinator shown above allows these two urges to neutralise each other — since as I’ve already mentioned, attraction and repulsion are negations of each other anyway.

Of course we may decide that some urges are more important than others. The urge to clump with friends is more important than the urge to avoid the enemy. So we want a scaling system, to increase or reduce the importance of a particular strategy compared to others.

(<*>) :: Double -> Strategy -> Strategy
n <*> s = scale n . s

(The scale function scales a Direction tuple by its first argument.) We can then increase or decrease the importance of a strategy by scaling it:

(0.7 <*> attractfriends) <+> attractfoes :: Strategy

So far we’ve assumed that one strategy is applicable in all cases. This is never the case — there are always corner cases and special situations which we should test for and evaluate accordingly. Let’s say we want our pieces to clump together until the crowd reaches a certain critical point. Then they march out to war or something.

I imagine we would run such a system a bit like the ?: operator from C.

condition <?> consequent <:> alternate :: Strategy

Let’s break it down. The part after <?> is a choice of two strategies, only one of which is applied. The choice is as simple as a tuple of (Strategy, Strategy) — so <:> is essentially an alias for the tuple constructor.

(<:>) :: Strategy -> Strategy -> (Strategy, Strategy)
(<:>) = (,)

The condition is slightly more intricate. What kinds of things would the predicate test? I guess anything that can be determined by looking at the circumstances of this player.

(<?>) :: (Situation -> Bool) -> (Strategy, Strategy) -> Strategy
predicate <?> choices = \x -> if predicate x
                                    then fst choices
                                    else snd choices

The conditional combinator is brand new for this post — I haven’t implemented it in the code yet. So I don’t know how horribly wrong it is! More on that later.

And because my post yesterday was mostly about baking but slightly about Haskell, I suppose I should balance things up by noting that yesterday’s loaf tasted even better this morning. Slightly moister and very tasty. But I’m going outside into the sunshine now!

Trackback URI |