8-Bit Software
Competition by Steven Flintham (15A) ----------------------------
Imagine two men 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 TEMPTATION TO
MUTUAL DEFECT
C COOPERATION
3 TO BOTH 5 TO P1
P2
TEMPTATION TO 'PENALTY' FOR
DEFECT MUTUAL
D DEFECTION
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.