[Algorithmus] Matrix nach Untermatrix durchsuchen

[Martin]

Ich suche nach einem Algorithmus, mit dem ich eine Matrix nach einer vorgegebenen Untermatrix durchsuchen kann. Die im Web verfügbaren Matrix-Packages bieten diese Funktion, so weit ich gesehen hab, nicht an. Hat jemand eine Idee, wie ich das am besten angeh?
In meinem speziellen Fall, beinhaltet die Matrix (beliebige Größe) nur die Werte 1 und 0 (eins bedeutet belegt und 0 frei), und es soll nach einer n*k-Untermatrix aus lauter Nullen gesucht werden. Der Algorithmus soll also z.B. erkennen, dass in folgender 5*3-Matrix nur noch ein 2*2-Feld frei ist.

1 1 1 1 1
1 1 1 0 0
1 1 1 0 0

Damit wäre mir fürs erste schon sehr geholfen. Toll wäre es dann noch, wenn auch jene Fälle berücksichtigt würden, bei denen die gesuchte Untermatrix in mehreren Teilen enthalten ist. Also z.B.:

1 1 1 1 1
1 1 1 0 0
1 0 0 1 1

wenn möglich aber auch

1 1 1 1 0
1 1 1 1 0
1 0 0 1 1

wichtig ist nur, dass immer mindestens zwei Felder nebeneinander frei sind.

Dann müsste man noch Fälle wie

1 1 0 0 1
1 1 1 0 0
1 1 1 1 1

1 0 1 1 1
1 0 0 1 1
1 1 0 1 1

herausnehmen, wo es zusätzlich eine vertikale/horizontale Überlappung gibt, usw.
(Ist ein Problem im Rahmen einer kleinen Spieleprogrammierung.)

Fürs erste wäre ich sehr dankbar, wenn jemand einen Ansatz für das grundlegende Problem hat, der in akzeptabler Rechenzeit machbar ist. Hab mir bis jetzt nur eine Lösung für 2*2-Untermatrizen überlegt und keine (vernünftige) Idee, wie sich das verallgemeinern lässt. Vielen Dank!

Grüße, Martin

 

[Wildcard]

Hab mal auf die Schnelle was zusammengetippt.
Ist weder hübsch, noch optimert (mehr so die Holzhammermethode )und nur als Denkanstoss gedacht.
Die Klasse sucht nach der größten zusammenhängenden Untermatrix(k*k)
in einer n*n Matrix. Sollen die 0er zu möglichst großen Blöcken einer 2er Potenz zusammengefasst werden,
oder willst du immer 2er Blöcke?
Vieleicht beschreibst du dass Problem mal anhand deines Spiels?

public class Matrix 
{
    private boolean[][] field;
   
    public Matrix()
    {
    }
    
    private boolean[][] start(boolean[][] field)
    {
        boolean [][] matrix = new boolean[0][0];
        boolean [][] tempMatrix = new boolean[0][0];
        for (int x=0;x<field.length;x++)
            for (int y=0;y<field[0].length;y++)
            {
                if (!field[x][y])
                {
                   tempMatrix = innerMatrix(field,x,y);
                   if (tempMatrix != null && tempMatrix.length>matrix.length)
                       matrix=tempMatrix;
                }
            }
        return matrix;
    }
    
    private boolean[][] innerMatrix(boolean[][] field, int x,int y)
    {
        boolean [][] innerMatrix = null;
        for (int max = 1;max<field.length-Math.max(x,y);max++)
        {
            boolean matrix = true;
            for (int i=0;i<=max;i++)
            {
                for (int j=0;j<=max;j++)
                {
                    if (field[i+x][j+y])
                       matrix=false; 
             
                }
            }
            if (matrix)
                innerMatrix=new boolean[max+1][max+1];
        }
        return innerMatrix;
    }
    
