/*
 * JMiniMax.java
 *
 * Created on 14. März 2004, 14:47
 */

package MiniMax;

/**
 * Iteratives, näherungsweises Verfahren zur Bestimmung des Werts eines 
 * Zweipersonen-Spiels nach dem MiniMax-Prinzip,
 * aus:
 * Paragraph 6, in: Wentzel, J.S. (1976); Elemente der Spieltheorie, 
 * Verlag Harri Deutsch, Frankfurt.
 *
 * @author  Florian Hiemeyer
 * @version 1.00
 */
public class JMiniMax {
    
    /** SpielMatrix, in Integerform transformiert. */
    private int[][] game;
    
    /** Zeilenzahl in game */
    private int rows;
    
    /** Spaltenzahl in game */
    private int cols;
    
    /** Kleinster Wert des Spiels */
    private int alpha;
    
    /** Größter Wert des Spiels */
    private int beta;
    
    /** optimale gemischte Strategie von Spieler A */
    private double[] mixStratA;
    
    /** optimale gemischte Strategie von Spieler B */
    private double[] mixStratB;
 
    /** Schätzer für den Wert des Spiels */
    private double nuEst;
    
    /** ist ein Exakter Wert des Spiels direkt ermittelbar? */
    private boolean exactNu = false;
    
    /** Maximale Iterationszahl */
    private int maxIter = 18;
    
    /** Abbruchgenauigkeit der Schätzung für den Wert des Spiels */
    private double nuEps = 0.0000001;
    
    /** Konstruktor, benutzerdefinierte Genauigkeit */
    public JMiniMax( int[][] _game, double eps, int maxIt ) {
        nuEps   = eps;
        maxIter = maxIt;
        if ( _game == null )
            System.out.println("Error! Invalid Game!");
        
        game = cleanGame(_game);
        
        values();
        
    }
    
    /** Konstruktor, nutze Voreinstellungen zur Genauigkeit */
    public JMiniMax( int[][] _game ) {
        if ( _game == null )
            System.out.println("Error! Invalid Game!");
        
        game = cleanGame(_game);
        
        values();
    }
    
    
    /** Ermittele Wert des Spiels und optimale Strategien für die Spieler (näherungsweise) */
    public void iterate() {
        
        System.out.println("Kein Sattelpunkt -> Iterationsverfahren; \"iterate()\":");
        // Variablen und Klassen-Attribute initialisieren
        int iter = 0;
        double nuMin = Integer.MIN_VALUE, nuMax = Integer.MAX_VALUE;
        nuEst = 0.;
        int tempStratA = -1, tempStratB = -1;
        int[] tempPayVectA = new int[rows];
        int[] tempPayVectB = new int[cols];
        mixStratA = new double[rows];
        mixStratB = new double[cols];
        
        // Erste Strategie von A (im ersten Spiel!) -> Zufällig auswählen!
        tempStratA = (int)Math.floor(Math.random()*rows);
        
        /** solange die maximale Iterationszahl nicht über- bzw. die gewünschte Genauigkeit
         *  nicht unterschritten ist -> neues Spiel mit der bis dato fälligen Auszahlung
         *  durchführen!
         */
        while( (iter < maxIter) && (nuMax-nuMin > nuEps)  ) {
           /** Addiere elementweise die Auswirkungen der aktuellen Strategie A auf die bisherigen 
            *  Auszahlungen für B
            *  Bestimme dabei auch tempStratB, die für B bei Betrachtung des bisherigen Verlaufs der 
            *  Spiele ideale Strategie.
            */
           int min = Integer.MAX_VALUE;
           for(int j = 0; j<cols;j++) {
              int temp = tempPayVectB[j] + game[tempStratA][j];
              if( temp < min ) {
                  min = temp;
                  tempStratB = j;
              }
              tempPayVectB[j] = temp;
           }
           
           // Jetzt die bisher gewählte Anzahl der Strategie "tempStratA" und 
           // "tempStratB" um eins erhöhen.
           mixStratA[tempStratA]++;
           mixStratB[tempStratB]++;
           
           /**
           System.out.print(( iter+1 )+" | "+ (tempStratA+1)+" |");
           for(int j=0;j<cols;j++)
             System.out.print(" "+tempPayVectB[j]+" |");
           System.out.print("| "+ (tempStratB+1)+" |");
           */
            
           /** Das gleiche für Strategie B */
           int max = Integer.MIN_VALUE;
           for(int i = 0; i<rows;i++) {
               int temp = tempPayVectA[i] + game[i][tempStratB];
               if( temp > max ) {
                   max = temp;
                   // neue Strategie für A
                   tempStratA = i;
               }
               tempPayVectA[i] = temp;
           }
            
           /**
           for(int i=0;i<rows;i++)
             System.out.print(" "+tempPayVectA[i]+" |");
           */
           
           // Bestimmung des minimalen und maximalen nu-Werts
           nuMin = (double)min/(iter+1);
           nuMax = (double)max/(iter+1);
           
           // Berechnung des mittleren nu-Werts als Schätzer.
           nuEst = (nuMin+nuMax)/2;
           
           /** System.out.println(" "+nuEst); */
           // Iterationszahl um eins erhöhen.
           iter++;
        }
          // aus den _Anzahlen_ der gewählten Strategien
          // die relativen Häufigkeiten berechnen
          for(int i=0;i<rows;i++) 
             mixStratA[i] /=iter;
          for(int j=0;j<cols;j++)
             mixStratB[j] /=iter;
          System.out.println("Abbruch nach "+iter+" Iterationen");
          System.out.println("Schätzer für den Wert des Spiels: "+nuEst); 
          System.out.println("Unterschied bei Abbruch: "+(nuMax-nuMin));
          System.out.println();
    }
    
