Le modèle de couches de protocoles a été créé pour des besoins militaires (sécurisation des communications téléphoniques en situation hostile). Mais il est resté parce qu’il est basé sur l’usage de routeurs qui permet une grande interconnexion des machines numériques.

Avantages :

• décharge l’utilisateur d’avoir à regarder dans les couches inférieures (inutile par exemple de connaître l’adresse MAC de sa machine pour consulter un site web)
• souplesse par rapport aux mises à jour (le passage d’IPv4 à IPv6 est transparent pour l’utilisateur et n’exige pas de changer de machine.

Inconvénients :

• perte en efficacité (débit par exemple : relier un clavier à un synthétiseur par un câble MIDI permet un meilleur débit que d’avoir à passer par un serveur distant)
• risque accru de piratage (attaque de l’hommedu milieu par exemple).

Un protocole réseau est ... un protocole. Non ? Si, si ! Il a donc la même fonction que tout autre protocole, à savoir établir un moyen de transformer une communication en transfert d’information, par la définition d’un langage commun entre l’émetteur et le récepteur.

Dans un bar, chaque fois qu’un client a soif, il passe une commande (en général après un clic sur le bouton submit) auprès du serveur. Le serveur, une fois qu’il a reçu la commande, prépare la boisson (par exemple un jus d’ananas 🍍, en réalité une page web) puis la transporte (toujours en http) au client.

La fibre optique permet un débit particulièrement élevé, de l’ordre du gigabit par seconde.

l’ADSL permet un débit assez élevé aussi, de l’ordre des 10 Mbits/s

La liaison modem 56kbits/s offrait donc un débit bien plus bas...

Légende

Dans les salles équipées en informatique, les PC sont des clients. Chaque salle ou groupe de salles d’informatique est doté d’un ou plusieurs switchs.

Le rôle de switch est également assuré par chacune des bornes wifi offertes par le conseil régional. Indiana Jones est d’ailleurs toujours en train de les chercher, ces bornes wifi. Les clients étaient les ordinateurs eux aussi offerts par le conseil régional (à l’époque, maintenant ce sont des tablettes surface).

Le lycée est doté d’un serveur qui est relié par fibre optique à Internet. Ce serveur possède, bien évidemment, un pare-feu. Il est relié au serveur du rectorat qui est lui aussi doté d’un pare-feu.

L’objectif d’un protocole de transport, comme son nom l’indique, est d’assurer la livraison des paquets.

Avec TCP,

• le fichier est découpé en paquets
• chaque paquet est muni d’un entête comprenant entre autres
  • le destinataire
  • le numéro du paquet (nécessaire pour reconstruire le fichier après livraison des paquets)
  • une durée de vie (variable utilisée par les routeurs, voir section 3.2)

L’onglet problème de la jeep de cet article décrit une situation similaire (il s’agir d’un problème d’Alcuin datant du VIII^e siècle, où un chameau devait transporter du couscous au milieu du désert, en se nourissant d’une partie de sa cargaison. La quantité de couscous représente la durée de vie d’un paquet TCP).

Dans UDP, il n’y a pas d’accusé de réception ni de durée de vie des paquets. Cela rend le débit plus rapide que TCP, mais sans garantie temporelle.

Le protocole UDP est utilisé pour DHCP (voir question 14), le steaming (hors Youtube et Netflix) et les jeux vidéo dits « à la première personne ».

Le protocole TCP est utilisé pour le web, les mails et le téléchargement. Même Netflix utilise TCP, alors que pour le streaming UDP est plus intéressant.

On joue à ce jeu (le plateau de jeu est téléchargeable en cliquant sur l’image) :

Les pions sont initialement en bas, et chaque joueur à son tour lance le dé (commun aux joueurs). Selon le résultat du lancer, le dé avance ou recule. Le premier dont le pion est arrivé dans la zone verte a gagné le jeu. Les autres joueurs continuent à jouer pour établir un classement.

Ensuite on rejoue avec des pions numérotés. Chaque pion représente un paquet TCP. Le numéro 1 commence, ensuite le 2 etc. Lorsque les pions sont arrivés il se peut qu’ils soient dans le désordre. Il faut alors recoller les paquets pour avoir le fichier d’origine. Cette variante du jeu a déjà été décrite dans l’onglet transmission de données dans un réseau de cet article.

Enfin on rejoue avec des dés en guise de pion. Par exemple le dé blanc commence, ensuite le dé vert, enfin le dé bleu. Les dés sont initialement tournés face ⚅ vers le haut.

Par exemple le joueur blanc lance le dé commun, si le résultat est 3 le dé blanc va tout droit mais à chaque déplacement d’un pion, on le tourne. Ainsi le dé blanc représente maintenant ⚄. Ceci simule la durée de vie du paquet.

Ensuite le joueur vert lance le dé commun et si le résultat tombe sur 5 son dé (vert) va en haut à gauche du plateau, mais là encore c’est sous la forme ⚄.

Ensuite le joueur bleu lance le dé commun et si le résultat est 1 le dé bleu va à droite. Mais c’est ⚄.

Puis le joueur blanc rejoue, et si le dé commun donne 4 le dé blanc revient au départ. Mais c’est ⚃ qu’on voit au départ.

Puis le joueur vert lance le dé commun et si le résultat est 3 le dé vert va à l’arrivée : le joueur vert a gagné le jeu. Mais c’est ⚃ qu’on voit à l’arrivée.

Ensuite le joueur bleu lance le dé commun et si le résultat est 4 son dé (bleu) va en haut à droite. Mais c’est ⚃ qui est en haut à droite.

Ensuite le joueur blanc relance le dé commun, si le résultat est 5 son dé va en haut à gauche. Mais il tourne et c’est ⚂ qui est en haut à gauche.

Ensuite, le joueur vert ayant déjà gagné, c’est au tour du joueur bleu de jouer. Il lance le dé commun et si le résultat est 3 son dé (bleu) revient en bas à droite (sous la forme ⚂).

C’est alors au joueur blanc de rejouer, il lance le dé commun et si le résultat est 1 son dé revient en bas à gauche (sous la forme ⚁).

Puis le joueur bleu lance le dé commun et si le résultat est 5 son dé (bleu) va à l’arrivée : il a fini de jouer (il est second). À ce stade la ligne d’arrivée est ⚃⚁.

Le joueur blanc relance le dé commun, si le résultat est 6 le dé blanc va en haut à droite (tout proche de l’arrivée) mais sous la forme ⚀. Si un dé est face ⚀ vers le haut, il ne peut plus être joué. Le joueur blanc est donc bloqué et n’arrivera jamais à l’arrivée.

Ceci illustre que des paquets peuvent être perdus.

L’objectif principal d’un protocole de la couche réseau est d’assurer le routage.

Protocoles de routage

18

{ 'A': 'BF', 'B': 'ADE', 'C': 'EG', 
         'D': 'BG', 'E': 'BCF', 'F': 'AE',
        'G': 'CD'}

def en_largeur(graphe):
	visités = []
	à_voir = list(graphe.keys())
	while à_voir:
		S = à_voir.pop(0)
		if S not in visités:
			visités.append(S)
		for T in graphe[S]:
			if T not in visités:
				à_voir.append(T)
	return visités

Pour simuler un réseau, on peut utiliser CaRMetal. C’est un logiciel de géométrie dynamique qui permet donc de dessiner les réseaux à simuler, mais le travail collaboratif se fait par un réseau aussi !

Avantages de la simulation :

• praticable également en distanciel (pour les élèves ayant installé Filius ou analogue, sur leur poste)
• revient moins cher en équipement
• Possibilité de simuler sans danger une panne de routeur
• permet de découvrir le langage bash si un des appareils simulés est sous Unix
• évite aux services informatiques du rectorat et aux assistants informatiques du lycée une bonne dose d’arrachage de cheveux...

Inconvénients de la simulation :

• Elle ne mobilise pas le canal kinesthésique autant que le ferait une manipulation sur un vrai réseau
• Les icônes du logiciel ne sont pas toujours ressemblants. En particulier, on a du mal à imaginer la taille réelle d’un switch ou d’un routeur.
• Avec une activité en réel, l’un au moins des objets connectés peut être un robot que les élèves peuvent guider dans un labyrinthe une fois qu’ils connaissent son adresse IP.
• Certaines activités en réel permettent aussi aux élèves d’utiliser leur propre matériel (par exemple, trouver l’adresse IP de leur smartphone).

Plus le réseau est connexe, et plus le temps de transfert est réduit (les paquets pouvant transiter chacun par sa route donc en même temps). La nature des liaisons joue également un rôle : la fibre optique est réputée très rapide. La longueur des entêtes tend à ralentir aussi le transfert (plus il y a de paquets, plus il y a d’entêtes). Le taux d’occupation d’Internet joue également un rôle (on conseille de surfer plutôt la nuit). Si un paquet n’arrive pas à destination (durée de vie écoulée), un message d’erreur est envoyé à la source, qui renvoie ce paquet et uniquement celui-ci. En raccourcissant la durée de vie des paquets, on augmente donc la fréquence des renvois ce qui peut accélérer le transfert.

Mais la garantie temporelle n’est plus assurée si on envoie un seul (grand) paquet : il arrive ou il n’arrive pas. Alors que s’il y a beaucoup de paquets, on est certain qu’au bout d’un temps plus ou moins long ils arrivent tous (quitte à les réémettre). Cependant s’il y a trop de paquets, le risque est accru que 2 ou 3 d’entre eux ne parviennent pas à destination et cela bloque le téléchargement du fichier.

Le World Wide Web est un système hypertexte public couvrant le monde entier. Il fonctionne sur Internet et permet à des clients (navigateurs comme Internet Explorer, Safari, Konqueror, Opera, Chrome, Chromium ou Firefox etc) de charger et afficher des pages hypertexte au format Html.

Le World Wide Web a été inventé par Tim Berners-Lee en 1992, au CERN.

Voici les étapes d’une séquence pédagogique ayant servi à plusieurs reprises à introduire Html et Css en classe de SNT (élèves à profils variés) :

1. Introduction aux balises avec l’activité « pile html » de cet article.
2. Saisie du cours de SNT visible dans le même article) en html, avec prises de notes en html par les élèves.
3. Devoir maison de Css sur l’article 222-33-3-2 du code pénal (texte que les élèves doivent connaître) : le texte est remis en html aux élèves qui sont chargés de rendre sa lecture attractive et aisée à l’aide de Css (effet de bord : les élèves, en plus de la pratique de Css, ont lu le texte et le connaissent).
4. Devoir maison durant le confinement : écrire son journal en html

