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!

Optimierung von Erkennunsmehtode für Vier Gewinnt?

  • 1
  • 2

Werbeanzeige

Brandy

Frischling

  • »Brandy« ist der Autor dieses Themas

Beiträge: 5

  • Private Nachricht senden

1

21.07.2008, 14:44

Optimierung von Erkennunsmehtode für Vier Gewinnt?

Ich habe vor einiger Zeit ein Konsolen 4-Gewinnt geschrieben, und nun würde ich wissen ob es möglichkeiten gibt, das Erkennungsverfahren für die viererkette zu optimieren. Dazu poste ich die Funktion:

C-/C++-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

//slot[][]: Ein einzelnes "Spielfeld", in das ein Spielstein passt

//height: Membervariable für Höhe

//width: Membervariable für Breite

bool Field::CheckField() {
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            if (slot[x][y] != 0 &&
                slot[x][y] == slot[x][y+1] &&
                slot[x][y] == slot[x][y+2] &&
                slot[x][y] == slot[x][y+3]) {
                return true;
            }
        }
    }
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            if (slot[x][y] != 0 &&
                slot[x][y] == slot[x-1][y+1] &&
                slot[x][y] == slot[x-2][y+2] &&
                slot[x][y] == slot[x-3][y+3]) {
                return true;
            }
        }
    }
    
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            if (slot[x][y] != 0 &&
                slot[x][y] == slot[x+1][y+1] &&
                slot[x][y] == slot[x+2][y+2] &&
                slot[x][y] == slot[x+3][y+3]) {
                return true;
            }
        }
    }

    
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            if (slot[x][y] != 0 &&
                slot[x][y] == slot[x+1][y] &&
                slot[x][y] == slot[x+2][y] &&
                slot[x][y] == slot[x+3][y]) {
                return true;
            }
        }
    }

    
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            if (slot[x][y] != 0 &&
                slot[x][y] == slot[x-1][y] &&
                slot[x][y] == slot[x-2][y] &&
                slot[x][y] == slot[x-3][y]) {
                return true;
            }
        }
    }

    return false;
}


Im Voraus:
Mir ist aufgefallen, dass ich immer alle Spielsteine prüfe, was eher suboptimal ist.
Mir fällt jedoch konkret nicht ein, wie ich relativ unkompliziert und sicher nur den letzten gesetzten Stein prüfen könnte.
Weiterhin habe ich festgestillt, dass ich, solange keine Viererkette vorliegt, unter Umständen die Arrays überschreite, was (mit fast vernachlässigbarer Wahrscheinlichkeit) zu einer Erkennung führen könnte, ohne dass eine 4erkette vorliegt.
Falls es eine wesentlich elegantere und schnellere Lösung gibt (was ich in anbetracht dieser 58 Codezeilen schon denke), würde ich um Denkanstöße bitten.
Irren ist menschlich, aber ein richtiges Chaos bringt nur ein Computer zustande!

drakon

Supermoderator

Beiträge: 6 513

Wohnort: Schweiz

Beruf: Entrepreneur

  • Private Nachricht senden

2

21.07.2008, 22:20

Hmm. Man könnte das ja auch mit Objekten machen, die auf die Nachbarsobjekte verweisen. (Also z.B Block* left,up,down ... )

Vlt. hilft das hier:
http://www.softgames.de/forum/frage121503.html
http://www.drakon.ch | Weltweit 31. Bester Solitär Spieler (Standard XP)

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

3

22.07.2008, 01:29

Hmm ich gehe an solche Probleme folgendermaßen ran:
-was das kernproblem ist
-wie würde ich das problem lösen
-problemlösung auf einfache begriffe reduzieren
-programmieren

Es kommt zwar nicht immer das non-plus-ultra bei raus, aber meistens ist es intuitiv, da naiv gedacht. In deinem Fall würde ich folgends versuchen:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12

