4-Gewinnt KI

L

LrdZwibl

0
Hi!

Muss für die Schule unter C - 4-Gewinnt schreiben!
Soweit so gut...

Nun habe ich das Problem das ich keine anständige KI hinbekomme!

Vielleicht kann mir ja jemand helfen!!!


Vielen Dank im voraus!!!
 
Hmm, das ist realtiv komplitziert.

Normalerweise würde ich dir zu einer Heuristik raten. D.h. du gibts jeder möglichen Stelllung einen Wert (100 bei gewonnen, -100 bei verloren, der Rest irgendwo dazwischen), ermittelst den Durchschnittswert aller möglchen Züge und lässt die KI dann den höchsten ausführen.

Ist umständlich zu erklären, aber du kannst ja auch mal nach heuristik googlen.
 
hab mir dies auch schon überlegt, aber noch nie programmiert: ich würde die KI folgendermassen machen:

Erstelle eine prioritätenliste mit "guten" spielzügen: z.B. 1. Prio: Gewinn in einem zug (logisch...), 2. Prio: Zug, dass der "Mensch" nicht gewinnt, 3. Prio. versuche, 3 steine in eine linie zu bekommen.... usw

hoffe, konnte dir weiter helfen
 
Hab mir das bisher so überlegt...

das ich den Feldern Werte zuteile!
Erster Spieler ist +1, KI -1 und wenn dann in einer Reihe ein Wert erreicht ist
wird gesetzt! Ist aber halt nur zu verteidigung und selbst dafür nicht richtig gut :(
 
ICh hab das selbst programmiert und bin mir nicht soo ganz sicher ob das so ok ist. ALso ich denke es sind der ein oder andere Fehler und nicht so 100%ig sauber geproggt. Daher isses meines erachtens nicht unbedingt Wert hier das ganze komplett zu posten da ich auch im Moment die KI noch weiter entwickeln möchte.

Daher.. X(


Wenn ich damit fertig bin kann ich gerne - wenn Interesse besteht - das ganze mal irgendwo zum DL anbieten.

EDIT: Ich hab auch von LrdZwibl noch reine Rückmeldung was er davon hält, er versucht es wohl noch zu verstehen.. :P
 
Das was eine Ki können muss ist:
1. Gucke nach ob du gewinnen kannst, wenn ja mach es.
2. Gucke nach ob der gegner Gewinnen kann., wenn ja verhinder es.
3. Programmiere ein paar Spielzüge ein.
4. Merke dir wann nicht der Computer gewonnen hat, und finde eine Lösung.



Ich habe das mal bei einem TicTacToe spiel gemacht. Ist im Prinzip das gleiche. Nur eben mit 3 in einer Reihe. Wenn du das Programm mal sehen willst geh mal auf http://www.saschaschwarz.de da findest du meine ICQ Nummer
 
Sorry das ich den alten Thread wieder nach vorne hol, aber meine Problem passt zu dem Thema.

Ich hab mich auch ein wenig mit Brettspiel-KIs beschäftigt (hauptsächlich TicTacToe und Vier Gewinnt) und hab auch schon ein TicTacToe-Computergegner programmiert (Java), der sogar halbwegs intelligent ist, aber perfekt spielt er noch lange nicht.
Auf der Suche nach weiteren Informationen stolpert man zwangsläufig über den Minimax-Algorithmus. Ich hab einiges darüber gelesen, hab auch ein Pseudo-Code-Beispiel (siehe unten) und will jetzt einen Computergegner coden, der seinen Zug mit Hilfe des Minimax-Algorithmus berechnet, meine bisherigen Versuche sind jedoch gescheitert.

Kann mir jemand bei der Umsetzung helfen? Wenn ja kann ich auch mein Vier Gewinnt Programm posten (da fehlt nur noch der Computergegner).

Hier mal der Pseudocode, den ich gefunden hab:
Code: 
function Minimax ( brett, farbe, tiefe ): integer
    solange tiefe > 0
        ermittle alle möglichen zuege der jeweiligen farbe

        für jeden neuen zug rufe auf:
            wert := minimax( neues_brett, not farbe, (tiefe-1) )

            wenn farbe = weiss dann
                wenn result < wert dann
                    result := wert
                    brett.naechsterzug := zug

            wenn farbe = schwarz dann
                wenn result > wert dann
                    result := wert
                    brett.naechsterzug := zug

    wenn tiefe = 0
        result := Bewerte_Stellung( brett )

ende - function

EDIT
Da noch niemand geantwortet hat, versuche ich mal meine Frage zu konkretisieren:

1. Die Funktion minimax hat doch einen Rückgabewert vom Typ int, oder? Wenn ja: Was wird weitergegeben? Die Position des Zuges oder der die Bewertung?

2. Woher weiß ich am Ende (Also wenn Tiefe==0) noch welchen Zug ich eigentlich bewerte, also an welchem Punkt die Zugsuche angefangen hat?

EDIT 2
Es funktioniert jetzt, die Fragen oben haben sich also erledigt. Jetzt feil ich an der Bewertungsfunktion. Wenn jemand Tipps, Anregungen oder vielleicht eine sehr gute Bewertungsfunktionen hat, wärs nett, wenn er sich meldet! :)

mal wieder ein EDIT :)
Die Behauptung das mein Code funktioniert war wohl etwas überhastet. Nachdem ich meinen Computergegner soweit hatte, dass er endlich mit dem Algorithmus Züge macht, hab ich gedacht, dass es funktioniert. Die Züge zeugten zwar von bescheidener Intelligenz, aber ich dachte das liegt an der schlechten Bewertungsfunktion. Jetzt hab ich das Ganze zur Überprüfung mal als TicTacToe-Version gecodet mit der einfachsten und gleichzeitig auch besten Bewertungsfunktion (Quelle: Wikipedia/Minimax). Doch auch hier spielt der Computergegner trotz maximaler Suchtiefe (Algorithmus bricht erst ab wenn das Feld voll ist oder ein Spieler gewonnen hat) total schlecht.

