How to optimize the code?

Hi Guys,

I developed a code that generates and displays all the possibilities of a game on a graph. Below, I'm sending the error-free code. The issue arises when the game has a large number of pieces, significantly increasing the quantity of possibilities. The question is: How can I optimize the code for better efficiency?

In the code, the variable "NBE," declared in the second line, ranges from 1 to 10. For options 1, 2, 3, 4, 5, it functions adequately. However, starting from 6 and onwards, the code fails to compile.

%% Variables Iniciales n^2+2n n=numero de fichas.
NBE= 4;% Número Bloques Equipo
EstadoInicial=[1:NBE 0 NBE+1:2*NBE];
GrafoEscalera=[EstadoInicial 0]; MatrizMatlab=[];
EstadosPendientes = 1; 

%% Generar Grafo
while (EstadosPendientes ~= 0)
    CEC=GrafoEscalera(:,end); % Ultima posición (Si ha sido visitado o no)
    PosicionEstadoConCero=find(CEC==0); % Encuentra 0s en la Matriz
    if isempty(PosicionEstadoConCero)
       EstadosPendientes = 1;
       break;
    end
    [NuevaCopiaEC] = GrafoEscalera(PosicionEstadoConCero(1,1),1:end-1);
    for P=1:4
        if P==1 % Accion 1 Mover 1 casilla a derecha
           NuevaCEC=NuevaCopiaEC;
           [MMatriz] = mover(NuevaCEC, 1);
           [MatrizMatlab] = NodosVertices(NuevaCEC, MMatriz, MatrizMatlab);
           [GrafoEscalera] = NuevoGrafo(MMatriz, GrafoEscalera);
        elseif P==2 % Accion 2 Mover 1 casilla a izquierda
           NuevaCEC=NuevaCopiaEC;
           [MMatriz] = mover(NuevaCEC, 2);
           [MatrizMatlab] = NodosVertices(NuevaCEC, MMatriz, MatrizMatlab);
           [GrafoEscalera] = NuevoGrafo(MMatriz, GrafoEscalera);
        elseif P==3 % Accion 3 Saltar 1 casilla a derecha
           NuevaCEC=NuevaCopiaEC;
           [SMatriz] = saltar(NuevaCEC, 1, NBE);
           [MatrizMatlab] = NodosVertices(NuevaCEC, SMatriz, MatrizMatlab);
           [GrafoEscalera] = NuevoGrafo(SMatriz, GrafoEscalera);
        elseif P==4 % Accion 4 Saltar 1 casilla a izquierda
           NuevaCEC=NuevaCopiaEC;
           [SMatriz] = saltar(NuevaCEC, 2, NBE);
           [MatrizMatlab] = NodosVertices(NuevaCEC, SMatriz, MatrizMatlab);
           [GrafoEscalera] = NuevoGrafo(SMatriz, GrafoEscalera);
        end
    end
    GrafoEscalera(PosicionEstadoConCero(1,1),end)=1;
end

