kramann.info
© Guido Kramann

Login: Passwort:










kramann.info
© Guido Kramann

Login: Passwort:




TicTacToe rekursiv

(EN google-translate)

(PL google-translate)

Um bei einer bestimmten Spielsituation zu beurteilen, wie groß ab da die Wahrscheinlichkeiten für ein Unentschieden, dafür, dass X gewinnt und dafür daß O gewinnt zu bestimmen, wird eine rekursive Funktion definiert.

Diese geht baumartig alle möglichen nachfolgenden Zugvarianten durch, bis sie entweder darin münden, das ein Spieler gewinnt, oder dass ein Unentschieden entsteht. Durch Weiterreichen des Arrays "statistik" an jede weitere Instanz der rekursiven Funktion, kann mitgezählt werden, bei welchen terminierenden Verzweigungen Kreuz oder Kreis gewinnt, bzw. ein Unentschieden auftritt.

Startet man die Rekursion mit einem leeren Feld, werden alle überhaupt möglichen Spielverläufe durchgespielt.

Um die Auswertung schneller und einfacher zu machen, wird das Spielfeld als eindimensionales Integer-Array der Länge 9 repräsentiert, in dem die Setzungen in den Feldern vom Spiel zeilenweise gemerkt werden: 0==leer, 1==X, 2==O.

Bei TicTacToe08 werden Spieler implementiert, die bei Übergabe eines Feldes immer den Zug zurückgeben, den sie machen "wollen".

    public void pruefen_rekursiv(int[] statistik, int[] feld)
    {
      //Statistik ergänzen, wenn unentschieden, oder einer gewonnen hat:
      if(feld[0]+feld[1]+feld[2]==3)  {statistik[0]++;return;}
      if(feld[0]+feld[1]+feld[2]==12) {statistik[1]++;return;}
      if(feld[3]+feld[4]+feld[5]==3)  {statistik[0]++;return;}
      if(feld[3]+feld[4]+feld[5]==12) {statistik[1]++;return;}
      if(feld[6]+feld[7]+feld[8]==3)  {statistik[0]++;return;}
      if(feld[6]+feld[7]+feld[8]==12) {statistik[1]++;return;}
  
      if(feld[0]+feld[3]+feld[6]==3)   {statistik[0]++;return;}
      if(feld[0]+feld[3]+feld[6]==12)  {statistik[1]++;return;}
      if(feld[1]+feld[4]+feld[7]==3)   {statistik[0]++;return;}
      if(feld[1]+feld[4]+feld[7]==12)  {statistik[1]++;return;}
      if(feld[2]+feld[5]+feld[8]==3)   {statistik[0]++;return;}
      if(feld[2]+feld[5]+feld[8]==12)  {statistik[1]++;return;}

      if(feld[0]+feld[4]+feld[8]==3)   {statistik[0]++;return;}
      if(feld[0]+feld[4]+feld[8]==12)   {statistik[1]++;return;}
      if(feld[2]+feld[4]+feld[6]==3)   {statistik[0]++;return;}
      if(feld[2]+feld[4]+feld[6]==12)   {statistik[1]++;return;}
  
      //Summe, wenn alle gesetzt:
      //1+4+1+4+1+4+1+4+1 == 21
      int summe = feld[0]+feld[1]+feld[2]+feld[3]+feld[4]+feld[5]+feld[6]+feld[7]+feld[8];
      if(summe==21) {statistik[2]++;return;}

      boolean kreuzdran = true;
      if(summe%5!=0)
          kreuzdran=false;
  
      for(int i=0;i<feld.length;i++)
      {
            if(feld[i]==0)
            {
                if(kreuzdran)
                {
                  feld[i] = 1;
                  pruefen_rekursiv(statistik,feld);
                  feld[i] = 0;
                }
                else
                {
                  feld[i] = 4;
                  pruefen_rekursiv(statistik,feld);
                  feld[i] = 0;
                }
            }
      }
   }

Code 0-1: Rekursive Prüffunktion, die in "statistik" mitzählt, wieviele Siege es ab dem übergebenen Feld für X und O gibt und wie oft unentschieden.

TicTacToe05_effizient.zip -- Einführung der rekursiven Funktion
TicTacToe06_effizient.zip -- Berechnung einer Gewinnwahrscheinlichkeit
TicTacToe08_Turnier.zip -- Implementierung von Spielern
Optimaler Spieler -- Nachtrag

Auffällig wurde im Unterricht vom 6.12., dass der als optimal ausgewiesene Spieler in TicTacToe08_Turnier, der Kreis O setzt, ab und zu verliert, dies jedoch eigentlich passieren dürfte, wenn optimal gespielt wird.

Es wurde ein Zusammenhang dazu vermutet, das nicht in passender Weise berücksichtigt wurde, wie tief im Entscheidungsbaum ein Sieg, eine Niederlage oder ein Unentschieden jeweils liegt, also "wie schwer" dieser Zustand zu erreichen ist.

Außerdem würde ein konservativer Spieler alles daran geben, nie zu verlieren und eher nicht auf Risiko spielen, da nie ganz sicher ist, ob ggf. ein einfältiges Verhalten des Gegners nur vorgetäuscht ist.

Beide Gedanken führen auf eine korrigierte Version, die sich darin auszeichnet, dass zum einen nicht nur Siege, Niederlagen oder Gleichstände gezählt werden, sondern auch die Wahrscheinlichkeit für deren Erreichen ausgehend von dem aktuell zu prüfenden Spielstand mit berücksichtigt wird.

Desweiteren wird als Kriterium für die Beurteilung eines Zuges, bzw. der sich durch den Zug ergebenden neuen Spielsituation nicht mehr die Schwerpunkt-Funktion genommen, sondern die Chance nicht zu verlieren, was das gleiche ist und sich berechnen läßt mit: 1 - P(zu verlieren)

