tokle.us

The hawk and dove game
an agent-based model in clojure

05 July 2014

I was recently thinking that it would be fun to implement an agent-based model (ABM) or cellular automaton (CA) in clojure, so I’ve written a version of the hawk and dove game. We can think of CAs as being defined by a handfulof mathematical functions which are iterated over the cells of a grid. This way of thinking about CAs maps very nicely to a functional programming style, which is where clojure comes in. Thanks to Ben for telling me about the model and suggesting that it would make for an interesting animation.

The game

The hawk and dove game is a version of the prisoner’s dilemma in which a player can be one of two types—a hawk or a dove—which determines their strategy: hawks always betray and doves always cooperate. I’ve implemented an iterated version of this mechanic as a grid-based agent-based model. Each agent is a hawk or dove (and their type never changes) and can choose to play a round of prisoner’s dilemma with one of their neighbors in each time step. Additionally, there is a death-and-birth mechanic: an agent starts with an initial score which is added to or subtracted from depending on the outcomes of the games they play. If an agent’s score falls to 0, they die, but if their score reaches a fixed threshold the agent gives birth to a new agent and the parent’s score is divided between their self and their child.

The agents live, move, play, and die on a 2-dimensional square grid, which is where the CA comes in. The defining aspect of a CA is that the rule to update a cell is a mathematical function of the cell and its neighbors. In a general ABM you can define any sort of interaction between agents, including one that depends on the global state. As we shall see, to implement my model’s update rules as a pure CA requires some indirection.

An agent in my simulation follows these rules:

  1. If you have any neighbors, pick one and play a round of prisoner’s dilemma with them.
  2. If your score is less than equal to 0, die. Otherwise, if your score is greater than a predefined threshold and you’re next to any empty cells, and try to put a child on it. If successful, your score is split between yourself and your child.
  3. If you are next to any empty cells, pick one and try to move to it.

Note that we could define a different ABM based on the hawk and dove game that didn’t make use of a cellular grid. In each time step, we could randomly pair up agents to play prisoner’s dilemma and we could simply leave out any kind of movement. But by placing the agents on a grid, we can look the emergence of global properties from local interactions. And besides, it makes for a better animation this way.

The complete code for this simulation is here. If you have leiningen you can run the simulation from the project directory with

lein run -m hnd.core

CAs as iterated functions

I mentioned above that we can define a CA as a set of functions that we iterate over the cells of a grid. I want to expand on this briefly, because it will make the implementation easier to follow.

Using math notation, let \(G \in S^{n\times m}\) define an \(n\times m\) grid of cells whose values are taken from \(S\). \(S\) is the collection of all possible cell states, e.g., whether the cell is occupied, and, if so, the properties of the agent that lives there. For a cell \(g_{ij} \in G\) we define the neighborhood function \(\text{nbhd}\) which returns the cell neighborhood:

(I should really write something like \(\text{nbhd}(G, i, j)\), because \(\text{nbhd}\) needs to know the dimensions and cell contents of \(G\). However, I think what I’ve written communicates the idea more clearly.) For each step in the algorithm and for each cell in the grid, we call \(\text{nbhd}\) on the cell and we pass the result to some function \(f\) which acts on a neighborhood to produce a new cell. In notation, we define a function \(\text{update}\) by

Then, if we let \(G_t\) denote the state of the grid in the \(t\)th time step we can define

where \(f\) is our update function. In fact, we might want to define several update functions \(f_1, \ldots, f_k\) such that one “time-step” in our algorithm consists of a chained sequence of updates:

This is the approach I take in my implementation.

In clojure

Modeling the implementation after the mathematical description, I represent the CA as a simple map. The following code creates new model instance with a 4x4 grid:

hnd.model> (make-ca 4 4)
{:nrow 4, :ncol 4, :grid [{} {} {} {} {:score 20, :type :hawk} {:score 20, :type :dove} {:score 20, :type :hawk} {} {:score 20, :type :dove} {} {} {} {} {} {} {}]}

As you can see, the grid of cells is represented by a flat vector and each element in the grid is a map. This way, an empty cell corresponds to an empty map, and an occupied cell to a non-empty map whose attributes describe the agent. The make-ca function I called above uses coin flips to determine the initial grid layout. In order to interpret the grid vector as a two-dimensional array we convert flat indices r as two-dimensional subscripts.

(defn ind->sub [ca r]
  [(quot r (:ncol ca)) (mod r (:ncol ca))])

