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)?

Erklärung: 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.

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

Erklärung: 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.

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?

Erklärung: 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.

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?

Erklärung: 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.

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.

Erklärung: 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.

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

Erklärung: 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.

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?

Erklärung: 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.

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?

Erklärung: 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.

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

Erklärung: 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.

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

Erklärung: 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.

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.

Erklärung: 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.

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)?

Erklärung: 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.

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?

Erklärung: 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.

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

Erklärung: 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.

Aufgabe 1 von 14