Ich hab mein Programm jetzt nach dem Pseudocode von Wikipedia programmiert und hab eigentlich gedacht ich hab alles richtig gemacht, aber anscheinend hab ich irgendwo ein Fehler. Kann mir jemand erklären was ich falsch mache?

Hier ist mein Minimax-Algorithmus (das komplette Programm ist im Anhang):

Code: 
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; 
        for(int i=0; i<9; i++){           
            //Suche mögliche Züge
            if(TicTacToe.position[i]=='0'){
                //Simuliere den Zug
                TicTacToe.position[i]='O';
                //Wenn keine Züge mehr möglich
                if(TicTacToe.voll()==true ||Sieg.sieg('O')==true)               
                    zugWert=bewertungsFunktion('X');                   
                else               
                    zugWert=minWert();
                //Zugsimulation zurücksetzen
                TicTacToe.position[i]='0';
                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;
        int wert; 
        for(int i=0; i<9; i++){           
            //Suche mögliche Züge
            if(TicTacToe.position[i]=='0'){
                //Simuliere den Zug
                TicTacToe.position[i]='X';
                //Wenn keine Züge mehr möglich
                if(TicTacToe.voll()==true ||Sieg.sieg('X')==true)               
                    zugWert=bewertungsFunktion('X');                   
                else               
                    zugWert=maxWert();
                //Zugsimulation zurücksetzen
                TicTacToe.position[i]='0';
                if(zugWert<ermittelt)
                    ermittelt=zugWert;
            }
        }
        return ermittelt;
    }
    private static int bewertungsFunktion(char c) 
    {                    
        if(Sieg.sieg('O')==true)
            return 1;     
        else if(Sieg.sieg('X')==true)
            return -1;
        else
            return 0;
    }
}

Gruß, Boar
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben