Gewinn- und Verlustzustände in Spielen
Leiten Sie ab, wer bei optimalem Spiel gewinnt
Gewinn- und Verlustzustände in Spielen ist eine kostenlose Competitive Programming Academy-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Competitive Programming Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Zwei Spieler, perfektes Spiel
In einem kombinatorischen Spiel wechseln sich zwei Spieler mit ihren Zügen ab, beide spielen perfekt, und wer keinen Zug mehr machen kann, verliert. Ihre Aufgabe ist lediglich, den Gewinner vorherzusagen. 🎯
Jede Stellung hat eine Kennzeichnung
Jede Spielstellung ist ein Zustand. Ihre gesamte Aufgabe besteht darin, jeden Zustand für den Spieler am Zug als Gewinn- oder Verluststellung zu kennzeichnen.
Was eine Gewinnstellung bedeutet
Ein Zustand ist eine Gewinnstellung, wenn der Spieler am Zug mindestens einen Zug in eine Verluststellung des Gegners machen kann.
Was eine Verluststellung bedeutet
Ein Zustand ist eine Verluststellung, wenn jeder einzelne Zug, den Sie machen, dem Gegner eine Gewinnstellung überlässt. Sie sitzen unabhängig von Ihrer Wahl fest.
Der Basisfall
Die Stellung, in der Sie überhaupt keinen Zug machen können, ist der Basisfall. Der Spieler, der ihr gegenübersteht, hat bereits verloren, also kennzeichnen Sie sie als Verluststellung.
Von unten nach oben aufbauen
Beginnen Sie mit den Basisfällen und arbeiten Sie sich nach außen vor. Die Kennzeichnung jedes neuen Zustands hängt nur von den Zuständen ab, zu denen seine Züge führen.
Ein guter Zug genügt
Um zu gewinnen, benötigen Sie nur einen Zug in eine Verluststellung des Gegners. Es genügt, irgendeinen Ausweg zu finden.
Ein kleines Beispiel
Nehmen Sie 1 oder 2 Steine von einem Haufen; wer den letzten nimmt, gewinnt. Bei 0 Steinen verliert der Spieler am Zug, also ist dies eine Verluststellung.
Den Gewinn-Check programmieren
Diese Rekursion kennzeichnet einen Zustand, indem sie jeden Zug ausprobiert und für das Ergebnis rekursiv weiterrechnet. ⚙️
def win(n):
if n == 0:
return False
return any(not win(n - k) for k in (1, 2))Mit Memoisierung schnell bleiben
Zustände wiederholen sich in verschiedenen Zweigen, daher sollten Sie jedes Ergebnis zwischenspeichern. Ein einfaches Memo macht aus exponentiellem Aufwand lineare Laufzeit.
from functools import lru_cache
@lru_cache(None)
def win(n):
return n != 0 and any(not win(n - k) for k in (1, 2))Symmetrie als Abkürzung
Ist eine Stellung vollständig symmetrisch, kann der zweite Spieler oft die Züge spiegeln und gewinnen. Achten Sie auf diesen Spiegelungstrick.
Kurzer Check
Sie stehen vor einem Zustand. Wann ist er für Sie eine Verluststellung?
Zusammenfassung
Sie kennzeichnen Zustände jetzt so: Eine Gewinnstellung hat einen Zug in eine Verluststellung des Gegners, eine Verluststellung hat keinen. Bauen Sie von den Basisfällen aus auf und verwenden Sie Memoisierung. 🧠
Häufig gestellte Fragen
Ist die Lektion „Gewinn- und Verlustzustände in Spielen“ kostenlos?
Ja — der vollständige Text von „Gewinn- und Verlustzustände in Spielen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Competitive Programming Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Competitive Programming Academy-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Gewinn- und Verlustzustände in Spielen“?
Leiten Sie ab, wer bei optimalem Spiel gewinnt Du übst Competitive Programming Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Competitive Programming Academy zu starten?
Keine Vorkenntnisse erforderlich. Competitive Programming Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.
Wie lange dauert die Lektion „Gewinn- und Verlustzustände in Spielen“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Competitive Programming Academy-Lektion Code schreiben und ausführen?
Ja. Jede Competitive Programming Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Gewinn- und Verlustzustände in Spielen
- Nim und die Grundy-Zahl
- Meet in the Middle
- Schnell debuggen: Stresstests und Triage