    /** 
     * Statische Methode, um eine Spielmatrix auszugeben
     */
    public static void showGame(int[][] _game,String displaytext) {
        // Show Game + Message
        System.out.println(displaytext);
        for (int i = 0; i<_game.length;i++) {
            for (int j = 0;j<_game[0].length;j++) {
                System.out.print("| "+_game[i][j]+" ");
            }
            System.out.println("|");
        }
        System.out.println();
    }
    /**
      * Entferne unzulässige und doppelte Strategien,
      * statische Methode
      */
    public static int[][] cleanGame(int[][] _game) {
        
        System.out.println("Zeilen-/Spaltenkontrolle; \"cleanGame()\":");
        showGame(_game,"Vorher:");        
        
        boolean[] remRows = new boolean[_game.length];
        boolean[] remCols = new boolean[_game[0].length];
        /** Zunächst Zeilen des Spiels mit jeder Zeile 
         *  (außer gleichen und bereits als ungünstigen gekennzeichneten)
         *  spaltenweise vergleichen, wenn nicht ungünstig -> nicht als
         *  ungünstig markieren.
         *  Die ungünstigen Zeilen werden in remRows[] mit "true" gespeichert.
         */
        for(int k = 0;k<_game.length;k++) {
            if( remRows[k] )
                    continue;
            for(int i = 0;i<_game.length;i++) {
               if ( ( i == k) || remRows[i] )
                      continue;
                boolean rem = true;
                for(int j = 0;j<_game[0].length;j++) {
                    if (_game[i][j] > _game[k][j]) {
                        rem=false;
                        break;
                    }
                }
                remRows[i]=rem;
            }    
        }
        
        // Kontrolle in den Spalten (siehe Zeilenkontrolle!)
        for(int k = 0;k<_game[0].length;k++) {
            if( remCols[k] )
                    continue;      
            for(int j = 0;j<_game[0].length;j++) {
                if ( (k == j) || remCols[j] )
                    continue;
                boolean rem = true;
                for(int i = 0;i<_game.length;i++) {
                    if (_game[i][j] < _game[i][k]) {
                        rem=false;
                        break;
                    }
                }
                remCols[j]=rem;
            }    
        }
        
        /** Neue Zeilen und Spaltenlänge des Spiels bestimmen, und 
         *  Veränderungen am Spiel ausgeben.
         */
        int newRows = 0;
        for(int i = 0;i<remRows.length;i++) {
            if( !remRows[i] )
                newRows++;
            else 
                System.out.println((i+1)+". Zeile entfernt weil unzulässig oder doppelt!");
        }
        
        int newCols = 0;
        for(int j = 0; j<remCols.length;j++) {
            if( !remCols[j] )
                newCols++;
            else 
                System.out.println((j+1)+". Spalte entfernt weil unzulässig oder doppelt!");
        }
        
        // Neues Spiel in passenden Dimensionen initialisieren
        int[][] retGame = new int[newRows][newCols];
        
        /** Die neue Spielmatrix mit allen noch "legitimen" Aktionen bzw. Zeilen und Spalten
         *  auffüllen
         */
        for (int i = 0, row = 0;i<remRows.length;i++) {
             if ( remRows[i] )
                 continue;
            for (int j = 0, col = 0;j<remCols.length;j++) {
                if ( remCols[j] )
                    continue;
                retGame[row][col] = _game[i][j];
            col++;
            }
        row++;
        }
       
        // Spiel erneut als Ausgabe präsentieren
        showGame(retGame,"Nachher:");
       
        return retGame;
    }
        
