IA et Python

à la recherche d’une stratégie gagnante
dimanche 25 novembre 2018
par  Alain BUSSER , Sébastien HOARAU

Le langage Python est très pratiqué en IA en particulier pour le deep learning (apprentissage profond). On va montrer ici comment Python permet de trouver une stratégie gagnante à un jeu : Le jeu des deux parkings.

PNG - 63.6 ko

Historique du jeu

Ce jeu a été créé il y a 2 ans (fin juillet 2016) :

HTML - 4.4 ko
jeu péï
jeu à deux joueurs, chacun ayant 3 pions

À la rentrée suivante, il a été intégré à l’atelier « jeux mathématiques » de l’IREM et imprimé pour les animations de l’IREM :

PDF - 132.6 ko

Ce jeu a donc été exploré, par des joueurs humains (parfois très jeunes, voire plus jeunes que la créatrice du jeu), à ces occasions :

Ces explorations n’ont pas permis de dégager une éventuelle stratégie gagnante ni pour les bleus ni pour les rouges. Il semblerait même que lorsque les deux joueurs jouent défensif, on aboutisse à une partie nulle. Par contre la victoire par blocage de l’adversaire, même si elle est rare, peut survenir et pourrait être la clé d’une stratégie gagnante.

Des généralisations du jeu sont jouables à la partie « jeu des parkings » de ce site. Elles n’éclairent pas vraiment sur la question puisque dans la version 1×1, les bleus n’ont d’autre choix que bloquer les rouges, il en est de même pour la version 1×2, mais par contre la version 2×1 semble comporter une stratégie gagnante pour les rouges ...

Démarche bayésienne

Une première idée est de faire jouer la machine contre elle-même, au hasard, et regarder quels sont les premiers coups ayant donné la victoire aux rouges, mais aussi si la victoire par blocage apparaît souvent comparée à la victoire par rapidité dans la course. Pour cela on va simuler le jeu au hasard en Python. Et pour cela, il faut d’abord trouver comment on représente le graphe en Python. Par l’expérience de codingame, c’est sous forme de liste de listes (de sommets voisins) que le graphe sera représenté. Avec la numérotation [1] visible dans le chapeau de cet article, le graphe est décrit ainsi :

graphe = [[1,3,5],[2,6],[4,7],[6],[6],[6,10],[7,8,9,11],[12],[10],[12],[11],[12],[]]
def voisins(a,b):
    return a in graphe[b] or b in graphe[a]

Pour économiser, on n’a représenté chaque arête qu’une fois, et la fonction voisins(a,b) tient compte de la symétrie dûe au fait que le graphe est non orienté : Pour que a et b soient voisins, il faut que, ou bien a soit dans graphe[b], ou bien que b soit dans graphe[a]. On remarque que la fonction voisins est booléenne. Ce genre de fonctions facilite la rédaction d’un programme Python qui soit proche de la langue naturelle.

On utilisera 4 variables globales : bleus qui est la liste des sommets où se trouvent actuellement les trois voitures bleues, rouges qui est la liste des positions des voitures rouges, coupsbleus qui est la liste des mouvements des voitures bleues lors du jeu, et coupsrouges qui contiendra l’historique des mouvements rouges :

bleus = [0,1,2]
rouges = [10,11,12]
coupsbleus,coupsrouges = [],[]
def vide(sommet):
    return sommet not in bleus and sommet not in rouges

Dire qu’un sommet du graphe est vide, c’est dire qu’il ne figure ni dans la liste des positions des voitures bleues, ni dans celle des voitures rouges. Là encore, il s’agit d’une fonction booléenne, qu’il aurait peut-être été plus judicieux de nommer est_vide que vide. Les fonctions booléennes suivantes disent si les bleus (respectivement, les rouges) peuvent mener une voiture de a vers b : Cela signifie qu’il y a une voiture en a, que le sommet b est vide (sinon on ne peut pas y ajouter la voiture qui est en a) et que les sommets sont adjacents :

def bleupeut(a,b):
    return a in bleus and voisins(a,b) and vide(b)
def rougepeut(a,b):
    return a in rouges and voisins(a,b) and vide(b)

