Bevor die KI zieht, muss sie ihren Zug in einem Heuhaufen aus hundertfünfzigtausend Wörtern finden und dann aufhören zu suchen.
Auf Englisch verfasst und redigiert. Diese deutsche Fassung wurde maschinell übersetzt; wo es auf Genauigkeit ankommt, ist das englische Original maßgeblich. Das englische Original lesen →
Geben Sie einer Person einen vollständigen Satz WordChess-Kacheln und die Anweisung „spiele ein gutes Wort“, und sie grenzt das Problem ein, ohne zu bemerken, dass sie es tut. Der Computer genießt keine solche Intuition. Auf einem 25×25-Brett, mit einem eigenen vollständigen Satz aus hundert Kacheln, kann er fast jedes der 148.941 Wörterbuchwörter versuchen, und jedes Wort kann an tausenden legalen Koordinaten und in verschiedenen Ausrichtungen abgelegt werden. Schlimmer noch: Eine Platzierung ist nur legal, wenn jeder neue Buchstabe, den sie einführt, auch dort, wo er das bereits auf dem Brett Liegende kreuzt, ein echtes Wort vervollständigt. Multiplizieren Sie die Wörter mit den Platzierungen und mit dieser Kreuzungsbedingung, und Sie haben einen Suchraum, den kein Spieler, ob aus Silizium oder nicht, vollständig auflisten und bewerten kann.
Das ist der Grund, warum ernsthafte Wortspiel-Engines, darunter Quackle, die Open-Source-Referenzimplementierung, das Wörterbuch nie per Brute-Force durchsuchen. 4 Steven Gordons GADDAG-Struktur von 1994 und die DAWG davor ermöglichen es einem Programm, Wörter von bereits auf dem Brett liegenden Kacheln aus nach außen zu wachsen und die Kreuzungen dabei zu prüfen, sodass illegale Äste früh sterben, anstatt bewertet und verworfen zu werden. 1 Die Aufgabe lautet nicht „liste jedes Wort auf". Sie lautet „erzeuge nur die Züge, die möglicherweise legal sein könnten, und tue es schnell".
Selbst ein schlanker Generator liefert mehr Kandidatenzüge, als sich gründlich bewerten lassen, daher ist das zweite Problem die Zeit. Brian Sheppards Maven, das erste Programm, das menschliche Spitzengegner überspielte, stand genau vor diesem Problem und löste es in zwei Stufen: Eine schnelle Heuristik sortiert die rohen Züge grob nach Qualität, und nur eine engere Auswahl der vielversprechendsten wird sorgfältig untersucht, indem das Spiel viele Male vorwärts simuliert wird, um zu sehen, welcher Kandidat tatsächlich am besten abschneidet. 2 Andere Spiele kennen dieselbe Idee unter anderen Namen, als Rollout im Backgammon und als Playout in Go-Programmen; bei Maven heißt sie Simulation.
WordChess arbeitet im selben Geist unter einer strengerer Einschränkung: ein festes Suchzeit-Budget pro Zug. Wenn das Budget aufgebraucht ist, verpflichtet sich die KI zum besten Wort, das sie bisher gefunden hat. Das ist kein Kompromiss, den die Ingenieure bedauern; es ist das gesamte Design. Ein Spieler, der für immer nachdenkt, ist kein besserer Gegner, nur ein langsamerer. Die Uhr zwingt die Maschine, das zu tun, was Menschen instinktiv tun: sich für einen Zug entscheiden, der offensichtlich gut ist, anstatt einen, der nachweislich der beste ist.
Das Wörterbuch zu kennen ist der leichte Teil. Zu wissen, wann man aufhört, es zu durchsuchen, ist der schwere.
Der faule Weg, eine Spiel-KI leichter zu machen, besteht darin, sie zufällig dumm zu machen, sie einen Zug verpatzen zu lassen, den sie offensichtlich gesehen hat. Spieler bemerken das, und sie nehmen es übel. Der Designer Sid Meier wird oft dafür angeführt, dass er Bündnisfunktionen aus Civilization strich, weil der Computer sie fast so gut ausnutzen konnte wie ein Spieler; die Wirkung würde, in Meiers Worten, wie eine Abhandlung über das Design von KI-Gegnern sie zitiert, „Gamern das Gefühl geben, sie könnten nicht gewinnen, weil der Computer schummelt“. 3 Schwierigkeit, die sich wie Unehrlichkeit anfühlt, vergiftet das Spiel, weshalb sich die Forschungsliteratur zur dynamischen Schwierigkeitsanpassung damit befasst, abzustimmen, wozu die KI fähig ist, und nicht, was sie sehen darf. 5
WordChess justiert seine vier Stufen entlang von Achsen, die ein Mensch erkennen würde, niemals dadurch, dass die KI verborgene Informationen erhält. Die Stufen unterscheiden sich darin, wie lange sie suchen dürfen, wie tief ihr Vokabular in das seltene Wörterbuch reicht und welche Wortlängenbereiche sie bevorzugen. Ein leichter Gegner spielt plausibel schwache Wörter, echte, sinnvolle, kurze, keinen Müll. Ein Großmeister teilt das ganze obskure Lexikon mit der schweren Stufe und hat die meiste Zeit, es auszuschöpfen. Der Spieler verliert gegen etwas, das wie ein größerer Wortschatz und schärferes Lesen aussieht, denn genau das ist es.
| Stufe | Reichweite des Vokabulars | Suchbudget | Tendenz zur Wortlänge |
|---|---|---|---|
| Einfach | Nur häufige Wörter | Am kürzesten | Kurz |
| Normal | Häufige + mittlere + halbe seltene Wörter | Kurz | Gemischt |
| Schwer | Vollständig | Lang | Länger |
| Großmeister | Vollständig | Am längsten | Unbegrenzt |
Ein Taschenrechner liefert jedes Mal dieselbe Antwort; ein Gegner überrascht Sie. WordChess fügt der Auswahl einen bewussten Zufallsschritt hinzu, sodass nahezu gleichwertige Züge nicht immer auf dieselbe Weise entschieden werden und die KI nicht jedes Mal dasselbe Wort erneut spielt. In Kombination mit Wortschatzobergrenzen pro Stufe erzeugt dies Abwechslung, das Gefühl, dass jemand auf der anderen Seite des Bretts sitzt und Entscheidungen trifft, von denen Sie einige auch hätten treffen können.
Das ist die stille Kunst dahinter. Ein glaubwürdiger Gegner braucht Zurückhaltung ebenso sehr wie Stärke: die Bereitschaft, ein bloß gutes Wort zu spielen, Punkte auf dem Tisch zu lassen und auf eine Weise schlagbar zu sein, die sich als verdient anfühlt. Das schwierigste ingenieurtechnische Problem der Maschine war die Suche im Heuhaufen. Das subtilste war zu lernen, wann man aufhören muss zu suchen, was man wissen soll und wie viel man zurückhalten muss.