Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Unnötige Schritte beim Brute-Force

Werbeanzeige

Thurien

Frischling

  • »Thurien« ist der Autor dieses Themas

Beiträge: 19

  • Private Nachricht senden

1

26.05.2015, 01:00

Unnötige Schritte beim Brute-Force

Hallo Zusammen!

Ich habe folgendes Problem:

Gegeben ist eine beliebige n x m-Matrix, mit n,m > 1, bestehend aus natürlichen Zahlen von einschließlich 1 bis einschließlich 7, oder gar keinem Wert. Beispielsweise sei folgende Matrix gegeben:

1 1 1
2 2 2

Man kann einen der Einträge in der Matrix um zwei Erhöhen bzw. verringern, wodurch sich alle direkten horizontalen und vertikalen Nachbarn um einen erhöhen bzw. verringern. Beispielsweise kann ein Zug wie folgt aussehen:

3 2 1
3 2 2

Das Ziel ist es, alle Werte in der Matrix gleich zu kriegen. Beim einem anderen Beispiel wären dies folgende zwei Züge:

1 3 5 -> 3 4 5 -> 5 5 5

Erlaubt sind dabei beliebig viele Züge. Sollte der Wert selber oder einer der Nachbar-Werte bei einem Zug über 7 oder unter 1 kommen, ist der Zug ungültig und es passiert nichts mit den Werten.

Ich möchte nun gerne einen "Löser" für diese Regeln implementieren und dabei die minimale Anzahl an Züge zum lösen und die hierbei benötigten Züge herausfinden und setze dabei auf einfaches ausprobieren aller Möglichkeit. Schnell stellte ich fest, dass mit steigender "maximalen Suchtiefe" die Anzahl der Durchläufe schnell wächst und bereits nach einer maximalen Suchtiefe von 7 Zügen und einem 2x3 Feld, etwa 19. Millionen Durchgänge benötigt werden. Dabei habe ich schon optimiert, dass auf dem selben Feld nicht hintereinander erhöht/verringert werden kann, da dies ja den vorherigen Zug irrelevant macht. Der Code sieht folgendermaßen aus:

Java-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

public void solve() {
        int currentDepth = 0;
        GridSolution solution = new GridSolution();
        
        for (int newY = 0; newY < gridCells.length; newY++) {
            for (int newX = 0; newX < gridCells[newY].length; newX++) {

                if (gridCells[newY][newX].getType() == GridCell.Type.NONE) continue;
                
                _solve(gridCells, newX, newY, Direction.INCREASE, currentDepth, solution);
                _solve(gridCells, newX, newY, Direction.DECREASE, currentDepth, solution);
                
            }
        }
        
        Collections.sort(solutions);
    }
    
    private void _solve(GridCell[][] grid, int x, int y, Direction direction, int depth, GridSolution solution) {

        this.iterations++;
        GridCell[][] copy = Grid.CopyGrid(grid);
        GridSolution copySolution = new GridSolution(solution);

        
        if (Grid.checkSolved(grid)) {
            solutions.add(copySolution);
            return;
        }

        if (direction == Direction.INCREASE) {
            if(!Grid.increase(copy, x, y)) {
                return;
            }
        } else {
            if(!Grid.decrease(copy, x, y)) {
                return;
            }
        }
        
        copySolution.AddTurn(new GridTurn(x, y, direction));
        
        
        depth += 1;
        
        if (depth > MAX_DEPTH) {
            return;
        }
        
        for (int newY = 0; newY < gridCells.length; newY++) {
            
            for (int newX = 0; newX < gridCells[newY].length; newX++) {
                
                if (gridCells[newY][newX].getType() == GridCell.Type.NONE) continue;
                
                if (newY != y && newX != x && direction != Direction.DECREASE) {
                    
                } else {
                    _solve(copy, newX, newY, Direction.INCREASE, depth, copySolution);
                }
                
                if (newY != y && newX != x && direction != Direction.INCREASE)  {
                    
                } else {
                    _solve(copy, newX, newY, Direction.DECREASE, depth, copySolution);
                }
                
            }
            
        }

    }


Was ich mir nun als nächstes dachte ist, dass ich ja einfach alle "Zustände", die bereits einmal gelöst worden sind, speichern kann und diese in Zukunft ignorieren. Das sollte dann ja einen Schneeballeffekt haben und die Anzahl der Durchgänge drastisch verringern und vor allem den exponentiellen Anstieg der Durchgänge mit erhöhter Suchtiefe stoppen. Implementieren wollte ich das ganze durch folgenden Code am Anfang der _solve-Methode

