Vinnande och förlorande tillstånd i spel
Resonera om vem som vinner vid optimalt spel
Vinnande och förlorande tillstånd i spel är en gratis lektion i Competitive Programming Academy på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Competitive Programming Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Två spelare, perfekt spel
I ett kombinatoriskt spel turas två spelare om att göra drag, båda spelar perfekt och den som inte kan göra ett drag förlorar. Uppgiften är helt enkelt att förutsäga vinnaren. 🎯
Varje position har en etikett
Varje spelposition är ett tillstånd. Er uppgift är att märka varje tillstånd som antingen vinst eller förlust för spelaren som står på tur.
Vad ett vinnande tillstånd betyder
Ett tillstånd är ett vinnande tillstånd om spelaren som står på tur har minst ett drag som leder till ett förlorande tillstånd för motståndaren.
Vad ett förlorande tillstånd betyder
Ett tillstånd är ett förlorande tillstånd när varje drag Ni gör ger motståndaren ett vinnande tillstånd. Ni sitter fast oavsett vad Ni gör.
Basfallet
Positionen där Ni inte kan göra något drag alls är basfallet. Spelaren som möter det har redan förlorat, så märk det som en förlust.
Bygg underifrån
Börja med basfallen och arbeta utåt. Varje nytt tillstånds etikett beror endast på de tillstånd som dess drag leder till.
Ett bra drag räcker
För att vinna behöver Ni bara ett drag till ett förlorande tillstånd för motståndaren. Det räcker att hitta en enda utväg.
Ett litet exempel
Ta 1 eller 2 stenar från en hög; den som tar den sista vinner. Med 0 stenar förlorar spelaren som står på tur, så det är ett förlorande tillstånd.
Koda vinstkontrollen
Den här rekursionen klassificerar ett tillstånd genom att prova varje drag och rekursivt behandla resultatet. ⚙️
def win(n):
if n == 0:
return False
return any(not win(n - k) for k in (1, 2))Memoisera för att hålla tempot
Tillstånd upprepas mellan grenarna, så cachelagra varje resultat. Ett enkelt memo omvandlar exponentiellt arbete till linjär tid.
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))Symmetri är en genväg
Om en position är perfekt symmetrisk kan den andra spelaren ofta spegla dragen och vinna. Håll utkik efter det speglingstricket.
Snabbkontroll
Ni står inför ett tillstånd. När är det ett förlorande tillstånd för Er?
Sammanfattning
Ni märker nu tillstånd: ett vinnande tillstånd har ett drag till motståndarens förlust, medan ett förlorande tillstånd inte har något sådant drag. Bygg från basfallen och memoisera. 🧠
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Vinnande och förlorande tillstånd i spel” gratis?
Ja – hela texten till ”Vinnande och förlorande tillstånd i spel” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Competitive Programming Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Vinnande och förlorande tillstånd i spel”?
Resonera om vem som vinner vid optimalt spel Ni övar på Competitive Programming Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Competitive Programming Academy?
Du behöver inga förkunskaper. Utbildningen i Competitive Programming Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”Vinnande och förlorande tillstånd i spel”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Competitive Programming Academy-lektionen?
Ja. Varje Competitive Programming Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Vinnande och förlorande tillstånd i spel
- Nim och Grundy-tal
- Mötas på mitten
- Felsök snabbt: stresstester och triage