Prisoner’s Dilemma and Conditionals

The Prisoner’s Dilemma is a classic problem in philosophy, economics, computer science, and well – life. I love it because it’s really easy to simulate, even for a beginning programmer, and it’s a great starting point for discussions on how you can use a computer program as a simulation for real-life phenomena.

I found this video on YouTube to explain the Prisoner’s Dilemma, and although the cigarette ads are a little edgy for the middle school audience, I think it dives in just deep enough. I showed this to the kids first.

The assignment for the kids then was to model the Prisoner’s Dilemma in a computer program. At this point, we had learned about variables, boolean expressions, “if” and “if/else” statements, and random number generation – and that’s pretty much it, so these programs weren’t going to be anything fancy. Here were the requirements.

1) Use the random() function to choose randomly whether two prisoners (call them A and B) will cooperate or defect.
2) Write the prisoners’ choices to the screen.
3) Use “if” statements and boolean expressions. Write the score to the screen as follows:
If A and B both cooperate, they both get 1 year in prison.
If A cooperates and B defects, A gets 3 years in prison and B goes free.
If B cooperates and A defects, A goes free and B gets 3 years in prison.
If A and B both defect, they both get 2 years in prison.

I decided to make this a pair programming activity. The students know by now there are 4 types of activities in CS class. Pair programming where I pick the partners; pair programming where they pick the partners; solo activities; and non-programming larger group activites such as card sorts and analysis tasks and that kind of thing. For the Prisoner’s Dilemma, I got to assign the partners. I reminded everyone of the norms first, a la this video from Code.org (which we watched earlier in the year, it’s wonderful)

* Don’t grab the mouse or keyboard.
* Do talk about the work.
* Do switch roles often.
* Don’t be bossy.
* Do be respectful.

I put everyone’s name in a bucket. I drew one name, and then invited that person to draw a name for their partner. They’d decide who was going to be driver and navigator, and head to the computer to work on the Prisoner’s Dilemma program. I gave them the coin flipper we worked on last class as a starter. Some kids spun off the coin flipper, some looked at it for ideas, and others built a program from scratch.

Coin Flipper Program

They worked really, really well together. I thought it might have been a fluke in one class, but then when it happened in the next class, I knew it wasn’t a fluke. Some combination of the task, the setup, and the accountability made it pretty darn magical for a really beautiful class period.

They worked hard for about 10 minutes and then the questions started coming in fast and furious, but happily, kids didn’t tend to get stuck and stay stuck. Pair programming is great for harder tasks, and I use solo programming for the easier tasks.

Some of the programs I got were pretty awesome.

Kevin and Patrick’s program, below, draws little stick figures for the prisoners. What I like about it is that they figured out the basics of translation by adding 150 to all of the x-coordinates, but keeping everything else the same.

Prisoners Dilema Kevin & Patrick

Made using: Khan Academy Computer Science.

In Maddie and Ragan’s program, they didn’t use the coin flipper’s random number generator, but used a random number generator from -11 to 11. We had an interesting discussion about whether the cut point between “defect” and “cooperate” should be at PrisonerA > 1 or PrisonerA > 0. They realized the probability of their prisoner cooperating was slightly less than the probability of defecting, but that the video indicated defecting was usually the better choice. I couldn’t argue.

Maddie and Ragan Prisoner’s Dilemma

Made using: Khan Academy Computer Science.

In Cole and Austin’s program, the model didn’t quite meet the requirements I set at first. Prisoner A and Prisoner B don’t make independent choices. Rather, Cole programmed the whole thing to have a 1/5 chance of both prisoners cooperating, a 1/5 chance of one defecting and the other cooperating (almost – their random number generator doesn’t quite work like they think) and a 2/5 chance of both defecting. I challenged them on this because a) that’s not the model that was in the requirement, which was that Prisoner A and Prisoner B make independent choices, and b) Cole did all the work and didn’t leave anything for Austin. This turned into a little bit of a battle of wills and eventually I convinced Cole to spin off the existing program, let Austin drive, and create two different outcomes for prisoner A and prisoner B. But at the same time, I was pretty impressed that the kid reasoned through the situation and wrote the whole program before the video was even done playing.

Prisoners Dilemma Cole and Austin