Java-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11

        //"Hash", to prevent deep copy comparing
        String hash = direction.toString() + Grid.createGridCellHash(grid);
        
        //Check if this state was already parsed
        for (String parsedGridHash : parsedStatesHashes) {
            if (parsedGridHash != "" && parsedGridHash.equals(hash))
                return;
        }
        
        //After completely parsing this state, add it to parsed states
        parsedStatesHashes.add(hash);


Die Anzahl der Durchgänge ist so von 19.000.000 auf gerade einmal 8 gesunken. Jedoch wird die richtige Lösung auch nicht mehr erkannt. Das lag dann natürlich daran, dass ich Zustände bereits als gelöst gespeichert habe, bevor sie tatsächlich gelöst wurden. Also packte ich das "parsedStatesHashes.add(hash)" an das Ende der _solve Methode. Nun sind es 48 Durchläufe, was mir logisch erscheint. Jedoch ist wieder keine Lösung dabei, obwohl bei der selben Matrix unoptimiert die perfekte Lösung gefunden wird.

Mir erscheint nun selber kein Logikfehler mehr, der mir unterlaufen ist. Filtere ich unabsichtlich nun zu früh eventuell korrekte Lösungen oder übersehe ich irgendeinen Denkfehler in meinem Code? Ich weiß, dass das viele Objekt-Erstellen sehr unperformant ist, jedoch fällt mir jedoch hierzu momentan keine Lösung ein. Außerdem hat das Überprüfen mit Profilern ergeben, dass dies nicht der Bottleneck ist, sondern tatsächlich das Milliardenfache durchlaufen.

Ich hoffe, dass jemand mir einen Tipp geben kann, der meine Lösung performanter und realistisch einsetzbar macht.

TypeOverride

Treue Seele

Beiträge: 268

  • Private Nachricht senden

2

26.05.2015, 01:44

Falls es ein "Suchproblem" ist, kannst du dir ja mal "Minimax" oder "Alpha-Beta Pruning" angucken.

Thurien

Frischling

  • »Thurien« ist der Autor dieses Themas

Beiträge: 19

  • Private Nachricht senden

3

26.05.2015, 08:02

Es gibt in meinem Fall jedoch keine zwei Spieler, sondern nur einen. Und mein Problem wäre darauf übertragen die Erstellung der
Bewerungsfunktion. Oder halten die beiden Theorien diesbezüglich noch etwas offen?

Ich denke, dass es sich momentan nur noch um einen Logikfehler bezüglich des Filterns der bereits durchgekauten Zustände handelt, jedoch komme ich einfach nicht da drauf.

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

4

26.05.2015, 08:46

Sehe ich es richtig, dass es nur 7 Zielzustände gibt? Dann käme eine bidirektionale Suche in Frage. Mit dieser kannst du die Suchtiefe halbieren.
David Scherfgens Website | Konzentrationstest Polizei

Thurien

Frischling

  • »Thurien« ist der Autor dieses Themas

Beiträge: 19

  • Private Nachricht senden

5

26.05.2015, 10:10

Bidirektionale Suche ist echt ein cooles Stichwort, danke. Das werde ich auf jeden Fall noch umsetzen.

Jedoch würde eine Halbierung noch immer nicht viel bringen, da bei einer maximalen Suchtiefe von etwa 20 und damit dann 10, und einer Matrix von bereits 5x5 die Anzahl der Durchläufe noch immer so gewaltig steigt, dass es nicht zweckmäßig einsetzbar sind. Also würde dies als weitere Optimierung in Frage kommen, aber ich denke den Großteil der Optimierung wird das Weglassen bereits durchlaufener Zustände sein, oder nicht? Die Frage ist nur, was an meiner Implementierung falsch sein könnte.

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

6

26.05.2015, 11:11

Wenn du kein Brute Force machen willst, dann mach doch einen A* und benutze als Schaetzfunktion eine Heuristik wieviel Zuege du aus einem bestimmten Zustand noch mindestens brauchen wirst. Dazu musst du ja nur berechnen, wie weit die Zahlen vom Durchschnitt abweichen. z.b. bei 1 3 5 ist die Abweichung 4, mit einem Zug kannst du maximal 5 addieren oder subtrahieren, es geht also in 1 Schritt usw. So hast du einen Lower Bound. Und wenn du eine Loesung findest kannst du die auch noch als Upper Bound nehmen.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Evrey