    /** Berechne den kleinsten und den größten Wert
     *  des Spiels
     */
    public void values() {
        System.out.println("Besetzung der Werte, Analyse auf Sattelpunkt; \"values()\":");
        /** Bestimme Dimensionen von game */
        rows = game.length;
        cols = game[0].length;
        
        if(rows == 0 || cols == 0 )
            System.out.println("Error! Invalid Game!");
        
       /** kleinster Wert (alpha) */
       alpha      = Integer.MIN_VALUE;
       int alphaStrat = -1;
       for(int i=0;i<rows;i++) {
           int alphaMin = Integer.MAX_VALUE;
           for(int j=0;j<cols;j++) {
               // Minimum über alle Spalten (für Zeile i) finden
               int temp = game[i][j];
               if( temp < alphaMin )
                   alphaMin = temp; 
           }
           if (alphaMin > alpha ) {
              // Maximum über alle Zeilen finden
              alpha      = alphaMin;
              alphaStrat = i;
           }
       }
       
       /** größter Wert (beta) */
       beta      = Integer.MAX_VALUE;
       int betaStrat = -1;
       for(int j=0;j<cols;j++) {
           int betaMax = Integer.MIN_VALUE;
           for(int i=0;i<rows;i++) {
               // Maximum über alle Zeilen (für Spalte j) finden 
               int temp = game[i][j];
               if( temp > betaMax ) {
                   betaMax = temp;
               }
           }
           if (betaMax < beta ) {
             // Minimum über alle Spalten finden
             beta = betaMax;
             betaStrat = j;
           }
       }
       
       System.out.println("Alpha: "+alpha);
       System.out.println("Beta : "+beta);
       
       
       if(alpha == beta)
           exactNu = true;
       
       System.out.println("Dim: "+rows+":"+cols);
       
       if( exactNu ) {
           System.out.println("Sattelpunkt gefunden!");
           nuEst = alpha;
           mixStratA = new double[rows];
           mixStratA[alphaStrat] = 1;
           mixStratB = new double[cols];
           mixStratB[betaStrat]++;
       } else        
           iterate();
       
        System.out.println("Gemischte Strategie für A: ");
          for(int i=0;i<rows;i++) {
              System.out.println( (i+1)+": "+mixStratA[i]);
          }
          System.out.println(); 
          
          System.out.println("Gemischte Strategie für B: ");
          for(int j=0;j<cols;j++) {
              System.out.println( (j+1)+": "+mixStratB[j]);
          }
          System.out.println("----- ENDE DER ANALYSE ------");
          System.out.println(); 
       
    }    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        
        // Beispielmatrix aus §6
        int[][] dreimaldrei = new int[3][3];
        dreimaldrei[0][0] = 8;
        dreimaldrei[0][1] = 2;
        dreimaldrei[0][2] = 4;
        dreimaldrei[1][0] = 4;
        dreimaldrei[1][1] = 5;
        dreimaldrei[1][2] = 6;
        dreimaldrei[2][0] = 1;
        dreimaldrei[2][1] = 7;
        dreimaldrei[2][2] = 3;
        
        // Mit 10 multiplizierte Matrix von S. 18 (Sattelpunkt!)
        int[][] viermalvier = new int[4][4];
        viermalvier[0][0] = 4;
        viermalvier[0][1] = 5;
        viermalvier[0][2] = 9;
        viermalvier[0][3] = 3;
        
        viermalvier[1][0] = 8;
        viermalvier[1][1] = 4;
        viermalvier[1][2] = 3;
        viermalvier[1][3] = 7;
        
        viermalvier[2][0] = 7;
        viermalvier[2][1] = 6;
        viermalvier[2][2] = 8;
        viermalvier[2][3] = 9;
        
        viermalvier[3][0] = 7;
        viermalvier[3][1] = 2;
        viermalvier[3][2] = 4;
        viermalvier[3][3] = 6;
        
        
        //5-mal-fünf Matrix (cleanGame-Test)
        int[][] fuenfmalfuenf = new int[5][5];
        fuenfmalfuenf[0][0] = 4;
        fuenfmalfuenf[0][1] = 5;
        fuenfmalfuenf[0][2] = 9;
        fuenfmalfuenf[0][3] = 3;
        fuenfmalfuenf[0][4] = 10;
        
        fuenfmalfuenf[1][0] = 8;
        fuenfmalfuenf[1][1] = 4;
        fuenfmalfuenf[1][2] = 3;
        fuenfmalfuenf[1][3] = 7;
        fuenfmalfuenf[1][4] = 20;
        
        fuenfmalfuenf[2][0] = 7;
        fuenfmalfuenf[2][1] = 6;
        fuenfmalfuenf[2][2] = 8;
        fuenfmalfuenf[2][3] = 9;
        fuenfmalfuenf[2][4] = 19;
        
        fuenfmalfuenf[3][0] = 7;
        fuenfmalfuenf[3][1] = 2;
        fuenfmalfuenf[3][2] = 4;
        fuenfmalfuenf[3][3] = 6;
        fuenfmalfuenf[3][4] = 19;
        
        fuenfmalfuenf[4][0] = 7;
        fuenfmalfuenf[4][1] = 2;
        fuenfmalfuenf[4][2] = 4;
        fuenfmalfuenf[4][3] = 6;
        fuenfmalfuenf[4][4] = 40;
        
        // Testet "Cleaning (und Sattelpunkt)"
        JMiniMax cleanTest = new JMiniMax(fuenfmalfuenf);
        
        // Testet "iteratives Approximieren"
        JMiniMax itTest = new JMiniMax(dreimaldrei);
    }
    
}