Les fonctions précédentes permettent de définir de manière proche du langage naturel, la liste des coups possibles pour les bleus : C’est la liste des couples de sommets a et b tels que bleupeut(a,b) :

def choixbleus():
    return [(a,b) for a in bleus for b in range(13) if bleupeut(a,b)]
def choixrouges():
    return [(a,b) for a in rouges for b in range(13) if rougepeut(a,b)]

Avec ces fonctions, on peut programmer la manière dont les bleus jouent au hasard (le module random a été importé au début du script) : Ils choisissent au hasard (avec choice du module random) un couple (début,fin) de sommets qu’ils peuvent jouer (autrement dit, un coup jouable au hasard) ; puis

  • ils enlèvent (« remove ») la voiture du sommet début puisqu’elle démarre son périple vers la fin du coup ;
  • ils placent (« append ») la voiture sur le sommet fin
  • ils trient (« sort ») dans l’ordre croissant la liste bleus
def bleusjouent():
    if not rougesgagnent():
        debut,fin = choice(choixbleus())
        bleus.remove(debut)
        bleus.append(fin)
        bleus.sort()

Mais tout ceci, ils ne doivent pas le faire si les rouges ont gagné. Pour savoir si les rouges ont gagné, on regarde si leurs trois voitures sont arrivées ou s’il n’y a aucun choix possible pour les bleus :

def bleusgagnent():
    return bleus==[10,11,12] or len(choixrouges())==0
def rougesgagnent():
    return rouges==[0,1,2] or len(choixbleus())==0
def fini():
    return bleusgagnent() or rougesgagnent()

On en a profité pour définir un test de fin du jeu : Le jeu est fini lorsque l’un des joueurs a gagné. À ce stade, rien ne prouve que la durée de vie du jeu est finie, il peut très bien y avoir des situations de jeu qui se répètent à l’infini, et dans ce cas il faudra annoncer la partie comme nulle (il n’est donc pas certain qu’il y ait une stratégie gagnante, puisqu’il peut y avoir une sorte de ko (go)). Pour simuler une partie il suffit maintenant de faire ceci :

while not fini():
    rougesjouent()
    bleusjouent()

Voici comment on peut jouer aléatoirement à ce jeu :

Zip - 557 octets

Les expériences menées avec ce script permettent déjà de constater quelques surprises :

  • Lorsque les deux joueurs jouent totalement au hasard, les bleus gagnent dans environ 40% des cas ; le graphe des configurations de jeu donne 42% des cas, en effet il y a 55 configurations gagnantes pour les bleus contre 76 pour les rouges.
  • Lorsque les bleus gagnent c’est toujours en allant plus vite que les rouges et jamais en bloquant ceux-ci ;
  • par contre lorsque les rouges gagnent, c’est dans presque le quart des cas, par blocage.
  • Parmi les premiers coups possibles des rouges, aucun ne semble mener plus souvent que les autres, à une défaite. Plus précisément,
    • La probabilité que les rouges aient joué la voiture du milieu sachant qu’ils ont gagné est environ 0,2. Cela peut surprendre mais en commençant par la voiture du milieu les rouges font un choix parmi 5
    • Les destinations 5, 6, 7, 8 et 9 sont équiprobables, sachant que les rouges ont gagné.
    • Par contre la probabilité que les rouges aient joué la voiture du milieu sachant qu’ils ont vaincu les bleus par blocage est plus élevée : environ une chance sur 4.

Cela suggère déjà un conseil pour les rouges : Commencer par mettre la voiture du milieu sur le sommet central, puis essayer à partir de là, de bloquer les bleus. Mais le jeu totalement au hasard éclaire peu sur les meilleurs choix des deux joueurs, il faut donc aller plus loin ; pour cela on a deux directions : Jouer moins au hasard (comme les joueurs humains qui reculent rarement), ou faire le graphe du jeu et repérer dans ce graphe les configurations gagnantes pour les rouges.

Jouer moins au hasard

Le problème avec les marches aléatoires sur le graphe, c’est qu’elles tendent à durer longtemps. Ceci est dû au fait que les deux joueurs reviennent souvent en arrière reproduisant ainsi une situation de jeu déjà présente. On peut donc explorer l’espace du jeu plus rapidement si chacun des joueurs joue un peu moins au hasard.