bool TesteStein(int x, int y)
{
//für diagonal nach unten

 for(int counter = 0; counter < 4; counter++)
    if(x+counter,y+counter ist nicht mehr im Feld || Stein(x+counter,y+counter) != Stein(x,y) )
        break;
    else if(counter == 3)
        return true;
//hier analog für die übrigen richtungen

        
return false;
}


Und wenn man ncoh einen schritt weiter gehen will:

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

bool TesteRichtung(int x, int y, int xrichtung, int yrichtung)
{
// xrichtung und xrichtung sollten nur die Werte -1,0,1 haben

for(int counter = 0; counter < 4; counter++)
{
    int newx = x+xrichtung*counter;     
    int newy = y+yrichtung*counter; 
    if(newx,newy ist nicht mehr im Feld || Stein(newx ,newx ) != Stein(x,y) )
        return false;
}
        return true;
}

bool TesteStein(int x, int y)
{
//für diagonal nach unten

if(TesteRichtung(x,y,1,1)) return true;
//hier analog für die übrigen richtungen

        
return false;
}



Übrigens sollte man in C/C++ es tunlichst vermeiden Arraygrenzen zu überschreiten. In anderen Sprachen geht das ohne Probleme, aber bei C/C++ nicht ohne weiteres.
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

jojendersie

Frischling

Beiträge: 47

Wohnort: Berlin

  • Private Nachricht senden

4

22.07.2008, 10:10

Wenn du den Quelltext von oben ein wenig anders strukturierst und kapselst wird er auch schon wesentlich optimaler.

C-/C++-Quelltext

 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

bool Field::CheckDir(int x, int y, int xrichtung, int yrichtung) {
    // Feldgrenzen absichern

    if(x+3*xrichtung < 0 || x+3*xrichtung > width) return false;
    if(y+3*yrichtung < 0 || y+3*yrichtung > height) return false;

    // Die Viererreihe testen

    if (slot[x][y] != 0 && 
        slot[x][y] == slot[x+xrichtung][y+yrichtung] && 
        slot[x][y] == slot[x+xrichtung*2][y+yrichtung*2] && 
        slot[x][y] == slot[x+xrichtung*3][y+yrichtung*3]) { 
            return true;
    }
}

