Winnende en verliezende toestanden in spellen
Redeneren over de winnaar bij optimaal spel
Winnende en verliezende toestanden in spellen is een gratis Competitive Programming Academy-les op CoddyKit. Dit is les 1 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Competitive Programming Academy. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Twee spelers, perfect spel
In een combinatorisch spel doen twee spelers om de beurt een zet, spelen ze allebei perfect en verliest degene die geen zet meer kan doen. Het is jouw taak om alleen de winnaar te voorspellen. 🎯
Elke positie heeft een label
Elke spelpositie is een toestand. Je hele taak bestaat uit het labelen van elke toestand als winst of verlies voor de speler die aan de beurt is.
Wat een winnende toestand betekent
Een toestand is een winnende toestand als de speler aan de beurt minstens één zet kan doen die de tegenstander naar een verliezende toestand brengt.
Wat een verliezende toestand betekent
Een toestand is een verliezende toestand als elke zet die je doet de tegenstander een winnende toestand geeft. Je zit vast, wat je ook doet.
Het basisgeval
De positie waarin je helemaal geen zet kunt doen, is het basisgeval. De speler die daarmee te maken krijgt, heeft al verloren, dus label je deze als verlies.
Van onderaf opbouwen
Begin met de basisgevallen en werk naar buiten toe. Het label van elke nieuwe toestand hangt alleen af van de toestanden waar zijn zetten naartoe leiden.
Eén goede zet is genoeg
Om te winnen heb je maar één zet nodig naar een verliezende toestand voor de tegenstander. Elke ontsnappingsroute is voldoende.
Een klein voorbeeld
Neem 1 of 2 stenen uit een stapel; wie als laatste een steen neemt, wint. Met 0 stenen verliest de speler die aan de beurt is, dus dat is een verliezende toestand.
De winstcontrole programmeren
Deze recursie labelt een toestand door elke zet te proberen en voor het resultaat opnieuw recursie uit te voeren. ⚙️
def win(n):
if n == 0:
return False
return any(not win(n - k) for k in (1, 2))Memoisatie voor snelheid
Toestanden komen in verschillende takken opnieuw voor, dus sla elk resultaat op. Een eenvoudige memo verandert exponentieel veel werk in lineaire tijd.
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 snelkoppeling
Als een positie volkomen symmetrisch is, kan de tweede speler vaak de zetten spiegelen en winnen. Let op die spiegeltruc.
Snelle controle
Je krijgt een toestand. Wanneer is die voor jou een verliezende toestand?
Samenvatting
Je labelt toestanden nu als volgt: bij winst leidt één zet naar verlies voor de tegenstander, bij verlies bestaat zo'n zet niet. Bouw vanuit basisgevallen op en gebruik memoisatie. 🧠
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Winnende en verliezende toestanden in spellen” gratis?
Ja — de volledige tekst van “Winnende en verliezende toestanden in spellen” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Competitive Programming Academy wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Competitive Programming Academy bevat in totaal 4 lessen.
Wat leer ik in “Winnende en verliezende toestanden in spellen”?
Redeneren over de winnaar bij optimaal spel Je oefent met Competitive Programming Academy door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Competitive Programming Academy te beginnen?
Ervaring vooraf is niet nodig. Competitive Programming Academy op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 1 van 4.
Hoe lang duurt de les “Winnende en verliezende toestanden in spellen”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Competitive Programming Academy?
Ja. Elke les over Competitive Programming Academy bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Winnende en verliezende toestanden in spellen
- Nim en het Grundy-getal
- Meet in the Middle
- Snel debuggen: stresstests en triage