State Machines – von Werwölfen und KI-Agenten

Ob Ampelschaltungen, Web-Frontends oder LLM-Agenten: Viele Software-Systeme lassen sich als State Machine modellieren. State Machines (deutsch: endliche Automaten) sind ein vielseitiges Entwurfsmuster, das Systeme nicht als Schritt-für-Schritt-Abfolge von Anweisungen betrachtet, sondern deklarativ durch Zustände und Zustandsübergänge beschreibt. Das zeigt explizit das Verhalten eines Systems unter verschiedenen Bedingungen. Wie bei vielen Entwurfsmustern ist ein Verständnis von State Machines auch dann von Vorteil, wenn ein System nicht explizit als State Machine implementiert ist. Das Betrachten von Systemen als State Machine erleichtert die Identifikation klar abgegrenzter Zustände und Reaktionsmöglichkeiten sowie die Kommunikation mit nicht-technischen Stakeholdern.

Kilian Kluge

Kilian Kluge entwickelt als Co-Gründer von Inlinity Prozesse, Software und Infrastruktur für vertrauenswürdige KI-Systeme. Zuvor war er als IT-Berater und Entwickler tätig und hat an der Universität Ulm zu nutzerzentrierter KI promoviert.

Philipp Schröppel

Philipp Schröppel arbeitet als Machine Learning Engineer und Projektleiter bei Inlinity daran, Erklärbare KI aus der Forschung in die Praxis zu bringen. Neben seiner Tätigkeit bei Inlinity forscht er als Doktorand an der Uni Ulm zu interpretierbarem Machine Learning und Mensch-KI-Interaktion.

Eine besondere Stärke entfalten State Machines bei komplexen Systemen, die aus mehreren unabhängig und nebenläufig ausgeführten Teilsystemen bestehen. Hier kann zur Modellierung das Aktorenmodell dienen, in dem jedes als State Machine betrachtete Teilsystem als unabhängiger Aktor den eigenen Zustand verwaltet und nur durch Austausch von Nachrichten mit anderen Aktoren interagiert. Die Open-Source-JavaScript-Bibliothek XState macht diese Kombination von State Machines und Aktorenmodell auf einfache Weise zugänglich. Ursprünglich mit Fokus auf Web-Frontends entwickelt, eignet sie sich auch für Backend-Anwendungen sowie die Implementierung von KI-Agenten, bei denen Large Language Models (LLMs) die Steuerung von Systemen übernehmen.

Dieser Artikel führt in die Grundlagen von State Machines und Aktorenmodell ein und zeigt Entwicklerinnen und Entwicklern die vielfältigen Einsatzmöglichkeiten auf.

Lesen Sie auch

Praxis Softwarearchitektur – das neue Sonderheft von iX Developer ist erschienen

Einführung in State Machines

Eine State Machine beschreibt ein System als eine Menge von Zuständen (States), zwischen denen Übergänge (Transitions) möglich sind, die durch Ereignisse (Events) ausgelöst werden. State Machines können durch Aktionen (Actions) mit ihrer Umwelt interagieren. Welche Aktion wann ausgeführt wird, hängt dabei vom Zustand und dem empfangenen Event ab. Ein anschauliches Beispiel für State Machines sind Login-Flows: Zu Beginn ist der Zustand "ausgeloggt". Nach der Eingabe der Zugangsdaten löst ein Klick auf den Button "Login" das Ereignis "Authentifizierung" aus. Im Erfolgsfall geht das System in den Zustand "eingeloggt" über, ansonsten erfolgt die Rückkehr in den Zustand "ausgeloggt". Dieser Vorgang lässt sich imperativ als Abfolge von Schritten beschreiben. Was in dem skizzierten einfachen Fall noch gelingt, führt bei komplexeren Abläufen häufig zu unübersichtlichen und verschachtelten Verzweigungen im Code. Spätestens, wenn es notwendig ist, nebenläufige Prozesse zu synchronisieren – beispielsweise Versand und Prüfung eines zweiten Authentifizierungsfaktors – steigen Aufwand und Anfälligkeit für Fehler.

Darstellung von State Machines mit Zustandsübergangsdiagrammen

Als Beispiel für die Anwendung von State Machines als Entwurfsmuster dient in diesem Artikel das Gesellschaftsspiel "Die Werwölfe von Düsterwald". Bei diesem Rollenspiel, das eine Gruppe von mindestens acht Personen spielt, interagieren die Spieler abhängig von Spielphase und Rolle miteinander. Parallele Handlungen und verdeckte Kommunikation sind dabei zentraler Bestandteil. In seiner einfachsten Form kennt das Werwolf-Spiel zwei Rollen: Dorfbewohner und Werwölfe. Die Werwölfe gewinnen das Spiel, wenn sie es schaffen, alle Dorfbewohner zu fressen, und die Dorfbewohner gehen als Sieger hervor, wenn sie alle Werwölfe töten. Ein Spielleiter oder eine Spielleiterin moderiert den Ablauf, führt Abstimmungen durch und setzt deren Ergebnisse um.