bool Field::CheckField() { 
    for (int y = 0; y < height; y++) { 
        for (int x = 0; x < width; x++) {
            CheckDir(x,y,0,1);
            CheckDir(x,y,1,1);
            CheckDir(x,y,1,-1);
        }
    }


Ausgehend davon, das du jeden Stein durchläufst brauchst du bloß 3 Richtungen zu prüfen. Wenn du den neuen Stein jedoch kennst, kann man die Schleife weglassen und dafür alle 8 Richtungen prüfen.

Brandy

Frischling

  • »Brandy« ist der Autor dieses Themas

Beiträge: 5

  • Private Nachricht senden

5

22.07.2008, 15:41

Danke für die vielen Antworten.

@Nox:
Ich hätte eine Frage zu einer Codezeile:

C-/C++-Quelltext

 
1

if(x+counter,y+counter ist nicht mehr im Feld || Stein(x+counter,y+counter) != Stein(x,y) )


Was genau ist der Sinn dieser Zeile (die ja nicht wirklich Code ist, ich schätze du hast irgendwo ein "//" vergessen), bzw der Funktion Stein (oder war hier das Array gemeint?)

Des Weiteren bin ich mir nicht ganz sicher, was diesen deinen Algorithmus (wenn man das denn so nennen kann) schneller macht als meinen.
Eine kurze Erklärung wäre nett.
Die Aufteilung in Funktionen, welche mir am ehesten auffällt, bringt, auch wenn ich glaube dass sie dank der Kürze sowieso implizit Inline sind, nicht
unbedingt einen Geschwindigkeitsvorteil, oder?
Ich verstehe auch ein paar andere Dinge nicht ganz, doch ich denke, das hängt mit der ominösen Codezeile oben zusammen.

Die Idee mit dem Counter kam mir auch zuallererst, ich hatte sie sogar beinahe fertig implementiert, nur aus irgendeinem Grund verworfen.
Prinzipiell gesehen ist deine Idee und die Idee meiner if-Abfragen gar nicht so grundverschieden, nur dass du das Ganze per Schleife umgesetzt, (woran ich scheinbar gescheitert bin), auf jeweils einen Stein beschränkt, sowie eine Arraygrenzen-Überprüfung eingebaut hast.

Bezüglich der Arrayüberschreitung: Normalerweise gibt es im Debugmodus von MVC++ ja eine Exception, dass eine Bereichsüberschreitung aufgetreten ist, oder gilt das nur bei dynamisch auf dem Heap erzeugt Objekten?
Bei anderen Programmen vermeide ich es auch, nur hier habe ich (speziell mit meiner Implementierung) ein Problem damit.

@jojendersie:
Deine Lösung gefällt mir auch, obwohl ich auch hier nicht genau festmachen kann, wo der Geschwindigkeitsvorteil liegt.
Entschuldigt bitte, wenn ich diesbezüglich nicht so ganz Bescheid weiß.

Im Allgemeinen wäre ich auch dankbar, wenn mir jemand sagen könnte, wie sich die einzelnen Dinge auf die Geschwindigkeit auswirken.

Arithmethische Operationen sind Milliardenmal in der Sekunde möglich, doch wie sieht es da (im Verhältnis) mit if-Abfragen und Schleifen aus?
Insbesondere bei diesen kommt es vermutlich stark auf die geprüfte(n) Bedingungen(n) bzw. den jeweils wiederholten Code ankommt, was eine allgemeine Einstufung wohl erschwert. Trotzdem würde ich gerne wissen, wie sich solche Schleifen und Bedingungen auf die Performance eines Programms auswirken.

Ich weiß es sind viele Fragen, aber ich hoffe es findet sich jemand sie zumindestens teilweise beantworten kann.

Danke im Voraus.
Irren ist menschlich, aber ein richtiges Chaos bringt nur ein Computer zustande!

Chase

Alter Hase

Beiträge: 753

Wohnort: Nagaoka / Darmstadt / Düsseldorf

Beruf: fauler Studi

  • Private Nachricht senden

6

22.07.2008, 16:48

Sorry, hab nich alles gelesen aber nur ein Gedankenanstoss:

Damit du nicht immer dein ganzes Spielfeld durchlaufen musst, pruefst du einfach immer beim Setzen eines neues Steines ob *dieser* Stein eine Reihe vervollstaendigt. Nox's Code reicht dazu fast aus. Du musst nur bedenken dass der neue Stein auch in der Mitte einer Reihe liegen kann. Also zaehlst du in alle 8 Richtungen wie viele Steine des selben Typs folgen. Dann addierst du jewails oben+unten, links+rechts, und die beiden Diagonalen. Ist einer dieser Summen dann groesser als 4 hast du einen Gewinner :)
"Have you tried turning it off and on again?"

Brandy

Frischling

  • »Brandy« ist der Autor dieses Themas

Beiträge: 5

  • Private Nachricht senden

7

22.07.2008, 17:22

Zitat

Sorry, hab nich alles gelesen

Kann ich dir nicht verdenken ;).

Das wäre eine (sehr gute) Möglichkeit.
Werde ich bei Gelegenheit mal ausprobieren.
Damit ist mir eigentlich schon geholfen, den Code werd ich wohl noch zusammenbringen.

Vielen Dank bis jetzt schon mal an alle die ich die Mühe gemacht haben, sich mit meinem Problem zu befassen.
Irren ist menschlich, aber ein richtiges Chaos bringt nur ein Computer zustande!

Nox

Supermoderator

Beiträge: 5 272

Beruf: Student

  • Private Nachricht senden

8

22.07.2008, 19:19

Hmm das der Stein in der mitte liegen kann habe ich völlig vergessen :oops: . Die Zeile "Code" ist Pseudocode. Sprich es wird die Aussage formuliert. Das kann manchmal sehr praktisch sein. Z.B.

C-/C++-Quelltext

 
1

while(es gibt noch ein leeres Feld)   FülleFeld(an der stelle x,y);


Geschwindigkeit allein auf Code basierend abzuschätzen ist oft sehr schwer bis fast unmöglich. Bei Bedingungen spielt z.B. die so genannte Sprungvorhersage der CPU eine wichtige rolle. Allerdings kann man mit einigen einfachen Sachen viel sparen (die hier auch genutzt werden):
-Wenn man nur den letzten Stein prüfen muss, dann prüft man nur den
-Wenn man einige Richtungen/Wege ausschließem kann, dann sollte man dies tun (siehe jojendersie Lösung)
-Teilen, Wurzelziehen und ähnliche sind sehr teuer

Im übrigen ist bei solche Sachen die Codeübersicht viel wichtiger als die Geschwindigkeit. Auch kann man durch das testen, ob die Grenzen überhaupt 4 Steine zulassen, viele andere Abfragen im Vorfeld überflüssig machen.
PRO Lernkurs "Wie benutze ich eine Doku richtig"!
CONTRA lasst mal die anderen machen!
networklibbenc - Netzwerklibs im Vergleich | syncsys - Netzwerk lib (MMO-ready) | Schleichfahrt Remake | Firegalaxy | Sammelsurium rund um FPGA&Co.

Brandy

Frischling

  • »Brandy« ist der Autor dieses Themas

Beiträge: 5

  • Private Nachricht senden

9

22.07.2008, 20:11

@Nox:
Gut, ich war mir wie gesagt nicht sicher, da ich es nicht gewohnt bin, "mitten" im kompilierbaren Code auf einmal Pseudocode vorzufinden.
Dann ist das wohl geklärt.

Auch

Zitat von »"Brandy"«

Ich verstehe auch ein paar andere Dinge nicht ganz, doch ich denke, das hängt mit der ominösen Codezeile oben zusammen.
ist jetzt geklärt.
Ich hatte mich auch gefragt, was passiert, wenn der Stein in der Mitte liegt, bei deinem Code.
Damit wäre dieses Thema (für mich) zu genüge behandelt und ich konnte sogar einige neue Erkenntnisse gewinnen.
Nochmal ein dickes Danke hierfür von mir ;)
Irren ist menschlich, aber ein richtiges Chaos bringt nur ein Computer zustande!

jojendersie

Frischling

Beiträge: 47

Wohnort: Berlin

  • Private Nachricht senden

10

22.07.2008, 22:31

Noch ein Nachtrag zu Geschwindigkeiten.

Einzelne Operatoren auszutauschen bringt nur bedingt etwas und eigentlich auch nur, wenn man davon ausgehen muss, dass die betreffende Stelle sehr oft durchgeführt wird.

Beispiel: eine Multiplikation ist meist schneller als eine Division (bei float).
Daher ist
for(i->10000) y=x/1.6;
langsamer als
f = 1/1.6;
for(i->10000) y=x*f; (Multiplikation mit dem Kehrwert)

Abfragen brauchen in etwa gleich viel Leistung wie die Arithmetik, oder weniger. Logische Operatoren wie and/or/bitshifts sind um Welten schneller, da die Arithmetik aus vielen logischen Operatoren zusammengesetzt ist. Hier lässt sich meist nur bei Dingen wie Multiplikation mit 2 etwas optimeren (statt x*2 nutze x<<1, aber nur bei Ganzzahlwerten, bei Float bekommst du bei sowas nichts gescheites).

Aber mit solchen Überlegungen kannst du meistens nicht viel optimeren. Viel besser ist das finden anderer Algorithmen mit geringerer komplexibilität. Das ist hier eben die Beschränkung auf den aktuellen Stein, aber das ist ja bereits geklärt.

Meine Lösung war nicht "wirklich" schneller. Sie hat nur überflüssige Richtungen weggelassen, war übersichtlicher und hatte die Sicherheitsabffragen zum Rand.

So ich hoffe mein Exkurs zur Optimierung nutzt dir etwas, ich glaube er ist eher unübersichtlich^^.

Werbeanzeige

  • 1
  • 2