3. Perfekte KI für Vier Gewinnt

Perfekte KI für Vier Gewinnt

  • 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