For example, in the output above, the fifth entry in the grid vector (a cell occupied by a hawk) is located in the second row and first column of the two-dimensional grid.

A top-level step in the algorithm consists of three stages, each of which comprises several smaller steps. I mentioned the three stages above: there’s the game playing stage, where agents play a round of prisoner’s dilemma with their neighbors, there’s the death-and-birth stage, and there’s the movements stage. The function that implements an algorithm step is as simple as can be.

(defn step
  "Execute one model step."
  [ca]
  (-> ca game-step death-and-birth-step move-step))

Let’s look at the definition of the movement stage.

(defn move-step
  [ca]
  (-> ca
      (update-ca #(center-propose-action-dir % empty?) :apply-to not-empty?)
      (update-ca center-accept-action-dir :apply-to empty?)
      (update-ca complete-move)))

In the next section I’ll show how this method implements movements. For now, I want to focus on the definition of update-ca, which is really an implementation of the mathematical \(\text{update}(G, f)\) function from the previous section. update-ca takes a model state and a function as arguments. The function argument operates on a neighborhood and returns a cell, which becomes the new value at the center of that neighborhood. update-ca also takes an optional third parameter which is a predicate to apply to grid cells before applying the update function. This is simply to save a few cycles. Let’s look at the definition.

(defn update-ca
  "For each cell in ca satisfying apply-to, call update-fn on the
  cell neighborhood and update ca with the new value."
  [ca update-fn & {:keys [apply-to] :or {apply-to (constantly true)}}]
  (let [ix-nbhds (filter-cell-neighborhoods ca apply-to)
        ix-cells (for [[ix nbhd] ix-nbhds] [ix (update-fn nbhd)])]
    (assoc ca :grid (update-grid (:grid ca) ix-cells))))

Ignoring the noisy syntax for optional keyword arguments, we can focus on the last three lines to understand what the function is doing. filter-cell-neighborhoods applies a predicate function to each cell in the grid. For each cell that satisfies the predicate, it returns a pair consisting of the grid index of the cell and the neighborhood centered at that cell. In the second line, we use a for statement to map the update function over the neighborhoods, which gives us a sequence of index-cell pairs. Finally, we call update-grid to fold the new cell values into the grid.

(defn update-grid
  "Given a list of index-cell pairs, replace the cells in grid with
  the corresponding values in ix-cells."  
  [grid ix-cells]
  (reduce (fn [g [ix cell]] (assoc g ix cell)) grid ix-cells))

Most of the complication in these functions vis-à-vis the mathematical description in the previous section is due to me not wanting to compute the neighborhood of every cell in every step when I only need to operate on a subset of cells.

Coordinating movement using local information

I wanted to implement the following movement rule: in each step, an agent randomly selects a neighboring empty cell and attempts to move there; if more than one agent tries to move to the same cell, then one randomly chosen agent completes the move and the rest stay where they are. The tricky part is that we want to prevent two agents from moving to the same cell. One way to implement this rule would be to break our mapping-functions-over-neighborhoods mechanic and allow coordination between agents. But I like this mechanic. Here are three solutions that use local (neighborhood-based) rules only.

  1. We could allow more than one agent to occupy a cell. We would represent the grid as a vector of vectors, each of the inner vectors could hold zero or more agents. The movement step would consist of two smaller steps: first, each agent proposes a direction that it wants to move to, randomly chosen. Then the cell at the center of the neighborhood is filled with the agents at neighboring cells that have requested to move to the center, if any.

    This solution is easy to implement, but it breaks the spatial mechanic of the model. I think part of the point of this simulation is that it treats space as a limited resource. In the death-and-birth stage, for example, an agent with a high enough score can give birth to a child agent, but only if they’re next to an empty cell. Allowing multiple agents to occupy a cell would significantly change the equilibrium state of the model (for the worse, I think).

  2. We could execute the movement step using a larger neighborhood definition so that an agent could see the neighbors of its neighbors and act accordingly. As with the first solution, we break the movement step into two smaller steps and in the first step each agent proposes to move to a neighboring empty cell. The function that completes the move is then passed the distance 2 Von Neumann neighborhood. That way, the center cell can see the neighbors of its neighbors; in particular, an agent can see which other agents have proposed to move to the same cell. We then implement a deterministic rule for resolving movement conflicts, e.g., yield to the right.

    I actually like this rule, but it involves a lot of superfluous computation. To complete the movement, we need to construct the extended neighborhood at every cell in the grid. The extended neighborhood comprises 13 cells, and the update function which operates on them will need to check the value of at most 4 of those cells.

  3. Instead of two smaller steps, we break movement into three smaller steps. As before, the first step is for agents to propose to move to an empty cell. For the second step, empty cells look around to see if any of their neighboring cells contain agents that have proposed to move into them. If so, it chooses one randomly and updates its state as accepting a movement from that direction. Finally, in the third step we simply update the grid according to these “movement accepted” attributes.

I decided to go with the third solution. My gut tells me that this approach is computing less than the second approach would have, but I haven’t done the math. Let’s take another look at the move-step function.

(defn move-step
  [ca]
  (-> ca
      (update-ca #(center-propose-action-dir % empty?) :apply-to not-empty?)
      (update-ca center-accept-action-dir :apply-to empty?)
      (update-ca complete-move)))

The three calls to update-ca correspond to the three partial steps to perform a movement. Recall from the last section that update-ca updates the CA by applying a function to cell neighborhoods in the grid, with the option of pre-filtering cells according to a predicate. Let’s apply the center-propose-action-dir function by hand to see how it works.

hnd.model> (make-ca 4 4)
{:nrow 4, :ncol 4, :grid [{} {:score 20, :type :dove} {:score 20, :type :hawk} {} {} {:score 20, :type :hawk} {:score 20, :type :hawk} {:score 20, :type :dove} {} {} {} {} {:score 20, :type :hawk} {:score 20, :type :hawk} {:score 20, :type :hawk} {:score 20, :type :dove}]}
hnd.model> (get-neighborhood *1 1)
{:c {:score 20, :type :dove}, :n {:score 20, :type :hawk}, :e {:score 20, :type :hawk}, :s {:score 20, :type :hawk}, :w {}}
hnd.model> (center-propose-action-dir *1 empty?)
{:propose-action-dir :w, :score 20, :type :dove}

First, note that a neighborhood is represented as a map with the keys :c, :n, :e, :s, and :w associated to the values at the center, north, east, south, and west cells of the neighborhood. The center-propose-action-dir function takes a neighborhood and a cell predicate as arguments. If any of the neighboring cells (i.e., cells in the neighborhood other than the center) satisfy the predicate, the function randomly chooses one and updates the center cell with a new key :propose-action-dir which references that neighbor cell’s direction. In the example above, the only nonempty neighbor was to the west, so that’s where :propose-action-dir points in the result. Here’s the code.

(defn center-propose-action-dir
  "Adds the key :propose-action-dir to the center cell with a value
  corresponding to a randomly chosen neighboring cell that satisfies
  cell-pred. If no neighbors satisfy cell-pred, the center cell is not
  altered. Returns the center cell."
  [nbhd cell-pred]
  (if-let [s (seq (filter-neighbor-cell-dir nbhd cell-pred))]
    (assoc (:c nbhd) :propose-action-dir (rand-nth s))
    (:c nbhd)))

The second step in move-step applies the center-accept-action-dir function to all empty cells in the grid. This function works essentially the same way as center-propose-action-dir (and the code is similar enough that I won’t include it). It checks neighboring cells to see if any of them have proposed to act on the center cell. If so, it randomly chooses one and updates the state of the center cell to accept an action from that direction.

Finally, we update the grid with the accepted movements. We need a function that operates on every neighborhood in the grid according to these rules: (1) if the cell has an :accept-action-dir key, replace the center cell with the neighboring cell in the accepted direction. (2) If the cell has a neighbor with an :accept-action-dir key that points to the center, then replace the center cell with an empty cell. (3) Otherwise, return the center cell unchanged. The implementation is a bit of a mouthful, but it’s also as complicated as the code in this program gets.

(defn complete-move
  "Update the center cell with any movement specified in the
  neighborhood."
  [nbhd]
  (let [accept-action-dir (:accept-action-dir (:c nbhd))
        target-dir (filter-neighbor-dir nbhd wants-action-from-center?)
        new-cell (cond accept-action-dir (accept-action-dir nbhd)
                       (seq target-dir) {}
                       :else (:c nbhd))]
    (dissoc new-cell :propose-action-dir)))

As a last step, I remove any :propose-action-dir attributes from cells. This isn’t strictly necessary (those attributes would be replaced by new values in subsequent steps), but it keeps the grid clean if we want to inspect it at the repl.

Break time

This seems a good time to take break. In a future post, I’ll describe the game-playing and death-and-birth mechanics (quickly, now that we’ve laid the groundwork), and I’ll explain the graphical implementation.