Tout d’abord, on propose de remplacer la fonction

def bleusjouent():
    if not rougesgagnent():
        debut,fin = choice(choixbleus())
        bleus.remove(debut)
        bleus.append(fin)
        bleus.sort()

par

def bleusjouent():
    if not rougesgagnent():
        debut,fin = bluechoice(choixbleus())
        bleus.remove(debut)
        bleus.append(fin)
        bleus.sort()

ce qui oblige à écrire une fonction bluechoice spéciale pour les bleus. Et de même une fonction redchoice pour les rouges, à la place de choice, mais a priori pas la même puisque les mouvements intéressants pour les rouges ne sont pas les mêmes que les mouvements intéressants pour les bleus (ils ne vont pas dans le même sens).

Avec la fonction

def bluechoice(liste):
    return choice(liste)

on a évidemment la même marche aléatoire qu’auparavant. Il en sera de même avec

def bluechoice(liste):
    return liste[randrange(len(liste))]

qui fabrique un indice aléatoire avec randrange puis prélève un élément de la liste pointé par cet indice. Maintenant, on peut modifier la fonction ci-dessus pour que les bleus choisissent plus souvent un sommet de numéro élevé qu’un retour en arrière. Pour cela, on utilise la fonction triangular qui simule une variable aléatoire de distribution affine par morceau : Elle part de 0 pour aller linéairement vers le nombre d’éléments de la liste, puis y rester (le dernier argument de la fonction est le mode de la loi de cette variable, les deux premiers sont les bornes de l’intervalle de définition). Mais pour avoir un indice de lecture dans une liste, il faut convertir ce nombre en un entier, ce qui se fait avec la fonction int :

def bluechoice(liste):
    return liste[int(triangular(0,len(liste),len(liste)))]

La fonction de choix aléatoire pour les rouges est aussi affine mais cette fois-ci on choisit 0 comme mode (statistiques) pour que les rouges aient tendance à aller plus vers les sommets de numéro faible (leur lieu de destination) :

def redchoice(liste):
    return liste[int(triangular(0,len(liste),0))]

Voici un exemple de jeu ainsi simulé [2] :

On voit que la partie ressemble beaucoup à un jeu mené entre humains plus ou moins débutants. Et encore une fois, c’est en bloquant les bleus, que les rouges gagnent relativement vite.

Pour produire des dessins animés comme ceux de cet article, et pour peu que le module graphviz soit installé, on peut utiliser le script que voici :

Zip - 926 octets

En augmentant la probabilité d’avancer par rapport à la probabilité de reculer, et en sélectionnant les parties les plus courtes se soldant par un blocage des bleus par les rouges, on obtient ce genre de jeu où les rouges gagnent en 25 coups :

L’animation ci-dessus tourne en boucle, si on attend suffisamment longtemps. N’a-t-on pas l’impression, en la regardant, que les deux joueurs et surtout les rouges font parfois des coups subtils ?

L’inférence bayésienne n’ayant pas donné de stratégie gagnante, on doit aller plus loin vers le deep learning avec un réseau bayésien. Comme le plateau de jeu est relativement petit, on va se contenter d’un graphe du jeu.

Exploration exhaustive

Une première, et essentielle, question qui se pose, est « comment va-t-on le représenter, ce fameux graphe ? »

Avec des triplets

La recherche d’une stratégie gagnante n’est pas si simple. Puisque le jeu est relativement petit nous avons écrit un script permettant de construire la totalité des configurations de jeu possibles : 34188 au total.

Une configuration de jeu est complètement définie par les positions de Rouge, celles de Bleu et par le joueur qui doit jouer. On pourrait coder en utilisant par exemple les tuples de Python :

Ainsi

((10, 11, 12), (0, 1, 2), 0)

représente la configuration initiale, et c’est à Rouge (modélisé par 0) de jouer. Les configurations atteignables à partir de celle-là sont :

((6,10,12), (0,1,2), 1)
((7,10,11), (0,1,2), 1)
((9,10,11), (0,1,2), 1)
((5,11,12), (0,1,2), 1)
((8,11,12), (0,1,2), 1)

Or « atteignable » se modélise par des arêtes dans un graphe orienté, dont voici le début :

PNG - 13.2 ko

