3. Perfekte KI für Vier Gewinnt

Perfekte KI für Vier Gewinnt

  • 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