% Řešení antagonistického konfliktu dvou hráčů - jednomaticové hry ve tvaru m x n
close all, clear all, clc
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Zadejte výplatní matici A, např. následovně:
% A=[7 -3; -1 6]

%Matice A musí nabývat rozměrů alespoň 2x2.
%Grafické znázornění řešení lze zobrazit u her s maticí A ve tvaru m x 2 nebo 2 x n.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Příklady vstupních parametrů:

%2 sedlové body
% A=[5 6 5; 2 7 4; 4 6 5]

%kámen nůžky papír
% A=[0,1,-1;-1,0,1;1,-1,0]

%z Wikipedie
% A=[6 2 4 3 5; 3 9 3 1 4; 5 10 4 4 5; 6 8 5 7 6; -3 7 2 1 5]

%0 sedlových bodů => smíšené strategie
% A=[6 -1 5; 4 -4 0; 1 7 10]

%0 sedlový bodů => smíšené strategie
% A=[-2 3 1;3 -4 0]

%0 sedlových bodu => smíšené strategie
% A=[-2 6;7 -3;-1 6]

%0 sedlových bodu => smíšené strategie
% A=[7 -3; -1 6]

% smíšené strategie, grafická metoda z [4]
% A=[5 5/2 3; 4 8 6]

% smišené strategie, grafická metoda z [7]
% A=[1 -2 5;3 4 0]

% příklad z diplomové práce pro znázornění rovnovážného bodu
% A=[4 3 3 4;-5 4 2 8;6 7 -2 7]

% příklad z diplomové práce pro grafickou metodu
% A=[3 0 7; 5 6 2]

% příklad z diplomové práce
%  A=[6 5 6 6;-3 6 4 10;8 9 0 9]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Zadejte vstupní parametry:




%kód algoritmu:
size_check=0;
[m,n]=size(A);
if (m>=2 && n>=2)
    size_check=1;
end

