Spielbaum und Minimax — wie ein Programm einen Zug wählt

Game trees and minimax — how a program chooses a move

Informatik Klasse 9 14 Aufgaben

InformatikAlgorithmenKIBaumdiagrammeZählprinzipKomplexität

Die Lernenden zählen die Verzweigungen eines Spielbaums (Tic-Tac-Toe, Streichholzspiel), bewerten Endstellungen mit +1, 0, −1 und reichen die Werte nach Minimax nach oben: Der Gegner wählt immer seinen besten Zug (Shannon 1950; Russell & Norvig 2020). Räumt die Vorstellung aus, der Computer „wolle" gewinnen oder habe das Wissen eingebaut (Mertala & Fagerlund 2024), ohne die Gegenvorstellung „KI = alles durchprobieren" zu erzeugen: Schach lässt sich nicht ausrechnen, Programme brechen ab und schätzen. Bereitet Komplexität und praktische Grenzen (Klasse 12) vor.

Voraussetzungen (1)

Das Zählprinzip

Klasse 5

›

Leicht

Multiple Choice #1 15s ▶ Testen

Vier gewinnt: Das Brett hat 7 Spalten, ein Stein fällt in eine Spalte bis nach unten. Wie viele Möglichkeiten gibt es für die ersten beiden Züge zusammen (erst Rot, dann Gelb)?

● 49
○ 42
○ 14

Zu jeder der 7 Spalten für Rot hat Gelb wieder 7 Spalten – auch dieselbe, denn der zweite Stein landet einfach auf dem ersten: 7 · 7 = 49 Äste im Spielbaum. 42 = 7 · 6 tut so, als wäre die Spalte nach einem Stein besetzt; 14 = 7 + 7 zählt die Spalten zusammen, statt die Paare.

Multiple Choice #2 20s ▶ Testen

Streichholzspiel: Wer am Zug ist, nimmt 1 oder 2 Hölzer, wer das letzte nimmt, gewinnt. Es liegen 4 Hölzer, du bist am Zug. Wie viele nimmst du?

● 1
○ 2
○ Egal, beides gewinnt

Nimmst du 1, bleiben 3: Der Gegner nimmt 1 oder 2, und du nimmst den Rest. Nimmst du 2, bleiben 2 – der Gegner nimmt beide und gewinnt. Möglichst viel nehmen ist kein Plan; man muss die Antworten des Gegners mitdenken.

Multiple Choice #3 15s ▶ Testen

Beide Spieler spielen Tic-Tac-Toe perfekt. Wie geht die Partie aus?

● Unentschieden
○ X gewinnt, weil X anfängt
○ O gewinnt

Minimax über den ganzen Spielbaum ergibt für den ersten Zug den Wert 0: Wer keinen Fehler macht, verliert nie. Wer den ersten Stein setzt, hat zwar einen Vorteil, aber keinen sicheren Sieg.

Wahr / Falsch #4 15s ▶ Testen

Ein Tic-Tac-Toe-Programm, das vor jedem Zug den ganzen Spielbaum mit Minimax durchrechnet, verliert nie.

✓ Wahr

Richtig. Es kennt zu jedem Zug den Wert bei bestem Gegenspiel und wählt nie einen Zug mit −1, solange es einen besseren gibt. Weil perfektes Spiel unentschieden ausgeht, gibt es immer mindestens einen Zug mit 0.

Mittel

Wahr / Falsch #1 20s ▶ Testen

Es gibt genau 9 · 8 · 7 · 6 · 5 · 4 · 3 · 2 · 1 = 362 880 verschiedene Tic-Tac-Toe-Partien.

✓ Falsch

Falsch. Viele Partien sind schon vorher zu Ende, weil jemand drei in einer Reihe hat – nach 5, 6, 7 oder 8 Zügen. Durchgezählt sind es 255 168 Partien. Ein Spielbaum hört an jeder Gewinnstellung auf.

Multiple Choice #2 20s ▶ Testen

Auf ein Brett mit 8 Feldern setzen zwei Spieler abwechselnd je einen Stein, bis alles voll ist. Auf dem leeren Brett gibt es 8! = 40 320 Reihenfolgen. Wie viele sind es noch, wenn 3 Felder belegt sind?

● 120
○ 20 160
○ 40 317

Es sind noch 5 Felder frei: 5 · 4 · 3 · 2 · 1 = 120. Jeder gesetzte Stein streicht einen ganzen Faktor – der Baum wird durch Teilen kleiner, hier auf den 336. Teil. 40 317 zieht nur die 3 Steine ab, 20 160 halbiert bloß einmal.

Wahr / Falsch #3 25s ▶ Testen

Streichholzspiel (1 oder 2 nehmen, das letzte gewinnt): Bei 6 Hölzern kann der Spieler am Zug sicher gewinnen, auch wenn der Gegner perfekt spielt.

✓ Falsch