    public static void main(String[] args) 
    {
        boolean [][] field = new boolean [20][20]; 
        for (int i=0;i<field.length;i++)
        {
            for (int j=0;j<field[0].length;j++)
            {
                if (Math.random()<0.7)
                {
                    field[i][j]=true;
                    System.out.print(1);
                }
                else
                    System.out.print(0);
            }
            System.out.println();
        }
        System.out.println();
        Matrix m = new Matrix();
        field=m.start(field);
        for (int i=0;i<field.length;i++)
        {
            for (int j=0;j<field[i].length;j++)
            {
                if (field[i][j])
                    System.out.print(1);
                
                else
                    System.out.print(0);
            }
            System.out.println();
        }           
    }
}

 

[Martin]

Zuerst mal Danke für die schnelle Hilfe, der Algorithmus gefällt mir schon sehr gut. thx

Zu Deinen Fragen: Prinzipiell sollen die freien Teile zu einer möglichst großen Matrix zusammengesetzt werden. Dadaurch kann ich die aktuelle Spielposition (die ja durch eine solche Matrix repräsentiert wird) auf einen einfacheren Fall zurückführen, bei dem ich mich schon "auskenne". Zum Beispiel gibt es Strategien für ein 2k*2n bzw. ein 2k*2n+1-Feld (und ich weiß, welcher Spieler z.B. auf einem 3*3-Brett gewinnt).

Bei dem Spiel geht es im Wesentlichen darum, beliebig viele Steine (im einfachsten Fall der Größe 1*1, allgemeiner 1*2 bzw. 1*k) auf ein Spielfeld der Größe n*k zu legen. Pro Spielzug darf nur in einer Reihe oder Spalte gezogen werden. Zwei Spieler ziehen abwechselnd und gewonnen hat, wer den letzten/vorletzten (je nach Variante) Zug macht.
Hoffe die Regeln des Spiels sind soweit klar. Ansonsten bitte fragen.
Im Moment interessiert mich vor allem die Variante mit 1*2-Spielsteinen. Daher die Einschränkung, dass zwei nebeneinanderliegende Felder frei sein müssen.

Wichtig ist aber auch, dass wirklich nur diese Matrix (bzw. die einzelnen Zeilen/Spalten) frei bleiben. Kurz gesagt: ich möchte Situationen finden, in denen der Spieler die selben bzw. ähnliche Zugmöglichkeiten hat wie auf einem kleineren Spielfeld.

1.)
1 1 1 1 1 1 1
1 1 0 0 0 1 1
1 1 0 0 0 1 1
1 1 0 0 0 1 1

2.)
1 0 0 1 1 1 1
1 1 0 0 0 1 1
1 1 0 0 0 1 1
1 1 0 0 0 1 1


In obiger Situation (1) soll z.B. erkannt werden, dass nur noch eine 3*3-Matrix frei ist. Das heißt der KI-Spieler muss von dieser Position an nicht mehr weiteranalysieren (sondern nur wissen, wie er auf einem 3*3-Spielfeld zu spielen hat). Hingegen beschränkt sich (2) nicht auf den Fall einer 3*3-Matrix.
Ein zusätzliches Problem ist die Tatsache, dass man auch genau wissen (und speichern) muss, wo und wie ein kleineres Spielfeld in einem großen vorkommt um in der Lage zu sein, die Steine an die richtige Stelle (im ursprünglichen Spielfeld) zu setzen. Fürs erste werd ich mich daher wohl auf den Fall beschränken, dass das kleine Spielfeld in der üblichen Form (als eine zusammenhängende Matrix) im Großen vorkommt.

Vielen Dank schon mal für Eure Hilfe.

Martin

 

[Wildcard]

Dein 2.Beispiel besteht also korrekterweise aus 3 Untermatrizen.
Folgt der KI-Spieler einer bestimmten Regel? Gibt es Matrizen idealer Größe
(soll heißen versucht er als nächstes auf der größten Untermatrix zu setzen oder etwas in die Art)?
Wenn nicht? Woher weißt du welche Matrix du verwenden möchtest?

 

[Martin]