Das Zustandsübergangsdiagramm (State Chart) in Abbildung 1 visualisiert die Zustände und mögliche Übergänge im Werwolf-Spiel. Zustandsübergangsdiagramme stellen die Logik von State Machines übersichtlich und ohne technische Implementierungsdetails dar. Sie bilden damit ein effektives Kommunikationstool bei der Abstimmung zwischen Entwicklungsteams und nicht-technischen Stakeholdern.

Ein Werwolf-Spiel beginnt im Zustand "Vorbereitung", in dem jeder Spieler zufällig und verdeckt eine der beiden Rollen Werwolf oder Dorfbewohner erhält. Auf die Vorbereitung folgt die erste Nacht. (Es gibt also nur einen möglichen Zustandsübergang.) Beim Eintreten des Zustands "Nacht" schließen zunächst alle Spielerinnen und Spieler ihre Augen, anschließend öffnen auf Anweisung des Spielleiters nur die Werwölfe die Augen. Sie stimmen durch Zeichen (schweigend und möglichst ohne Geräusche) ab, welchen Dorfbewohner sie umbringen möchten und schließen nach der Entscheidung wieder ihre Augen.

Aus dem Zustand "Nacht" gibt es zwei mögliche Übergänge. Wenn noch Dorfbewohner am Leben sind, geht das Spiel in den Zustand "Tag" über. Haben die Werwölfe mit ihrer Entscheidung jedoch den letzten verbleibenden Dorfbewohner gefressen, haben sie gewonnen und das Spiel geht in den Zustand "Werwölfe gewinnen" über. Im Zustand "Tag" öffnen zunächst alle Spieler ihre Augen und der Spielleiter oder die Spielleiterin verkündet, wer in der Nacht umgebracht wurde. Dieser Spieler scheidet aus und verlässt die Spielrunde. Alle verbleibenden Spieler diskutieren und bestimmen schließlich durch Abstimmung, wen sie als Werwolf verdächtigen. Der gewählte Spieler scheidet aus und offenbart den verbleibenden Spielern seine Rolle. Vom Zustand "Tag" gibt es drei mögliche erreichbare Zustände. Wenn nach dem Ausscheiden des gewählten Spielers alle Werwölfe tot sind, endet das Spiel im Zustand "Dorfbewohner gewinnen". Ist der ausgeschiedene Spieler der letzte verbleibende Dorfbewohner, geht das Spiel in den Zustand "Werwölfe gewinnen" über. In allen anderen Fällen wechselt das Spiel zurück in den Zustand "Nacht". Die Zustände "Werwölfe gewinnen" und "Dorfbewohner gewinnen" signalisieren das Spielende und sind finale Zustände, von denen keine weiteren erreichbar sind.

Implementierung einer State Machine mit XState

XState ist eine JavaScript-Bibliothek, die es ermöglicht, zustandsbasierte Logik explizit als State Machines zu definieren und zu verwalten. Mit XState implementierte State Machines lassen sich in gängige Web-Frontend-Frameworks integrieren oder mit Node.js im Backend ausführen. Hinter dem Open-Source-Projekt steht mittlerweile das Unternehmen Stately, das den visuellen Editor "Stately Studio" zum Erstellen und Verwalten von State Machines anbietet. Darin lassen sich State Machines grafisch darstellen und interaktiv anpassen. Anschließend ist es möglich, den zugehörigen Quellcode zu generieren und zu exportieren. Das Verwenden des Editors erfordert keine Programmierkenntnisse und ermöglicht auch Mitarbeiterinnen und Mitarbeitern ohne Programmierkenntnisse, Prozesse und Logik zu beschreiben und nachzuvollziehen.

Der im vorherigen Abschnitt beschriebene Spielablauf lässt sich in XState wie in Listing 1 gezeigt implementieren. Wie in dem Diagramm in Abbildung 1 zu sehen, bilden dabei die möglichen Zustände (states) die oberste Ebene. Übergänge erfolgen entweder zwingend (always) oder aufgrund eines Ereignisses (on). Zudem kann man die Auswahl des nächsten Zustands (target) von der Erfüllung eines Kriteriums abhängig machen (guard). Die State Machine beginnt stets im Zustand "Start" (initial) und endet, sobald ein finaler Zustand (final) erreicht ist. Jede State Machine besitzt einen Kontext, in dem beliebige Informationen gespeichert werden können (context).

export const gameMachine = setup({}).createMachine({
  initial: "Start",
  states: {
    Start: {
	always: {target: "Night"}
    },
    Day: {
      on: {
        votesCollected: [
          { guard: 'allVillagersDead', target: 'WerewolvesWin' },
          { guard: 'allWerewolvesDead', target: 'VillagersWin' },
          { target: 'Night' }
        ]
      ]}},
    Night: {
      on: {
        votesCollected: [
          { guard: 'allVillagersDead', target: 'WerewolvesWin' },
          { target: 'Day' }
        ]
      }
    },
    VillagersWin: {
			type: "final"
		},
    WerewolvesWin: {
			type: "final"
		},
  },
  context: {},
});

Listing 1: Implementierung des in Abbildung 1 dargestellten Zustandsübergangsdiagramms in XState.