Nous pouvons donc construire un graphe orienté de 34188 sommets et dont les arêtes représentent le passage possible d’une configuration A à une configuration B par un coup valide. En voici un extrait :

PNG - 964.5 ko

L’étude des ces 34188 configurations a révélé les 76 configurations gagnantes pour Rouge et les 55 pour Bleu. Ce qui explique dans les parties aléatoires les 42% de victoires pour Bleu contre 58% pour Rouge.

Parmi ces 76 configurations gagnantes pour Rouge il y a les 12 configurations où Bleu est bloqué (comme celle présentée sur l’animation précédente).

Dessiner le graphe en entier n’est pas très utile, on n’y verrait pas grand-chose avec 34188 sommets. C’est un problème typique des Big data, sur lesquelles il faudrait raisonner directement plutôt qu’un dessin exhaustif. Mais déjà, pour raisonner sur des Big Data, on doit d’abord se les procurer, ces « Big » Data ! Le format Json est approprié.

Python dispose d’un module json permettant de traduire de et vers une relation (mathématiques), ou « dictionnaire » en Python, ou JSON sur le ouèbe [3].

Avec des ensembles de sommets

Ce graphe a été modélisé par ses listes d’adjacences, en utilisant un dictionnaire et des ensembles (la structure de données set de Python est vraiment intéressante, nous y reviendrons à la fin de cet article) :

all_configs = { '10,11,12,0,1,2,0' :
{ '6,10,12,0,1,2,1',
  '7,10,11,0,1,2,1',
  '9,10,11,0,1,2,1',
  '5,11,12,0,1,2,1',
  '8,11,12,0,1,2,1'
},
... }

Nous avons abandonné les tuples au profit des chaînes de caractères. En effet une fois ce graphe calculé, nous l’avons stocké dans un fichier texte au format de données json. 0r ce format n’accepte pas les tuples comme clé des dictionnaires. D’où le choix des str.

Il est alors très simple de stocker notre graphe dans un fichier :

import json
with open(mon_fichier.json, 'w') as f_out:
        json.dump(all_configs, f_out, indent=3)

Le paramètre indent est facultatif mais facilite la visualisation du fichier dans un éditeur de texte. La récupération de notre graphe est tout aussi simple [4] :

import json
with open(mon_fichier.json) as f_in:
        all_configs = json.load(f_in)

Le fichier final est disponible ci-dessous [5] :

Zip - 623.3 ko

Sa création repose sur un parcours en largeur du graphe dont on parlait. On part de la configuration initiale et on génère toutes les configurations atteignables à partir de celle là. Puis on traite chacune de ces configurations de la même façon et ainsi de suite. Il faut bien sûr conserver une trace des configurations visitées pour ne pas les traiter deux fois. Le processus s’arrête quand on n’a plus de configurations à traiter.

Au départ nous pensions, avec ce graphe, pouvoir coder une stratégie privilégiant le choix d’une configuration qui minimiserait la distance à une configuration gagnante. Cette stratégie s’est avérée inefficace, se soldant par des parties très longues (les deux joueurs campent sur leurs positions). Lorsque Rouge adopte cette stratégie et que Bleu joue au hasard, Bleu gagne presque systématiquement : en fait Rouge change constamment d’objectif. Peut-on y voir là un clin d’œil : la persévérance paie.

Les tests effectués nous ont persuadés que la stratégie la plus efficace pour Rouge est d’essayer de bloquer Bleu plutôt que de le prendre de vitesse. Cette observation a déjà été constatée par les joueurs humains.

En codant la stratégie qui consiste à augmenter la probabilité d’avancer, on constate que Rouge gagne un peu moins souvent qu’avant (52%) et les victoires de Rouge par blocage représentent moins de 4% (contre 25% dans les parties aléatoires).

Gagner par étouffement

Comme pressenti, la stratégie consistant à vouloir réduire systématiquement les degrés de liberté de Bleu pour tenter d’aller vers une victoire par blocage, est efficace.

Application de la théorie des ensembles

Notons qu’avec la structure de données set le calcul des degrés de liberté d’une configuration se fait très simplement par différence ensembliste :