Eine genaue Strategie hab ich mir noch nicht überlegt. Es gilt aber folgendes:
Matrizen bei denen der 2. Spieler gewinnt sind zum Beispiel:
3*3 sowie 2k*2n (das heißt alle Felder mit gerader Zeilen- und Spaltenanzahl).
Wenn der Computerspieler auf einen solchen Fall spielt, gewinnt er (wenn er gut spielt).
Fälle, in denen der 1. Spieler gewinnt sind zum Beispiel alle 2k*(2n+1)-Felder. Spielt ein Spieler auf eine solche Position, hat sein Gegner die Chance ihn zu schlagen (=schlechter Zug).
Idealerweise sollte nach allen, bzw. nach möglichst großen Untermatrizen gesucht werden. Zur Zeit versuche ich für kleine Spielfelder den kompletten Spielegraph (Baum) zu berechnen (geht bis 3*5 ganz gut). Erst nachdem ich diese Möglichkeit ausgereizt habe (und ich glaube, dass ich durch die Reduzierung auf kleinere Spielfelder noch um einiges weiter kommen kann), werde ich mir genauere Strategien bzw. Heuristiken überlegen, mit denen man auf größeren Feldern gut spielen kann.

Zum 2. Beispiel. In welche drei Matrizen würdest Du das teilen. Man muss ja beachten, dass es durchaus Spielzüge gibt, die dann über mehrere dieser Untermatrizen gehen. Der Fall von mehreren Untermatrizen hilft mir (so weit ichs mir bis jetzt überlegt hab) nur, wenn diese völlig "unabhängig" von einander sind, d.h., wenn es keinen Zug gibt, der einen Stein mehrere Untermatrizen setzt. Also z.B.:

1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 0 0 0 1
1 1 1 1 1 1 0 0 0 1
1 1 1 1 1 1 0 0 0 1
1 1 1 0 0 1 1 1 1 1
1 1 1 0 0 1 1 1 1 0

Diese 10*5-Matrix enthält zwei Untermatrizen (3*3, 2*2). Das Feld ganz rechts unten kann vernachlässigt werden, da es durch keinen Zug gefüllt werden kann. Hab schon einen kleinen Algorithmus, der diese Felder (alle Nachbarn =0) mit Einsen auffüllt.

Martin

 

[Wildcard]

Das Problem das beim einteilen in kleinere Spielfelder entsteht, oder versteh ich jetzt das Spiel falsch,
ist aber das man die nicht so einfach isoliert betrachten kann.
Wenn der KI-Gegner in eine frei Untermatrix setzt, zwingt das denn Spieler doch nicht in die selbe Matrix
zu setzen. Oder doch?
Das heißt ein Sieg in einer Untermatrix kann zur Niederlage im Spiel führen?
Insofern ist mir nicht ganz klar wie du damit das Problem herunterbrechen kann.
Gibt es vieleicht auch einen Algorithmus für die Gesamtzahl der freien Felder
(so nach dem Motto versuche möglichst viele Felder pro Zug zu besetzen aber wähle eine gerade Zahl?)
Gibts irgendein Beispiel im Web wo ich mir das Spiel mal ansehen kann?

 

[Martin]

Am einfachsten wäre es natürlich, wenn wirklich nur eine komplette Matrix (oder auch lauter Felder, in die max. 1 Spielstein passt) übrig bleiben würden. Aber auch für den Fall, dass mehrere ganze Spielfelder (also zum Beispiel ein 2*2- und ein 3*3-Feld) übrig bleiben, kann man sich etwas überlegen (Summensatz für stark endliche Spiele). Ist jetzt auf die Schnelle schwer (anschaulich) zu erklären, funktioniert aber sehr gut. Kurz gesagt: Wenn Du weißt, was in jedem einzelnen Spiel los ist, kannst Du auch das Summenspiel (bei jedem Zug in einem der Spiele ziehen) analysieren.
Im Web gibt es das Spiel (so weit ich weiß nicht), ist ja auch quasi eine Eigenproduktion. Sobald ich das GUI fertig hab, kann ich Dir ja eine spielbare Version schicken (wird aber wohl noch dauern).

Martin

 

[Wildcard]

Dann müsste es dpch möglich sein mit dem Algorithmus von mir zu arbeiten.
Müsste man so erweitern das er auf n*k anwendbar ist. Statt die größte Matrix rauszufiltern sammelt man
alle, und eleminiert die, die schon komplett in einer andern enthalten sind.

 

[Martin]

Dein Algorithmus berücksichtigt aber noch nicht, dass der Rest des Spielfelds belegt sein muss. Das müsste man halt auch noch einbauen.

 