%% Hallar la Frecuencia
%% Generar Grafo
[s,t] = IDNodos(GrafoEscalera, MatrizMatlab);
% MatrizA=[ID' num2str(Matriz1(:,1:end-1))];sourceTarget=[Matriz2 Matriz3];
G = graph(s,t);
h = plot(G,'Layout','force','WeightEffect','direct');
hold on

%% Funciones
% Levantar
function [MMatriz] = mover(MatrizB, lado)
    idx=find(MatrizB==0);
    [~,B]=size(MatrizB);
    if lado==1 && idx < B && idx > 1% Derecha
       Bloque=MatrizB(idx-1);
       MatrizB(idx-1)=0;
       MatrizB(idx)=Bloque;
    elseif lado==2 && idx < B % Izquierda
       Bloque=MatrizB(idx+1);
       MatrizB(idx+1)=0;
       MatrizB(idx)=Bloque;
    end
    MMatriz=MatrizB;
end

function [SMatriz] = saltar(MatrizB, lado, NB)
    idx=find(MatrizB==0);
    [~,B]=size(MatrizB);
    MA=(1:NB);MB=(NB+1:NB*2);
    if lado==1 && idx>2 % Derecha
       Bloque=MatrizB(idx-2);
       BloqueDeSalto=MatrizB(idx-1);
       % En que grupo esta Bloque y BloqueDeSalta
       if (ismember(Bloque,MA) && ismember(BloqueDeSalto,MB)) || (ismember(Bloque,MB) && ismember(BloqueDeSalto,MA))
          MatrizB(idx-2)=0;
          MatrizB(idx)=Bloque;
       end
    elseif lado==2 && idx < B-2% Izquierda
       Bloque=MatrizB(idx+2);
       BloqueDeSalto=MatrizB(idx+1);
       if (ismember(Bloque,MA) && ismember(BloqueDeSalto,MB)) || (ismember(Bloque,MB) && ismember(BloqueDeSalto,MA))
          MatrizB(idx+2)=0;
          MatrizB(idx)=Bloque;
       end
    end
    SMatriz=MatrizB;
end

function [MatrizMatlab] = NodosVertices(Matriz1, Matriz2, MatrizMatlab)
    [A,~]=size(MatrizMatlab);Comparar=1;
    if isequal(Matriz1, Matriz2)
        Comparar=0;
    else
        Matriz3 = [Matriz1 Matriz2];
        Matriz4 = [Matriz2 Matriz1];
        for j=1:A
            if isequal(Matriz3, MatrizMatlab(j,:)) || isequal(Matriz4, MatrizMatlab(j,:))
               Comparar=0;
            end
        end
    if Comparar==0
       MatrizMatlab=MatrizMatlab;
    elseif Comparar==1
           MatrizMatlab = cat(1,MatrizMatlab,Matriz3);
    end
    end
end

function [GrafoEscalera] = NuevoGrafo(Matriz1, Matriz2)
    [A,~]=size(Matriz2);
    Comparar=1;
    Matrizi=[Matriz1 0];
    for j=1:A
        if isequal(Matriz1, Matriz2(j,1:end-1))
           Comparar=0;
        end
    end
    if Comparar==0
       GrafoEscalera=Matriz2;
    elseif Comparar==1
       GrafoEscalera=cat(1,Matriz2,Matrizi);
    end
end

function [s,t] = IDNodos(Matriz1, Matriz2)
    [A,~]=size(Matriz1);
    [B,C]=size(Matriz2);
    s=[];t=[];
    for i=1:A
        Nodo = Matriz1(i,1:end-1);
        for j=1:B
            if isequal(Nodo, Matriz2(j,1:C/2))
                s(j,1) = i;
            end
            if isequal(Nodo, Matriz2(j,C/2+1:C))
                t(j,1) = i;
            end                        
        end
    end
end

Answer 1

[Nathan Hardenberg]

You write "the code fails to compile". What do you mean by that? You most likely run the code, and it takes very long to finish, right? At least so long that you stop it beforehand. Matlab does not compile, if you run it in Matlab itself.

Regarding the time it takes: It is very hard to optimize such large code if one does not have any more insighs except the code itself. But I think in your case it does not really matter. Displaying all possibilities is expected to take very long when you increase the number of players. I don't know details of the game, but the number of posibilities is most likely exponential. That's why it is quite fast in the begining, but at some point it takes very long. A popular example is a chess-engine, that tries to calculate all posiibilities. But if I remember correctly the maximum moves it can predict is about 5 or so (But other trickery gets used aswell, to save computation).

Small example:

Fill a "Connect Four"-game. Red and Yellow colored balls. Now it depends on the size of the board.

• 1x1 field: 2 possibilities
• 2x1 field: 4 possibilities
• 2x2 field: 16 possibilities
• ...
• 5x5 field: 33,554,432 possibilities
• 6x6 field: 68,719,476,736 possibilities

Here the number of possibilites gets calculated by , where n is the number of fields. As you can see, calculating all of that is very time expensive. And in your game it is most likely something similar

[John Jairo Páez Rodriguez]

"Thank you for your kind response. You are right about how difficult it is to optimize code without knowing its structure."

Best Regards.