Falsch. Nimmt er 1, bleiben 5 – der Gegner nimmt 2 und lässt 3 übrig. Nimmt er 2, bleiben 4 – der Gegner nimmt 1 und lässt wieder 3 übrig. Bei 3 (und 6, 9 …) verliert, wer am Zug ist. Der Spielbaum zeigt: Jeder Ast endet beim Gegner.

Multiple Choice #4 25s ▶ Testen

Streichholzspiel (1 oder 2 nehmen): Wie viele verschiedene Spielverläufe gibt es, wenn 4 Hölzer liegen?

● 5
○ 8
○ 4

1-1-1-1, 1-1-2, 1-2-1, 2-1-1, 2-2: fünf Äste. 8 = 2 · 2 · 2 tut so, als hätte man immer drei Züge mit je 2 Möglichkeiten – aber nach 2 + 2 ist das Spiel schon vorbei. 4 zählt nur die Hölzer.

Multiple Choice #5 25s ▶ Testen

Bewertung: +1 du gewinnst, 0 unentschieden, −1 du verlierst. Nach Zug A kann der Gegner zwischen +1 und −1 wählen, nach Zug B nur zwischen 0 und 0. Welchen Zug wählt Minimax?

● Zug B
○ Zug A
○ Beide sind gleich gut

Der Gegner wählt seinen besten Zug: Nach A nimmt er −1, nach B bleibt 0. Also ist A −1 wert und B 0 – Minimax wählt B. Zug A setzt darauf, dass der Gegner einen Fehler macht; „gleich gut" rechnet mit dem Durchschnitt (0) statt mit dem schlechtesten Fall.

Multiple Choice #6 20s ▶ Testen

Bewertung: +1 du gewinnst, 0 unentschieden, −1 du verlierst. Nach deinem Zug kann der Gegner Stellungen mit den Werten +1, 0 und −1 erreichen. Welchen Wert bekommt dein Zug nach Minimax?

● −1
○ +1
○ 0

Der Gegner sucht sich unter seinen Antworten die für dich schlechteste aus: −1. Wer +1 einträgt, hofft auf den Fehler des Gegners; 0 ist der Durchschnitt, aber der Gegner würfelt nicht.

Wahr / Falsch #7 20s ▶ Testen

Ein Tic-Tac-Toe-Programm wählt seine Züge mit Minimax, ohne Zufall. Es bekommt zweimal genau dieselbe Stellung – einmal nachdem es gewonnen, einmal nachdem es verloren hat. Es setzt beide Male seinen Stein auf dasselbe Feld.

✓ Wahr

Richtig. Das Programm rechnet aus derselben Stellung dieselben Werte aus und nimmt denselben besten Zug. Es ärgert sich nicht über eine Niederlage, freut sich nicht über einen Sieg und hat aus der letzten Partie nichts übernommen – es vergleicht nur Zahlen.

Multiple Choice #8 20s ▶ Testen

In einer Schachstellung hat der Spieler am Zug grob 30 erlaubte Züge, und so geht es weiter. Wie viele Zugfolgen gibt es damit ungefähr für die nächsten 4 Halbzüge (2 für jede Seite)?

● Rund 800 000
○ Rund 120
○ Rund 900

Jeder Halbzug vervielfacht: 30 · 30 · 30 · 30 = 810 000. 120 = 30 · 4 zählt die Möglichkeiten zusammen, statt sie zu multiplizieren; 900 = 30 · 30 hört nach zwei Halbzügen auf. Shannon schätzte 1950 so die Größe des Schachbaums: rund 10¹²⁰ Partien – viel zu viele, um sie durchzurechnen.

Multiple Choice #9 25s ▶ Testen

Ein Schachprogramm rechnet einige Züge voraus, hört dann auf und gibt der erreichten Stellung Punkte – nur nach Material: Bauer 1, Springer und Läufer je 3, Turm 5, Dame 9. Welche Stellung bewertet es für Weiß am höchsten?

● Weiß hat einen Turm mehr, Schwarz hat zwei Bauern mehr
○ Weiß hat drei Bauern mehr, Schwarz hat einen Springer mehr
○ Weiß hat einen Läufer mehr, Schwarz hat zwei Bauern mehr

Gerechnet wird mit Punkten, nicht mit der Zahl der Figuren: Turm gegen zwei Bauern ergibt 5 − 2 = +3, drei Bauern gegen einen Springer 3 − 3 = 0, Läufer gegen zwei Bauern 3 − 2 = +1. Weil das Programm nicht bis zum Partieende rechnen kann, setzt es an der Abbruchstelle so eine geschätzte Punktzahl ein und wendet darauf Minimax an.

Wahr / Falsch #10 20s ▶ Testen

Ein Chatbot findet seine Antwort, indem er wie ein Tic-Tac-Toe-Programm alle möglichen Antworten durchprobiert und die beste nimmt.

✓ Falsch

Falsch. Alle möglichen Sätze durchzuprobieren wäre noch aussichtsloser als beim Schach. Ein Sprachmodell wählt Wort für Wort eines, das nach den gelernten Zahlen gut passt — es probiert nicht alle Antworten durch. „Alles durchprobieren" beschreibt Tic-Tac-Toe, nicht jede KI.