# TicTacToe KI-Player mit Heuristik



## skenil (2. Mai 2006)

Hi,
ich programmiere gerade ein javabasierendes TicTacToe-Spiel auf GUI-Basis mit einer eigenen KI.
Ich konnte bisher bereits einige KI-Gegner programmieren,  die jedoch noch relativ einfach zu besiegen sind.
Mein Ziel ist es nun einen KI-Gegner zu bauen der alle möglichen Züge berechnet und diese dann heuristisch bewertet.
Das Spielfeld ist ein 2-dimensionales Array.

Hat jemand sowas vielleicht schonmal gemacht und hätte den Code noch da ? Mein bisheriger VErsuch "läuft" zwar, jedoch zieht er nicht gerade optimal 


```
public class PC1337 {

  static int[] RSumme = new int[13];

 // Ermittlung der Reihensummen
 public static void berechneR(position P){
   int h=0; // Hilfvariable
   RSumme = new int[13];
   //Reihen
   for(int i=0;i<3;i++){
     h = P.feld[i][0] + P.feld[i][1] + P.feld[i][2];
     RSumme[h] = RSumme[h]+1;
   }

   //Spalten
   for(int i=0;i<3;i++){
     h = P.feld[0][i] + P.feld[1][i] + P.feld[2][i];
     RSumme[h] = RSumme[h]+1;
   }

   //Diagonalen
   h = P.feld[0][0] + P.feld[1][1] + P.feld[2][2];
   RSumme[h]=RSumme[h]+1;
   h = P.feld[0][2] + P.feld[1][1] + P.feld[2][0];
   RSumme[h]=RSumme[h]+1;
 }



 // heuristische Bewertung
 // -a * O(3) + b * X(2) – c * O(2) + d * X(1) – e * O(1),     mit a > b > c > d > e
 // Hat ein Spieler eine Dreierreihe erzielt, kann der Gegenspieler höchstens zwei Zweierreihen erreicht haben,
 // daher muss a > 2b gelten, weshalb wir b = 15 setzen. Besitzt ein Spieler eine Zweierreihe,
 // so kann der Gegner nicht mehr als drei Einserreihen besitzen, also gilt: b > 2e und c > 2d,
 // was durch die Setzung c = 7, d = 3 und e =1 erreicht werden kann.“
 // S1 am Zug: -31 * O(3) + 15 * X(2) – 7 * O(2) + 3 * X(1) – 1 * O(1)
 // s2 am Zug: -31 * X(3) + 15 * O(2) – 7 * X(2) + 3 * O(1) – 1 * X(1)
  public static int bewerte(int x, position P){
    berechneR(P);
    return (-31 * RSumme[3*(5-x)] + 15 * RSumme[2*x] - 7 * RSumme[2*(5-x)] + 3 * RSumme[x] - RSumme[5-x]);
  }

  public static int[] zugPC(int dran, position P){
    int bewertung[][] = new int[3][3];   // Speichert die Züge
    int[] zug = new int[2]; // Rückgabevariable

    for(int k=0;k<3;k++){
      for(int j=0;j<3;j++){
        if (P.feld[k][j] == 0) {      // Wenn das Feld frei ist
          P.zug(dran, k, j);        // ziehe dorthin
          bewertung[k][j] = bewerte(dran,P);   // speichere die Bewertung
          P.feld[k][j] = 0;          // mache das Feld wieder frei für den nächsten Zug
        }
        else bewertung[k][j] = 100;  // Ein bereits besetztes Feld hat den schlechtesten Wert
      }
  // Vergleiche alle Züge \\
      int[] h = new int[9];                  // Hilfsarray
      int b = 100;                         // Muss über maximalem Bewertungswert liegen
      int min;                             // Vergleichsvariable

      int count = 0;
  // Umformung zur einfacheren Verarbeitung
      for(int x=0;x<3;x++){
        for(int y=0;y<3;y++){
         h[count]=bewertung[x][y];
         count++;
        }
      }
     count=0;
  // Vergleiche der  Bewertungen mit min()
      for(int i=0;i<h.length;i++) {
        if (h[i]<b) {
          count = i;
          b = h[i];       // b wird vor dem nächsten Durchlauf auf den aktuell besten Wert gesetzt
        }
      }

 // count trägt die Information des besten Zuges
 // nun müssen die Zuginformationen noch aus h[] "dechiffriert" werden
      int count2=0;
      for(int u=0;u<3;u++){
        for(int g=0;g<3;g++){
          if (count == count2){
            zug[0] =u;
            zug[1] =g;
            return zug;
          }
          else count2++;

        }
      }
    }    // Ende äußere for-Schleife
    return zug; 
  }

}
```


----------



## Dukel (2. Mai 2006)

Ich würde alle möglichen züge berechnen lassen und einen, der zum sieg führt ausführen.


----------



## Guest (2. Mai 2006)

> Mein Ziel ist es nun einen KI-Gegner zu bauen der alle möglichen Züge berechnet und diese dann heuristisch bewertet.



Genau das ist ja auch mein Ziel ... Leider ist das Resultat alles andere als optimal :/[/quote]


----------



## mischer (8. Mai 2006)

Hi,

natürlich wäre es theoretisch (und auch praktisch) möglich alle möglichen Züge im Voraus zu berechnen und dann den Besten (oder einen der Besten, da es wohl oft gleich gute geben wird) auszuwählen. Allerdings würde ich Dir hier den Min-Max-Algorithmus und als Erweiterung noch das Alpha-Beta-Prinzip (auch auf dieser Seite besprochen) ans Herz legen, da das im Vergleich zum stupiden Durchexerzieren aller Möglichkeiten einem menschlichen Spieler doch mehr ähnelt und außerdem in Sachen Spielstärke skalierbar ist. Wer spielt schon gerne gegen einen unbesiegbaren Gegner?

MfG
mischer


----------