Si on prend

  • POS_ROUGE = l’ensemble des positions occupées par Rouge,
  • POS_BLEU celles occupées par Bleu,
  • S_ROUGE = l’ensemble des positions atteignables à partir des positions de Rouge,

alors le nombre de libertés est le cardinal (« len » en Python) de cet ensemble :

S_ROUGE - POS_ROUGE - POS_BLEU.

Avec cette stratégie, Bleu qui joue au hasard perd dans 100% des cas, et toujours par blocage. En voici un exemple :

Bien sûr, si Bleu ne joue pas au hasard, on retombe sur le problème des parties interminables et la nécessité de modifier les règles pour interdire le trop grand nombre de répétitions. On peut pour cela s’inspirer de la règle du ko (go)...

Conclusion

L’IA de Python ne nous a pas permis de trouver une stratégie permettant à Rouge de gagner à coup sûr [6], mais la quête d’une telle stratégie s’est révélée intéressante en elle-même et nous a permis de voir, par la pratique, à quoi ressemblent les bases de l’IA en Python, et quelles sont ses limites.

Voici le graphe du parcours effectué :

PNG - 58.3 ko

En guise d’exercice, vous pouvez essayer, avec les outils présentés ici, de chercher qui gagne à la version étendue du jeu, et comment (existe-t-il une stratégie gagnante pour l’un des joueurs ?)

Voici le jeu étendu :


