3. Perfekte KI für Vier Gewinnt

Perfekte KI für Vier Gewinnt

  • V

    antialias schrieb:

    Da ich mich auch mal mit dem Thema beschäftigt habe (allerdings als Spieler) empfehle ich dir die Masterarbeit von Victor Allis:

    "A Knowledge-based Approach of Connect-Four - The Game is Solved: White Wins"
    http://www.connectfour.net/Files/connect4.pdf
    (Source code gibts an diversen Stellen im Netz.)

    In seiner Arbeit bekommst du die komplette Theorie, um eine perfekte (sprich: unschlagbare) KI für 4 gewinnt zu schreiben*. Brute-force/Alpha-Beta Algorithmen sind unnötig.

    * Dies gilt natürlich nur sofern die KI den ersten Zug erhält. Der Spieler mit dem ersten Zug gewinnt bei 4-gewinnt immer sofern er keinen Fehler macht.

    Man braucht nicht mehr Alpha-Beta, um die (sehr gute) Bewertungsfunktion auch noch sinnreich zu benutzen? Seltsam. Wie geht das?
    Seite 81:

    The evaluation function was not powerful enough to determine the game-theoretical value of
    the standard 7 x 6 board. After some search techniques were implemented, it became clear, that the
    search tree would become very large. Still it was possible, using 2 Sun-4 computers of the Vrije
    Universiteit of Amsterdam, to show that the initial position can be won by white.
    Mostly due to hardware problems and wrong choices of variations by the author more than 1000
    hours of CPU-time were used. The four winning variations described in chapter 13, together took
    about 350 hours of CPU-time

    0
  • ?

    Gut, ich bedanke mich schon mal für die vielen Antworten.
    Also kann ich davon ausgehen, dass eine perfekte KI so ohne weiteres nicht möglich ist...
    Vllt. rede ich dann doch mal mit meinem Lehrer und frag ihn, was er dazu sagt, wenn die KI dann doch nicht perfekt spielt (gegen die KI gewinnen konnten bis jetzt nur andere Programme).
    Aber das mit dem "Sockenschuss" lass ich glaub ich weg..... 😃
    Und zu dem was die Mädchen in unserem Kurs machen....
    Naja, was soll man da sagen. Ist doch klar, dass die Erwartungen da ein bisschen geringer sind. Ansonsten wären die beiden auch schon wech...

    Von den Killermoves habe ich auch schon etwas gelesen. Bei Vier Gewinnt scheinen diese aber nicht besonders hilfreich zu sein. Deswegen habe ich mich nicht weiter damit beschäftigt.

    SeppJ schrieb:

    ein kleiner Tipp: Frag deinen Lehrer, ob du das Spielfeld verkleinern kannst.

    Das wäre auch eine Möglichkeit, würde aber natürlich einige grundlegende Änderungen bedeuten. Dann hätte ich vllt. sogar eine perfekte KI...

    Eisflamme schrieb:

    Hi,

    AlphaBeta-Suche kenne ich nicht. Eine Hashmap bei so einem kleinen Spielfeld erscheint mir ziemlich uebertrieben.

    Naja, es werden ja vielmehr Stellungen mit ihren Bewertungen in der Hash-Tabelle abgelegt. Auf die kann man zugreifen, wenn man zu einem anderem Zeitpunkt wieder die gleiche Stellung erreicht. Daher sind die schon sinnvoll

    antialias schrieb:

    Da ich mich auch mal mit dem Thema beschäftigt habe (allerdings als Spieler) empfehle ich dir die Masterarbeit von Victor Allis:

    "A Knowledge-based Approach of Connect-Four - The Game is Solved: White Wins"
    http://www.connectfour.net/Files/connect4.pdf
    (Source code gibts an diversen Stellen im Netz.)

    Ohh, das scheint aber ziemlich hartes Zeug zu sein. Das lass ich mal lieber...

    Aber noch mal was anderes:
    Es gibt ja offensichtlich Programme, die perfekt spielen (mustrum, 4inarow...). Wie haben die das denn geschafft?
    Mustrum scheint ja eine Datenbank zu verwenden. Vllt. gibt es ja irgendwo im Internet eine, die ich auch verwenden kann. Da muss ich nochmal suchen...
    Oder vllt. weiß ja einer von euch wo man die findet....

    Nochmals Danke für die Antworten...

    0
  • A

    Man braucht nicht mehr Alpha-Beta, um die (sehr gute) Bewertungsfunktion auch noch sinnreich zu benutzen? Seltsam. Wie geht das?

    Kapitel 5-8 beschäftigen sich mit threats und welche davon wie vereitelt werden können (bzw. welche überhaupt keine threats sind und eigentlich völlig ignoriert werden können). Man muss sehr wenig 'suchen' um eine Siegstrategie zu erhalten. Menschliche 4-gewinnt Spieler gehen ja auch nicht durch den Suchraum sondern nutzen dieses Vorwissen (und den Zugzwang) um die Anzahl der zu untersuchenden Variationen zu minimieren.

    Kapitel 13 gibt einen Einblick in Anfangszüge/Situationen (von denen es erstaunlich wenige gibt bis es völlig trivial wird durch Zugzwang zu gewinnen)

    Es gibt implementationen unter Java die in Sekunden den bestmöglichen Zug liefern.

    Ich hab jetzt selbst noch kein 4-gewinnt Programm geschrieben, aber aus der hohlen Hand würde ich das über Threat-analyse und Zugzwang-vorwissen machen. Es ist dafür nicht nötig Züge im Voraus zu berechnen.

    0
  • V

    antialias schrieb:

    Man braucht nicht mehr Alpha-Beta, um die (sehr gute) Bewertungsfunktion auch noch sinnreich zu benutzen? Seltsam. Wie geht das?

    Kapitel 5-8 beschäftigen sich mit threats und welche davon wie vereitelt werden können (bzw. welche überhaupt keine threats sind und eigentlich völlig ignoriert werden können). Man muss sehr wenig 'suchen' um eine Siegstrategie zu erhalten. Menschliche 4-gewinnt Spieler gehen ja auch nicht durch den Suchraum sondern nutzen dieses Vorwissen (und den Zugzwang) um die Anzahl der zu untersuchenden Variationen zu minimieren.

    Kapitel 13 gibt einen Einblick in Anfangszüge/Situationen (von denen es erstaunlich wenige gibt bis es völlig trivial wird durch Zugzwang zu gewinnen)

    Es gibt implementationen unter Java die in Sekunden den bestmöglichen Zug liefern.

    Ich hab jetzt selbst noch kein 4-gewinnt Programm geschrieben, aber aus der hohlen Hand würde ich das über Threat-analyse und Zugzwang-vorwissen machen. Es ist dafür nicht nötig Züge im Voraus zu berechnen.

    Ich glaube trotzdem nicht, daß man Alpha-Beta-Pruning durch die gute aber nicht vollkommene Bewertungsfunktion komplett los wird.
    Selbst als Mensch wirst Du es nicht los. Du schaust Dir doch die Threads an. Und dann guckst Du, wo Du reinwerfen mußt oder nicht reinwerfen darfst. Oder genauer: Du guckst, wo der Stein landen würde und ob das eher gut oder eher schlecht ist. Und wenn zwei gleichwertige Züge möglich sind, schaust Du, was der Gegner drauf machen würde und wie Du antworten würdest.

    0
  • V

    ToniToni schrieb:

    Es gibt ja offensichtlich Programme, die perfekt spielen (mustrum, 4inarow...). Wie haben die das denn geschafft?

    http://www.ce.unipr.it/~gbe/velena.html
    schreibt, daß die Datenbank deswegen so "winzig" (nur 60000 Stellungen) sein kann, weil die Regeln von Allis so stark sind.

    0
  • V

    Auf http://homepages.cwi.nl/~tromp/c4.html unter
    Opening Game Tree ("Joseki")
    ist eine recht hübsche Eröffnungsbibliothek.
    Die würde ich vielleicht noch per Hand reinfummeln.

    0
  • A

    Stimmt..die Joseki-charts hatte ich ganz vergessen. Die sind gut und zeigen auch sehr hübsch welche Spiele 'langweilig' sind und welche interessant.

    Du schaust Dir doch die Threads an. Und dann guckst Du, wo Du reinwerfen mußt oder nicht reinwerfen darfst. Oder genauer: Du guckst, wo der Stein landen würde und ob das eher gut oder eher schlecht ist. Und wenn zwei gleichwertige Züge möglich sind, schaust Du, was der Gegner drauf machen würde und wie Du antworten würdest.

    Lustigerweise macht man das als Spieler nicht (zumindest nicht so wie im Schach, wo man sich Antworten auf gegnerische Züge überlegt und dann wieder Antworten darauf etc.). Bei 4-Gewinnt hast du als Spieler einfach einige Punkte im Kopf auf die du auf keinen Fall bei der derzeitigen Situation einen Stein schmeissen darfst (Aji). Daraus ergibt sich in den allermeisten Fällen genau einen Zug den du machen darfst (Atari) um weiterhin siegesgewiss zu sein (odr als schwarz genau einen Zug in dem du nicht vorzeitig verlierst).

    Kurz mal den Gedankengang den ein halbwegs fähiger Spieler durchmacht*: Dein Threat muss immer unterhalb des des Gegners sein (für Weiß in 'ungeraden' Positionen für Schwarz in 'geraden' Positionen). Threats auf den anderen Positionen aufzubauen ist für die Katz. Da du in jeder Situation sowieso nur (höchstens) 7 mögliche Züge hast beschränkt das deine Auswahl. Threats weiter oben zu bauen wenn es noch Möglichkeiten gibt für den Gegner gleichzeitig einen tieferen Threat aufzubauen ist ebenfalls sinnlos. Insofern fällt das ganze 'Fallen stellen' - wie beim Schach - weg. Sprich: du musst nie ein ganzes Spiel im Kopf durchspielen sondrn allerhöchstens bis zum Auffüllen deiner nächstmöglichen Threat-Ebene. Unbeteiligte Kolumnen können völlig vernachlässigt werden da sie höchstens tit-for-tat von beiden Spielern aufgefüllt werden um das unausweichliche zu verzögern.

    Die allermeisten Spiele unter fähigen Kontrahenten laufen auf 'auffüllen' hinaus (abwechselndes Werfen in eine unbeteiligten Kolumne bis diese voll ist um das Setzen in eine der oben genannten 'verbotenen' Positionen zu vermeiden). Durch Zwang zu gewinnen (also wenn es egal ist was der Kontrahent unter mehreren Möglichkeiten wirft) ist absolut unüblich und kommt nur vor wenn einer einen totalen Schnitzer macht. Nur wenn man so einen Zwang aufbauen kann ist es überhaupt nützlich Threats auf geraden (weiß) oder ungeraden (schwarz) Positionen aufzubauen. Aber wenn du das kannst dann hast du den anderen Spieler sowieso so derart im Griff dass du Kreise um ihn spielen kannst.

    In einem Spiel mit guten Kontrahenten zieht also weiß immer so, dass sein Threat (im langwierigsten Fall auf Reihe 6) am leben bleibt und schwarz muss dauernd so ziehen, dass weiß keinen Threat auf einer früheren Reihe aufbauen kann. Nur wenn einer einen groben (und meist leicht ersichtlichen) Fehler macht kann sich das ändern. Züge im voraus werden dazu nicht mental berechnet. Dass ist eher Pattern-matching.

    Es ist sogar meist nach wenigen Zügen klar in welche Position der Siegstein gespielt werden wird (ich kann bei vielen Spielen mit Neulingen nach 4-5 Zügen genau sagen wo ich gewinnen werden - selbst wenn der ab dann perfekt weiterspielt). Selbst bei Profis ist das meist recht früh klar. Ab da braucht man nicht weiter strategisch zu spielen. Das Auffüllen übernimmt den Rest (sprich: hier muss ein Programm auch nicht mehr irgend welche Entscheidungsbäume durchlaufen)

    *Ich würd mich jetzt mal frecherweise als 'halbwegs guter Spieler' bezeichnen - allerdings nicht als perfekt.

    0
  • M

    Ein normales Backtracking mit einer einfachen Bewertungsfunktion reicht aus für eine nahezu perfekte KI.
    Ich habe so etwas mal vor 17 Jahren gemacht und die Rechenzeiten waren kein Problem. Eine Rechentiefe von 5 Zügen war ausreichend. Höhere Rechentiefen brachten keine besseren Ergebnisse, sondern nur höhere Rechenzeiten.

    0
  • E

    Gut. OP stellt seine CPU fertig, dann packst Du deine vom Dachboden und einer von euch postet dann den Termin, wo wir uns das alles Life über irgendein public desktop sharing anschauen können.

    *holt das Popcorn raus* 😋

    0
  • ?

    MichelRT schrieb:

    Ein normales Backtracking mit einer einfachen Bewertungsfunktion reicht aus für eine nahezu perfekte KI.
    Ich habe so etwas mal vor 17 Jahren gemacht und die Rechenzeiten waren kein Problem. Eine Rechentiefe von 5 Zügen war ausreichend. Höhere Rechentiefen brachten keine besseren Ergebnisse, sondern nur höhere Rechenzeiten.

    Um einen durchschnittlichen menschlichen Spieler wie mich zu schlagen reichen mit Sicherheit 5 oder 6 Züge Rechentiefe. Aber ein "halbwegs guter Spieler" wie antialias würde so ein Programm in der Luft zerreißen, es sei denn das Programm hätte sonst noch irgendwelche intelligenten Algorithmen drin....

    Naja, ich habe auf der Seite mustrum.de eine Eröffnungsdatenbank mit bis zu 12 Steinen gefunden und heruntergeladen. Jetzt muss ich erstmal versuchen die zu komprimieren und dann mein Programm zu erweitern. Wenn ich das noch schaffe, dann würde das Programm zumindest für die ersten 12 Züge perfekt spielen. Ich hoffe mal, dass das Durchsuchen der Datenbank nicht zu lange dauert, weil da sind schon einige Stellungen drin.

    Vllt. traue ich mich dann noch an die BitBoards dran, aber das wird vermutilich extrem aufwendig...

    0
  • K

    Das kommt sicherlich auch auf die Bewertungsfunktion an. Wie gesagt, meine alte Vier-Gewinnt-KI war (glaub'ich) relativ stark mit Suchtiefe 7. Die Bewertungsfunktion war simpel aber effektiv. Für jeden eigenen Stein und für jede Orientierung (waagerecht, senkrecht, diagonal, ...), gab es einen Punkt, falls der Stein in dieser Orientierung noch zu einem 4er ausbaufähig war.

    Beispiel:

    [ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][X][ ][ ][ ]

    X: 4 Punkte

    Beispiel 2:

    [ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][O][ ][ ][ ]
[ ][ ][ ][X][ ][ ][ ]

    X: 3 Punkte
    O: 4 Punkte

    Beispiel 3:

    [ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][O][ ][ ][ ]
[ ][ ][X][X][ ][ ][ ]

    X: 3+2 Punkte (3 vom ersten und 2 vom zweiten 😵
    O: 4 Punkte

    Beispiel 4:

    [ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][X][ ][ ][ ]
[ ][ ][ ][O][ ][ ][ ]
[ ][ ][ ][X][ ][ ][ ]

    X: 3+4 Punkte (3 vom ersten und 4 vom zweiten 😵
    O: 3 Punkte

    u.s.w.
    Der Wert, den die Bewertungsfunktion zurück gibt, ist die Differenz der Punktzahlen oder INT_MAX bzw INT_MIN falls eine der beiden Parteien gewonnen hat.

    Zumindest habe ich nie gewonnen, wenn die KI angefangen hat. Dabei habe ich u.a. auch "gemogelt" (mich von anderen 4-Gewinnt-KIs beraten lassen).

    kk

    0
  • U

    ich würde bei der bewertung z.bsp. das erste x höher bewerten.
    es ist nicht nur rechts oben, links oben und oben und in der waagerechten möglich, sondern es ist einmal nach rechts und einmal nach links möglich.

    ich denke aber auch, dass man nicht mehr braucht, um eine perfekte ki zu bauen.
    dann gibt man dem 4. stein in einer reihe noch eine wertigkeit von <großer wert> und schon hat man auch ne abbruch-bedingung 😉

    bb

    0
  • A

    Um einen durchschnittlichen menschlichen Spieler wie mich zu schlagen reichen mit Sicherheit 5 oder 6 Züge Rechentiefe.

    Wie gesagt: 4-gewinnt ist nicht Schach. Rechentiefe bedeutet bei 4-Gewinnt überhaupt nichts.

    Die Mentalität der beiden Spiele ist vollständig anders:
    Schach: Beide Spieler versuchen zu gewinnen und eine Situation herzustellen, die für den anderen unentrinnbar zur Niederlage führt. Beide verfolgen dazu eigene Strategien die nur zum Teil vom Gegenüber mitbestimmt werden. Insbesondere ist die Entwicklung der ersten Züge nur sehr lose aneinander gekoppelt.

    4-gewinnt:
    Eques (X, weiß) hat bereits vor dem ersten Zug gewonnen.
    Knotts (O, schwarz) hat bereits vor dem ersten Zug verloren.

    Es geht für Eques nicht darum eine Gewinnstrategie zu finden. Es geht nicht darum eine Situation herzustellen die Schwarz keine Wahl lässt. Diese Situation besteht bereits bevor das Spiel überhaupt begonnen hat. Es geht für Eques lediglich darum den sicheren Sieg nicht zu verspielen. Dazu ist es lediglich erforderlich ein paar (wenige) Konfigurationen zu vermeiden.

    Für Knotts gibt es keine Strategie ausser auf einen Fehler von Eques zu warten.
    Er kann Eques zu garnichts zwingen so lange dieser keinen Fehler begeht - egal wie 'clever' er spielt. Der erste Fehler führt dabei (wahrscheinlich) noch nichtmal zu einem Sieg von Knotts sondern zu einem Remis.

    Daher ist das suchen in Zustandsbäumen nach Gewinn-/Verlust-Situationen nach 4,6,n-Schritten (IMO) nicht der richtige Ansatz.

    0
  • A

    Das kommt sicherlich auch auf die Bewertungsfunktion an. Wie gesagt, meine alte Vier-Gewinnt-KI war (glaub'ich) relativ stark mit Suchtiefe 7. Die Bewertungsfunktion war simpel aber effektiv. Für jeden eigenen Stein und für jede Orientierung (waagerecht, senkrecht, diagonal, ...), gab es einen Punkt, falls der Stein in dieser Orientierung noch zu einem 4er ausbaufähig war.

    Ich spiel das mal durch (Aus Übersicht sind nur die untersten 4 reihen angegeben):

    X sei dein Programm
    O bin ich

    [ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][X][ ][ ][ ]

    [ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][O][ ][ ][ ]
[ ][ ][ ][X][ ][ ][ ]

    [ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][X][ ][ ][ ]
[ ][ ][ ][O][ ][ ][ ]
[ ][ ][ ][X][ ][ ][ ]

    [ ][ ][ ][ ][ ][ ][ ]
[ ][ ][ ][X][ ][ ][ ]
[ ][ ][ ][O][ ][ ][ ]
[ ][ ][ ][X][O][ ][ ]

    Wenn ich das jetzt richtig verstanden habe würde dein Programm jetzt das spielen:

    [ ][ ][ ][X][ ][ ][ ]
[ ][ ][ ][X][ ][ ][ ]
[ ][ ][ ][O][ ][ ][ ]
[ ][ ][ ][X][O][ ][ ]

    damit wäre mein nächster Zug das:

    [ ][ ][ ][X][ ][ ][ ]
[ ][ ][ ][X][ ][ ][ ]
[ ][ ][ ][O][O][ ][ ]
[ ][ ][ ][X][O][ ][ ]

    und damit das Spiel effektiv zu meinen Gunsten beendet (Sieg nach auffüllen durch in der zweiten Reihe). Das kann von X nicht mehr unterboten werden da ein Sieg in Reihe 1 von mir auf alle Fälle blockierbar ist. Ansonsten muss ich einfach immer nur einen Stein dahin setzten wo dein Programm einen hinsetzt.

    0
  • U

    verstehst du falsch - der alg. würde das testen - aber dann im nächsten zug merken, dass der ast ne schlechtere bewertung hat, als ein anderer

    0
  • A

    Warum hat der ne schlechte Bewertung? Der Sieg käm ja erst nach weiteren 35 Zügen (bei optimalem Spiel).

    0
  • U

    hmm.. ich denk trotzdem, dass es einen besseren zug gibt - hatte aber keine lust, alles durchzurechnen.
    wie man rel. einfach abhilfe schaffen könnte:
    die länge der reihe als exponent nehmen(nat. nur, wenn man mit dieser Reihe gewinnen könnte).

    ich glaube so gar, dass das allg. nicht gerade doof wäre.

    vll hab ich ja dann mal genug lange weile...

    bb

    0
  • K

    antialias schrieb:

    Ich spiel das mal durch (Aus Übersicht sind nur die untersten 4 reihen angegeben):

    X sei dein Programm
    O bin ich
    ...

    Ich kann Deine Züge nicht ohne weiteres nachvollziehen. Es ist aber schon klar, dass die Bewertungsfunktion für einen Spieler noch mit "Quasi-Unendlich" für einen Sieg zu erweitern und die Differenz der Punktzahlen beider Spieler in Verbindung mit Suchalgorithmen wie MiniMax oder AlphaBeta zu verwenden ist, ja?

    kk

    0
Anmelden zum Antworten