Address

Author Topic: Who Wants To Go To Prison? (a coding challenge)  (Read 2239 times)

tetsuharu

  • FamiLAB Member
  • Sr. Member
  • *
  • Posts: 487
  • My sincerest contrafibularities.
    • View Profile
Who Wants To Go To Prison? (a coding challenge)
« on: October 22, 2012, 01:06:28 PM »
A classic experiment in the fields of computer science and game theory is the simulation of the Prisoner's Dilemma. The original experiment showed that the optimal behavior for this particular competitive game is Tit-For-Tat, which was revolutionary because it was an entirely cooperative behavior, not competitive or greedy like everyone expected.

Richard Dawkins explains it well :)
http://www.youtube.com/watch?v=48EWLj3gIJ8

I will be running a similar simulation event sometime in December, so if you're a coder or want to learn to code to submit something, write em up and post them here :) .


Problem:
Requirements:
  • Read a single line, this will be your opponent's ID
  • Process decision based on previous experience
  • Write a single line to STDOUT with your decision as "cooperate" or "defect"
  • Read a single line, this will be your opponent's decision as "cooperate" or "defect"
  • Update your decision making process based on result
Example stream of 3 games -
STDIN        8
STDOUT       cooperate
STDIN        cooperate
STDIN        7
STDOUT       cooperate
STDIN        defect
STDIN        5
STDOUT       defect
STDIN        cooperate


Resources:
  • You will be given 500M of disk space, 500M of memory, one CPU core, and STDIN and STDOUT will be hooked up to the simulation environment.
  • You may store data you uncover about your opponents and use them in the decision making process.
  • You may take up to 5 minutes to process your decision (though I expect it to take much less time).
I will try to recreate a few of the basic examples: tit-for-tat, always-defect, etc, for comparison.


If this goes well I may put this up as a permanent installation :)
« Last Edit: October 22, 2012, 01:41:20 PM by tetsuharu »

tetsuharu

  • FamiLAB Member
  • Sr. Member
  • *
  • Posts: 487
  • My sincerest contrafibularities.
    • View Profile
Re: Who Wants To Go To Prison? (a coding challenge)
« Reply #1 on: October 22, 2012, 05:28:09 PM »
Example program loop (in ruby):


# your genius algorithm's data store

def processDecision(opponent_id)
    # your genius algorithm's decision making process

    # returns true or false
end

def learn(opponent_id, decision, opponent_decision)
    # your genius learning algorithm, so your processDecision output changes
end

while true
    opponent_id = gets.chomp
    decision = processDecision(opponent_id)
    puts decision ? "cooperate" : "defect"
    opponent_decision = gets.chomp
    learn(opponent_id, decision, opponent_decision)
end
« Last Edit: October 22, 2012, 05:33:30 PM by tetsuharu »

tetsuharu

  • FamiLAB Member
  • Sr. Member
  • *
  • Posts: 487
  • My sincerest contrafibularities.
    • View Profile
Re: Who Wants To Go To Prison? (a coding challenge)
« Reply #2 on: October 22, 2012, 05:32:19 PM »
Example program loop (in python):


import sys

# your genius algorithm's data store

def processDecision(opponent_id):
    # your algorithm's decision making process
    # returns true or false


def learn(opponent_id, decision, opponent_decision):
    # your algorithm's learning method

while True:
    opponent_id = sys.stdin.readline().strip()
    decision = processDecision(opponent_id)
    print "cooperate" if decision else "defect"
    opponent_decision = sys.stdin.readline().strip()
    learn(opponent_id, decision, opponent_decision)

tetsuharu

  • FamiLAB Member
  • Sr. Member
  • *
  • Posts: 487
  • My sincerest contrafibularities.
    • View Profile
Re: Who Wants To Go To Prison? (a coding challenge)
« Reply #3 on: October 23, 2012, 09:55:23 AM »
mack suggests using Thrift, which apparently facebook uses for their challenges

http://thrift.apache.org/
http://www.davideisenstat.com/fbpfaq/


also, an alternative to stdin/stdout is to create a socket server for the simulation, and give people lots of example code for connecting to and communicating with the socket server. each user would have to run their own agent.
« Last Edit: October 23, 2012, 09:59:23 AM by tetsuharu »

willasaywhat

  • Administrator
  • Hero Member
  • *****
  • Posts: 985
    • View Profile
Who Wants To Go To Prison? (a coding challenge)
« Reply #4 on: October 23, 2012, 10:44:55 AM »
Thrift is freaking insane. I did some challenges for Facebook way back when. It's a neat piece of tech and let's you do inter language comms easily. <3

willasaywhat

  • Administrator
  • Hero Member
  • *****
  • Posts: 985
    • View Profile
Who Wants To Go To Prison? (a coding challenge)
« Reply #5 on: October 23, 2012, 10:46:01 AM »
The dinosaur island one would make for a great FAMiLab game...

tetsuharu

  • FamiLAB Member
  • Sr. Member
  • *
  • Posts: 487
  • My sincerest contrafibularities.
    • View Profile
Re: Who Wants To Go To Prison? (a coding challenge)
« Reply #6 on: October 28, 2012, 03:56:29 PM »
The FishTank offers up this excerpt from a classic Robert Axelrod book "The Evolution of Cooperation":

http://books.google.com/books?id=KFf2HXzVO58C&lpg=PP1&dq=the%20evolution%20of%20cooperation&pg=PA109#v=onepage&q&f=false

Great read for the Prisoner's Dilemma!