[1faite à l’aide de cette application.

[2fabriqué à l’aide de graphviz qui dessine et colorie le graphe du jeu avec une fonction de ce genre :

def colorieGraphe(numero):
    g = Graph(format='png')
    g.body.extend(['rankdir=LR','size="2"'])
    for n in range(13):
        if n in bleus:
            g.node(str(n),' ',shape='circle',color='blue',style='filled')
        elif n in rouges:
            g.node(str(n),' ',shape='circle',color='red',style='filled')
        else:
            g.node(str(n),' ',shape='circle')
    for i in range(13):
        for j in range(i,13):
            if voisins(i,j):
                g.edge(str(i),str(j))
    g.render('g'+str(2000+numero),view=False)

[3Est-ce un hasard ? Bien que programmé en CoffeeScript plutôt qu’en Python, le logiciel Nirina974 utilise lui aussi le format Json pour représenter les graphes

[4Mais il est commode de convertir en ensembles avec

for config in all_configs:
    all_configs[config] = set(all_configs[config])

ce qui revient à « mapper » la fonction set (de conversion en ensembles) sur la structure all_configs.

[5Pesant 5,4 Mio, il est relativement long à ouvrir. Vous vouliez des Big Data ? Vous êtes servis !

[6Par contre il semble que Bleu puisse, en jouant assez finement, se garantir une partie nulle, sauf à changer les règles du jeu pour prévenir ce genre de « blocage »


Commentaires

Annonces

Prochains rendez-vous de l’IREM

Séminaire EDIM-IREM

- Mercredi 13 février 2019, 14h-18h, campus du Tampon.
- Mercredi 6 mars 2019, 14h-18h, PTU, Saint-Denis, salle S23.6.
- Mercredi 10 avril 2019, 14h-18h, campus du Tampon.

Colloque EDIM-IREM

- Mercredi 5 juin 2019, 9h-12h et 14h-17h, Saint-Denis.

Fête de la science

- Du 10 au 18 novembre 2018. Thème : « Idées reçues ».

Semaine des mathématiques et congrès MATh.en.JEANS

- Du 25 au 31 mars 2019. Thème : « Jouons ensemble aux mathématiques ».


Brèves

Notation au bac

lundi 11 décembre 2017

Une nouvelle notation sera pratiquée à partir de la session 2018 pour les algorithmes au bac. Elle est décrite avec de nombreux exemples, ici.

Décès de Roger Mohr

mardi 27 juin 2017

On sait bien que Nicolas Bourbaki n’était pas le nom d’une personne mais le pseudonyme d’un groupe. L’équivalent en informatique théorique est Claude Livercy, auteur de la théorie des programmes. Roger Mohr était un des membres de Claude Livercy.

À travers les labyrinthes : algorithmes et fourmis

dimanche 1er septembre 2013

Quand les chercheurs mettent au point des modèles d’optimisation et de recherche de plus court chemin qui s’inspirent du comportement de masse de colonies de fourmis...
À écouter : Sur les Épaules de Darwin, émission diffusée sur France Inter samedi 31 août 2013.

Rencontres Mondiales du Logiciel Libre à St-Joseph

mardi 20 août 2013

Les RMLLd se dérouleront pour la 2e fois à Saint-Joseph du 22 au 25 août.
C’est une opportunité pour les élèves qui suivent la spécialité ISN et les passionnés d’informatique.

Voici pour le samedi et le dimanche quelques interventions choisies :
- http://2013.d.rmll.info/Raspberry-votre-ordinateur-au-format-carte-de-credit?lang=fr
- http://2013.d.rmll.info/Materiel-libre-et-DIY?lang=fr
- http://2013.d.rmll.info/Arduino-de-l-electronique-libre?lang=fr

Noter aussi les conférences Art et Culture du dimanche, ainsi qu’une conférence plus engagée.

Le programme complet se trouve ici. Une radio sera ouverte pour l’occasion.
Des plaquettes à distribuer se trouvent ici.

Hyper-vidéos pour l’algorithmique au lycée

dimanche 19 août 2012

Olivier Roizès, à la demande de l’ADIREM, a réalisé une collection d’hyper-vidéos de présentation de logiciels et environnements de programmation. Ces hyper-vidéos, c’est-à-dire des vidéos contenant des éléments clicables, devraient être utiles aux enseignants désireux de se familiariser avec Python, CaRMetal, R, Rurple, Scilab ou Xcas.

Ouverture du SILO

mardi 1er novembre 2011

Le SILO (Science Informatique au Lycée : Oui !) est un espace collaboratif documentaire de partage et de formation collégiale, à destination des professeurs appelés à enseigner l’informatique au lycée.

Une initiative du CNDP, de l’INRIA et de Pasc@line, à laquelle se sont associés SPECIF, fuscia, EPI et ePrep.

Sur le Web : Site du SILO

Introduction à la science informatique

lundi 12 septembre 2011

Le CRDP de Paris publie le premier ouvrage destiné aux professeurs chargés d’enseigner la nouvelle spécialité « Informatique et sciences du numérique » en Terminale S à la rentrée 2012. Cet ouvrage a été coordonné par Gilles Dowek, directeur de recherche à l’INRIA.

Sur la création de la spécialité ISN, on pourra également consulter l’interview donnée au Café pédagogique par l’inspecteur général Robert Cabanne.

Sur le Web : CRDP de Paris

Deux publications sur l’algorithmique

samedi 17 octobre 2009

L’IREM d’Aix-Marseille publie une brochure de 73 pages, téléchargeable librement, intitulée Algorithmes et logique au lycée. Ces notions sont illustrées et déclinées sur des exercices du programme de spécialité mathématique en série L, mais sont adaptables aux programmes à venir.

Le hors série thématique n° 37 du magazine Tangente, disponible actuellement en kiosque, s’intitule « Les algorithmes. Au cœur du raisonnement structuré ». Extrait de l’éditorial : « La rédaction de Tangente a conçu la quasi-totalité de ce hors série thématique pour qu’il puisse être lu par des élèves de Seconde ».

Une carte mentale pour l’algorithmique

jeudi 10 septembre 2009

Sur son site, Jean-Jacques Dhénin a publié une carte mentale géante qui renvoie vers plus de 30 documents en ligne sur l’algorithmique. Tout ce qu’il faut — et même davantage — pour faire face au nouveau programme de Seconde !

Un catalogue libre d’algorithmes pour le lycée

dimanche 30 août 2009

Guillaume Connan, de l’IREM de Nantes, publie un catalogue libre de 119 pages d’algorithmes pour le lycée. Sur son site très riche, on trouvera d’autres documents en rapport avec l’algorithmique, notamment sur l’utilisation des langages fonctionnels au lycée et sur la comparaison programmation fonctionnelle/programmation impérative.

Statistiques

Dernière mise à jour

mercredi 5 décembre 2018

Publication

801 Articles
Aucun album photo
138 Brèves
11 Sites Web
141 Auteurs

Visites

553 aujourd'hui
1659 hier
2593646 depuis le début
34 visiteurs actuellement connectés