CoddyRun
Quand un joueur perd contre l'ordinateur, il dit volontiers que « l'IA est forte ». Le mot impressionne, et il laisse imaginer une machine qui réfléchit, qui comprend le jeu, qui a un plan.
La réalité est beaucoup plus modeste, et beaucoup plus intéressante à enseigner : un adversaire de jeu ne comprend rien du tout. Il applique des règles, ou il compte. C'est tout.
Pour le montrer, j'ai fait s'affronter trois adversaires au morpion. Aucun des trois ne sait ce qu'est un alignement, une menace ou une stratégie. Et pourtant, deux d'entre eux sont très difficiles à battre.
Ce qu'on appelle « IA » dans un jeu
Dans un jeu, l'intelligence artificielle ne pense pas. Elle répond à une seule question, encore et encore :
Parmi tous les coups possibles, lequel jouer ?
Rien d'autre. Le programme reçoit une position, il rend une case. Toute la différence entre un adversaire ridicule et un adversaire redoutable tient dans la manière de répondre à cette question.
Il y a essentiellement trois familles de réponses, et on peut les classer par ce qu'elles coûtent à écrire.
Niveau zéro : le hasard
La réponse la plus simple consiste à choisir une case libre au sort.
tant que trouve = faux
c vaut hasard(0, 8)
si cel[c] = 0 alors
choix vaut c
trouve vaut vrai
fin si
fin tant que
Cet adversaire ne sait pas qu'il joue. Il ne remarque pas qu'il va perdre au coup suivant, il ne voit pas qu'il pourrait gagner immédiatement.
Il a pourtant une utilité réelle : il sert de référence. Sans lui, impossible de dire si les autres sont bons. On ne mesure jamais une performance dans l'absolu, toujours contre quelque chose.
Niveau un : les règles en cascade
C'est de très loin la technique la plus répandue dans les jeux, et la plus rentable. On écrit une liste de priorités, et on prend la première qui s'applique.
Pour le morpion, quatre suffisent :
- Si je peux gagner ce coup-ci, je le joue.
- Sinon, si l'adversaire peut gagner au coup suivant, je l'en empêche.
- Sinon, je prends le centre, puis un coin.
- Sinon, un bord.
Comment le programme sait-il qu'il peut gagner ? Il n'a aucune notion d'alignement. Il triche, en quelque sorte : il pose son pion, regarde si la position est gagnante, puis le retire.
cel[k] vaut joueur
// on vérifie les huit alignements possibles
cel[k] vaut 0
si gagnant = joueur alors
choix vaut k
fin si
C'est là le point essentiel : l'IA ne raisonne pas, elle essaie. Elle simule un coup, observe le résultat, annule. Neuf essais, et la décision est prise.
Cet adversaire ne voit qu'un seul coup à l'avance. Il ne prépare rien, il n'a aucun plan. Il gagne pourtant l'immense majorité de ses parties contre le hasard.
L'ordre des règles est la stratégie. Intervertissez les règles 1 et 2 bloquer avant de gagner, et l'adversaire devient absurde : il défend une position déjà perdue pour lui alors qu'il avait la victoire. Toute l'intelligence apparente tient dans cet ordre, décidé par le programmeur, pas par la machine.
Niveau deux : la simulation
Le troisième adversaire est le plus déroutant, parce qu'il ne connaît aucune règle du jeu. Ni le centre, ni les coins, ni l'idée de bloquer.
Voici tout ce qu'il fait. Pour chaque case libre :
- il y pose son pion,
- il termine la partie complètement au hasard, seize fois de suite,
- il compte combien de ces parties absurdes il a gagnées.
Puis il joue la case dont le score est le meilleur.
C'est tout. Aucune stratégie n'a été programmée. Aucun humain ne lui a expliqué que le centre est une bonne case. Et pourtant il le découvre tout seul : statistiquement, les parties jouées n'importe comment à partir du centre se terminent mieux.
Cette méthode porte un nom "la recherche de Monte-Carlo" et c'est une cousine simplifiée de ce qui a permis aux programmes de jeu de Go de dépasser les meilleurs joueurs humains.
Le renversement de perspective est complet : là où l'IA à règles sait des choses, l'IA à simulation ne sait rien mais compte beaucoup.
Mesurer, pas croire
Une IA de jeu ne se juge pas à l'impression qu'elle donne. Elle se mesure.
Le programme fait donc s'affronter les trois adversaires, trente parties par confrontation, en alternant celui qui commence. Ce détail n'est pas cosmétique : au morpion, commencer est un avantage réel, et une mesure qui l'ignore ne vaut rien.
Les résultats sont sans appel. Le hasard ne gagne presque jamais contre les règles. La simulation, elle, tient la comparaison sans avoir reçu la moindre consigne stratégique.
Ce protocole vaut pour tout : quand vous ajoutez une règle à votre adversaire, faites-le jouer cent parties contre la version précédente. Si le taux de victoire ne bouge pas, la règle ne sert à rien, quelle que soit l'élégance de l'idée.
Pourquoi ça ressemble quand même à de l'intelligence
Un joueur humain qui perd contre l'IA à règles a l'impression qu'elle a compris son plan. C'est une illusion, et elle repose sur trois mécanismes.
La constance. L'ordinateur n'oublie jamais de vérifier s'il peut gagner. Un humain, si. Une machine qui ne se trompe jamais sur une chose simple paraît attentive.
La rapidité. La décision est instantanée. On prête volontiers de la réflexion à ce qui répond vite.
Notre penchant à prêter des intentions. Nous racontons une histoire derrière chaque coup — « il a vu ma menace » — alors que le programme a simplement parcouru neuf cases dans l'ordre.
Bonnes pratiques pour écrire un adversaire
Commencez par le hasard. C'est votre point de comparaison, et il permet de vérifier que le jeu fonctionne avant de penser à la stratégie.
Ajoutez les règles une par une, et mesurez chaque fois. Une règle qui n'améliore pas le taux de victoire est une règle à supprimer.
Rangez les règles par priorité, jamais en vrac. L'ordre est la stratégie.
Simulez plutôt que raisonner. « Je joue ici, que se passe-t-il ? » est presque toujours plus simple à écrire que « comment savoir si ce coup est bon ? ».
N'oubliez pas de rendre l'adversaire battable. Une IA parfaite au morpion ne perd jamais : le jeu devient sans intérêt. La bonne question n'est pas « comment le rendre plus fort », mais « comment le rendre agréable à affronter ». Un adversaire qui laisse passer une occasion de temps en temps est souvent meilleur, du point de vue du joueur, qu'un adversaire imbattable.
Conclusion : compter n'est pas comprendre
Trois adversaires, trois approches, aucune intelligence.
Le premier tire au sort. Le deuxième applique quatre règles dans un ordre choisi par un humain. Le troisième joue des milliers de parties absurdes et retient celles qui finissent bien.
Aucun des trois ne sait ce qu'est le morpion. Aucun n'a d'intention, de plan, ni de conscience de gagner. Il n'y a que des essais, des comparaisons et des comptages.
C'est peut-être la leçon la plus utile qu'un jeu puisse donner sur l'intelligence artificielle : ce que nous prenons pour de la réflexion n'est souvent qu'une énumération très rapide. Le programme n'est pas plus malin que nous. Il est seulement infatigable.
Et cette leçon-là dépasse largement le morpion.
Programme :
// ===========================================================
// L'INTELLIGENCE ARTIFICIELLE SANS INTELLIGENCE
// Trois adversaires au morpion, aucun ne « comprend » le jeu.
// 1. HASARD joue n'importe où
// 2. RÈGLES quatre priorités en cascade
// 3. SIMULATION joue au hasard dans sa tête, et compte
// Écran DÉMO : une partie rejouée coup par coup, avec la
// raison de chaque décision.
// Écran TOURNOI : les trois s'affrontent, on mesure.
// ===========================================================
@ CONFIGURATION
vue est une toile
dimension(vue, 700, 520)
NBSIM est un nombre
NBSIM vaut 16
NBMATCH est un nombre
NBMATCH vaut 30
ia1 est un nombre
ia2 est un nombre
ia1 vaut 2
ia2 vaut 1
ecran est un texte
ecran vaut "demo"
relancer est un booléen
relancer vaut vrai
montre est un nombre
montre vaut 0
touche est un nombre
@ LE PLATEAU et LES ALIGNEMENTS
// Les neuf cases, numérotées de 0 à 8
cel est un tableau
sim est un tableau
pour k de 0 à 8
cel ajoute 0
sim ajoute 0
fin pour
// Les huit alignements gagnants, décrits une fois pour toutes
ln1 est un tableau
ln2 est un tableau
ln3 est un tableau
ln1 ajoute 0
ln2 ajoute 1
ln3 ajoute 2
ln1 ajoute 3
ln2 ajoute 4
ln3 ajoute 5
ln1 ajoute 6
ln2 ajoute 7
ln3 ajoute 8
ln1 ajoute 0
ln2 ajoute 3
ln3 ajoute 6
ln1 ajoute 1
ln2 ajoute 4
ln3 ajoute 7
ln1 ajoute 2
ln2 ajoute 5
ln3 ajoute 8
ln1 ajoute 0
ln2 ajoute 4
ln3 ajoute 8
ln1 ajoute 2
ln2 ajoute 4
ln3 ajoute 6
// Ordre de préférence de l'IA 2 : centre, puis coins, puis bords
prefer est un tableau
prefer ajoute 4
prefer ajoute 0
prefer ajoute 2
prefer ajoute 6
prefer ajoute 8
prefer ajoute 1
prefer ajoute 3
prefer ajoute 5
prefer ajoute 7
@ MÉMOIRE de LA PARTIE MONTRÉE
histCase est un tableau
histQui est un tableau
histTxt est un tableau
pour k de 0 à 8
histCase ajoute 0
histQui ajoute 0
histTxt ajoute ""
fin pour
nbCoups est un nombre
nbCoups vaut 0
issue est un texte
issue vaut ""
@ RÉSULTATS DU TOURNOI
parA est un tableau
parB est un tableau
resA est un tableau
resB est un tableau
resN est un tableau
pour k de 0 à 2
parA ajoute 1
parB ajoute 2
resA ajoute 0
resB ajoute 0
resN ajoute 0
fin pour
@ NOM D'UNE IA
procédure nomIA(t, x, y, n, coul, ta)
txt est un texte
si n = 1 alors
txt vaut "HASARD"
sinon si n = 2 alors
txt vaut "RÈGLES"
sinon
txt vaut "SIMULATION"
fin si
label(t, x, y, txt, coul, ta)
fin procédure
@ UNE BARRE de pourcentage
procédure barrePct(t, x, y, larg, pct, coul)
rectangle_arrondi(t, x, y, larg, 14, 7, #E2E8F0)
lp est un nombre
lp vaut arrondi(larg * pct / 100)
si lp > 0 alors
rectangle_arrondi(t, x, y, lp, 14, 7, coul)
fin si
fin procédure
@ BOUCLE PRINCIPALE
tant que vrai
// =========================================================
// SIMULATION : le même bloc sert à la démo et au tournoi
// =========================================================
si relancer = vrai alors
relancer vaut faux
montre vaut 0
nbPaires est un nombre
nbParties est un nombre
enregistre est un booléen
si ecran = "demo" alors
parA[0] vaut ia1
parB[0] vaut ia2
nbPaires vaut 1
nbParties vaut 1
enregistre vaut vrai
sinon
parA[0] vaut 1
parB[0] vaut 2
parA[1] vaut 1
parB[1] vaut 3
parA[2] vaut 2
parB[2] vaut 3
nbPaires vaut 3
nbParties vaut NBMATCH
enregistre vaut faux
fin si
pour ip de 0 à nbPaires - 1
vA est un nombre
vB est un nombre
vN est un nombre
vA vaut 0
vB vaut 0
vN vaut 0
pour g de 1 à nbParties
// ---------- une partie complète ----------
pour k de 0 à 8
cel[k] vaut 0
fin pour
nbCoups vaut 0
issue vaut ""
// On alterne celui qui commence, pour que la mesure soit honnête
joueur est un nombre
joueur vaut 1
si g - arrondi_inferieur(g / 2) * 2 = 0 alors
joueur vaut 2
fin si
vainqueur est un nombre
vainqueur vaut 0
tour est un nombre
tour vaut 0
tant que vainqueur = 0 et tour < 9
// Quelle IA joue ce coup ?
niv est un nombre
si joueur = 1 alors
niv vaut parA[ip]
sinon
niv vaut parB[ip]
fin si
adv est un nombre
adv vaut 3 - joueur
choix est un nombre
choix vaut - 1
raison est un texte
raison vaut ""
// =================================================
// IA 1 : LE HASARD
// Aucune notion de jeu. Une case libre au hasard.
// =================================================
si niv = 1 alors
trouve est un booléen
trouve vaut faux
essais est un nombre
essais vaut 0
tant que trouve = faux et essais < 200
essais ajoute 1
c est un nombre
c vaut hasard(0, 8)
si cel[c] = 0 alors
choix vaut c
trouve vaut vrai
fin si
fin tant que
raison vaut "au hasard"
// =================================================
// IA 2 : QUATRE RÈGLES EN CASCADE
// 1 gagner 2 bloquer 3 centre 4 coin 5 bord
// =================================================
sinon si niv = 2 alors
// Règle 1 : puis-je gagner tout de suite ?
pour k de 0 à 8
si cel[k] = 0 et choix < 0 alors
cel[k] vaut joueur
gagnant est un nombre
gagnant vaut 0
pour L de 0 à 7
x est un nombre
x vaut cel[ln1[L]]
si x > 0 et cel[ln2[L]] = x et cel[ln3[L]] = x alors
gagnant vaut x
fin si
fin pour
cel[k] vaut 0
si gagnant = joueur alors
choix vaut k
raison vaut "je gagne en jouant là"
fin si
fin si
fin pour
// Règle 2 : l'adversaire gagnerait-il ici ?
si choix < 0 alors
pour k de 0 à 8
si cel[k] = 0 et choix < 0 alors
cel[k] vaut adv
gagnant vaut 0
pour L de 0 à 7
x vaut cel[ln1[L]]
si x > 0 et cel[ln2[L]] = x et cel[ln3[L]] = x alors
gagnant vaut x
fin si
fin pour
cel[k] vaut 0
si gagnant = adv alors
choix vaut k
raison vaut "je bloque l'adversaire"
fin si
fin si
fin pour
fin si
// Règles 3 à 5 : centre, puis coins, puis bords
si choix < 0 alors
pour k de 0 à 8
si choix < 0 et cel[prefer[k]] = 0 alors
choix vaut prefer[k]
si choix = 4 alors
raison vaut "je prends le centre"
sinon si choix = 0 ou choix = 2 ou choix = 6 ou choix = 8 alors
raison vaut "je prends un coin"
sinon
raison vaut "il ne reste qu'un bord"
fin si
fin si
fin pour
fin si
// =================================================
// IA 3 : LA SIMULATION
// Elle ne connaît aucune stratégie. Pour chaque
// case libre, elle finit la partie au hasard un
// grand nombre de fois et garde la case qui gagne
// le plus souvent.
// =================================================
sinon
meilleur est un nombre
meilleur vaut 0 - 99999
pctBest est un nombre
pctBest vaut 0
pour k de 0 à 8
si cel[k] = 0 alors
note est un nombre
note vaut 0
gagnes est un nombre
gagnes vaut 0
pour n de 1 à NBSIM
// On recopie la position et on la termine au hasard
pour q de 0 à 8
sim[q] vaut cel[q]
fin pour
sim[k] vaut joueur
qui est un nombre
qui vaut adv
fini est un nombre
fini vaut 0
coupsSim est un nombre
coupsSim vaut 1
// Y a-t-il déjà un gagnant après ce coup ?
pour L de 0 à 7
x vaut sim[ln1[L]]
si x > 0 et sim[ln2[L]] = x et sim[ln3[L]] = x alors
fini vaut x
fin si
fin pour
tant que fini = 0 et coupsSim < 9
libre est un nombre
libre vaut - 1
essais vaut 0
tant que libre < 0 et essais < 200
essais ajoute 1
c vaut hasard(0, 8)
si sim[c] = 0 alors
libre vaut c
fin si
fin tant que
si libre < 0 alors
coupsSim vaut 9
sinon
sim[libre] vaut qui
coupsSim ajoute 1
pour L de 0 à 7
x vaut sim[ln1[L]]
si x > 0 et sim[ln2[L]] = x et sim[ln3[L]] = x alors
fini vaut x
fin si
fin pour
qui vaut 3 - qui
fin si
fin tant que
si fini = joueur alors
note ajoute 2
gagnes ajoute 1
sinon si fini = 0 alors
note ajoute 1
fin si
fin pour
si note > meilleur alors
meilleur vaut note
choix vaut k
pctBest vaut arrondi(gagnes * 100 / NBSIM)
fin si
fin si
fin pour
raison vaut "simulation : " + pctBest + " % de parties gagnées"
fin si
// ---------- on joue le coup retenu ----------
si choix >= 0 alors
cel[choix] vaut joueur
si enregistre = vrai alors
histCase[nbCoups] vaut choix
histQui[nbCoups] vaut joueur
histTxt[nbCoups] vaut raison
fin si
nbCoups ajoute 1
fin si
// ---------- y a-t-il un alignement ? ----------
pour L de 0 à 7
x vaut cel[ln1[L]]
si x > 0 et cel[ln2[L]] = x et cel[ln3[L]] = x alors
vainqueur vaut x
fin si
fin pour
joueur vaut 3 - joueur
tour ajoute 1
fin tant que
si vainqueur = 1 alors
vA ajoute 1
issue vaut "Victoire du joueur 1"
sinon si vainqueur = 2 alors
vB ajoute 1
issue vaut "Victoire du joueur 2"
sinon
vN ajoute 1
issue vaut "Match nul"
fin si
fin pour
resA[ip] vaut vA
resB[ip] vaut vB
resN[ip] vaut vN
fin pour
fin si
// =========================================================
// AFFICHAGE
// =========================================================
effacer(vue)
contour(vue, #0)
remplir(vue, #EEF2F7)
rectangle_arrondi(vue, 12, 10, 676, 76, 14, #FFFFFF)
label(vue, 26, 40, "UNE IA SANS INTELLIGENCE", #B45309, 20)
label(vue, 26, 62, "Trois adversaires au morpion : aucun ne comprend le jeu, et pourtant…", #64748B, 12)
label(vue, 26, 80, "[A] IA 1 [Z] IA 2 [T] démo / tournoi [P] coup suivant [R] relancer", #2563EB, 11)
si ecran = "demo" alors
// ---------- LE PLATEAU ----------
rectangle_arrondi(vue, 12, 94, 330, 414, 14, #FFFFFF)
label(vue, 30, 122, "Joueur 1 : ", #DC2626, 13)
appelle nomIA(vue, 106, 122, ia1, #DC2626, 13)
label(vue, 30, 144, "Joueur 2 : ", #2563EB, 13)
appelle nomIA(vue, 106, 144, ia2, #2563EB, 13)
pour k de 0 à 8
lg est un nombre
cl est un nombre
lg vaut arrondi_inferieur(k / 3)
cl vaut k - lg * 3
xk est un nombre
yk est un nombre
xk vaut 46 + cl * 84
yk vaut 170 + lg * 84
rectangle_arrondi(vue, xk, yk, 76, 76, 10, #E7EDF5)
// On ne montre que les coups déjà joués
qui est un nombre
qui vaut 0
pour n de 0 à montre - 1
si histCase[n] = k alors
qui vaut histQui[n]
fin si
fin pour
si qui = 1 alors
cercle(vue, xk + 38, yk + 38, 24, #FCA5A5)
cercle(vue, xk + 38, yk + 38, 15, #E7EDF5)
sinon si qui = 2 alors
rectangle_arrondi(vue, xk + 16, yk + 34, 44, 8, 3, #93C5FD)
rectangle_arrondi(vue, xk + 34, yk + 16, 8, 44, 3, #93C5FD)
fin si
fin pour
label(vue, 30, 448, "Coup " + montre + " sur " + nbCoups, #0F172A, 13)
si montre >= nbCoups alors
label(vue, 150, 448, issue, #16A34A, 13)
fin si
label(vue, 30, 474, "Appuie sur [P] pour dérouler la partie", #94A3B8, 11)
label(vue, 30, 496, "Chaque coup affiche la raison qui l'a produit.", #94A3B8, 11)
// ---------- LE JOURNAL DES DÉCISIONS ----------
rectangle_arrondi(vue, 352, 94, 336, 414, 14, #FFFFFF)
label(vue, 370, 122, "POURQUOI CE COUP ?", #0F172A, 14)
pour n de 0 à nbCoups - 1
yn est un nombre
yn vaut 152 + n * 38
si n < montre alors
coulJ est un texte
si histQui[n] = 1 alors
coulJ vaut #DC2626
sinon
coulJ vaut #2563EB
fin si
label(vue, 370, yn, "Coup " + (n + 1) + " - joueur " + histQui[n] + ", case " + (histCase[n] + 1), coulJ, 12)
label(vue, 370, yn + 18, histTxt[n], #64748B, 11)
sinon
label(vue, 370, yn, "Coup " + (n + 1) + " - ?", #CBD5E1, 12)
fin si
fin pour
sinon
// ---------- LE TOURNOI ----------
rectangle_arrondi(vue, 12, 94, 676, 414, 14, #FFFFFF)
label(vue, 30, 124, "TOURNOI - " + NBMATCH + " parties par confrontation", #0F172A, 15)
label(vue, 30, 146, "Chacun commence à tour de rôle, pour que la mesure soit honnête.", #94A3B8, 11)
pour ip de 0 à 2
yp est un nombre
yp vaut 190 + ip * 96
appelle nomIA(vue, 30, yp, parA[ip], #DC2626, 14)
label(vue, 150, yp, "contre", #94A3B8, 12)
appelle nomIA(vue, 210, yp, parB[ip], #2563EB, 14)
pctA est un nombre
pctB est un nombre
pctN est un nombre
pctA vaut arrondi(resA[ip] * 100 / NBMATCH)
pctB vaut arrondi(resB[ip] * 100 / NBMATCH)
pctN vaut 100 - pctA - pctB
appelle barrePct(vue, 30, yp + 14, 300, pctA, #DC2626)
label(vue, 342, yp + 26, pctA + " %", #DC2626, 12)
appelle barrePct(vue, 30, yp + 36, 300, pctB, #2563EB)
label(vue, 342, yp + 48, pctB + " %", #2563EB, 12)
appelle barrePct(vue, 30, yp + 58, 300, pctN, #94A3B8)
label(vue, 342, yp + 70, pctN + " % nuls", #94A3B8, 12)
label(vue, 420, yp + 26, "victoires : " + resA[ip], #DC2626, 12)
label(vue, 420, yp + 48, "victoires : " + resB[ip], #2563EB, 12)
label(vue, 420, yp + 70, "nuls : " + resN[ip], #94A3B8, 12)
fin pour
label(vue, 30, 486, "Quatre règles écrasent le hasard. La simulation ne connaît aucune règle et fait aussi bien.", #B45309, 12)
fin si
affiche vue
// =========================================================
appuyer ["p", "a", "z", "t", "r"] dans touche
si touche = 1 alors
si montre < nbCoups alors
montre ajoute 1
fin si
sinon si touche = 2 alors
ia1 vaut ia1 + 1
si ia1 > 3 alors
ia1 vaut 1
fin si
relancer vaut vrai
sinon si touche = 3 alors
ia2 vaut ia2 + 1
si ia2 > 3 alors
ia2 vaut 1
fin si
relancer vaut vrai
sinon si touche = 4 alors
si ecran = "demo" alors
ecran vaut "tournoi"
sinon
ecran vaut "demo"
fin si
relancer vaut vrai
sinon
relancer vaut vrai
fin si
fin tant que
