Umsetzung des Minimax-Algorithmus

[Boar]

Hi!
Ich beschäftige mich im Moment mit der Programmierung verschiedener kleiner Brettspiele (z.B. TicTacToe und Vier Gewinnt). Die Umsetzung der Spiele an sich ist kein Problem, nur bei der Programmierung der Computergegner hakt es. Auf der Suche nach weiteren Informationen stolpert man zwangsläufig über den Minimax-Algorithmus (Informationen dazu gibt es hier). Jetzt hapert es da aber noch an der Umsetzung (Ich habe versucht den Pseudo-Code von Wikipedia (siehe Link) in Java zu programmieren).

Bei TicTacToe z.B. kann man den Suchbaum mit dem Minimax-Verfahren komplett aufbauen (weil die Anzahl der möglichen Züge verhältnismäßig klein ist). Deshalb spielt der Computergegner (wenn er richtig programmiert ist) perfekt. Bei meinem Programmier-Versuch spielt der Computer aber total bescheiden... Deshalb denke ich, dass ich einen Fehler im Code hab, ich weiß jedoch nicht wo.

Hier ist die Klasse, die den Minimax-Algorithmus enthält:

package spiel;

public class Comp {
    static int next;    
    static int wert;
    static char notC; 
    
    //Funktion maxWert
    public static int maxWert() {
        int ermittelt=-1000;
        int zugWert=0; 
        for(int i=0; i<9; i++){           
            //Suche mögliche Züge
            if(TicTacToe.position[i]=='L'){ //L = leeres Feld
                //Simuliere den Zug
                TicTacToe.position[i]='O';
                //Wenn keine Züge mehr möglich
                if(TicTacToe.voll()==true ||Sieg.sieg('O')==true)               
                    zugWert=bewertungsFunktion();                   
                else               
                    zugWert=minWert();
                //Zugsimulation zurücksetzen
                TicTacToe.position[i]='L';
                if(zugWert>ermittelt){
                    ermittelt=zugWert;
                    next=i; //für das Hauptprogramm (Position des nächsten Zugs)
                }
            }
        }
        return ermittelt;
    }
    //Funktion minWert
    public static int minWert() {
        int ermittelt=1000;
        int zugWert=0;
        int wert; 
        for(int i=0; i<9; i++){           
            //Suche mögliche Züge
            if(TicTacToe.position[i]=='L'){
                //Simuliere den Zug
                TicTacToe.position[i]='X';
                //Wenn keine Züge mehr möglich
                if(TicTacToe.voll()==true ||Sieg.sieg('X')==true)               
                    zugWert=bewertungsFunktion();                   
                else               
                    zugWert=maxWert();
                //Zugsimulation zurücksetzen
                TicTacToe.position[i]='L';
                if(zugWert<ermittelt)
                    ermittelt=zugWert;
            }
        }
        return ermittelt;
    }
    private static int bewertungsFunktion() 
    {                    
        if(Sieg.sieg('O')==true)
            return 1;     
        else if(Sieg.sieg('X')==true)
            return -1;
        else
            return 0;
    }
}

TicTacToe.position[0..8] speichert die Züge (X = menschliche Spieler, O = Computer, L = Leeres Feld)
Aufgerufen wird der Computerzug nachdem der menschliche Spieler gesetzt hat:

x = Comp.maxWert();
Setze.pos(Comp.next,'O',Color.blue);

Wenn ihr noch weitere Informationen braucht sagt bescheid.

Danke für die Hilfe!

 

[Boar]

Also dieser Post hilft mir auch nicht weiter, kann mir denn niemand helfen? Oder hat vielleicht einer einen Link wo der Algorithmus verständlich erklärt wird?

 

[mic_checker]

Hab mir den Source nicht angeguckt, aber hier steht was von nem java source dazu