4. Minimax Algorythmus

Minimax Algorythmus

  • C

    Hallo zusammen.

    Ich schreibe zurzeit an einer KI für mein einfaches TicTacToe.
    Der Grundgedanke ist ganz simpel :
    --> Wenn Sieg möglich : Letzten Stein setzen
    ---> Wenn Gegner im nächsten Zug siegen würde : Blockierenden Stein setzen
    ----> ...
    -----> Wenn nichts zutrifft zufällig auswählen.

    Soweit so einfach.
    Allerdings muss ich nun die Wertigkeit eines Feldes anhand der bereits gesetzten Punkte erkennen und ihnen eine Wichtigkeit zuordnen, dh.
    +---+---+---+
    | X | 1 | 2 |
    +---+---+---+
    | 1 | 0 | 1 |
    +---+---+---+
    | 2 | 1 | o |
    +---+---+---+

    1 -> Kann durch ein legen hier zum Sieg kommen / den Sieg des Gegners Verhindern
    2 -> Beides
    0 -> Keines - Irrelevantes Feld.

    Ok, Überlegung erledigt.
    Da es nun aber 255.168 mögliche Spielverläufe gibt, habe ich gedacht, ich nutze einen einfachen Algorythmus um die Wertigkeit dieser Felder zu beurteilen.
    Allerdings gibt es dazu weder ein Tutorial in deutsch - was nicht wirklich was ausmacht - noch eins in C, zugegeben in C++ ein TicTacToe zu programmieren wäre für eine Computer Anwendung wohl sinnvoller, da das ganze aber eine eigene kleine Hardware bekommt, kommt nur C in Frage.

    Meine Frage ist also : Gibt es ein Tutorial wie der Minimax Algo arbeitet bzw. ein Sample in C oder würde es eine viel einfachere Lösung geben ?

    Gruss

    0
  • Mod

    Wenn das Ziel ist, dass Programm auf einen Mikrocontroller zu übertragen, wäre es dann nicht sinnvoller, die bekannten optimalen Züge direkt einzuprogrammieren, anstatt dem Programm eine KI zu verpassen?

    Die optimale Strategie lässt sich schließlich in wenigen Sätzen zusammenfassen:
    http://en.wikipedia.org/wiki/Tic_tac_toe#Strategy

    0

  • Hallo CybroX,

    wenn du doch den KI-Algorithmus umsetzen willst, dann schau zuerst mal unter http://de.wikipedia.org/wiki/Minimax-Algorithmus. Dann studiere aber dort den NegaMax-Algorithmus (erspart, daß man zwei Funktionen Min und Max benötigt). Und dann als Suchverbesserung http://de.wikipedia.org/wiki/Alpha-Beta-Suche verwenden.

    Als Spoiler kann ich dir folgenden Code anbieten (entstanden 1992 auf dem Amiga ;-):

    char Feld[3][3];
char spieler, zug, level;
int x, y;

void computer()
{
 short besterzug;
 Zeige_Feld();
 printf("\n Ich denke nach...\n");

 level=zug=0;
 besterzug=f2(-1,-10,10);

 Feld[y][x]=-1;
}

char Dreier_Test()
{
 int i,j;
 char wert;
 for(i=0;i<3;i++)
 {
  wert=Feld[i][0];
  if(wert!=0 && wert==Feld[i][1] && wert==Feld[i][2]) return wert;
 }
 for(j=0;j<3;j++)
 {
  wert=Feld[0][j];
  if(wert!=0 && wert==Feld[1][j] && wert==Feld[2][j]) return wert;
 }
 wert=Feld[0][0];
 if(wert!=0 && wert==Feld[1][1] && wert==Feld[2][2]) return wert;
 wert=Feld[0][2];
 if(wert!=0 && wert==Feld[1][1] && wert==Feld[2][0]) return wert;
 return 0;
}

/* Alpha-Beta-Pruning */

short f2(char sp, short a, short b)
{
 int i,j;
 short max=a,t=Dreier_Test();
 if(t!=0 || level>=9 || zug>9)
 {
  max=(10-level)*sp*t; /* Bewertungsfunktion */
  goto done;
 }
 for(i=0;i<3;i++)
  for(j=0;j<3;j++)
  {
   if(Feld[i][j]!=0) continue;
   Feld[i][j]=sp;
   level++;
   zug++;
   t=-f2(-sp,-b,-max);
   zug--;
   level--;
   Feld[i][j]=0;
   if(t>max)
   {
    max=t;
    if(level==0)
    {
     y=i;
     x=j;
    }
   }
   if(max>=b) goto done;
  }
done:
 return max;
}

    f2 ist die Verbesserung von f (dem Min-Max-Algorithmus) 😉

    0
  • C

    Hallo zusammen,

    Ersteinmal danke für eure Antworten, ich bin leider nicht früher dazu gekommen mich noch einmal ran zu setzen.

    @SeppJ Ja, das wäre auch auf diesem Weg möglich, allerdings soll das Endgerät mit einem kleinen Stufenregler auf der Seite mehrere Schwierigkeitsgrade (KI macht absichtlich falsche Züge, KI macht irgendwas (=> random), einfache KI und eine schwere KI)
    Die einfache KI habe ich bereits erstellt, sie "gewinnt" nur und verhindert Gegnerische Gewinnzüge, den ganzen Rest macht sie random.
    Nun sitze ich aber noch an der Schweren.
    Ich habe es jetzt so gemacht, dass zuerst immer noch der Dreier Test ausgeführt wird - Standard.
    Danach wird geprüft ob ein Feld noch frei ist (alle Felder per for-Scleife durch), wenn nicht erhält es - im Parallelarray "Fieldrating" - den Wert 0.
    Sollte es nicht besetz sein, wird geprüft in welchen Reihen sie dieses Feld befindet und wie diese Reihen im Moment aussehen.

    Das ist ein Rechentechnisch gesehen guter Mittelweg, da das Errechnen des Spielbaumes über mehrere Ebenen deutlich mehr Leistung braucht und das Ergebnis bei einem Spiel wie TTT auch nicht viel besser ist.

    Technisch bin ich da noch nicht so weit, aber ich denke, dass diese Lösung so funktionieren (sollte)

    Was ich allerdings nicht ganz versetehe ist

    besterzug=f2(-1,-10,10);

 Feld[y][x]=-1;

    Wo ist da der Zusammenhang ?
    Aber auf jeden Fall, danke für den Code, ich werd' dann wohl mal weiterlernen 😉

    0
  • Mod

    CybroX schrieb:

    Das ist ein Rechentechnisch gesehen guter Mittelweg, da das Errechnen des Spielbaumes über mehrere Ebenen deutlich mehr Leistung braucht und das Ergebnis bei einem Spiel wie TTT auch nicht viel besser ist.

    Wie in den Artikeln beschrieben, brauchst du keinen Spielbaum. Es ist in jeder Situation aus einfachen Regeln (ein paar 5-10 if-Abfragen) ganz klar vorgegeben, was der bestmögliche* Zug ist (bis auf Drehsymmetrie). Welche Züge danach kommen könnten ist irrelevant. Das Spiel bedarf keines Vorausdenkens.

    *: Und zwar wirklich der beste, perfekte, ideale Zug, nicht bloß ein relativ guter.

    0
Anmelden zum Antworten