3. Problem mit Minimax-Algorithmus

Problem mit Minimax-Algorithmus

  • P

    Hallo!

    Ich bin grade dabei, eine Implementierung eines Fingerspiels zu schreiben. Die Regeln sind folgendermaßen: Zwei Spieler zeigen am Anfang je einen Finger von jeder Hand. Dann tippt abwechselnd einer der Spieler eine der Hände des Gegners an , dabei wird die Zahl der Finger zur Hand des Gegners addiert. Hat einer 5 Finger an einer Hand, ist sie verloren und wer zuerst beide Hände verliert, hat verloren. Das ganze wollte ich mit einem Minimax-Algorithmus machen. Mein Code bisher:

    #include <iostream>
#include <cstdlib>
#include <cstdio>
#include <conio.h>
#include <ctime>
using std::cout;
using std::cin;
using std::endl;
using std::rand;
using std::min;
using std::max;

int MAX(int,int,int,int,int);

void wait () //Wartet einen Tastendruck ab
{
    FlushConsoleInputBuffer(GetStdHandle(STD_INPUT_HANDLE));
    getch();
}  

void anzeige(int sR, int sL, int cR, int cL) {
    cout<<"Computer linke Hand: "<<cL<<" Computer rechte Hand: "<<cR<<endl<<endl<<
        "Spieler linke Hand: "<<sL<<" Spieler rechte Hand: "<<sR<<endl<<endl;
}

int bewerte(int sR, int sL, int cR, int cL) {
    int wert = 0;
    wert += ((cR+cL) - (sR+sL));
    if(!sR)
        wert += 10;
    if(!sL)
        wert += 10;
    if(!cR)
        wert -= 10;
    if(!cL)
        wert -= 10;
    return wert;
}

int MINI(int sR, int sL, int cR, int cL, int tiefe) {
    if(tiefe==0) 
        return bewerte(sR, sL, cR, cL);
    else {
        int a=10000;
        int b=10000;   
        int c=10000;
        int d=10000;
        int e=10000;
        int f=10000;

        if(cR || sR)
            a=MAX(sR, sL, ((cR+sR)%5), cL, tiefe--);
        if(cR || sL)
            b=MAX(sR, sL, ((cR+sL)%5), cL, tiefe--);
        if(cL || sR)
            c=MAX(sR, sL, cR, ((cL+sR)%5), tiefe--); 
        if(cL || sL)
            d=MAX(sR, sL, cR, ((cL+sL)%5), tiefe--);

        if((sL+sR)%2==0) {
            if(cR) 
                e=MAX((sR+sL)/2, (sR+sL)/2, (cR+(sR+sL)/2)%5, cL, tiefe--);
            if(cL)
                f=MAX((sR+sL)/2, (sR+sL)/2, cR, (cL+(sR+sL)/2)%5, tiefe--);
        }
        return min(min(min(min(min(a,b),c),d),e),f);
    }
}

int MAX(int sR, int sL, int cR, int cL, int tiefe) {
    if(tiefe==0) 
        return bewerte(sR, sL, cR, cL);
    else {
        int a=10000;
        int b=10000;   
        int c=10000;
        int d=10000;
        int e=10000;
        int f=10000;

        if(cR || sR)
            a=MINI((sR+cR)%5, sL, cR, cL, tiefe--);
        if(cR || sL)
            b=MINI(sR, (sL+cR)%5, cR, cL, tiefe--);
        if(cL || sR)
            c=MINI((sR+cL)%5, sL, cR, cL, tiefe--); 
        if(cL || sL)
            d=MINI(sR, (sL+cL)%5, cR, cL, tiefe--);

        if((cL+cR)%2==0) {
            if(sR)
                e=MINI((sR+((cR+cL)/2))%5, sL, (cR+cL)/2, (cR+cL)/2, tiefe--);
            if(sL)
                f=MINI(sR, (sL+((cR+cL)/2))%5, (cR+cL)/2, (cR+cL)/2, tiefe--);
        }
        return max(max(max(max(max(a,b),c),d),e),f);
    }
}

