The hawk and dove game II
an agent-based model in clojure
Today I’ll finish desribing my implementation of an agent-based model based on the hawk and dove game. I’ll cover the game-playing and death-and-birth mechanics and I’ll show how I animated the model’s evolution. This is a continuation of the previous post which gives more background on the simulation mechanics. The complete code for this simulation is available here.
Playing games
Recall that one top-level step in our model comprises three stages: a game-playing stage, in which agents can play a round of prisoner’s dilemma with their neighbors, a death-and-birth stage, and a movement stage. The clojure code for the top-level step looked like this:
(defn step
"Execute one model step."
[ca]
(-> ca game-step death-and-birth-step move-step))In the last post, we covered move-step, because it had the simplest mechanic. Now let’s take a look at game-step. Like move-step, it’s implement as a sequence of calls to update-ca.
(defn game-step
"Perform a single game-playing step."
[ca]
(-> ca
(update-ca #(center-propose-action-dir % not-empty?) :apply-to not-empty?)
(update-ca complete-games :apply-to :propose-action-dir)))In words, the game-playing stage consists of two parts. In the first part, every agent checks its neighborhood for other agents. If it sees any, then it chooses one at random and proposes to play a round of prisoner’s dilemma with it. In the second part, every agent who has proposed a game plays all pending games and updates their score accordingly (only agents who proposed a game in the first part will have any pending games to play in the second part).
If I did a good job writing the last post, then it should be clear that
(update-ca ca #(center-propose-action-dir % not-empty?) :apply-to not-empty?)implements the first part of the game-playing stage. Briefly, we map the center-propose-action-dir over all neighborhoods in ca whose centers are not empty. The centers of those neighborhoods are then updated with a :propose-action-dir attribute which points in the direction of a neighboring agent, if there are any.
In my simulation, all proposed games are played. That means that an agent plays prisoner’s dilemma with whoever they’ve proposed to play with, and they also play with other agents who initiated a proposal.
(defn complete-games
"Play all opponents, update score, and remove :propose-action-dir key."
[agent-nbhd]
(let [center (:c agent-nbhd)
opponents (game-opponents agent-nbhd)
payoffs (for [opp opponents] (game-payoff center opp))]
(-> (reduce (fn [agent [score _]] (add-score agent score)) center payoffs)
(dissoc :propose-action-dir))))Let’s break down the component functions of complete-games.
Finding opponents
Under the propose-direction mechanic, the opponents of the center cell of a neighborhood are in the cell that the center has proposed toward and in the cells that have proposed toward the center. The game-opponents function adds opponent agents to a set so that the center agent doesn’t play the same opponent twice.
(defn game-opponents
"Returns a seq of game opponents."
[agent-nbhd]
(let [center (:c agent-nbhd)
opponent-dir (filter-neighbor-dir agent-nbhd wants-to-act-on-center?)
opponents (into #{} (for [dir opponent-dir] (dir agent-nbhd)))]
(conj opponents ((:propose-action-dir center) agent-nbhd))))Computing game outcomes
This is the step where the hawk and dove game comes in. Recall that in the prisoner’s dilemma, hawks always betray and doves always cooperate. Therefore, the outcome of a single game is a function of the playing agents types. The game-payoff function is a simple lookup.
(defn game-payoff
"Returns the outcome of a game between the given agents."
[agent-1 agent-2]
(default-payoffs [(:type agent-1) (:type agent-2)]))where
(def default-payoffs {[:hawk :hawk] [-2 -2]
[:hawk :dove] [1 -2]
[:dove :hawk] [-2 1]
[:dove :dove] [2 2]})Updating the center agent
The last two lines in the complete-games function (i.e., the body of the let statement) update the center agent according to the outomes of games played. add-score is a simple helper function that tallies the agent score, and we remove the :propose-action-dir tag just to be tidy.
Death and birth
We also implement a death-and-birth mechanic in our simulation. With this mechanic, our simulation becomes a sort of ecosystem, with hawks and doves competing for space. The death rule is straightforward: each agent starts with an initial score, if that score falls to zero then the agent dies. The birth rule is only slightly more complicated, because we have to check for available space. If an agent’s score reaches a predefined threshold, then the agent tries to place a child on a neighboring empty square. If successful, the parent’s score is split between itself and its chid. Here’s the code for the death-and-birth stage.
(defn death-and-birth-step
[ca]
(-> ca
thin-the-herd
(update-ca #(center-propose-action-dir % empty?) :apply-to abundant?)
(update-ca center-accept-action-dir :apply-to empty?)
(update-ca complete-split)))The thin-the-herd function replaces any cells in the grid with a score less than zero with an empty cell. The rest of the function looks a lot like the move-step function because the mechanics are essentially the same. The abundant? predicate tests to see if the cell contains an agent whose score is greater than the splitting threshold. If it does, then the cell proposes to act on a neighboring empty cell. Like in the movement stage, we then empty cells choose to accept a proposed action or not. Afterward, we update the grid according to the accepted action. Let’s take a look at the definition of complete-split.
(defn complete-split
"Update the center cell with any splits specified by 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
(let [[_ child] (split-agent (accept-action-dir nbhd))]
child)
(seq target-dir)
(let [[parent _] (split-agent (:c nbhd))]
parent)
:else (:c nbhd))]
(dissoc new-cell :propose-action-dir)))This is very similar to complete-move, described in the last post. We test to see if the cell has an :accept-action-dir attribute. If it does, we replace the cell with a new child cell. Next, we check to see if a neighboring cell has accepted a proposed action from the center cell. If it does, we replace the cell with a parent cell resulting from a parent-child split. Otherwise, we leave the center cell as it is. For completeness, here’s the split-agent function.
(defn split-agent
"Create two agents with the score of the original agent split
between them."
[agent]
(let [current-score (:score agent)]
[(assoc agent :score (quot (inc current-score) 2))
(assoc agent :score (quot current-score 2))]))Animating the grid
That completes our discussion of the model logic, now let’s turn to the visualization. Part of the reason I wanted to implement a CA is that they make for nice animations. Our goal is straightforward: draw a grid of squares where each hawk is represented by a square of one color and each dove is represented by a square of another color. To make it more interesting, we can use the alpha channel to encode the agents’ scores, with lower scores corresponding to more transparent agents.
I’ve been reading about game programming lately, so I decided to apply a method from that domain: in each time step I just blank out the entire grid and iterate over the cells to draw the new state. If you’re using a basic game programming library, though, you can assume double buffering. When I initially tried to implement this approach using java swing, I got a lot of screen flicker. After some web searching, I found an incantation to set up double buffering in java, but in the end result I have a window decoration being painted over my CA. I decided, however, that this was good enough for what I’m trying to achieve here.
Drawing the CA is handled by the draw-ca function in hnd.core.
(defn draw-ca [ca g g-width g-height]
(let [grid-width (quot g-width (:ncol ca))
grid-height (quot g-height (:nrow ca))]
(.clearRect g 0 0 g-width g-height)
(doseq [i (range (:nrow ca)) j (range (:ncol ca))]
(let [cell (model/get-cell ca (model/sub->ind ca i j))]
(if (model/not-empty? cell)
(let [type (:type cell)
rgb (if (= type :dove) gui-dove-rgb gui-hawk-rgb)
alpha (get-alpha cell)
x (* i grid-width)
y (* j grid-height)]
(.setColor g (Color. (rgb 0) (rgb 1) (rgb 2) alpha))
(.fillRect g x y grid-width grid-height)))))))The function takes a CA instance, a graphics context, and the width and height of the graphics context. We first compute the width and height of an individual cell, and we blank out the drawing area by calling clearRect. Then, for each cell in the grid we pick a color depending on its type and compute its alpha value by calling the get-alpha function (which I’ll show below). We compute its coordinates, set the color, and draw a little rectangle. That’s it.
gui-dove-rgb and gui-hawk-rgb are defined as
(def gui-dove-rgb (into [] (map float [0.149020 0.545098 0.823529])))
(def gui-hawk-rgb (into [] (map float [0.796078 0.294118 0.086275])))That’s blue and orange from the venerable solarized color scheme. The get-alpha function returns the fraction of an agent’s current score divided by the splitting threshold score. It also ensures that the return value is between 0 and 1.
(defn get-alpha [cell]
(let [alpha (/ (:score cell) model/default-split-at)
alpha (max 0 (min 1 alpha))]
(float alpha)))The function to construct a frame to draw on (including the double-buffering incantation) looks like this.
(defn make-frame [width height]
(let [ge (GraphicsEnvironment/getLocalGraphicsEnvironment)
gs (.getDefaultScreenDevice ge)
gc (.getDefaultConfiguration gs)
frame (Frame. gc)
window-closer (make-window-closer frame)]
(doto frame
(.setIgnoreRepaint true)
(.setTitle "Hawk and Dove Game")
(.setSize (Dimension. width height))
(.setVisible true)
(.createBufferStrategy 2)
(.addWindowListener window-closer))))The make-window-closer function simply returns a WindowListener proxy with the windowClosing callback implemented to dispose of the frame.
Finally, we put it together in a main function which builds the frame and advances the model step by step. All the symbols that start gui- are constants. As the number of occupied cells increases, so does the amount of time that it takes to compute a step. I throttle the animation update speed to make this effect less noticeable. The call to Thread/sleep ensures that each step is on the screen for at least gui-refresh-delay milliseconds. I use an atom—one of clojure’s reference types—to store the model state between iterations.
(defn -main [& args]
(let [ca (atom (model/make-ca gui-nrow gui-ncol))
frame (make-frame gui-width gui-height)
strategy (.getBufferStrategy frame)]
(dotimes [_ gui-steps]
(let [ts (System/currentTimeMillis)
g (.getDrawGraphics strategy)]
(swap! ca model/step)
(draw-ca @ca g (.getWidth frame) (.getHeight frame))
(.dispose g)
(.show strategy)
(Thread/sleep (max 0 (- gui-refresh-delay
(- (System/currentTimeMillis) ts))))))))future stuff
I think this way of writing a CA as a sequence of functions iterated over a grid of cells is conceptually nice, but it’s probably slower and more resource hungry than a naive implementation using mutable grid cells. One advantage, however, is that it’s immediately parallelizable. In a future post I’d like to reimplement model update functions using clojure reducers and run it on larger grids.
I also to rewrite the animation code to target the HTML5 canvas element using clojurescript. I feel like this could be an interesting platform for interactive web-based visualizations.