8-Bit Software Competition by Steven Flintham (15A) ---------------------------- Imagine two men sitting in a room facing each other across a table. Eachhas 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 turnsover the two cards and pays one or both of the players depending on whichcards 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, sincethe cards are not turned over until both have played. The big question is - how should oneplay to obtain the largest possible amount of money? You might reason that if your opponenthas played cooperate, your best move isto 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 thenreceive 1 instead of your opponentreceiving 5. So, using logic (?), youhave deduced that you should always defect. However, your opponent can legitimately follow exactly the same reasoning and deduce that he/she shouldalso defect all of the time. This leadsto you both receiving £1 per go - so you are both worse off than you wouldbe 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 explainingwhy 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 chancefor revenge. This knowledge leads to similar behaviour on the second from last move, and therefore the third fromlast move, and so on, which is why the duration of the game must be keptsecret. 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 andthe 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 variablescooperate% and defect% for ease of use, but you can use the numbers if youwant. 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 movesby both programs. move%(1,X) holds theresult 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 thefirst round. After that, it makes whatever move its opponent made on theprevious 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 forround 1, when there is no information about your opponent's previous moves. If you want to, you can also lookat 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 theprograms play against each other, including themselves. This means thatyour 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 theprogram 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 bythe 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 thatyou can use 200-round% in your strategyto tell you how many rounds are left. In the final tournament, the number ofrounds will be changed to prevent thiskind 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.