Stati vincenti e perdenti nei giochi
Stabilire chi vince con un gioco ottimale
Stati vincenti e perdenti nei giochi è una lezione Competitive Programming Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Competitive Programming Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Competitive Programming Academy include 4 lezioni in totale.
Due giocatori, gioco perfetto
In un gioco combinatorio, due giocatori alternano le mosse, giocano entrambi in modo perfetto e chi non può muovere perde. Il suo unico compito è prevedere il vincitore. 🎯
Ogni posizione ha un'etichetta
Ogni posizione di gioco è uno stato. Il suo compito è assegnare a ogni stato l'etichetta vincente o perdente per il giocatore che deve muovere.
Che cosa significa stato vincente
Uno stato è uno stato vincente se il giocatore di turno ha almeno una mossa che porta a uno stato perdente per l'avversario.
Che cosa significa stato perdente
Uno stato è uno stato perdente quando ogni mossa possibile consegna all'avversario uno stato vincente. Non c'è via d'uscita.
Il caso base
La posizione in cui non è possibile effettuare alcuna mossa è il caso base. Il giocatore che la deve affrontare ha già perso, quindi la si etichetta come perdente.
Costruire dal basso verso l'alto
Parta dai casi base e proceda verso l'esterno. L'etichetta di ogni nuovo stato dipende solo dagli stati raggiunti dalle sue mosse.
Basta una buona mossa
Per vincere, le serve solo una mossa verso uno stato perdente per l'avversario. Trovare una qualunque via di fuga è sufficiente.
Un piccolo esempio
Si possono prendere 1 o 2 pietre da un mucchio; vince chi prende l'ultima. Con 0 pietre il giocatore di turno perde, quindi si tratta di uno stato perdente.
Implementare il controllo della vittoria
Questa ricorsione assegna un'etichetta allo stato provando ogni mossa e applicando la ricorsione al risultato. ⚙️
def win(n):
if n == 0:
return False
return any(not win(n - k) for k in (1, 2))Usare la memoization per restare veloci
Gli stati si ripetono tra i diversi rami, quindi memorizzi ogni risultato. Una semplice memo trasforma il lavoro esponenziale in tempo lineare.
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))La simmetria è una scorciatoia
Se una posizione è perfettamente simmetrica, spesso il secondo giocatore può imitare le mosse dell'avversario e vincere. Presti attenzione a questa strategia di imitazione.
Verifica rapida
Si trova davanti a uno stato. Quando è uno stato perdente per lei?
Riepilogo
Ora sa assegnare un'etichetta agli stati: uno stato vincente ha una mossa verso una sconfitta dell'avversario, mentre uno perdente non ne ha nessuna. Parta dai casi base e usi la memoization. 🧠
Domande Frequenti
La lezione «Stati vincenti e perdenti nei giochi» è gratuita?
Sì — il testo completo di «Stati vincenti e perdenti nei giochi» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Competitive Programming Academy, passa a CoddyKit PRO. Il corso Competitive Programming Academy include 4 lezioni in totale.
Cosa imparerò in «Stati vincenti e perdenti nei giochi»?
Stabilire chi vince con un gioco ottimale Eserciti Competitive Programming Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Competitive Programming Academy?
Non è richiesta alcuna esperienza precedente. Competitive Programming Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.
Quanto tempo richiede la lezione «Stati vincenti e perdenti nei giochi»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Competitive Programming Academy?
Sì. Ogni lezione Competitive Programming Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Stati vincenti e perdenti nei giochi
- Nim e numero di Grundy
- Meet in the Middle
- Debug rapido: stress test e triage