[Wildcard]

Dein Algorithmus berücksichtigt aber noch nicht, dass der Rest des Spielfelds belegt sein muss. Das müsste man halt auch noch einbauen.

Versteh nicht so ganz was du meins?
Es werden freie Untermatrizen gesucht, das heißt alles was nicht gefunden wird ist zwangsläufig belegt.
Wenn ich demnächst ein bisschen Zeit finde bau ich dir das so um das du alle freien Matrizen bekommst.

 

[Guest]

Es werden freie Untermatrizen gesucht, das heißt alles was nicht gefunden wird ist zwangsläufig belegt.

Nein.

1 0 0 1 1 1
1 1 1 0 0 1
1 1 1 0 0 1
0 0 1 1 1 0
1 1 1 0 1 0

Hier findet Dein Algorithmus die freie 2*2-Matrix in der Mitte. Das Spiel reduziert sich allerdings nicht auf ein 2*2-Spiel, da ich durchaus noch an anderen Stellen Spielsteine platzieren kann. Zum Beispiel so:

1 1 1 1 1 1
1 1 1 0 0 1
1 1 1 0 0 1
0 0 1 1 1 0
1 1 1 0 1 0

Mit diesen Fall würde ich wie folgt verfahren. Entweder (einfache Lösung) er wird gar nicht vereinfacht, oder ich finde einen Algorithmus der alle beiden (!) 2*2-Felder erkennt.

1 0 0 1 1 1
1 1 1 0 0 1
1 1 1 0 0 1
0 0 1 1 1 0
1 1 1 0 1 0

Ich möchte in erster Linie z.B. folgendes erkennen:

0 1 1 1 1
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0
1 0 0 0 0

Hier bleibt wirklich nur eine 4*4-Matrix übrig (und das nach nur 2 Zügen). Du kannst Dir sicher vorstellen, was für einen Rechenaufwand man sich sparen, kann wenn man hier abbrechen kann, anstatt alle (!) Möglichkeiten für die 4*4-Matrix zu analysieren.

Oder auch:
1 1 1 0 1 0
1 1 0 1 0 1
1 1 1 1 1 0
0 0 1 1 1 1
0 0 1 0 1 0
Hier bleibt genau eine 2*2-Matrix übrig (in die restlichen freien Felder kann nicht mehr gesetzt werden).

oder
1 1 1 0 0
1 1 1 0 0
0 0 1 1 1
0 0 1 1 1
(zwei 2*2-Matrizen)

nicht aber
1 1 0 0
0 0 0 0
0 0 1 1

(zwei 2*2 Matrizen, aber ein Zug möglich, der beide besetzt:

1 1 0 0
0 1 1 0
0 0 1 1

--> Spielposition kann nicht auf die Analyse von zwei 2*2-Spielen zurückgeführt werden)


Fürs erste such ich also nach einem Algorithmus, der folgendes tut (schreibs einfach nochmal möglichst ausführlich hin):

suche in einer n*k Matrix M eine möglichst große zusammenhängende Untermatrix
wenn gefunden (größe l*k){
   wenn nur noch in dieser Matrix Spielzug möglich --> return l,k
   sonst return 0,0
}

Die obigen Spezialfälle (Matrizen nicht zusammenhängend, mehrere Matrizen...) sind fürs erste noch nicht wichtig.

Ich hoffe Du weißt jetzt ungefähr, was ich meine. ??

Grüße (und Dank für Deine Mühe), Martin

 

[Wildcard]

Achso! Jetzt ist klar wie du meinst.
Sobald ich ein bisschen Luft hab überleg ich mir was.

 

[Martin]

Wäre echt super. Danke!

 

[Martin]

Ist Dein Angebot noch aktuell?
Hab mir gestern zwar was überlegt, aber ich kriegs nicht so ganz in den Griff.

Martin

 

[Wildcard]

Sorry, hab dich irgendwie vergessen.
Am besten du meldest dich hier an, dann schick ich dir meinen ersten Ansatz per PN

 

[Martin]

Hab mich angemeldet (war ja schon überfällig das mal zu tun ;-))
Nochmals Danke für Deine Hilfe!

Martin