Im Spiel: der Gegner entscheidet sich
Optional. Diese Seite ist ein Zusatzangebot am Ende des Kapitels. Sie führt nichts Neues ein, und weder der Rückblick noch die späteren Kapitel setzen sie voraus.
Auf der Seite Beispiel: Entscheidungsbaum hast du einen Entscheidungsbaum als Bild gesehen. Hier wird er zu einer Datenstruktur, die ein Gegner sechzigmal pro Sekunde durchläuft.
Scratch for Java in fünf Minuten
Diese Seite macht einen Entwurf mit der Grafikbibliothek Scratch for Java sichtbar. Du musst sie nicht kennen – hier steht alles, was du dafür brauchst. Geladen wird sie über libraries="scratch"; import-Zeilen gibt es nicht.
| Begriff | Was er bedeutet |
|---|---|
Stage |
die Bühne, 480 × 360 Pixel. Der Punkt (0, 0) liegt in der Mitte, die y-Achse zeigt nach oben. Man schreibt eine eigene Klasse, die von Stage erbt. |
Sprite |
eine Figur auf der Bühne. Auch dafür schreibt man eigene Klassen, die von Sprite erben. |
addCostume("coin_gold") |
gibt einer Figur ihr Bild. Die Bibliothek bringt über 1700 fertige Kostüme mit. |
this.add(objekt) |
fügt eine Figur oder einen Text der Bühne hinzu. Was nicht hinzugefügt wurde, sieht man nicht. |
run() |
wird für jedes Objekt etwa 60-mal pro Sekunde aufgerufen. Alles Fortlaufende steht hier drin. |
getTouchingSprite(Muenze.class) |
liefert das berührte Objekt oder null, wenn gerade keins berührt wird. Das null muss man immer abfragen. |
Dazu isKeyPressed(KeyCode.RIGHT) für die Tastatur, changeX(4) zum Bewegen, remove() zum Entfernen und new Text(text, x, y, breite) mit showText(...) für die Anzeige.
Zum Nachlesen: Die erste Grafik erklärt Bühne und Koordinatensystem, Eigene Sprites die eigenen Figurenklassen mit run(). Alle Methoden auf einen Blick: Referenz.
Woran es hakt
So sieht die Entscheidung eines Gegners aus, wenn man sie direkt hinschreibt:
public void run() {
if (this.distanceToSprite(spieler) < 120) {
if (spieler.getLeben() < 3) {
verfolge();
} else {
fliehe();
}
} else {
if (this.getX() > 0) {
patrouilliere();
} else {
warte();
}
}
}Das funktioniert und ist sogar lesbar. Trotzdem hat es drei Eigenschaften, die ab einer gewissen Größe stören:
- Die Entscheidung steht im Code. Wer sie ändern will, muss programmieren und neu übersetzen.
- Jeder Gegnertyp braucht seine eigene
run-Methode, auch wenn sich nur die Reihenfolge der Fragen unterscheidet. - Man kann die Entscheidung nicht anschauen, nicht ausgeben, nicht abspeichern und nicht vergleichen.
Dieselbe Entscheidung als Baum
Sieh dir die if-Verschachtelung noch einmal an. Sie ist bereits ein Baum – man sieht ihn nur nicht:
flowchart TD
A[Spieler nah?] -->|ja| B[Spieler schwach?]
A -->|nein| C[rechte Hälfte?]
B -->|ja| D[verfolgen]
B -->|nein| E[fliehen]
C -->|ja| F[patrouillieren]
C -->|nein| G[warten]
In einem Entscheidungsbaum trägt jeder innere Knoten eine Frage und jedes Blatt eine Aktion.
Die Auswertung ist immer dieselbe: Ist der Knoten ein Blatt, führe die Aktion aus. Sonst stelle die Frage und mache im linken Teilbaum weiter, wenn die Antwort ja lautet, sonst im rechten.
Das ist genau die Struktur aus Binärbaum – ein linker und ein rechter Teilbaum, mehr braucht es nicht.
Der entscheidende Unterschied zur if-Kaskade: Die Entscheidung ist nun Daten, nicht Programm.
Man kann sie zur Laufzeit umbauen, ausgeben, aus einer Datei laden, zwei Gegnern verschiedene Bäume geben – und alles davon, ohne eine Zeile der Auswertung anzufassen. Die Auswertung bleibt immer dieselben acht Zeilen.
Der Gegner im Spiel
Unten läuft es. Jeder der drei Gegner sagt, was er gerade entschieden hat. Lauf mit den Pfeiltasten auf sie zu und wieder weg, und sieh zu, wie sich die Antworten ändern.
Die beiden roten Gegner haben denselben Baum, der blaue einen anderen – bei gleichem Programmcode.
Drücke 1 und 2: Damit änderst du die Leben des Spielers und beantwortest die Frage „schwach?" anders. Die Wächter wechseln daraufhin zwischen verfolgen und fliehen – ohne dass am Programm etwas geändert wurde.
Sieh dir entscheide noch einmal an. Sie ist rekursiv, und sie ist es aus demselben Grund wie jeder Baumalgorithmus: Ein Teilbaum ist selbst wieder ein Baum.
Der Basisfall ist das Blatt. Der rekursive Fall reicht die Entscheidung an genau einen der beiden Teilbäume weiter – nicht an beide. Deshalb ist der Aufwand nicht die Zahl aller Knoten, sondern nur die Höhe des Baums.
Aufgabe 1: den Baum lesen und ändern
a) Der Wächterbaum hat sieben Knoten. Wie viele davon sind Blätter, wie viele innere Knoten? Welche Höhe hat er?
b) Wie viele Fragen werden für eine Entscheidung höchstens gestellt? Begründe mit der Höhe.
c) Baue einen dritten Gegnertyp: Er verfolgt nur, wenn der Spieler nah und schwach ist, flieht sonst immer. Du darfst nur baue...() schreiben – Gegner bleibt unverändert.
d) Der baueFeigling-Baum hat nur drei Knoten. Warum stürzt entscheide trotzdem nicht ab, obwohl der Baum viel kleiner ist?
Aufgabe 2: mit dem Baum arbeiten
a) Schreibe eine Methode zaehleBlaetter(BinaryTree<Knoten> pBaum): Wie viele verschiedene Aktionen kann dieser Gegner überhaupt zeigen?
b) Schreibe hoehe(BinaryTree<Knoten> pBaum).
c) Gib den Baum als eingerückten Text aus – Wurzel, darunter der linke, darunter der rechte Teilbaum. Welche Traversierung ist das?
d) Beurteile: Ab wann lohnt sich der Baum gegenüber der if-Kaskade? Nenne eine Situation, in der die Kaskade die bessere Wahl bleibt.
Und ohne Spiel?
| Im Spiel | Derselbe Baum woanders |
|---|---|
| Gegner entscheidet sich | ärztliche Diagnose, Kreditvergabe, Fehlersuche im Handbuch |
| Frage im inneren Knoten | Merkmal in einem gelernten Entscheidungsbaum |
| Blatt trägt eine Aktion | Klasse, in die eingeordnet wird |
| Baum tauschen, Auswertung behalten | dasselbe Programm für andere Regeln |
Entscheidungsbäume sind eines der ältesten Verfahren des maschinellen Lernens: Dort wird der Baum nicht von Hand gebaut, sondern aus Daten erzeugt – die Auswertung bleibt genau die, die hier in acht Zeilen steht.