Die Wahrscheinlichkeit für das Erreichen eines bestimmten terminierenden Zustandes (gewinnen, verlieren, Gleichstand), ergibt sich, wenn man der rekursiven Funktion zunächst die Wahrscheinlichkeit 1 mitgibt und diese Anfangsverteilung bei jeder Verzweigung im Suchbaum gleichmäßig aufteilt. Sind also an einem bestimmten Rekursionspunkt noch 5 Felder frei, heißt das ja, dass nun 5 Rekursionsaufrufe nachfolgen. Diesen wird nun jeweils 1/5 des Wahrscheinlichkeitswertes mitgegeben, der für den aktuell betrachteten Rekursionsaufruf galt.

Nachfolgend ist der Quellcode für die dazu passende neue Prüffunktion / Prüfklasse vollständig dargestellt:

public class Pruefer
{
    private double[] statistikP = new double[3];  //Wahrscheinlichkeiten bestimmen
    private int[] kopie = new int[9];

    public double bestimmeP_Kreuz_gewinnt(int[] feld) 
    {
         statistikP[0]=0.0;
         statistikP[1]=0.0;
         statistikP[2]=0.0;
         pruefen_rekursiv(1.0,statistikP,feld);
         return 1.0 - statistikP[1];
    }

    public double bestimmeP_Kreis_gewinnt(int[] feld)
    {
         statistikP[0]=0.0;
         statistikP[1]=0.0;
         statistikP[2]=0.0;
         pruefen_rekursiv(1.0,statistikP,feld);
         return 1.0 - statistikP[0];
    }


    //statistik muß vorher mit Nullen gefüllt werden
    //und liefert die Fälle, mit x o unentschieden
    //Feld Indices:
    //012
    //345
    //678
    public void pruefen_rekursiv(double pAktuell, double[] statistikP, int[] feld)
    {
      //Statistik ergänzen, wenn unentschieden, oder einer gewonnen hat:
      if(feld[0]+feld[1]+feld[2]==3)  {statistikP[0]+=pAktuell;return;}
      if(feld[0]+feld[1]+feld[2]==12) {statistikP[1]+=pAktuell;return;}
      if(feld[3]+feld[4]+feld[5]==3)  {statistikP[0]+=pAktuell;return;}
      if(feld[3]+feld[4]+feld[5]==12) {statistikP[1]+=pAktuell;return;}
      if(feld[6]+feld[7]+feld[8]==3)  {statistikP[0]+=pAktuell;return;}
      if(feld[6]+feld[7]+feld[8]==12) {statistikP[1]+=pAktuell;return;}
  
      if(feld[0]+feld[3]+feld[6]==3)   {statistikP[0]+=pAktuell;return;}
      if(feld[0]+feld[3]+feld[6]==12)  {statistikP[1]+=pAktuell;return;}
      if(feld[1]+feld[4]+feld[7]==3)   {statistikP[0]+=pAktuell;return;}
      if(feld[1]+feld[4]+feld[7]==12)  {statistikP[1]+=pAktuell;return;}
      if(feld[2]+feld[5]+feld[8]==3)   {statistikP[0]+=pAktuell;return;}
      if(feld[2]+feld[5]+feld[8]==12)  {statistikP[1]+=pAktuell;return;}

      if(feld[0]+feld[4]+feld[8]==3)   {statistikP[0]+=pAktuell;return;}
      if(feld[0]+feld[4]+feld[8]==12)   {statistikP[1]+=pAktuell;return;}
      if(feld[2]+feld[4]+feld[6]==3)   {statistikP[0]+=pAktuell;return;}
      if(feld[2]+feld[4]+feld[6]==12)   {statistikP[1]+=pAktuell;return;}
  
      //Summe, wenn alle gesetzt:
      //1+4+1+4+1+4+1+4+1 == 21
      int summe = feld[0]+feld[1]+feld[2]+feld[3]+feld[4]+feld[5]+feld[6]+feld[7]+feld[8];
      if(summe==21) {statistikP[2]+=pAktuell;return;}

      boolean kreuzdran = true;
      if(summe%5!=0)
          kreuzdran=false;
  
      //Nachfolgewert der aktuellen Wahrscheinlichkeit ergibt sich anteilig aus der Anzahl der freien Felder:
      double pAktuellNeu = pAktuell;
      int frei  = 0;
      for(int i=0;i<feld.length;i++)
            if(feld[i]==0)
                frei++;
      if(frei>0)
         pAktuellNeu/=(double)frei;
  
      for(int i=0;i<feld.length;i++)
      {
            if(feld[i]==0)
            {
                if(kreuzdran)
                {
                  feld[i] = 1;
                  pruefen_rekursiv(pAktuellNeu,statistikP,feld);
                  feld[i] = 0;
                }
                else
                {
                  feld[i] = 4;
                  pruefen_rekursiv(pAktuellNeu,statistikP,feld);
                  feld[i] = 0;
                }
            }
      }
   }
}

Code 0-2: Korrigierte Prüffunktion mit Wahrscheinlichkeiten und Verwendung von "1 - P(zu verlieren)".

TicTacToe08_Turnier_P_korrigiert.zip -- Turnier, bei dem der Zufallsspieler X und der optimale Spieler O ist mit jetzt WIRKLICH optimalem Spieler.
Der korrigierte optimale Spieler verliert nicht mehr (Beispielscreenshot nach einem Turnier mit 100 Spielen.)

Bild 0-1: Der korrigierte optimale Spieler verliert nicht mehr (Beispielscreenshot nach einem Turnier mit 100 Spielen.)