Prisoner Dilemma Problem

-

Prisoner Dilemma Problem

Cooperation is usually analyzed in game theory by means of a non-zero-sum game called the “Prisoner’s Dilemma”. The two players in the game can choose between two moves, either “cooperate” or “defect”. The idea is that each player gains when both cooperate, but if only one of them cooperates, the other one, who defects, will gain more. If both defect, both lose (or gain very little) but not as much as the “cheated” co-operator whose cooperation is not returned. The whole game situation and its different outcomes can be summarized by table below, where hypothetical “points” are given as an example of how the differences in result might be quantified.

Payoff Matrix for Prisoner Dilemma
Player 1
Player 2

Cooperate
Defect
Cooperate
3,3
5,0
Defect
0,5
1,1



Step1 : Initialization of 20 population each of 70 (64+6) Strings where six extra letters encode three previous games used by strategy to decide how to move in the first actual game.

Step 2 : Fitness Function has been evaluated based on the payoff matrix table mentioned above.

Step 3 : Selection : Sorted selection has been used which sorts the fitness of 20 individuals and return the  index of top eight fittest individuals.

Step 4: Crossover : Single point crossover is used where the point is randomly selected.

Step 5 : Termination : implementation has been coded for 40 different runs of 50 generations  using different random number seeds for each run.



Source Code

Language :MATLAB

Source code for Fitness function :


function [ total_score ] = Fitness( a )

    p1=0;
    p2=0;
    for i=1:2:70         %calculating the values according to truth table.
   
        if (a(i)==1 && a(i+1)==1)
            p1=p1+3;
            p2=p2+3;
        end
       
        if (a(i)==1 && a(i+1)==0)
            p1=p1+5;
            p2=p2+0;
        end
       
        if (a(i)==0 && a(i+1)==1)
            p1=p1+0;
            p2=p2+5;
        end
       
        if (a(i)==1 && a(i+1)==1)
            p1=p1+1;
            p2=p2+1;
        end
    end
    total_score=p1+p2;           % Return the total score of the string.
end




Source code for Selection function :

function [ Index ] = selection( Score , pop_size , best_pop_size )
% The function for sorting the score array and finding the index of best score 
    temp=Score;
    for i=1:pop_size
        for j=pop_size:-1:i
            if(temp(i)<temp(j))
                t=temp(i);
                temp(i)=temp(j);
                temp(j)=t;
            end
        end
    end
    
    for i=1:best_pop_size
        for j=1:pop_size
            if(temp(i)==Score(j))
                Index(i)=j;
            end
        end
    end
end


** Score represents the fitness of individuals of size 'pop_size' from which 'best_pop_size' fittest individuals will be selected based on their fitness for the crossover.


Source code for Crossover function :

function [ P1 P2 ] = crossover( P1 , P2 )
 % single Random point crossover between Parent P1 and P2
    crossover_point=round(1+rand()*60);     % single Random point crossover
    for i=crossover_point:70
        temp=P1(i);
        P1(i)=P2(i);
        P2(i)=temp;
    end
end


Source code for Maximum function :

function [ max ] = maximum( a , size )
% The function return the index of element that have maximum value
    max=1;
    for i=2:size
        if(a(max)<a(i))
            max=i;
        end
    end
end

Source code for main programme :

clc;
clear;
% The number of generations to be scanned.
No_of_generation=input('Enter the number of generations:');                  %Chrmosome size 70 bit string each
chrom_size=70;                         
% total no of runs
no_of_run=40;
best_string_after_each_run=zeros(no_of_run,chrom_size);
best_score_after_each_run=zeros(1,no_of_run);
run=1;
while(run<=no_of_run)


% population size
pop_size=20;                                   
% Chrmosome size 70 bit string each
chrom_size=70;                                 
% 8 best out of tournament
best_pop_size=8;                               
% total population in each generation
a=zeros(pop_size,chrom_size);                  
% fitness score of each indivisual
Score=zeros(1,pop_size);                       
% 8 fittest indivisual in each genearation
select_string=zeros(best_pop_size,chrom_size);  best_score=zeros(1,No_of_generation);    
best_string=zeros(No_of_generation,chrom_size);
counter=1;

%%========================= Population initialization ==================%%
% Initialization of 20 population each of 70 bit strings
for i=1:pop_size               
      for j=1:chrom_size
            a(i,j)=round(rand());
      end
end
%%========================= Population initialization ==================%%


%%========================= Fitness Evaluation =========================%%
% finding the fitness of each indivisual in the population
for i=1:pop_size                                        
    Score(i)=Fitness(a(i,:));
end
%%========================= Fitness Evaluation =========================%%

%%============================= selection ==============================%%

 % computing the indices of best population out of population size
Index=selection(Score,pop_size,best_pop_size);      

 %%============================= selection ==============================%%

for i=1:best_pop_size
    % The order of best Score is stored in Index
    p=Index(i);                                        