int computerZug(int sR, int sL, int cR, int cL) {
    int a=-10000;
    int b=-10000;   
    int c=-10000;
    int d=-10000;
    int e=-10000;
    int f=-10000;
    int tiefe=6;

    if(cR || sR) 
        a=MINI((sR+cR)%5, sL, cR, cL, tiefe--);
    if(cR || sL)
        b=MINI(sR, (sL+cR)%5, cR, cL, tiefe--);
    if(cL || sR)
        c=MINI((sR+cL)%5, sL, cR, cL, tiefe--); 
    if(cL || sL)
        d=MINI(sR, (sL+cL)%5, cR, cL, tiefe--);

    if((cL+cR)%2==0) {
        if(sR)
            e=MINI((sR+((cR+cL)/2))%5, sL, (cR+cL)/2, (cR+cL)/2, tiefe--);
        if(sL)
            f=MINI(sR, (sL+((cR+cL)/2))%5, (cR+cL)/2, (cR+cL)/2, tiefe--);
    }

    if(a>b && a>c && a>d && a>e && a>f)
        return 0;
    if(b>a && b>c && b>d && b>e && b>f)
        return 1;
    if(c>a && c>b && c>d && c>e && c>f)
        return 2;
    if(d>a && d>b && d>c && d>e && d>f)
        return 3;
    if(e>a && e>b && e>c && e>d && e>f)
        return 4;
    if(f>a && f>b && f>c && f>d && f>e)
        return 5;
    if(a==b && a==c && a==d && a==e && a==f)
        return rand()%6;
}

int main()  {
    int sR=1; //Spieler rechte Hand
    int sL=1; //Spieler linke Hand
    int cR=1; //Computer rechte Hand
    int cL=1; //Computer linke Hand
    int zugS=0;
    int zugC=0;

    srand(static_cast<unsigned>(time(NULL)));

    while((sR+sL != 0) && (cR+cL != 0)) {
        anzeige(sR, sL, cR, cL);
        cout<<"Zug eingeben"<<endl;
        cin.ignore(cin.rdbuf()->in_avail());
        cin>>zugS;

        switch(zugS) { //Zug des Spielers anwenden...
            case 0: 
                if(sR || cR)
                    cR = (sR+cR)%5;
                else {
                    cout<<"Zug nicht erlaubt."<<endl;
                    continue; 
                }
                break;
            case 1: 
                if(sL || cR)
                    cR = (sL+cR)%5;
                else {
                    cout<<"Zug nicht erlaubt."<<endl;
                    continue; 
                } 
                break;
            case 2:
                if(sR || cL)
                    cL = (sR+cL)%5;
                else {
                    cout<<"Zug nicht erlaubt."<<endl;
                    continue; 
                } 
                break;
            case 3: 
                if(sL || cL)
                    cL = (sL+cL)%5;
                else {
                    cout<<"Zug nicht erlaubt."<<endl;
                    continue; 
                }
                break;
            case 4:
                if((sL + sR)%2 == 0) {
                    sL=(sL + sR)/2;
                    sR=(sL + sR)/2;
                    continue; //Spieler kann nach Fingertausch noch einen normalen Zug machen
                } else {
                    cout<<"Zug nicht erlaubt!"<<endl;
                    continue;
                }
            default: 
                cout<<"Zug nicht erlaubt."<<endl;
                continue;
            }

            anzeige(sR, sL, cR, cL);
            zugC=computerZug(sR, sL, cR, cL); //Minimax-Algorithmus

            switch(zugC) { //Zug des Computers anwenden...
            case 0: 
                sR = (cR+sR)%5; 
                break;
            case 1: 
                sR = (cL+sR)%5; 
                break;
            case 2:
                sL = (cR+sL)%5; 
                break;
            case 3: 
                sL = (cL+sL)%5; 
                break;
            case 4:                    
                cL=(cL + cR)/2;
                cR=(cL + cR)/2;
                sR=(cR + cL)%5;
                break;
            case 5:
                cL=(cL + cR)/2;
                cR=(cL + cR)/2;
                sL=(cR + cL)%5;
                break;
            default: 
                cout<<"Fehler im Programm"<<endl;
                wait();
                exit(0);
                break;
            }
      }
}

    Das ist jetzt ein Haufen Code, aber ich wollte es vollständig posten, damit ihr den Fehler nachvollziehen könnt. Das ganze wird nämlich fehlerfrei kompiliert, aber bei der Ausführung stürzt es immer beim Computerzug ab und ich finde die Ursache nicht.
    Zweite Sache: Ich habe da ja recht viele unelegante Konstruktionen verwendet, habe aber keine Idee, wie man diese Massen von ifs und dergleichen kürzer und einfacher schreiben könnte. Kann mir jemand weiterhelfen?

    Gruß phyll.

    edit: Ist der Klammernstil so in Ordnung? Will mir grad sauberes Arbeiten mit 1TBS angewöhnen.

    edit2: Sourcecode durtch neuere Version ersetzt

    0
  • T

    Zuerst einmal die Fehler:

    Du deklarierst mittels

    int a=10000;