Treue Seele

Beiträge: 245

Beruf: Weltherrscher

  • Private Nachricht senden

7

26.05.2015, 11:30

Ich sehe nirgends, dass du die Grenzen von 1 bis 7 überprüfst. Für diese Grenzen brauchste sogar nur 4 Bit für jede Zelle der Matrix, oder 8 Bit, wenn du dir viel Shifting ersparen willst. Solltest du 4 Bit nutzen, kannste dir auch das ganze Hash-Gedönse sparen, da die Information selbst kompakt genug für einen direkten Vergleich ohne SSE ist.

Eine weitere Möglichkeit, unsinnige Rechenschritte zu sparen, ist die Erkennung von Symmetrie. Diese zwei Matrizen haben zum Beispiel im Prinzip die gleichen Lösungswege, bloß in der Mitte gespiegelt:

Quellcode

 
1
2

321    123
322    223
Da du Hashes gegen Dopplungen nutzt, kannst du dir einen Hash ausdenken, der solche Symmetrien als "Gleich" erkennt. Beispiel:

Quellcode

 
1
2

abc
def  => Hash => (a^c)<<24 | (d^f)<<16 | (b)<<8 | (e)<<0
Den Hash kannste dann auch direkt so als Integer nutzen, spart dieses unsinnige String-Gedönse. Weiterhin solltest du ein Set für die Hashes nutzen. Diese Container erkennen dank Hashing automatisch beim Einfügen, ob sie einen Eintrag schonmal hatten. Erspart dir die Iteration durch die komplette Liste, also O(1) vs. O(n).

C-/C++-Quelltext

 
1
2
3
4

int main(int _argc, char** _argv) noexcept {
  asm volatile("lock cmpxchg8b %eax");
  return 0;
} // ::main
(Dieses kleine Biest vermochte einst x86-Prozessoren lahm zu legen.)

=> Und er blogt unter Hackish.Codes D:

Spiele Programmierer

Alter Hase

Beiträge: 1 223

Wohnort: Deutschland Bayern

Beruf: Schüler

  • Private Nachricht senden

8

26.05.2015, 11:40

Ich würde mir besonders von TGGCs Vorschlag bezüglich des Algorithmus eine drastische Verbesserung erhoffen.

Um allerdings nochmal auf die Performance einzugehen:
Als erstes würde ich mal auf die Rekursion verzichten. Du fügst in der Methode Arrays mit "MAX_DEPTH" Einträgen für die aktuellen Lösungsschritte und alle Zwischenergebnisse an und kannst dann dort deine Kopien ablegen ohne neuen Speicher zu allokieren.

Außerdem gibt es natürlich noch viele kleinere Dinge. Zum Beispiel "INCREASE" und "DECREAE" direkt mit +1 und -1 Integern zu ersetzen oder man könnte verschiedene Verzweigungen aus den Schleifen rausziehen.

Thurien

Frischling

  • »Thurien« ist der Autor dieses Themas

Beiträge: 19

  • Private Nachricht senden

9

26.05.2015, 20:45

Vielleicht verstehe ich das falsch, aber bleibt für den Fall, dass keine Lösung existiert (was ja mein Problem ist, dies dann trotzdem schnell herauszufiinden, bei A* letztendlich nicht trotzddm nur das Durchlaufen bis zur maximalen Suchtiefe? Das würde mir dann ja insofern keine Optimierung für diesen Fall geben, oder? Ansonsten machr A* tatsächlich Sinn. Das mit der bidirektionalen Suche scheint mir da aber vielleicht noch ein wenig sinnvoller in dem Fall?

Aber das Problem wäre ja immernoch, dass ich es nicht schaffe die Millionen unnötigen und bereits überprüften Züge zu filtern.

@Evrey: Die Grenzen werden in den Increase und Decrease Methoden überprüft. Deshalb sit das ganz auch als Methode ausgelagert. Das ganze so abstrakt als mathematisches Problem zu sehen ist in meinem Fall nicht ganz möglich, da noch Platz für weitere, logik-umfassenderer Elemente sein soll. Deshlab kommt nur ein komplettes Durchsimulieren des Spielablaufs in Frage.

Werbeanzeige

Ähnliche Themen