if (size_check==1)
    %radkova minima
    for i=1:m
        Ai=A(i,:);
        mn=min(Ai);
        [~,p{i}]=find(Ai==mn); %[m,n]=find(min) <--zajima me jen index sloupce n
        k1(i)=numel(p{i}); %pocitani, kolikrat je minimum na radku
    end
    
    %sloupcova maxima
    for i=1:n
        Bi=A(:,i);
        mx=max(Bi);
        [q{i},~]=find(Bi==mx); %[m,n]=find(min) <--zajima me jen index radku m
        k2(i)=numel(q{i}); %pocitani, kolikrat je minimum ve sloupci
        
    end
    
    %indexovani radkovych minim
    X= [0,0];
    for i=1:numel(k1)
        for j=1:k1(i)
            C1(j,:)=[i,p{i}(j)]; %v ramci i-teho p-cka najdi j-tou hodnotu C1(1,1)=[]
        end
        X=[X;C1];
        C1=[];
    end
    
    %indexovani sloupcovych maxim
    Y=[0,0];
    for i=1:numel(k2)
        for j=1:k2(i)
            C2(j,:)=[i,q{i}(j)]; %v ramci iteho q-cka najdi jtou hodnotu
        end
        Y=[Y;C2];
        C2=[];
    end
    
    %odstraneni prvnich nul
    X=X(2:end,:);
    Y=Y(2:end,:);
    
    %prohozeni indexu ve sloupcovych maximech
    swap = [1 2];
    Y(:, swap) = Y(:, flip(swap));
    
    %nalezeni spolecnych strategii minmax=maxmin
    C = intersect(X,Y,'rows');
    
    disp('Nalezená řádková minima:')
    [length_Z,~] = size(X); %kolik ma matice radkovych minim radku(tzn, zaznamu)
    for i=1:length_Z
        fprintf('Strategie x%g: a(i=%g,j=%g)=%g\n',X(i,1),X(i,1),X(i,2),A(X(i,1),X(i,2)));
    end
    
    disp('............................')
    disp('Nalezená sloupcová maxima:')
    [length_U,~] = size(Y); %kolik ma matice sloupcovych maxim radku(tzn, zaznamu)
    for i=1:length_U
        fprintf('Strategie y%g: a(i=%g,j=%g)=%g\n',Y(i,2),Y(i,1),Y(i,2),A(Y(i,1),Y(i,2)));
    end
    
    [length_C,~] = size(C);
    saddle_check=0;
    %kontrola existence sedloveho prvku
    if (length_C>0)
        disp('............................')
        if(length_C>1)
            disp('Řešením hry jsou nedominované rovnovážné body:')
        else
            disp('Řešením hry je nedominovaný rovnovážný bod:')
        end
        for i=1:length_C
            fprintf('a(i=%g,j=%g)=%g \n',C(i,1),C(i,2),A(C(i,1),C(i,2)));
        end
        fprintf('cena hry je: v=%g \n',A(C(1,1),C(1,2)));
        
    else
        disp('............................')
        % LINEARNÍ PROGRAMOVÁNÍ %
        %X = linprog(f,A,b,Aeq,beq,LB,UB)
        
        %linprog parametry prvniho hrace
        f1=[zeros(m,1);-1];
        A1=-A';
        A1_linprog=[A1 ones(n,1)];
        b1=zeros(n,1);
        A1eq=[ones(1,m) 0];
        b1eq=1;
        LB1=[zeros(m,1); -inf];
        
        X1_linprog=linprog(f1,A1_linprog,b1,A1eq,b1eq,LB1);
        X1=X1_linprog(1:m); %vypis smisenych strategii
        v1=X1_linprog(m+1); %vypis ceny hry
        
        %linprog parametry druheho hrace
        f2=[zeros(n,1); 1];
        A2_linprog=[A -ones(m,1)];
        b2=zeros(m,1);
        A2eq=[ones(1,n) 0];
        b2eq=1;
        LB2=[zeros(n,1); -inf];
        
        X2_linprog=linprog(f2,A2_linprog,b2,A2eq,b2eq,LB2);
        X2=X2_linprog(1:n); %vypis smisenych strategii
        v2=X2_linprog(n+1); %vypis ceny hry
        
        disp('............................')
        disp('Matice nemá žádný sedlový prvek, řešení hry existuje ve smíšených strategiích:');
        disp('Pravděpodobnosti voleb strategií prvního hráče:');
        for i=1:size(X1-1)
            fprintf('x%g=%g \n',i,X1(i));
        end
        fprintf('cena hry je v=%g \n',v1);
        
        disp('......................................');
        
        disp('Pravděpodobnosti voleb strategií druhého hráče:');
        for i=1:size(X2-1)
            fprintf('y%g=%g \n',i,X2(i));
        end
        fprintf('cena hry je v=%g \n',v2);
        
        %GRAFICKA METODA - pokud je matice ve tvaru 2 x n nebo m x 2:
        %%%%%%%%%%%%%%%%%%% matice 2 x n %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
        if m==2 && n>=2
            graph_check=0;
            figure(1)
            for i=1:n
                [y1(i),y2(i)] = graph_line_value(A(1,i),A(2,i));
                plot([0,1],[y1(i),y2(i)],'-k')
                hold on
            end
            %vyznaceni ceny hry
            plot([X1(1),X1(1)],[0,v1],'-b','LineWidth',1.2)
            hold on
            plot([0,1],[0,0],'-k')
            hold on
            set(gca,'XLim',[0 1])
            xlabel('p')
            ylabel('g( j )')
            title('Grafické řešení hry pro strategie hráče 1')
            
            %nalezeni indexu optimalnich smisenych strategii
            j=1;
            for i=1:length(X2)
                if X2(i)>0
                    opt_index(j)=i;
                    j=j+1;
                    
                end
            end
            
            %tvorba matice pro zpracovani grafickeho reseni pro druheho hrace
            A_opt_2=[A(1,opt_index(1)),A(1,opt_index(2));A(2,opt_index(1)),A(2,opt_index(2))];
            A_opt_2=A_opt_2';
            figure(2)
            for i=1:2
                [y1(i),y2(i)] = graph_line_value(A_opt_2(1,i),A_opt_2(2,i));
                plot([0,1],[y1(i),y2(i)],'-k')
                hold on
            end
            
            %vyznaceni ceny hry
            plot([X2(opt_index(1)),X2(opt_index(1))],[0,v1],'-b','LineWidth',1.2)
            hold on
            plot([0,1],[0,0],'-k')
            hold on
            set(gca,'XLim',[0 1])
            xlabel('q')
            ylabel('g( j )')
            title('Grafické řešení hry pro strategie hráče 2')
        end
        
        graph_check=0;
        if(m==2 && n==2)
            graph_check=1; %zruseni dvojnasobneho vykreslovani pro 2x2 hry
        end
        
        %%%%%%%%%%%%%%%%%%% matice m x 2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
        if n==2 && m>=2 && graph_check==0
            figure(1)
            for i=1:m
                [y1(i),y2(i)] = graph_line_value(A(i,1),A(i,2));
                plot([0,1],[y1(i),y2(i)],'-k')
                hold on
            end
            %vyznaceni ceny hry
            plot([X2(1),X2(1)],[0,v1],'-b','LineWidth',1.2)
            hold on
            plot([0,1],[0,0],'-k')
            hold on
            set(gca,'XLim',[0 1])
            xlabel('q')
            ylabel('g( j )')
            title('Grafické řešení hry pro strategie hráče 2')
            
            %nalezeni indexu optimalnich smisenych strategii
            j=1;
            for i=1:length(X1)
                if X1(i)>0
                    opt_index(j)=i;
                    j=j+1;
                    
                end
            end
            
            %tvorba matice pro zpracovani grafickeho reseni pro druheho hrace
            A_opt_2=[A(opt_index(1),1),A(opt_index(2),1);A(opt_index(1),2),A(opt_index(2),2)];
            A_opt_2=A_opt_2';
            figure(2)
            for i=1:2
                [y1(i),y2(i)] = graph_line_value(A_opt_2(1,i),A_opt_2(2,i));
                plot([0,1],[y1(i),y2(i)],'-k')
                hold on
            end
            
            %vyznaceni ceny hry
            plot([X1(opt_index(1)),X1(opt_index(1))],[0,v1],'-b','LineWidth',1.2)
            hold on
            plot([0,1],[0,0],'-k')
            hold on
            set(gca,'XLim',[0 1])
            xlabel('p')
            ylabel('g( j )')
            title('Grafické řešení hry pro strategie hráče 1')
        end
    end
else
    disp('Chyba: matice musí mít rozměry alespoň 2x2.');
end

%  FUNKCE PRO GRAFICKE ZNAZORNENI 2 x n / m x 2
function [y1,y2] = graph_line_value(c1,c2)

g= @(x) c1*x + c2*(1-x);
y1 = feval(g,0);
y2 = feval(g,1);

end



