Basic prisoner's dilemma?

Discussion in 'Java' started by theglazeb, Apr 18, 2011.

  1. theglazeb

    theglazeb Guest

    Hi there!

    I was wondering if you were able to help with me a basic prisoner's
    dilemma strategy? How would I implement a basic tit for tat strategy?
    And perhaps try to avoid the "death spiral" from occurring when two
    players use the tit for tat strategy?

    See below

    Thanks!

    /*
    * File: PDStrategy.java
    * ---------------------
    * This class encapsulates the strategy for an Iterated Prisoner's
    * Dilemma game. To enter the contest, all you have to do is change
    * the definition of chooseAction so that it takes account of the
    * history and does something more clever than cooperating (or
    * defecting) all the time.
    */

    import java.util.*;

    class PDStrategy {

    /*
    * Method: chooseAction
    * --------------------
    * This method determines the player's action for the current
    * game, based on two ArrayLists containing the history of play:
    * one for your algorithm and one for the opponent. Each of these
    * ArrayLists contains strings, which are guaranteed to be one of
    * the uppercase strings "COOPERATE" or "DEFECT". Your method
    * should look at the history and return one of those two strings
    * representing the action you take on the current round.
    */

    public String chooseAction(ArrayList<String> myHistory,
    ArrayList<String> oppHistory) {
    return "COOPERATE"; //currently, it is only cooperating
    }

    }
    theglazeb, Apr 18, 2011
    #1
    1. Advertising

  2. theglazeb

    Lew Guest

    theglazeb wrote:
    > I was wondering if you were able to help with me a basic prisoner's
    > dilemma strategy? How would I implement a basic tit for tat strategy?
    > And perhaps try to avoid the "death spiral" from occurring when two
    > players use the tit for tat strategy?
    >
    > See below
    >
    > Thanks!
    >
    > /*
    > * File: PDStrategy.java
    > * ---------------------
    > * This class encapsulates the strategy for an Iterated Prisoner's
    > * Dilemma game. To enter the contest, all you have to do is change


    Tell us more about this contest. Where is it held? Do you have a link? What
    can you win?

    --
    Lew
    Honi soit qui mal y pense.
    http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
    Lew, Apr 18, 2011
    #2
    1. Advertising

  3. theglazeb

    Esmond Pitt Guest

    On 18/04/2011 1:15 PM, Lew wrote:
    > Tell us more about this contest. Where is it held? Do you have a link?
    > What can you win?


    .... and then tell us why we should help *you* rather than try to win it
    ourselves. Prisoner's dilemma in fact ;-)
    Esmond Pitt, Apr 18, 2011
    #3
  4. theglazeb

    theglazeb Guest

    On Apr 17, 8:54 pm, Esmond Pitt <> wrote:
    > On 18/04/2011 1:15 PM, Lew wrote:
    >
    > > Tell us more about this contest. Where is it held? Do you have a link?
    > > What can you win?

    >
    > ... and then tell us why we should help *you* rather than try to win it
    > ourselves. Prisoner's dilemma in fact ;-)



    Thanks for the messages! This is a sample question from a competition
    a couple of years ago. Someone passed it to me in my university
    department passed it to me and suggested I try it out in order to
    think more about prisoner's dilemma and learn java (I'm still a
    novice, I'm afraid) I believe it may have been from
    http://www.prisoners-dilemma.com/competition.html

    So I am trying to figure out how I could create a tit for tat strategy
    using an Arraylist. Or even a set of random outcomes based on the
    history. Any help would be appreciated. The "win" for me in this case
    is a better understanding of java.

    You don't need to help if you don't want to, but of course it would be
    appreciated. If don't want to help, it could be great if you could
    point in me in the correct direction - how could make it output random
    DEFECT or COOPERATE? and then following on that, how could I start
    thinking about a Tit for Tat strategy?

    Thanks so much!
    theglazeb, Apr 18, 2011
    #4
  5. theglazeb

    markspace Guest

    On 4/17/2011 10:08 PM, theglazeb wrote:

    > You don't need to help if you don't want to, but of course it would be
    > appreciated. If don't want to help, it could be great if you could
    > point in me in the correct direction - how could make it output random
    > DEFECT or COOPERATE? and then following on that, how could I start
    > thinking about a Tit for Tat strategy?



    The first thing you might want to do is to have clear in your mind what
    "tit-for-tat" means, and also perhaps try to understand what the
    Prisoner's Dilemma is really talking about. I found the Wikipedia
    article very helpful, and of course I found that with Google.

    Random: you can use Math.random() to generate random numbers.

    Tit-for-tat, once you understand it, is just very basic array list
    manipulation. I'll let you think on that part.
    markspace, Apr 18, 2011
    #5
  6. On 2011-04-18, theglazeb <> wrote:
    > And perhaps try to avoid the "death spiral" from occurring when two
    > players use the tit for tat strategy?


    If both players use tit for tat then the death spiral doesn't ever
    occur because both players start out by cooperating, and both players
    continue cooperating.

    The death spiral only occurs when one player deviates from tit for tat
    for whatever reason and defects, while the other player continues a
    straight tit for tat strategy, and the first player then also starts
    adopting either tit for tat or always defect (which is effectively the
    same thing in this case).

    The obvious alternative to tit for tat in this situation is to
    sometimes cooperate in spite of tit for tat dictating defect: either
    by keeping track of the play history and doing periodic cooperates; or
    alternatively by randomly cooperating (say, with 5% chance anytime you
    would normally defect) if you don't want to keep track of state.

    If memory serves, I think the general conclusion is that tit for tat
    is always superior to trying to be clever, unless you have some
    information about your opponent's algorithm (personality) that you can
    exploit to your advantage.

    Cheers,

    Bent D
    --
    Bent Dalager - - http://www.pvv.org/~bcd
    powered by emacs
    Bent C Dalager, Apr 18, 2011
    #6
  7. theglazeb

    Stefan Ram Guest

    theglazeb <> writes:
    >I was wondering if you were able to help with me a basic prisoner's
    >dilemma strategy? How would I implement a basic tit for tat strategy?


    (It's spelled »tit-for-tat strategy«.)

    This depends on the interface of the game.
    First, specify the game interface.
    Then, specify the player's algorithm on this game interface.

    class Player implements GameFramework.Player
    { public void move( final Game game )
    { if( this.opponentProvokedIn( game ))this.retaliate( game );
    else this.cooperate( game ); }
    (...) }
    Stefan Ram, Apr 18, 2011
    #7
  8. On 18/04/2011 04:51, theglazeb allegedly wrote:
    > Hi there!
    >
    > I was wondering if you were able to help with me a basic prisoner's
    > dilemma strategy? How would I implement a basic tit for tat strategy?
    > And perhaps try to avoid the "death spiral" from occurring when two
    > players use the tit for tat strategy?
    >
    > See below
    >
    > Thanks!
    >
    > /*
    > * File: PDStrategy.java
    > * ---------------------
    > * This class encapsulates the strategy for an Iterated Prisoner's
    > * Dilemma game. To enter the contest, all you have to do is change
    > * the definition of chooseAction so that it takes account of the
    > * history and does something more clever than cooperating (or
    > * defecting) all the time.
    > */
    >
    > import java.util.*;
    >
    > class PDStrategy {
    >
    > /*
    > * Method: chooseAction
    > * --------------------
    > * This method determines the player's action for the current
    > * game, based on two ArrayLists containing the history of play:
    > * one for your algorithm and one for the opponent. Each of these
    > * ArrayLists contains strings, which are guaranteed to be one of
    > * the uppercase strings "COOPERATE" or "DEFECT". Your method
    > * should look at the history and return one of those two strings
    > * representing the action you take on the current round.
    > */
    >
    > public String chooseAction(ArrayList<String> myHistory,
    > ArrayList<String> oppHistory) {
    > return "COOPERATE"; //currently, it is only cooperating
    > }
    >
    > }


    Basic tit-for-tat is as follows:
    - if it's the first time you encounter that opponent (this implies you
    keep a 'memory' of previous encounters), cooperate.
    - otherwise, replicate that opponent's last move.

    In code (assuming oppHistory contains only the history with "this"):

    public String chooseAction(
    ArrayList<String> myHistory, ArrayList<String> oppHistory)
    {
    return oppHistory.isEmpty() ? "COOPERATE" : oppHistory.get(
    oppHistory.size());
    }
    (or oppHistory.get(0), depending on whether it's used as a FIFO or a LIFO).


    You can add various tricks, but don't expect to get far with them,
    because tit-for-tat is the evolutionary stable strategy.

    If you're interested in the topic apart from the programming aspect, I
    *very* strongly suggest you read Dawkins' "Selfish Gene" and "Blind
    Watchmaker". Even if you're not, by the way -- those are IMHO must-reads.

    --
    DF.
    An escaped convict once said to me:
    "Alcatraz is the place to be"
    Daniele Futtorovic, Apr 18, 2011
    #8
  9. On 18/04/2011 19:34, Lew allegedly wrote:
    > Daniele Futtorovic wrote:
    >> Basic tit-for-tat is as follows:
    >> - if it's the first time you encounter that opponent (this implies you
    >> keep a 'memory' of previous encounters), cooperate.
    >> - otherwise, replicate that opponent's last move.
    >>
    >> In code (assuming oppHistory contains only the history with "this"):
    >>
    >> public String chooseAction(
    >> ArrayList<String> myHistory, ArrayList<String> oppHistory)
    >> {
    >> return oppHistory.isEmpty() ? "COOPERATE"
    >> : oppHistory.get( oppHistory.size()

    > - 1
    >> );
    >> }
    >> (or oppHistory.get(0), depending on whether it's used as a FIFO or a
    >> LIFO).
    >>
    >>
    >> You can add various tricks, but don't expect to get far with them,
    >> because tit-for-tat is the evolutionary stable strategy.
    >>
    >> If you're interested in the topic apart from the programming aspect, I
    >> *very* strongly suggest you read Dawkins' "Selfish Gene" and "Blind
    >> Watchmaker". Even if you're not, by the way -- those are IMHO must-reads.

    >


    Well spotted. Thanks, Lew.
    Daniele Futtorovic, Apr 18, 2011
    #9
  10. theglazeb

    Lew Guest

    Daniele Futtorovic wrote:
    > Lew allegedly wrote:


    >> Daniele Futtorovic wrote:
    >>> Basic tit-for-tat is as follows:
    >>> - if it's the first time you encounter that opponent (this implies you
    >>> keep a 'memory' of previous encounters), cooperate.
    >>> - otherwise, replicate that opponent's last move.
    >>>
    >>> In code (assuming oppHistory contains only the history with "this"):
    >>>
    >>> public String chooseAction(
    >>> ArrayList<String> myHistory, ArrayList<String> oppHistory)
    >>> {
    >>> return oppHistory.isEmpty() ? "COOPERATE"
    >>> : oppHistory.get( oppHistory.size()

    >> - 1
    >>> );
    >>> }
    >>> (or oppHistory.get(0), depending on whether it's used as a FIFO or a
    >>> LIFO).

    [snip]

    > Well spotted. Thanks, Lew.


    HTH.

    As a matter of good habit, I also suggest using interface-typed parameters to
    the method, but that is not germane to the point of your example.

    Inevitably my mind starts spinning coder fantasies even on these toy examples:

    - "Wouldn't an enum base type and return type be better than String?"
    - "What if we keep a rolling buffer of choices of size N rather than recording
    all history?"
    - "What if there were a third response possible (thus more reason to use an
    enum), say, 'PREVARICATE'?"
    - "What would that even mean?"
    - "What if the choices were more like Rock-Paper-Scissors?"
    - "What is the reward / cost for each combination of choices?"
    - "What if that reward / cost increased or decreased with k, the number of
    game rounds played so far?"
    - "What is the terminating condition of the game?"

    I'm firing these questions out without recently having reviewed the Prisoner's
    Dilemma, but the simple form you describe is only the launching point.

    --
    Lew
    Honi soit qui mal y pense.
    http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
    Lew, Apr 18, 2011
    #10
  11. On 18/04/2011 22:33, Lew allegedly wrote:
    > As a matter of good habit, I also suggest using interface-typed
    > parameters to the method, but that is not germane to the point of
    > your example.


    I hesitated to make it a Queue to better prove the point.


    > Inevitably my mind starts spinning coder fantasies even on these toy
    > examples:


    So does mine on similar occasions, but on this here matter that would be
    missing the important point, which is the model the prisoner's dilemma
    represents as well as what's an evolutionary stable strategy. I didn't
    modify the original code to make it cleaner, like using an enum value as
    the return and interface types, because I'd daresay it's more important
    to understand what's behind the prisoner's dilemma than knowing how to code.

    > - "What if we keep a rolling buffer of choices of size N rather than
    > recording all history?"


    Not necessarily. It would limit strategies if they couldn't look back as
    far as they wanted, for the sake of algorithmic efficiency, which isn't
    the point here at all.

    > - "What if there were a third response possible (thus more reason to
    > use an enum), say, 'PREVARICATE'?"


    No. There are variants of the prisoner's dilemma, in different settings.
    What's important is that the choice be to cooperate or not, that it be
    a non-zero-sum game, and that the length of the game be not known.


    > - "What would that even mean?"


    > - "What if the choices were more like Rock-Paper-Scissors?"


    That's a zero-sum game.

    > - "What is the reward / cost for each combination of choices?"


    Factors may vary. Different weighing will slightly affect how quickly an
    evolutionary stable strategy emerges. One and I believe the canonical
    example is:
    Both cooperate: both get three
    One betrays: betrayer gets five, betrayed gets naught.
    None cooperates: both get one

    > - "What if that reward / cost increased or decreased with k, the
    > number of game rounds played so far?"


    It's important that the "passes" be interchangeable, non-ordered (if you
    see what I mean).

    > - "What is the terminating condition of the game?"


    There must be none. If you're ever in a prisoner's dilemma kind of
    situation, and know that there are only a limited number of passes left,
    there is only one viable strategy: betray.

    --
    DF.
    An escaped convict once said to me:
    "Alcatraz is the place to be"
    Daniele Futtorovic, Apr 18, 2011
    #11
  12. theglazeb

    Lew Guest

    ODaniele Futtorovic wrote:
    > Lew allegedly wrote:
    >> - "What is the terminating condition of the game?"


    > There must be none. If you're ever in a prisoner's dilemma kind of
    > situation, and know that there are only a limited number of passes left,
    > there is only one viable strategy: betray.


    Thank you for those informative answers, but the last one leaves me wondering
    still about the terminating condition of the game. Obviously if there's a
    payout (3/3, 5/0, 1/1), there must be an ending. What you've described is
    that the players cannot know when that ending will occur, but surely it must
    still eventually occur?

    So one of the terminating conditions, or attributes of those conditions, is
    player ignorance. What are the rest?

    This time I don't ask that you feel obligated to answer this question - I will
    certainly do the research. I am deeply grateful that you answered the other
    questions - your answers were focused and helpful. But I had asked them
    primarily to indicate the kinds of questions one might ask, whatever their
    answers, and like the one I ask in this post, answers lead in turn to even
    more questions.

    For example, and I just offer it as an example and not something one is
    required to answer just now, what is the effect of changing the payouts? What
    if partial information were leaked to the prisoner's about release times, but
    the prisoner has to guess how valid that information is? What if the
    information about the other prisoner's responses is distorted, as happens in
    real-life prisoner situations?

    And I remain curious about game choices other than COOPERATE or BETRAY.

    I plan to read up on all this now that the forum has sparked my interest.

    --
    Lew
    Honi soit qui mal y pense.
    http://upload.wikimedia.org/wikipedia/commons/c/cf/Friz.jpg
    Lew, Apr 18, 2011
    #12
  13. theglazeb

    markspace Guest

    On 4/18/2011 3:37 PM, Lew wrote:
    > ODaniele Futtorovic wrote:
    >> Lew allegedly wrote:
    >>> - "What is the terminating condition of the game?"

    >
    >> There must be none. If you're ever in a prisoner's dilemma kind of
    >> situation, and know that there are only a limited number of passes left,
    >> there is only one viable strategy: betray.

    >
    > Thank you for those informative answers, but the last one leaves me
    > wondering still about the terminating condition of the game. Obviously
    > if there's a payout (3/3, 5/0, 1/1), there must be an ending.



    The payout in a traditional prisoner's dilemma is 2.5 years in jail if
    the prisoner betrays, and 5.25 years in prison if he doesn't. That's
    assuming equal chances of his partner in crime choosing to betray or not.

    It's 0 years if he betrays and his partner doesn't, or 5 years each if
    they both betray. Average: 2.5.

    It's 6 months if neither betrays, or 10 years if only his partner does.
    Average: 5.25.


    > What
    > you've described is that the players cannot know when that ending will
    > occur, but surely it must still eventually occur?


    The trick is knowing that there are no rounds left. If you know that,
    then the best strategy at the last round is to betray, because there's
    no way your partner can retaliate. However, if you and your partner
    both know when the last round is, then you'll both betray.

    But if you know that you'll both betray on the last round, then there's
    no incentive to cooperate on the n-1 round. So betray on that round
    too. And then for the n-2 round, and the n-3 round, etc. Until you
    might as well betray on all of them.


    > So one of the terminating conditions, or attributes of those conditions,
    > is player ignorance. What are the rest?



    It's knowing when the rounds terminate that makes the difference.
    Normally, the prisoners don't know how many rounds they'll go through.
    But the rounds do terminate, usually after a fixed number of iterations.
    But the prisoners don't know, it's "blind," someone else makes that
    determination.


    > And I remain curious about game choices other than COOPERATE or BETRAY.
    >
    > I plan to read up on all this now that the forum has sparked my interest.
    >


    The Wikipedia article is pretty good.
    markspace, Apr 18, 2011
    #13
  14. Daniele Futtorovic wrote:
    >
    > If you're interested in the topic apart from the programming aspect, I
    > *very* strongly suggest you read Dawkins' "Selfish Gene" and "Blind
    > Watchmaker". Even if you're not, by the way -- those are IMHO must-reads.


    Another nice work on the subject, particularly for someone with just a
    casual interest who's looking for a light treatment, is William
    Poundstone's _Prisoner's Dilemma_, which combines an introduction to
    and history of game theory with biographical anecdotes about von
    Neumann, Nash, and others.

    --
    Michael Wojcik
    Micro Focus
    Rhetoric & Writing, Michigan State University
    Michael Wojcik, Apr 19, 2011
    #14
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Chris
    Replies:
    0
    Views:
    404
    Chris
    Nov 10, 2003
  2. Kevin Spencer

    Events Dilemma

    Kevin Spencer, Oct 25, 2004, in forum: ASP .Net
    Replies:
    1
    Views:
    348
    Bishop
    Oct 25, 2004
  3. =?Utf-8?B?RGVtZXRyaQ==?=

    Web Service Dilemma

    =?Utf-8?B?RGVtZXRyaQ==?=, Nov 29, 2004, in forum: ASP .Net
    Replies:
    0
    Views:
    296
    =?Utf-8?B?RGVtZXRyaQ==?=
    Nov 29, 2004
  4. Don Parker
    Replies:
    1
    Views:
    346
    Eliyahu Goldin
    Jan 20, 2005
  5. =?Utf-8?B?cm9kY2hhcg==?=

    summary dilemma

    =?Utf-8?B?cm9kY2hhcg==?=, Oct 7, 2005, in forum: ASP .Net
    Replies:
    2
    Views:
    337
    =?Utf-8?B?cm9kY2hhcg==?=
    Oct 8, 2005
Loading...

Share This Page