by Steven Flintham (15A)
------------------------
Imagine two menu sitting in a room facing each other across a table. Each
has in his hand two cards, marked "Cooperate" and "Defect". Both lay one
card face down on the table and after both have done so, a banker turns over
the two cards and pays one or both of the players depending on which cards
they have played. After an predetermined, but unknown to the players, number
of goes the game ends and the players walk alway with their winnings.
Payouts are made according to the following table:
Key: P1 - player 1's move
P2 - player 2's move
C - cooperate
D - defect
P1
C D
+-------------------+-------------------+
: REWARD FOR MUTUAL : TEMPTATION TO :
: COOPERATION : DEFECT :
C : : :
: 3 TO BOTH : 5 TO P1 :
: : :
P2 +-------------------+-------------------+
: TEMPTATION TO : 'PENALTY' FOR :
: DEFECT : MUTUAL DEFECTION :
D : : :
: 5 TO P2 : 1 TO BOTH :
: : :
+-------------------+-------------------+
So, for instance, if one player played "Defect" and the other played
"Cooperate", the player who defected would receive 5. It is important to
remember that neither player can see the other's card, since the cards are
not turned over until both have played.
The big question is - how should one play to obtain the largest possible
amount of money?
You might reason that if your opponent has played cooperate, your best move
is to defect, since you will then receive 5 rather than both of you
receiving 3. If your opponent has played defect, your best bet is still to
defect, since you will both then receive 1 instead of your opponent
receiving 5. So, using logic (?), you have deduced that you should always
defect.
However, your opponent can legitimately follow exactly the same reasoning
and deduce that he/she should also defect all of the time. This leads to you
both receiving 1 per go - so you are both worse off than you would be if
you both cooperated all the time, which would yield 3 per go!
It can be quite interesting to actually play this game with another human -
it becomes something of an exercise in trust.
At this point, it is worth explaining why it is important that the players
do not know how many goes are left at any time. If the duration of the game
is unknown, players will be more reluctant to defect on their opponent since
they know that their opponent will have a chance at revenge.
However, if the players know that it is the last go, there will be no such
incentive since there will be no chance for revenge. This knowledge leads to
similar behaviour on the second from last move, and therefore the third from
last move, and so on, which is why the duration of the game must be kept
secret.
The computer program
--------------------
The accompanying program Comp1 is a computer version of this which pits
strategies implemented as BASIC functions against one another. A strategy is
a piece of BASIC which, using the information available, must decide whether
to lay down a cooperate or defect card. A tournament is held between all the
strategies, and a ranking order is produced.
To see how to implement a strategy, let's have a look some of the strategies
in the program as supplied.
Each strategy is preceded by a DATA statement which gives its full name and
the name of the function which implements it. So, the Random strategy in the
program has the following data line:
DATA Random,random
because it is called "Random" and is implemented by FNrandom.
The function itself must return either a 1 to cooperate or a 2 to defect.
These are held in the variables cooperate% and defect% for ease of use, but
you can use the numbers if you want. The full listing of the random strategy
is:
DATA Random,random
DEF FNrandom(discard%)
=RND(2)
Ignore the parameter for the moment. It can be seen that random simply
returns either 1 or 2 without any consideration for previous moves, and is
therefore in a sense a "non-strategy".
A slightly more complex strategy is Tit for Tat:
DATA Tit for Tat,tit_for_tat
DEF FNtit_for_tat(subscript%)
IF round%=1 THEN =cooperate%
=move%(round%-1,subscript%)
This illustrates several points. Firstly, the parameter passed to the
function. This is the second subscript of the move%() array which holds the
details of the previous moves by both programs. move%(1,X) holds the result
of the first move by both programs - only AFTER the first move has been
made, obviously. move%(1,subscript%) is the move which was made by the
strategy's opponent on round 1. The current round number is held in the
variable round%.
Therefore, the Tit for Tat function will always cooperate on the first
round. After that, it makes whatever move its opponent made on the previous
round.
A still more complex (although not necessarily better) strategy is Grudger:
DATA Grudger,grudger
DEF FNgrudger(subscript%)
LOCAL opp_defect%,check%
IF round%=1 THEN =cooperate%
opp_defect%=FALSE
FOR check%=1 TO round%-1
IF move%(check%,subscript%)=defect% THEN opp_defect%=TRUE
NEXT
IF opp_defect% THEN =defect%
=cooperate%
This, like Tit for Tat, always cooperates on the first round. After that, it
checks all its opponents previous moves to see if it has ever defected. If
it has, Grudger also defects. If its opponent has not yet defected, Grudger
continues to cooperate.
You should now be able to work out what the other strategies provided do. In
order to help you to write your own, here are a few tips:
Always provide some special action for round 1, when there is no information
about your opponent's previous moves.
If you want to, you can also look at your own past moves by using
(3-subscript%) as the second array subscript.
Even if you are called after your opponent, move%(round%,subscript%) will
not yet contain your opponent's move, so you can't sneakily look at its
choice!
Note that in a tournament, all the programs play against each other,
including themselves. This means that your strategy will end up playing
against itself.
Also because of the tournament system, note that how successful a strategy
is is determined by how the other strategies behave. For instance, the Tit
for Two Tats strategy in the program as supplied is very good in this
"climate", but it might be unsuccessful if competing against different
strategies. This is true of all tournaments, and is not a failing of the
program.
Functions must not create any global variables of their own. They can only
read the ones provided - round% and move%(). However, you can create as many
LOCAL variables as you like.
The competition
---------------
To enter the competition, you must submit ONE strategy which will be entered
into a tournament with all the other entries. You need only submit the DATA
line and the function definition itself - they will be appended onto the end
of the routine by the competition organiser.
Of course, you can write as many strategies as you like for your own testing
purposes, but only ONE can be submitted. This is because it would otherwise
be possible to submit two strategies, one of which was designed to be
exploited by the other in order to increase its score.
Although the number of rounds is currently 200, this does not mean that you
can use 200-round% in your strategy to tell you how many rounds are left. In
the final tournament, the number of rounds will be changed to prevent this
kind of cheating!
N.B. - the supplied strategies are based on descriptions of those written by
several games theorists. I did not design them and they will not be entered
into the competition tournament with the exception of Random. The first
tournament of this kind was, I believe, held by a Dr/Professor (?) Axelrod,
who I feel obliged to mention as the inventor of this kind of contest.