3. Computer Algorithmus Vier gewinnt!

Computer Algorithmus Vier gewinnt!


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

    0
  • P

    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.

    0
  • P

    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.

    0

  • 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).

    0
  • P

    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;
}
}
    0
  • P

    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 ?

    0

  • 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).

    0
  • P

    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.

    0
  • P

    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 ?

    0
  • V

    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

    0
  • ?

    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.

    0
Anmelden zum Antworten