Computer Algorithmus Vier gewinnt!



  • Hallo,

    bin gerade dabei Vier gewinnt zu programmieren. Player vs Player geht schon.
    Aber Player vs Computer da bin ich dabei den Algorithmus für den Computer zu programmieren. Naja der Computer kann in 7 verschiedene Spalten werfen. Jetzt geht es darum welche die beste ist. Ich bin da auf den MinMax Algorithmus gestossen. Maximaler Nutzen für den Computer, minimaler für den Player. Soweit so gut. Aber wie soll ich das jetzt implementieren. Der Algorithmus würde ja auch für Schach etc. gehen. Wenn immer man die voll Spielübersicht hat. Die Frage wie mach ich das jetzt für 4 Gewinnt.



  • Entscheidend ist dann einfach die Bewertungsfunktion, d.h. ein Sieg positiv (hoch) bewerten und eine Niederlage negativ, und dazwischen dann entsprechend Abstufungen.
    Und wichtig: die Anzahl der Züge bis zum Sieg (oder Niederlage) einberechnen (falls du nicht komplett durchrechnen läßt)

    Und statt dem MinMax nimm die verbesserte Version: Alpha-beta-Pruning

    Hier als Hint meine Bewertungsfunktion:

    int VierGewinnt::GetValuation(int nCheckLine)
    {
    	if(nCheckLine<=WinLine/2) return 1+random(10);
    	if(nCheckLine>WinLine) nCheckLine=WinLine;
    	int f = MaxLevel*nCheckLine-(nLevel-1);
    	return -(5*f+random(5));
    }
    

    nCheckLine gibt die max. Anzahl der in einer Reihe befindlichen Steine (und WinLine ist hier bei 4 Gewinnt einfach 4 😉
    nLevel ist der aktuelle Schwierigkeitslevel (Berechnungstiefe) der KI (von MinLevel bis MaxLevel) - kannst du erst einmal ignorieren.
    Und der Zufall ist drin, um ein bißchen Abwechslung zu haben...



  • aber ich muss ja für jede Spalte die Reihe prüfen. Schließlich können die Steine je Spalte unterschiedlich hoch sein. Und was bringt es mir nur die Anzahl der STeine je Zeile zu prüfen. Ich muss ja irgendwie prüfen ob ich daraus 4 gleiche Steine machen kann.

    z.B 1:gelb 2:rot 3:leer 4:leer 5:rot 6:gelb 7:gelb

    Jetzt könnte ich beim Algorithmus hypothetisch in Spalte 3 werfen. Viel wird das dann nicht bringen da der Spieler dann in Spalte 4 wirft. Hmm.



  • Mit "x in einer Reihe" meine ich natürlich nicht die Anzahl pro Spalte sondern schon alle Varianten (horizontal, vertikal, diagonal). Und klar - benötigt man dafür eine Funktion, welche für die ausgewählte Spalte (bzw. für alle Spalten) den maximalen Wert ermittelt.



  • Seh ich das richtig, dass der Algorithmus des Computers schon sehr kompliziert ist. Gibt es im Netz schon einen implementierten Algorithmus der wenn der Computer beginnt immer gewinnt ? Würd mich mal intressieren wie der aussieht.



  • Peter_Mueller schrieb:

    Seh ich das richtig, dass der Algorithmus des Computers schon sehr kompliziert ist. Gibt es im Netz schon einen implementierten Algorithmus der wenn der Computer beginnt immer gewinnt ? Würd mich mal intressieren wie der aussieht.

    zumindest auf unentschieden spielen sollte bei optimalen Spielzügen immer drin sein.
    Einfach alle (bzw. möglichst viele) Spielzüge simulieren, in einem Baum speichern, und dort dann immer den Zweig (=Speilzug) nehmen, der am besten für den Computer ist.



  • Score4 (Connect four) (beachte auch den Link auf die Erklärung für die "AI").



  • hgfhfhf schrieb:

    Einfach alle (bzw. möglichst viele) Spielzüge simulieren, in einem Baum speichern, und dort dann immer den Zweig (=Speilzug) nehmen, der am besten für den Computer ist.

    Wenn ich das richtig berechne, dann hat man beim Vier Gewinnt 7 Möglichkeiten den Stein hineinzuwerfen. Es würde also 7 hoch 42 Möglichkeiten geben(ob die Rechnung genau stimmt weiss ich jetzt nicht, jedenfalls wäre das 10 hoch 35 ). Die alle zu speichern ist wohl etwas aufwändig selbst wenn man die Symmetrie ausnutzt. Der beste Zug für den Spieler wäre doch dann der wo er am schnellsten gewinnt. Tiefensuche mininmal also.



  • Th69 schrieb:

    Score4 (Connect four) (beachte auch den Link auf die Erklärung für die "AI").

    also ich seh da nur Implementierungen in diversen Programmiersprachen. Link für die AI seh ich noch nicht *gg*. Also seh mir gerade die Java Implmentierung an. Keine Ahnung ob das die beste ist.

    Welchen Link meinst du ?

    Schade dass der Java Code kaum kommentiert ist.



  • Direkt in der Überschrift: http://users.softlab.ece.ntua.gr/~ttsiod/score4.html

    Und die AI ist jeweils in der (statischen) Methode "abMinimax" implementiert (auch wenn ich diese Implementierung nicht so gelungen finde).



  • Ich versteh den Code irgendwie nicht richtig. Leider wird kaum was kommentiert.

    public static void minimax(
    bool maximizeOrMinimize, Mycell color, int depth, Board board,
    out int move, out int score)
    {
    if (0 == depth) {
    move = ‐1;
    score = ScoreBoard(board);
    } else {
    int bestScore=maximizeOrMinimize?‐10000000:10000000;
    int bestMove=‐1;
    for (int column=0; column<width; column++) {
    if (board._slots[0][column]!=Mycell.Barren)
    continue;
    int rowFilled = dropDisk(board, column, color); // damage the state
    if (rowFilled == ‐1)
    continue;
    int s = ScoreBoard(board);
    if (s == (maximizeOrMinimize?orangeWins:yellowWins)) {
    bestMove = column;
    bestScore = s;
    board._slots[rowFilled][column] = Mycell.Barren;
    break;
    }
    int moveInner, scoreInner;
    minimax(
    !maximizeOrMinimize,
    color==Mycell.Orange?Mycell.Yellow:Mycell.Orange,
    depth‐1,
    board,
    out moveInner, out scoreInner);
    board._slots[rowFilled][column] = Mycell.Barren; // Undo the damage
    if (depth == maxDepth && g_debug)
    Console.WriteLine(
    "Depth {0}, placing on {1}, score:{2}",
    depth, column, scoreInner);
    // No need for lists and sorting ‐ just keep the best value you meet.
    if (maximizeOrMinimize) {
    if (scoreInner>=bestScore) {
    bestScore = scoreInner;
    bestMove = column;
    }
    } else {
    if (scoreInner<=bestScore) {
    bestScore = scoreInner;
    bestMove = column;
    }
    }
    }
    move = bestMove;
    score = bestScore;
    }
    }
    


  • Wie würde ich persönlich mal ganz unabhängig einen Algorithmus für den Computer implementieren.

    1. Checke ob der Computer gewinnen kann.
    2. Checke ob der Player gewinnen kann.
    3. Checke ob Computer horizontal/vertikal/diagonal wenigstens 3 zusammen bringt.
    Checke ob Computer horizontal/vertikal/diagonal wenigstens 2 zusammen bringt.
    Sonst werfe irgendwo zufällig rein.
    4. Prüfe was der Player im nächsten Wurf dann machen könnte.

    So würde ich das implementieren. Ohne Kenntnis von MinMax.

    Ich versteh jetzt immer noch nicht, ob der MiniMax auch für Schach geeignet ist, da Schach ja unendlich viele Spielsituationen hat. Bedeutet der Minimax dass ich alle mögliche Spielsitutationen in einem Baum speicher und dann immer den Baum durchgehe und den besten Move mache. Dabei versteh ich auch noch nicht wie ich die Punkte vergeben soll.

    Das hätte mit meiner Implementierung ja gar nichts zu tun. Oder ?



  • Hast du denn den Link zur AI gelesen (d.h. den Min-Max-Tree angeschaut)?

    Der Min-Max Algorithmus rechnet einfach alle möglichen Positionen durch (solange bis ein Spieler gewonnen hat oder ein Remis entstanden ist) und gibt dann für alle Spielsituationen jeweils den Zug mit der besten Bewertung zurück. Und genau diese Bewertungsfunktion ist eben das Entscheidende bei der Umsetzung.

    Generell würde Min-Max auch bei Schach funktionieren (wenn man unendlich Rechenzeit einkalkuliert ;-), jedoch nimmt man besser die (wie von mir oben schon erwähnte) Alpha-Beta-Suche.

    Deine Vorgehensweise ist ja prinzipiell richtig, nur daß du daraus dann (aus einer beliebigen Spielsituation) dann eine Bewertungsfunktion ableiten mußt.
    Als ich meinen ersten Beitrag oben für dich schrieb, bin ich davon ausgegangen, daß du den Min-Max-Algorithmus schon komplett verstanden hattest ;-).

    PS: Wenn du schon Code hier reinstellst, dann lass die Formatierung drin (so ist der Code echt nicht mehr zu lesen).



  • Wie kommt man eigentlich an die numerische Bewertungen der Knoten wenn man z.B. nur bis Tiefe 4 geht.

    Ich mein wenn ich bis ans Blatt geh, dann seh ich ja ob dieser Spielzug gewinnt oder verliert. Dann geb ich +10 oder -10 punkte.

    Aber um die Sache zu beschleunigen möchte man ja die Tiefe begrenzen. Wie soll man da jetzt an den "Leafs" eine Bewertung vornehmen.

    Und ich versteh überhaupt nicht was das mit meiner Herangehensweise zu tun haben soll. Ich bau doch gar keinen Baum auf. Bevor das Spiel anfängt muss man sich den Baum aufbauen. Oder wie geht das.

    Und ich versteh auch nicht. Ist der Terminal State ein Gewinn für den Player dann bekommt dieser die höchste Punktzahl. Aber sicherlich gibt es viele Spielzuge wo der Player gewinnen würde. Welchen nimmt man dann überhaupt.

    Und wenn ich das richtig verstehe haben nur die Leafs also die Terminal States einen Nutzenwert. Diesen Nutzenwert reicht man dann bis zum Root Knoten hoch und man weiss welchen Spielzug man machen muss.

    Ah ok. Wenn man nicht zum Leaf möchte muss man sich wohl eine Evaluations Funktion basteln. Hm.



  • Also ich programmiere gerade meinen eigenen Algorithmus.

    Werfe ich in eine Spalte prüfe ich wieviel gleiche ich dadurch horizontal,vertikal und diagonal zusammenbekomme. Davon würde ich dann abziehen was der Gegner gewinnen würde wenn er in eine der anderen Spalte wirft.

    Klingt das gut ?



  • Peter_Mueller schrieb:

    Also ich programmiere gerade meinen eigenen Algorithmus.

    Werfe ich in eine Spalte prüfe ich wieviel gleiche ich dadurch horizontal,vertikal und diagonal zusammenbekomme. Davon würde ich dann abziehen was der Gegner gewinnen würde wenn er in eine der anderen Spalte wirft.

    Klingt das gut ?

    Ja. Aber er wird recht doof bleiben und nur Anfängern das Leben schwer machen, fürchte ich fast. Viele Spiele werden sind früh verloren, was sich aber erst in Zug 38 oder so verwirklicht. So weit kann er einfach nicht gucken.
    Deswegen würde ich an https://en.wikipedia.org/wiki/Monte_Carlo_tree_search denken.
    Und natürlich den Klassiker http://www.pomakis.com/c4/expert_play.html

    ups: https://en.wikipedia.org/wiki/Connect_Four#Algorithms



  • Und wo ist dein Programm? Hast du es geschrieben und funktioniert es? Keine Rückmeldung. Ich frage nur weil ich schon einen neuen Thread sehe in dem auch nur Fragen gestellt werden aber sonst nichts gezeigt wird.


Log in to reply