if(cR || sR)
   int a=MAX(sR, sL, ((cR+sR)%5), cL, tiefe--);

    zwei Variablen namens a, so daß die obere Variable a immer den Wert 10000 behält.
    Entferne also (jeweils) das "int" bei der zweiten Variable (d.h. nur eine neue Zuweisung).

    Dann als 2.:
    Deine beiden Funktionen MINI und MAX arbeiten jeweils mit dem Minimum (statt mit Minimum und Maximum).

    Du solltest dir mal die Verbesserung des Minimax-Algorithmus anschauen: NegaMax (s. http://de.wikipedia.org/wiki/Minimax-Algorithmus)
    Dann benötigst du nur noch eine Funktion.

    Außerdem sollte dein Computer-Zug einfach den Minimax (bzw. NegaMax) Algorithmus verwenden (anstatt doppelten Code zu haben).

    Den besten Zug (Finger) solltest du dann dir innerhalb des Minimax-Algorithmus merken (wobei ich jetzt noch nicht verstanden habe, was die Möglichkeiten 4 bzw. 5 (beim Computer) sind).

    Und dann noch zum Schluß:

    continue;
break;

    Das break dort ist sinnlos, da das continue ja schon eine "Sprunganweisung" darstellt.

    Schreib das jetzt mal soweit wie möglich um, und dann kannst du ja noch mal nachfragen, falls es imemr noch nicht richtig funktioniert.

    0
  • P

    Servus!

    1. Den Fahler mit der doppelten Deklaration habe ich schon gestern abend gefunden und behoben.

    2. Eventuell habe ich das Konzept des Minimax-Algorithmus falsch verstanden, meiner Meinung nach ist es doch so, dass jeder Knoten jeweils den kleinsten Wert seiner Unterknoten an seinen Überknoten zurückgibt. Der oberste Knoten ComputerZug() muss ja an meine main() nicht den kleinsten Wert zurückgeben, sondern die ID des sinnvollsten Zuges, daher habe ich dafür ne extra Funktion geschrieben.

    3. Das mit dem Negamax habe ich gelesen, verstehe aber nicht, wie es funktionieren soll, denn wenn ich einen Zug des Spielers simuliere, muss ich ja berücksichtigen, dass der Spieler andere Züge mit ganz anderen Wirkungen macht, als der Computer. Wie geht das, wen ich nur eine Funktion habe?

    4. Die Möglichkeiten 4 und 5 resulieren daher, dass man, wenn man eine gerade Anzahl Finger hat, so tauschen kann, dass beide Hände gleich viele Finger haben. (Das hatte ich beim Spieler noch vergessen)

    5. Das mit break und continue wird gleich behoben, wird aber wohl kaum die Ursache meines Fehlers sein. Der Debugger sagt, es sei ein Segmentation Fault beim Aufruf von MINI()

    Gruß und danke, phyll

    0
  • T

    Einen Fehler habe ich noch:
    statt "tiefe--" solltest du "tiefe - 1" beim Aufruf von MINI bzw. MAX nehmen.

    Ich nehme an, du hast einen Stack-Overflow produziert, ansonsten steppe einfach mit deinem Debugger durch die Funktionen und schau nach, wo er den Runtime-Fehler verursacht (einen anderen Grund für einen "segmentation error" sehe ich nicht, da du ja keine Zeiger verwendest).

    Der oberste Knoten ComputerZug() muss ja an meine main() nicht den kleinsten Wert zurückgeben, sondern die ID des sinnvollsten Zuges, daher habe ich dafür ne extra Funktion geschrieben.

    Ja, das stimmt schon, aber trotzdem hast du ja den Code dupliziert (d.h. daraus könntest du dann eine eigene Funktion machen).

    Der Negamax Algorithmus interpretiert das Ergebnis des gegenerischen Zugs einfach als negativen Wert (je besser der Gegner, desto schlechter für mich und umgekehrt):

    int Negamax(int sR, int sL, int cR, int cL, int tiefe)
{
  ...
  a = -Negamax(sR, sL, ((cR+sR)%5), cL, tiefe-1);
  ...
}

    Wenn du doch deine 2 Funktionen nutzen willst, dann solltest du in MAX aber alle Variablen auf "-10000 setzen" (so wie beim Computer-Zug).

    P.S: Ich bin kein Freund des K&R Klammerstils, aber ansonsten sieht es lesbar aus...

    0
  • P

    Hallo,

    habe jetzt tiefe-1 statt tiefe-- eingebaut, immer noch das gleiche Problem. Mehr als dass der Speicherfehler beim Aufruf von MINI() auftritt, sagt mir der Debugger nicht. Bin mittlerweile einigermaßen ratlos, hat irgendjemand noch ne Idee?

    phyll

    edit: Hatte einmal das "tiefe--" übersehen, das war es wohl, was den overflow produzierte. Jetzt ist das Problem behoben, danke!

    0
  • C
    Mod

    Lerne, den Debugger zu nutzen

    0
Anmelden zum Antworten