for j=1:chrom_size
    select_string(i,j)=a(p,j);
    end
end

while(counter <=No_of_generation)

    for i=1:2:best_pop_size-1
        [a1 a2]=crossover(select_string(i,:),select_string(i+1,:));
        select_string(i,:)=a1;
        select_string(i+1,:)=a2;
    end
    Score=zeros(1,pop_size);
    % Fitness function returns the Score of each best string
    for i=1:best_pop_size-1
        Score(i)=Fitness(select_string(i,:));                      
    end
    Index=selection(Score,pop_size,best_pop_size);
    best_score(counter)=Score(Index(1));
    p=Index(1);
    for j=1:chrom_size
        best_string(counter,j)=a(p,j);
    end
    counter=counter+1;
end
fprintf('\n================ RESULT FROM RUN%d ==================\n\n',run);
% output the best score after each run.
for p=1:No_of_generation                                  
fprintf('The best score in the generation%d :',p);
    fprintf(' %d \n', best_score(p));
end
fprintf('\n');
for i=1:No_of_generation
    fprintf('\nTHE BEST STRING IN GENERATION %d:', i);
    for j=1:chrom_size
        if(mod(j,2)==1 && j~=1)
            fprintf(' ');
        end
      % Converting 1’S AND 0’S to D AND C
        if(best_string(i,j)==1)       
           fprintf('D');
        else
            fprintf('C');
        end
    end
end
% Computing the index of best from selected.
ind=maximum(best_score,No_of_generation);                   
fprintf('\n\nTHE BEST STRING IN ALL GENERATION :');
for i=1:chrom_size
    if(mod(i,2)==1 && i~=1)
        fprintf(' ');
    end
    if(best_string(ind,i)==1)
        fprintf('D');
    else
        fprintf('C');
    end
    best_string_after_each_run(run,i)=best_string(ind,i);
end
fprintf('\nTHE CORRESPONDING BEST SCORE IS: %d \n',best_score(ind));
best_score_after_each_run(run)=best_score(ind);
run=run+1;
end
% Computing the index of best from selected after each run.
ind1=maximum(best_score_after_each_run,no_of_run);          
fprintf('\n== RESULT AFTER %d RUN OF %d GENERATIONS ==',run-1,No_of_generation);
fprintf('\n\nTHE BEST STRING AFTER 40 RUN :');
for i=1:chrom_size
    if(mod(i,2)==1 && i~=1)
        fprintf(' ');
    end
    if(best_string_after_each_run(ind1,i)==1)
        fprintf('D');
    else
        fprintf('C');
    end
end
fprintf('\nTHE CORRESPONDING BEST SCORE IS: %d \n',best_score_after_each_run(ind1));







*********** The End ***********

Popular posts from this blog

8 Bit Plane Slicing of an image in Image Processing

-
Image
%================ Bit Plane Slicing Program =================% A=imread('bit_plane_img.tif'); subplot(3,3,1),imshow(A),title('INPUT IMAGE'); for i=1:8     B=bitplaneslicing(A,i);     subplot(3,3,i+1),imshow(B),title(i); end %====================================================% %================ Bit Plane Slicing Function =================% function [ B ] = bitplaneslicing( A ,n) % function for n bit plane slicing where n<=8 [M,N]=size(A); B=zeros(M,N); for i = 1:M     for j = 1:N         str=dec2bin(A(i,j),8);         if strcmp(str(9-n),'0')             B(i,j)=0;         else             B(i,j)=2^(n-1);         end     end end end %====================================================% Input Image: bit_plane_img.tif Output Image:
Read more

Code to upload multiple files simultaneously using JSP, Servlet .

-
Image
Step 1 : Create a jsp page. index.jsp <%--      Document   : index     Created on : 21 Sep, 2013, 5:58:32 PM     Author     : snlkjha --%> <%@page contentType="text/html" pageEncoding="UTF-8"%> <!DOCTYPE html> <html>     <head>         <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">         <title>JSP Page</title>     </head>     <body>         <form action="UploadServlet" method="post" enctype="multipart/form-data">             <input type="file" id="file" name="file1" accept="image/*"  multiple="muliple" required/><br>             <input type="submit"/>            <br><br> ${requestScope.message} ...
Read more

STRING PALINDROME USING STACK AND QUEUE

-
#include<stdio.h> #include<stdlib.h> #include<string.h> void push(char ); char pop(); void nq(char ); char dq(); typedef struct list {     char data;     struct list *next; }node; node *top=NULL,*front=NULL,*rear=NULL; int main() {     char word[20];     printf("Type the Word:");     scanf("%s",word);     int length=strlen(word),i=0;     while(word[i]!='\0')     {         push(word[i]);         nq(word[i]);         i++;     }     for(i=0;i<length;i++)     {         if(pop()!=dq())         break;             }     if(i==length)        ...
Read more