function [A,J,computation,pathLength]=fimp(actionSpaces,funJ,A0)
% 
%
% Finds an improvement path for a N-player game. 
%
% Inputs:
% actionSpaces - cell array with N entries containing the action
%                spaces for each player. Specifically, 
%                       actionSpaces{i}
%                is a numerical row (or column) vector that
%                contains all the actions of player i.
    
% A0   - matrix with N entries with the player's actions at the start
%        of the improvement path.

% funJ - matlab anonymous function that returns an N-element matrix
%        with the players' costs for a given matrix of
%        players' actions. Specifically, given an N-element matrix A
%        with the actions of all the players, the costs' matrix is
%        obtained using  funJ(A)
%    
% Outputs:
% A  - matrix with N entries with the player's actions at the end
%      of the improvement path. 
% J  - matrix with N entries with the player's costs at the end
%      of the improvement path. 
% computations - number of time that J had to be evaluated to find
%                the path
% pathLength - number of elements in the path
%
% The variables, A0, J, A, and Js must all have the same size.
    
    computation=0;
    pathLength=1;

    N=prod(size(actionSpaces)); % number of players
    J=funJ(A0); % compute the initial costs for every player
    computation=computation+1;
    len=1;
    A=A0;
    improved=true;
    while improved
        improved=false;
        % range over players in random order
        for i=randperm(N)
            % range over all alternative actions for player i
            actionSpace=setdiff(actionSpaces{i},A(i));
            for newAi=actionSpace(randperm(length(actionSpace)))
                % oldPhi=sudoku_potential1(A);
                oldAi=A(i);  % save previous action
                A(i)=newAi;  % try alternative action
                newJ=funJ(A);
                % newPhi=sudoku_potential1(A);
                % if newJ(i)-J(i) ~= newPhi-oldPhi
                %     newJ(i)-J(i)
                %     newPhi-oldPhi
                %     error('error in potential\n');
                % end
                computation=computation+1;
                if newJ(i)<J(i)
                    % new action improves outcome for player i, keep it
                    %fprintf('player %3d: old a=%2d, Ji=%7g > new a=%2d, Ji=%7g -- improved\n',i,oldAi,J(i),A(i),newJ(i));
                    J=newJ;
                    improved=true;
                else
                    % new action does not improve, discard it
                    % if i==specialPlayer
                    %     fprintf('player %3d: old a=%2d, Ji=%7g <= new a=%2d, Ji=%7g\n',i,oldAi,J(i),A(i),newJ(i));
                    % end
                    A(i)=oldAi;
                end
            end % for newAi=...
            if improved
                % found improvement: keep new action and try all players again
                pathLength=pathLength+1;
                break; % for i=...
            end
        end % for i=...
    end % while improved
    
end