Question transversaleMathsNSIArbres et structures de données

Un ordinateur peut-il prévoir tous les coups d'une partie d'échecs ?

Q: Calculez log₁₀(30).

$log₁₀30=log₁₀3+1≈1,48$.

Q: Combien de nœuds jusqu'à la profondeur 4 avec 30 coups par position ?

$1+30+900+27 000+810 000=837 931$.

Au morpion, il y a au plus 9! = 362 880 suites de coups (255 168 parties réelles) : un programme explore tout. Aux échecs, avec environ 30 coups possibles par position, l'arbre compte de l'ordre de 10¹²⁰ parties : impossible. On explore quelques coups à l'avance avec l'algorithme minimax et l'élagage alpha-bêta.

Grand oral session 2027 : exposé de 10 minutes debout, puis 10 minutes d'échange, sans calculatrice. Plan prévu pour 9,5 min.

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

J'ai programmé en NSI un morpion contre l'ordinateur, impossible à battre. Mon professeur m'a expliqué que le programme envisageait toutes les parties possibles. Je me suis demandé si un ordinateur pouvait faire de même aux échecs, et j'ai découvert, en comptant les branches de l'arbre de jeu, que le nombre de parties dépasse de très loin le nombre d'atomes de l'Univers.

L'enjeu et les notions du programme

Dénombrer les nœuds d'un arbre de jeu par des puissances et des factorielles, et comprendre comment un algorithme récursif choisit un coup.

Mathématiques

Dénombrement, factorielle, puissances (terminale)
Ordres de grandeur, logarithme décimal (seconde, terminale)
Suites géométriques (première)

Numérique et sciences informatiques

Arbres, parcours récursif (terminale)
Algorithmes de jeu, minimax (terminale)

Le plan de l'exposé en 9,5 min

1. Introduction
1 min
Un jeu à deux joueurs se représente par un arbre : la racine est la position de départ, chaque branche un coup, chaque feuille une fin de partie. Problématique : peut-on parcourir tout l'arbre pour jouer parfaitement ?
2. Mathématiques : compter les parties
4 min
Morpion : le premier joueur a 9 cases, le second 8, et ainsi de suite. Sans tenir compte des parties qui s'arrêtent avant, il y a au plus $9! = 362880$ 9!=362 880 suites de coups. En retirant les parties terminées plus tôt, il reste $255168$ 255 168 parties : un ordinateur les parcourt en une fraction de seconde.
Échecs : environ 30 coups possibles par position, et une partie dure environ 40 coups par joueur, soit 80 demi-coups. L'arbre a de l'ordre de $3 0^{80}$ 30⁸⁰ feuilles. Comme $lo g_{10} 30 \approx 1, 48$ log₁₀30≈1,48, $3 0^{80} \approx 1 0^{118}$ 30⁸⁰≈10¹¹⁸ : c'est l'ordre de grandeur estimé par Shannon en 1950 (environ $1 0^{120}$ 10¹²⁰). On estime le nombre d'atomes de l'Univers observable à $1 0^{80}$ 10⁸⁰.
Le nombre de nœuds jusqu'à la profondeur $d$ d est $1 + b + b^{2} + \dots + b^{d} = \frac{b ^{d + 1} - 1}{b - 1}$ 1+b+b²+…+b^(d)=(b^(d+1)-1)/(b-1) : une somme géométrique dominée par son dernier terme $b^{d}$ b^(d).
3. NSI : minimax et élagage
3 min
Minimax : on évalue chaque feuille (gagné, perdu, nul, ou une note pour une position non terminée). Puis, en remontant, chaque nœud prend le maximum de ses enfants si c'est au programme de jouer, le minimum si c'est à l'adversaire : on suppose qu'il joue au mieux. C'est une fonction récursive.
Aux échecs, on s'arrête à une profondeur fixée et on évalue la position (matériel, mobilité). L'élagage alpha-bêta évite d'explorer les branches qui ne peuvent pas changer la décision : dans le meilleur cas, il réduit le coût de $b^{d}$ b^(d) à environ $b^{d /2}$ b^(d/2), ce qui double la profondeur atteignable. Les programmes modernes ajoutent des réseaux de neurones pour évaluer les positions.
4. Conclusion
1,5 min
Un ordinateur peut prévoir toutes les parties de morpion, pas celles des échecs : l'arbre de jeu croît comme $b^{d}$ b^(d), soit environ $1 0^{120}$ 10¹²⁰ parties. Il joue en explorant quelques coups avec minimax et l'élagage alpha-bêta. J'ouvre sur le jeu de dames, entièrement résolu par ordinateur en 2007.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

morpion : 9! = 362880 (dont 255168 parties r \overset{e}{ˊ} elles) morpion : 9!=362 880 ( dont 255 168 parties réelles ) \overset{e}{ˊ} checs : 3 0^{80} = 1 0^{80 l o g_{10} 30} \approx 1 0^{118} 1 + b + \dots + b^{d} = \frac{b ^{d + 1} - 1}{b - 1} échecs : 30⁸⁰=10^(80log₁₀30)\approx10¹¹⁸ 1+b+\dots+b^(d)=(b^(d+1)-1)/(b-1)

Conclusion : la réponse à la question

Le dénombrement des branches dit ce qu'un ordinateur peut explorer : tout le morpion, une infime partie des échecs. L'algorithme minimax, récursif, et l'élagage permettent pourtant de jouer à un niveau surhumain.

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Pourquoi 9! est-il seulement un majorant au morpion ?

Beaucoup de parties s'arrêtent avant que la grille soit pleine, quand un joueur aligne trois symboles.

Calculez log₁₀(30).

$lo g_{10} 30 = lo g_{10} 3 + 1 \approx 1, 48$ log₁₀30=log₁₀3+1≈1,48.

Qu'apporte l'élagage alpha-bêta ?

Il évite d'explorer des branches inutiles et permet d'aller environ deux fois plus profond dans le même temps.

Que suppose minimax sur l'adversaire ?

Qu'il joue toujours le coup le plus défavorable pour nous, c'est-à-dire le meilleur pour lui.

Combien de nœuds jusqu'à la profondeur 4 avec 30 coups par position ?

$1 + 30 + 900 + 27000 + 810000 = 837931$ 1+30+900+27 000+810 000=837 931.

Les pièges qui coûtent des points

Confondre nombre de positions et nombre de parties.
Croire que les ordinateurs ont « résolu » les échecs.
Oublier qu'un nœud de l'adversaire prend le minimum.

Revoir les notions

Autres questions : arbres et structures de données

Toutes les questions maths-nsi →

Préparer l'oral, pas seulement le contenu

Gestion des 20 minutes de préparation, usage du tableau, posture debout, réponses au jury : la méthode complète, conforme aux règles de la session 2027.

Méthode : traiter une question de Grand oral →

Continuer la préparation

Le Grand oral 2027 →Méthode : traiter une question →Toutes les questions, par combinaison →Questions de maths seules →Questions maths-physique-chimie →Questions maths-SES →Questions maths-SVT →Questions maths-SI →Questions maths-HGGSP →Questions maths-anglais →