Made using: Khan Academy Computer Science.   Justin and Ian were an interesting match, because Justin has been programming forever and pretty much knows all of this already. Ian is brand new to all of this and is still learning the basics of things like JavaScript syntax and how to use the coordinate plane. Justin wrote the program, and when he got done and called me over to check it, like 10 minutes after the activity started, I noticed it was pretty plain with a white background and plain text. I suggested they switch roles, let Ian drive and make the program fancier. Add color, add graphics, something to jazz it up so it’s a cooler simulation. So they did, and both kids did a marvelous job working together, and I think Ian came away understanding JavaScript a lot better than he did. Plus their prisoners are really cute.

Spin-off of “Coin Flipper” ian r and justin b

Made using: Khan Academy Computer Science.

Then there’s Paul and Ethan’s program. They finished the basics in a hurry and then just giggled for the rest of class, and I walk over to check their work and they have this rainbowy creation. By far the fanciest Prisoner’s Dilemma simulator I got so far.

Paul and Ethan Prisoner’s Dilemma

Made using: Khan Academy Computer Science.

As a closer to this lesson, I will include a tie-in to the Iterated Prisoner’s Dilemma. Playing PD one time is an interesting simulation, but of course in real life, you encounter people over and over again, and every interaction with someone can be its own round of PD.

According to the Wikipedia entry, in 1984, a computer science competition was held during which computer programs would play each other in a round-robin tournament, where in each round, they would play another program in “N” rounds of Prisoner’s Dilemma.

The winning strategy was called “Tit for Tat” and it was the simplest of all the programs entered, consisting of only four lines of code. It always opened by cooperating, and after that, it did to the opponent whatever the opponent chose in the previous round. That’s it. It scored more points than any other strategy.

When I was a kid, I enjoyed sci-fi/fantasy novels and one of my favorite authors was Piers Anthony. In his Xanth series, one of the books was Golem in the Gears. The final chapter of this book describes a multi-player Prisoner’s Dilemma situation in which two Golems and two Hags play 6 rounds each of PD and then compare their final scores in the end. The winning strategy was, of course, Tit for Tat, and I like to read this chapter of the book to the kids. They enjoy being read to, and it’s cool to see an obscure CS reference show up in a fantasy novel.

It would be interesting to have the kids write an iterated PD program. I am considering, as an extension, having the kids tweak their programs so they have what they think is the optimal probability of defecting vs. cooperating – and then tallying up the number of years in prison they get after “N” rounds against another prisoner. When we learn about loops, perhaps we can go back and modify the programs further and even splice two groups’ prisoners together to see how they do!

Advertisements

About dupriestmath

I'm a former software engineer who has taught middle school math and computer science for the past 6 years. I believe every kid has the right to be a thinker. I started this blog to save resources for integrating programming in the Common Core math classroom. I also use it to save my lessons and reflections from teaching budding computer scientists! Coding has transformed how I teach and think. You'll love what it does for you. You should try it.

3 responses to “Prisoner’s Dilemma and Conditionals”

  1. Mike Zamansky (@zamansky) says :

    We do PD sometimes in our intro classes. One of my teachers once asked why? Because it’s a neat concept that can be applied to so many situations.

    I’ve done it in any number of languages, including a custom one – to show the kids that they can learn a new language using web resources once they have solid fundamentals .

    I also do it on a grid – each square gets a strategy and plays against its neighbors. I don’t remember how I set up the specifics – it’s been a few years, but basically, we fill the grid with random strategies, they play their neighbors a bunch of times, and then have a scoring system by which some cells die and are replaced by other strategies.

    If you set it up right, it starts with aggressive strategies (alldefect, for instance) taking over most of the board with tit-for-tat and cooperative strategies barely holding on – then the tit-for-tat starts to and ultimately takes over – it’s a great visual.

  2. dupriestmath says :

    That’s awesome. I would love to see the grid model. I found this web site with some examples of iterated Prisoner’s Dilemma, and I let my students experiment with it some today. They find this problem really engaging. I swear it’s an activity that opens your eyes to how you can understand, and therefore change, the world by programming – and a beginner can easily take it on.
    http://www.gametheory.net/applets/prisoners.html

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: