Bevor die KI ihren Zug spielt, muss sie ihren Zug in einem Heuhaufen aus hundertfünfzigtausend Wörtern finden und dann aufhören zu suchen.
Geben Sie einer Person ein WordChess-Fach und die Anweisung „spiele ein gutes Wort“, und sie verkleinert das Problem, ohne zu bemerken, dass sie es tut. Der Computer genießt keine solche Intuition. Auf einem 25×25 Brett, mit Zugang zum vollen Pool aus hundert Kacheln, kann er fast jedes der 148,941 Wörter des Wörterbuchs versuchen, und jedes Wort kann an tausenden legalen Koordinaten und Ausrichtungen abgelegt werden. Schlimmer noch, eine Platzierung ist nur legal, wenn jeder neue Buchstabe, den es einführt, auch dort, wo er mit dem bereits auf dem Brett befindlichen überlappt, ein echtes Wort vervollständigt. Multiplizieren Sie die Wörter mit den Platzierungen und dieser Kreuzungsbeschränkung, und Sie haben einen Suchraum, den kein Spieler, ob aus Silizium oder nicht, vollständig auflisten und bewerten kann.
Dies ist der Grund, warum ernsthafte Wortspiel-Engines, Quackle, die Open-Source-Referenzimplementierung, darunter, niemals das Wörterbuch per Brute-Force durchsuchen.4 Steven Gordons 1994 GADDAG Struktur und die DAWG davor, lasse ein Programm Wörter von bereits auf dem Brett liegenden Kacheln nach außen wachsen und prüfe dabei die Kreuzungen, damit illegale Verzweigungen frühzeitig absterben, anstatt bewertet und verworfen zu werden.1 Die Aufgabe lautet nicht „jedes Wort auflisten“. Sie lautet „nur die Züge generieren, die möglicherweise legal sein könnten, und das schnell“.
Selbst ein schlanker Generator liefert mehr Kandidatenzüge, als tief bewertet werden können, daher ist das zweite Problem die Zeit. Das stärkste je gebaute Scrabble-Programm, Brian Sheppards Maven, stand genau vor diesem Problem und löste es in zwei Stufen: Eine schnelle Heuristik sortiert die rohen Züge in eine grobe Qualitätsreihenfolge, und nur eine kurze Liste der vielversprechendsten Kandidaten wird sorgfältig untersucht, indem das Spiel viele Male nach vorne simuliert wird, um zu sehen, welcher Kandidat tatsächlich am besten abschneidet.2 Sheppard übernahm den Namen der Idee aus anderen Spielen, was Backgammon als Rollout bezeichnet und Go als Play-out, nannte er Simulation.
WordChess arbeitet im gleichen Geist, aber unter einer strengerer Bedingung: ein festes Zeitbudget pro Zug. Wenn das Budget aufgebraucht ist, verpflichtet sich die KI auf das beste Wort, das sie bisher gefunden hat. Dies ist kein Kompromiss, den die Entwickler bedauern; es ist das gesamte Design. Ein Spieler, der ewig 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 zu entscheiden, der offensichtlich gut ist, anstatt einen, der nachweislich der beste ist.
Das Wörterbuch ist nicht der Geist des Gegners. Die Uhr ist es.
Der faule Weg, die KI eines Spiels leichter zu machen, besteht darin, sie zufällig dumm zu machen, sie einen Zug fummeln zu lassen, den sie offensichtlich gesehen hat. Spieler bemerken das und empfinden es als ärgerlich. Der Designer Sid Meier wird oft zitiert, weil er Civilization -Funktionen entfernt hat, die es dem Computer ermöglichten, Spieler im Verhandeln zu übertreffen, da der Effekt, wie eine Abhandlung über das Design von KI-Gegnern es ausdrückt, „bei Gamern das Gefühl hinterlassen würde, sie könnten nicht gewinnen, weil der Computer schummelt.“3 Schwierigkeit, die als Unehrlichkeit wahrgenommen wird, vergiftet das Spiel, weshalb sich die Forschungsliteratur zur dynamischen Schwierigkeitsanpassung damit befasst, was die KI fähig ist, zu tun, anstatt, was sie sehen darf.5
WordChess justiert seine vier Stufen entlang von Achsen, die ein Mensch erkennen würde, niemals, indem der KI verborgene Informationen zugeführt werden. Jede Stufe unterscheidet sich darin, wie lange sie suchen darf, wie tief in das seltene Wörterbuch ihr Vokabular reicht und welche Wortlängenbänder sie bevorzugt. Ein leicht Gegner spielt plausibel schwache Wörter, echte, sinnvolle, kurze, kein Müll. Ein Großmeister hat das gesamte obskure Lexikon und die Zeit, es zu durchforsten. Der Spieler verliert gegen etwas, das wie ein besserer Wortschatz und schärferes Lesen aussieht, denn genau das ist es auch.
| Stufe | Reichweite des Wortschatzes | Suchbudget | Tendenz zur Wortlänge |
|---|---|---|---|
| Leicht | Nur gebräuchlich | Kürzeste | Kurz |
| Normal | Gebräuchlich + mittel | Kurz | Gemischt |
| Schwer | Breit | Lang | Länger |
| Großmeister | Vollständig selten | Längste | Unbegrenzt |
Ein Rechenwerk liefert jedes Mal dieselbe Antwort; ein Gegner überrascht Sie. WordChess fügt der Auswahl einen bewussten, zufallsbasierten Anti-Kopier-Schritt hinzu, sodass nahezu gleichwertige Züge nicht immer auf dieselbe Weise aufgelöst werden und die KI nicht einfach Ihren letzten Zug spiegelt. In Kombination mit wortschatzbezogenen Obergrenzen pro Stufe erzeugt dies Abwechslung, das Gefühl, dass jemand gegenüber am Brett sitzt und Entscheidungen trifft, von denen einige auch Sie hätten treffen können.
Das ist die stille Kunst dahinter. Ein glaubwürdiger Gegner braucht Zurückhaltung ebenso wie Stärke: die Bereitschaft, ein bloß gutes Wort zu spielen, Punkte liegen zu lassen und auf eine Weise schlagbar zu sein, die sich als verdient anfühlt. Das schwierigste ingenieurtechnische Problem der Maschine war das Durchsuchen des Heuhaufens. Das subtilste war zu lernen, wann man aufhört zu suchen, was man wissen soll und wie viel man zurückhalten muss.