Verbinde vier KI – spiele gegen eine Minimax-Engine

Diese Connect Four-KI ist ein echter suchbasierter Gegner, kein geskripteter oder zufälliger Bot. Wählen Sie, ob Sie als Roter oder Gelber spielen möchten (Rot wird immer geöffnet, wie beim standardmäßigen „Vier verbinden“), wählen Sie einen Schwierigkeitsgrad und beginnen Sie mit dem Abwerfen von Scheiben, indem Sie auf eine Spalte oder den Pfeil darüber klicken. Die Scheibe wird bis zu ihrer Landereihe animiert, vier in einer Reihe werden sofort in jeder Richtung erkannt – horizontal, vertikal und in beiden Diagonalen – und eine kurze Statuszeile zeigt Ihnen immer an, wer an der Reihe ist oder gibt den Gewinner bekannt.

Die Engine hinter der KI ist eine Negamax-Suche mit Alpha-Beta-Pruning, derselben Algorithmenfamilie, die auch von klassischen Brettspiel-Engines verwendet wird: Sie untersucht den Baum möglicher zukünftiger Züge, lässt jede Seite versuchen, ihr eigenes Ergebnis zu maximieren, während sie davon ausgeht, dass der Gegner ebenfalls gut spielt, und schneidet Zweige weg, die das Ergebnis nicht ändern können, sobald bereits eine bessere Linie gefunden wurde. Da Connect Four nur sieben Spalten zur Auswahl hat, kann diese Suche schnell mehrere Schritte vorausschauen. Es läuft mit iterativer Vertiefung – durchsuchen einer Schicht, dann zwei, dann drei usw. – innerhalb eines kurzen Zeitbudgets pro Zug (ungefähr eine Viertelsekunde auf „Einfach“ bis zu etwa anderthalb Sekunden auf „Schwer“), sodass der Browser beim Warten auf einen Zug nie einfriert.

Wenn die Suche das Ende des Spiels innerhalb seiner Tiefe nicht erreichen kann, werden Züge durch eine echte Positionsbewertungsheuristik statt durch eine Vermutung beurteilt: Jedes mögliche Vier-in-einer-Reihe-Fenster auf dem Brett wird basierend darauf bewertet, wie viele von jeder Farbe es bereits belegen (ein leeres Fenster ist nichts wert, ein Fenster, in dem nur Ihre Scheiben mehr wert sind, wenn es sich füllt, ein Fenster, das von beiden Farben blockiert wird, ist nichts wert) und Zellen in den mittleren Spalten zählen mehr, weil sie an mehr möglichen Linien teilnehmen. „Einfach“ und „Mittel“ fügen ein wenig kontrollierte Zufälligkeit zwischen Bewegungen hinzu, die nahezu die gleiche Punktzahl erzielen, sodass sich die KI menschlicher und schlagbarer anfühlt. Hard spielt immer seinen stärksten gefundenen Zug. Dies ist ein wirklich starker Minimax-Gegner, der auf echter Suche und Bewertung basiert – kein Anspruch auf unschlagbares oder perfektes Spiel und keine Simulation von irgendetwas: Jeder Zug ist die tatsächliche Ausgabe des oben genannten Algorithmus.