États gagnants et perdants dans les jeux
Déterminer qui gagne avec un jeu optimal
États gagnants et perdants dans les jeux est une leçon Coding Interview Prep gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage Coding Interview Prep, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours Coding Interview Prep comprend 4 leçons au total.
Deux joueurs, un jeu parfait
Dans un jeu combinatoire, deux joueurs jouent à tour de rôle, jouent tous deux parfaitement, et celui qui ne peut plus jouer perd. Votre objectif est simplement de prédire le vainqueur. 🎯
Chaque position possède une étiquette
Chaque position du jeu est un état. Votre tâche consiste à étiqueter chaque état comme une victoire ou une défaite pour le joueur dont c’est le tour.
Signification d’un état gagnant
Un état est un état gagnant si le joueur dont c’est le tour possède au moins un coup menant à un état perdant pour l’adversaire.
Signification d’un état perdant
Un état est un état perdant lorsque chacun des coups que vous pouvez jouer donne à l’adversaire un état gagnant. Vous êtes bloqué, quoi que vous fassiez.
Le cas de base
La position dans laquelle vous ne pouvez absolument pas jouer est le cas de base. Le joueur qui y est confronté a déjà perdu : étiquetez donc cette position comme perdante.
Construire depuis la base
Commencez par les cas de base et progressez vers l’extérieur. L’étiquette de chaque nouvel état dépend uniquement des états vers lesquels ses coups mènent.
Un bon coup suffit
Pour gagner, vous n’avez besoin que d’un coup menant à un état perdant pour l’adversaire. Trouver une seule issue suffit.
Un petit exemple
Prenez 1 ou 2 pierres dans un tas ; le dernier à en prendre gagne. Avec 0 pierre, le joueur dont c’est le tour perd : c’est donc un état perdant.
Coder la vérification de victoire
Cette récursion étiquette un état en essayant chaque coup, puis en lançant une récursion sur le résultat. ⚙️
def win(n):
if n == 0:
return False
return any(not win(n - k) for k in (1, 2))Mémoriser pour rester rapide
Les états se répètent entre les différentes branches : mettez donc chaque résultat en cache. Un simple mémo transforme un travail exponentiel en temps linéaire.
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 symétrie est un raccourci
Si une position est parfaitement symétrique, le deuxième joueur peut souvent reproduire les coups de l’adversaire et gagner. Soyez attentif à cette stratégie de symétrie.
Vérification rapide
Vous êtes face à un état. Quand est-il perdant pour vous ?
Récapitulatif
Vous savez maintenant étiqueter les états : une win possède un coup menant à une défaite adverse, tandis qu’une défaite n’en possède aucun. Construisez depuis les cas de base et utilisez la mémorisation. 🧠
Questions Fréquemment Posées
La leçon « États gagnants et perdants dans les jeux » est-elle gratuite ?
Oui — le texte complet de « États gagnants et perdants dans les jeux » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours Coding Interview Prep, passe à CoddyKit PRO. Le cours Coding Interview Prep comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « États gagnants et perdants dans les jeux » ?
Déterminer qui gagne avec un jeu optimal Tu pratiques Coding Interview Prep avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer Coding Interview Prep ?
Aucune expérience préalable n'est requise. Coding Interview Prep sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.
Combien de temps prend la leçon « États gagnants et perdants dans les jeux » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon Coding Interview Prep ?
Oui. Chaque leçon Coding Interview Prep inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.
Toutes les leçons de ce cours
- États gagnants et perdants dans les jeux
- Nim et le nombre de Grundy
- Diviser pour mieux régner au milieu
- Déboguer rapidement : tests de contrainte et triage