1. Parmi les langages suivants, lequel est un langage de programmation ?
Css
Html
Python
W3C

2. Parmi les balises suivantes, laquelle souligne le texte ?
La balise a
la balise b
la balise i
la balise u

3. Quel est le code Css qui écrit en rouge les titres de niveau 2 ?
h2 {background-color: red; }
h2 {color: red; }
h2 {text-color: red; }
titre {text-color(2): red; }

Pour la question 1, les distracteurs sont les langages du web (à une exception près, W3C qui n’est pas un langage. Le seul langage qui soit de programmation, est Python.

Pour la question 2, les questions ont été choisies parce qu’elles sont courtes (noms de balises peu explicites). Cela nécessite de faire le lien entre l’initiale du mot et le mot complet : a→anchor, b→bold, i→italic et u→underlined. La bonne réponse est donc u.

Pour la question 3, la propriété color désignant la couleur du texte, les autres réponses sont des distracteurs (background-color désigne la couleur de fond, text-color n’est pas reconnu dans Css). Text-color a été choisi deux fois pour éviter que trop d’élèves déduisent la réponse de statistiques sur l’ensemble des réponses.

Une URL typique s’écrit ainsi (on suppose que le protocole est https) :

https://site.sous-domaine.domaine/dossier/sous_dossier/page_web.html

La charnière est le domaine. Avant lui, on trouve éventuellement un sous-domaine, et encore des sous-sous-domaines éventuels, et au début, le site (et avant ça, le protocole).

Après le nom du domaine, on trouve un chemin Unix (dossiers - ou plutôt répertoires - contenant des dossiers contenant des fichiers).

Dans l’analogie proposée à la question 3, il faut un langage que comprennent à la fois le client et le serveur. C’est http ou https. Http est utilisé à la fois par le client pour commander sa boisson, et par le serveur pour apporter la boisson (une page html) au client. Noter que l’adresse du bar s’appelle action.

Lorsque le client (voir questions 5 et 27) commande une boisson c’est parce qu’il a soif, et qu’il souhaite avoir une boisson. Il utilise alors la méthode GET ce qui, à l’action (l’adresse du bar), ajoute ce code (si le client a choisi du jus d’ananas) :

 ?fruit_choisi=mananasy+🍍

La requête est alors seulement orale : un message envoyé au serveur. Dans l’exemple ci-dessus, la variable fruit_choisi prend la valeur mananasy.

Lorsque le client a fini sa consommation, il rappelle le serveur par une nouvelle requête, pour payer. Cette fois-ci il utilise la méthode POST parce qu’il donne de l’argent : la requête possède, en plus de son entête, un corps (l’argent que le serveur ramène au bar pour encaisser).

Un TP sur les formulaires proposé en première a consisté à faire une application de triche aux tests d’intelligence, que voici :

• Recopier à l’aide d’un éditeur de texte, le source du fichier, qui est

<!DOCTYPE html>
<html lang="fr">
<head>
<meta charset="utf-8">
</head>
<body>
    <h1>Test d'intelligence</h1>
<form action="https://oeis.org/search" method="get">
    Entrez ici les premiers termes de la suite, 
    séparés par des espaces : 
    <input type="text" name="q">
    <input type="submit" value="appel à l'expert">
</form>

</body>
</html>

• Enregistrer le fichier html puis l’ouvrir avec un navigateur (par exemple Firefox).
• Entrer une suite de nombres entiers séparés par des espaces (par exemple 1 3 6 10).
• Pour connaître le nombre suivant, cliquer sur le bouton submit.
• Regarder le contenu de la barre d’adresse du navigateur (par exemple https://oeis.org/search?q=1+3+6+10)
• Remplacer la méthode GET du formulaire par la méthode POST et refaire un test. Regarder l’effet obtenu par cette modification sur la barre d’adresse.

• Le chiffrement symétrique utilise une clé unique (selon le principe de Vernam), servant à la fois au chiffrement et au déchiffrement. L’algorithme utilisé est rapide ce qui permet d’utiliser ce genre de chiffrement pour la communication sécurisée. Mais la clé (WEP par exemple) doit être secrète pour que la sécurité soit assurée.
• Le chiffrement asymétrique (RSA par exemple) utilise une clé publique pour le chiffrement et une autre clé, privée car connue d’une seule personne, pour le déchiffrement. Dans RSA ce sont des exposants (65537 pour le chiffrement en général) et connaître la clé privée est possible en théorie mais impossible en pratique (il faut factoriser un grand nombre).
• Le protocole https utilise une paire de clés asymétriques pour échanger entre le client et le serveur une clé de chiffrement symétrique qui sera connue d’eux seuls. Le protocole de Diffie-Hellman propose ce schéma :
  • Alice engendre (aléatoirement) une longue clé de chiffrement asymétrique.
  • Alice chiffre cette clé à l’aide de sa clé publique et envoie le résultat à Bob.
  • Bob chiffre la clé chiffrée, à l’aide de sa clé publique à lui et envoie la clé surchiffrée à Alice.
  • Alice déchiffre le résultat à l’aide de sa clé privée, et obtient sa clé symétrique chiffrée par la clé de Bob.
  • Alice envoie le résultat à Bob.
  • Bob déchiffre ce résultat à l’aide de sa clé privée et obtient la clé de chiffrement symétrique. Alice connaît déjà cette clé puisqu’elle l’a engendrée, et la communication sécurisée peut commencer entre Alice et Bob.

Une activité ludique permettant de montrer le principe du chiffrement symétrique est celle-ci :

• aller sur le site Alkindi et cliquer sur entraînement.
• Choisir le sujet 2018-2019
• Choisir le jeu réseau de Feistel
• Faire les 3 niveaux du jeu [1]

• Enchaîner sur l’activité Python présentée au début de ce cours

Ces activités sont basées sur le triptyque manipuler-verbaliser-abstraire et les élèves sont attentifs parce qu’actifs. L’activité Alkindi est en lien avec l’histoire de l’informatique parce que le chiffrement DES est basé sur la notion de réseau de Feistel (datant des années 1970). Enfin, le caractère ludique de l’activité Alkindi est la garantie que les élèves sont tous concentrés et peuvent progresser chacun à son rythme dans l’activité.

Un moteur de recherche sert à trouver une ressource dans une base de données. Les moteurs de recherche sur le web suivent donc un modèle selon lequel le web est une base de données et servent à trouver une page web vérifiant certains critères.

Le web est modélisé par un graphe orienté. L’algorithme de Larry Page consiste à simuler une chaîne de Markov sur ce graphe (cliquer sur « jouer » puis sur le dé). Si le pion est bloqué sur un sommet sans successeurs, on le replace au hasard sur le graphe et on recommence. Cela donne des statistiques sur les visites de sommet : Le pagerank d’un sommet (page web) est d’autant plus grand que le sommet est souvent visité. Google affiche en premier les pages de rang élevé. Cette activité permet de comprendre le fonctionnement de l’algorithme en mode débranché.

Un exposé peut servir, dès la 2^nde, à préparer les élèves au Grand Oral. Par conséquent, la grille du BO peut servir à évaluer un exposé.

Une base de données est adaptée à la gestion d’une bibliothèque parce que tant les livres que les lecteurs sont décrits, du point de vue du bibliothécaire, par des attributs. D’autre part il est nécessaire de pouvoir effectuer des modifications de la base de données (retrait d’un livre s’il est emprunté, inscription d’un nouvel utilisateur).

Deux langages semblent approriés :

• Php, qui gère les formulaires Html (au programme de 1^re) et est déjà très utilisé pour les interfaces avec les bases de données,
• Python3, grâce à son module Flask, rend les mêmes services,
• Python, qui est le langage au programme, et qui possède un module sqlite3 permettant de communiquer avec la base de données.

Dans ce dernier cas, la bibliothèque (ou module) Tkinter est intéressante, parce que d’une part elle a probablement déjà été utilisée par les élèves lors d’un autre projet, d’autre part elle est basée sur la programmation objet, qui est au programme de Tle.

En allant sur MoCoDo, et en entrant ce code :

livres: id, titre, auteur, ann_publi
emprunts, 1N livres, 1N eleves: debut, fin
eleves: id, nom, prenom, classe

On obtient le document 13 de l’énoncé :

Alors que si on entre

livres: id, titre, auteur, ann_publi
emprunts: debut, fin
eleves: id, nom, prenom, classe

on obtient le document 14 de l’énoncé :

Dans le modèle entité-association, emprunts est considéré comme une association alors que livres et eleves sont des entités. Dans les tables implémentées par l’élève, il n’y a pas d’association. Ce dont l’élève n’a pas tenu compte ce sont les relations entre les trois tables, matérialisées par exemple par le rajout de clés étrangères à emprunts (par exemple livres.id et eleves.id).

Si des élèves mènent un projet sur les bases de données, il sera plus efficace de se baser sur leur exemple pour présenter le concept de clé étrangère. On présente rapidement à l’ensemble de la classe l’état de leur projet et on cite l’exemple de la table emprunt pour donner les deux clés étrangères :

Une entrée de la table emprunt ne peut pas contenir que les attributs debut et fin : il faut aussi savoir qui a emprunté le livre, et quel livre a été emprunté.
Or il se trouve que ces informations sont déjà disponibles, dans les tables eleves et livres. On peut donc les récupérer depuis ces tables.
L’objet d’une clé étrangère est de créer une liaison entre deux tables, en permettant de récupérer par exemple la clé eleves.id de la table eleves depuis la table emprunts. C’est parce que la clé est déjà dans une autre table (eleves) qu’on la qualifie d’étrangère.

Pour éviter que les élèves se consacrent exclusivement à la partie sur Tkinter, il vaut mieux ne pas donner trop de points sur la maîtrise de l’interface et l’annoncer dès le début aux élèves. Tenir compte de la cohérence de la base de données, des références au cours, de la liaison entre la base de données et l’IHM, de la régularité de la tenue du journal, de l’efficacité du travail collaboratif voire de la qualité de la présentation orale du projet.

On se refère au texte d’Édouard Lucas sur les labyrinthes : si on regarde les couloirs du labyrinthe plutôt que les murs, on a un graphe. Le parcours en profondeur de ce graphe donne un arbre couvrant du graphe.

Si on évite les carrefours à 4 issues, l’arbre est binaire.

On propose donc de commencer par ce labyrinthe :

En traçant les lignes médianes des couloirs on a (en rouge) le graphe, qui est déjà un arbre (on dit que le labyrinthe est parfait, c’est-à-dire qu’il n’y a pas de cycles) :

Si on enlève les murs du labyrinthe, on voit mieux l’arbre :

C’est en ajoutant les nœuds de l’arbre et en les étiquetant par les trajets, qu’on vérifie que l’arbre est binaire :

Pour obtenir le nom du parent d’un nœud, il suffit d’enlever la dernière lettre de son nom. Par exemple le parent de gddg est gdd. Ainsi, chaque nœud a au maximum deux enfants, dont le nom s’obtient en ajoutant, au nom du nœud, ou bien « g », ou bien « d » : l’arbre est bel et bien binaire. Le choix entre « g » et « d » a été fait plus ou moins au hasard, pour donner à l’arbre une allure à peu près équilibrée. On aurait pu le faire en version tortue : « g » pour l’enfant qui est à gauche de la tortue au moment où elle arrive, « d » pour l’enfant qui est à sa droite.

Alors, chercher la sortie du labyrinthe, c’est effectuer un parcours depuis la racine (en jaune) vers une des feuilles (en vert). En l’occurrence la feuille dggg dont le nom signifie que pour sortir du labyrinthe, il faut aller à droite puis 3 fois à gauche.

Le parcours en largeur est celui effectué par une fourmilière ou un blob (biologie) : en partant de la racine, on envoie plein de monde (ou de signaux, ou de tentacules) dans tous les sens possibles, et lorsque des fourmis sont sorties, elles envoient des messages vers celles qui les suivent, lesquelles transmettent les messages vers leurs suiveuses etc. et en même temps les fourmis qui sont dans une impasse envoient leurs message vers celles qui les suivent etc.

Le parcours en profondeur est celui décrit par Édouard Lucas. Il permet aussi de trouver la sortie mais n’est pas parallélisable.

Pour quelque raison mystérieuse, l’algorithme minimax de Von Neumann a été rebaptisé min-max, au mépris de la syntaxe Python qui n’admet pas le tiret « - » dans un nom de fonction (min-max sera interprété par Python comme une soustraction, entre min et max).

L’énoncé définit la fonction min-max sur une représentation de l’arbre par ensembles d’adjacence (via la fonction situations-atteignables) et non par listes d’adjacences. C’est une manière très logique de représenter un graphe en Python, mais elle n’est pas très classique.

Version 1

Nous sommes en pleine partie de TicTacToe contre AlphaTTT, une IA redoutable. La situation s’appelle A, et c’est au tour de AlphaTTT de jouer. Il a 3 coups possibles qui débouchent sur les situations B, C et D.
Chacune d’elles conduit à deux nouvelles situations qui elles-mêmes débouche chacune à une situation finale. Les situations finales sont énumérées de K à V sur le graphe ci-dessous qui résume les fins possibles de cette partie :

C’est AlphaTTT qui dessine ce graphe dans sa tête (je vous l’ai dit il est très fort)... sur les configurations finales il a fait apparaitre des -1, 0, 1 qui correspondent respectivement à une défaite de sa part (une victoire pour son adversaire donc), une partie nulle et une victoire pour lui.

Comment faire remonter ses informations ?

Prenons la situation E : elle mène soit à K où AlphaTTT gagne soit à L qui est une partie nulle.
Mais qui décide ici si on va aller vers K ou vers L ? Repartons du début : en A c’est AlphaTTT qui joue, donc en B c’est moi et en E c’est AlphaTTT, qui choisira donc la situation K, celle où il gagne.
S’il y avait eu plusieurs situations ça n’aurait pas changé le raisonnement : AlphaTTT aurait choisi la situation avec une valeur d’évaluation maximale. C’est exactement ce que font dans l’algorithme du min-max les lignes 6 et 7.
Prenons la situation C où ce sera à moi de jouer. Si je choisis G, AlphaTTT aura le choix entre O ou P, deux situations perdantes pour lui. Je vais donc choisir cette situation qui me garantit une victoire. Et s’il y avait eu plusieurs situations, j’aurai, ou plutôt AlphaTTT suppose que j’aurai choisi celle avec une valeur minimale c’est-à-dire la pire pour lui. C’est le sens des lignes 8 et 9.
Dans l’algorithme, comme dans une vraie partie il ne faut pas sous-estimer son adversaire et raisonner en supposant toujours qu’il ou elle fera le meilleur coup.
Ainsi, lorsqu’on est sur un nœud du graphe (une situation), si c’est l’IA qui joue (AlphaTTT) alors on associe au nœud le maximum des valeurs associées aux nœuds en-dessous et si c’est l’humain on associe le minimum :

• la ligne K à V : ce sont les situations finales, on associe 1 quand l’IA gagne, -1 quand elle perd et 0 en cas de nul ;
• la ligne E à J : on remonte le max (c’est l’IA qui choisit)
• la ligne B, C, D : on remonte le min (c’est l’humain qui choisit)
  Et en A, AlphaTTT choisit le max c’est-à-dire la situation B qui emmène au mieux (pour lui) à une partie nulle. Au mieux signifie que si l’adversaire (moi) joue ses meilleurs coups AlphaTTT ne pourra pas faire mieux que partie nulle. Mais attention à la moindre erreur de ma part (choisir E par exemple) la réponse d’AlphaTTT sera sans appel (K et victoire pour lui) !

Version 2

On propose de montrer le fonctionnement de l’algorithme sur cet exemple :

L’IA joue les « X » et l’humain joue les « O ». C’est donc l’IA qui a commencé le jeu. Dans un premier temps, on a évalué le minimax sur les feuilles de l’arbre (parties terminées) avec un -1 s’il y a un alignement de « O » (car alors l’humain a gagné), un 1 s’il y a un alignement de « X » (car alors l’IA a gagné) et un 0 si le tableau est rempli sans aucun alignement (match nul). Du point de vue du joueur humain (les « O ») l’évaluation devient

Si l’IA peut obtenir un alignement XXX alors, comme l’IA joue au mieux, la position depuis laquelle cet alignement vaut aussi -1 du point de vue humain. Ce qui permet de remplir (toujours du point de vue du joueur humain) l’avant-dernier niveau de l’arbre (ligne 7 de l’algorithme) :

Il suffit, à ce stade, de changer les signes pour revenir au point de vue de l’IA :

Recopier une valeur depuis l’enfant du nœud ne suffit plus : il y a plusieurs enfants. Alors l’IA fait l’hypothèse que l’humain aussi joue au mieux, et va systématiquement essayer de minimiser le minimax. L’IA va alors donner à chaque nœud une valeur égale au minimum des valeurs de ses enfants (ligne 9 de l’algorithme) :

Parmi les 3 enfants de la racine de l’arbre, l’IA a donc intérêt à jouer le troisième qui lui garantit au moins la partie nulle (les deux autres risquant de la faire perdre). La valeur de la racine est donc le maximum (ligne 7) des valeurs de ses enfants, soit 0.

Pour que les élèves réussissent à programmer l’algorithme en Python, il peut être nécessaire de leur préciser que cet algorithme est récursif.

À chaque étape, l’ordinateur choisit le mouvement le moins mauvais pour lui (maximum) parmi les possibilités. Son jeu est donc optimal (il garantit au minimum la partie nulle parce que max(0,-1)==0).

1. au début, l’IA a 9 possibilités pour placer un X
2. ensuite l’humain a 8 possibilités pour placer un O
3. puis l’IA peut placer un X dans une des 7 cases libres
4. puis l’humain peut placer un 0 dans 6 cases possibles
5. puis l’IA peut placer un X dans 5 cases qui restent
6. puis l’humain peut placer un O dans une des 4 cases restantes
7. puis l’IA a 3 choix pour un X
8. puis l’humain a deux choix pour son dernier O
9. et l’IA finit par un X (s’il n’y a pas déjà eu alignement avant).

La hauteur de l’arbre ne dépasse donc pas 9 et il n’y a pas plus de 9 ! = 362 880 nœuds dans l’arbre. En fait l’arbre n’est pas un arbre (par exemple si l’IA joue d’abord au nord-est puis l’humain au centre puis l’IA au nord-ouest, on a exactement la même position que si l’IA jouait d’abord au nord-ouest puis l’humain au centre puis l’IA au nord-est). Voir Berlekamp, Conway et Guy pour une esquisse de ce graphe. Le graphe n’a que 304 sommets si on tient compte des symétries.

Remarque : L’algorithme du minimax n’est pas le seul, on peut aussi faire appel à un algorithme qui apprend.

On suppose que c’est l’IA qui joue en premier, en mettant un X en plein centre (c’est le meilleur coup). Alors on essaye

1. de jouer au centre (impossible car déjà joué par l’IA) pour vérifier que le programme ne permet pas cela.
2. de jouer mal (en haut au milieu puis en bas au milieu par exemple) pour vérifier que le programme joue gagnant (une diagonale)
3. de jouer au mieux (un angle puis empêcher l’IA de compléter un alignement) pour vérifier que l’IA arrive à une partie nulle.

Il faut éviter de donner trop de poids à la partie sur l’IHM Tkinter car cela aboutirait à ce que les élèves ne travaillent que cette partie. Il faut évidemment les en prévenir rapidement. C’est la programmation de l’algorithme minimax qui est cruciale ici : présence de commentaires, usage correcte de la récursivité, utilisation pertinente des fonctions min et max de Python...

Une grille d’évaluation pour l’épreuve pratique est donc appropriée pour ce sujet.