La programmation génétique

Introduction

Contexte

On s'intéresse ici à la programmation génétique dans le cadre des jeux.

Je fais tout de suite plein d'hypothèses pour simplifier le discours

• on considère un jeu de plateau, à deux joueurs
• il n'y a pas d'information cachée (main de cartes, etc)
• il n'y a pas de hasard (pas de dés, etc)

Typiquement, des jeux qui rentrent dans cette catégorie sont les échecs, les dames, le morpion, le reversi (othello), le jeu de go, etc.

Je suppose que les mécanismes présentés pourraient s'appliquer à un care plus large mais je m'intéresse aux jeux.

Objectif

Le but est de concevoir un programme informatique qui joue au jeu en question, de préférence qui joue bien, grâce à une technique qu'on va appeler programmation génétique.

Définitions

Un génome

Chaque joueur du jeu va être figuré par une petite bête, à laquelle on s'intéresse uniquement pour son génome.

Le principe de la programmation génétique est que chaque petite bête ne sais pas réfléchir, mais sait bêtement jouer. Les coups à jouer dans chaque situation sont indiqués dans le génome de la petite bête.

Lorsqu'un humain joue contre une petite bête, chacun fait une action à son tour. L'humain réfléchit, puis décide de la meilleure action. La bébète, elle, ne réfléchit pas : pour chaque situation possible, son génome lui indique quoi jouer.

Mais, elle va être nulle ! me direz-vous. Eh, oui. c'est le principe. Sauf qu'en fait, ce n'est pas si simple :

Au début, en effet, va construire aléatoirement les génomes des petites bêtes, ce qui revient à les faire jouer au hasard.

Amélioration de la population

Mais ensuite, on peut opposer deux petites bêtes, et regarder laquelle va gagner. Sur une population nombreuse de petites bêtes aléatoires, certaines seront ainsi meilleures que d'autres (le critère étant de gagner la partie de jeu).

On va donc élire un certain nombre de ces bébètes, réputées plus fortes, et on va les croiser entre elles, pour donner une nouvelle population nombreuse de bébètes, dont on espère qu'elles sont globalement plus fortes que celles de la génération précédente. Exactement comme si on croisait entre eux des chevaux de course dans un haras.

En faisant ainsi un cycle régulier:

1. Confrontation des bébêtes deux à deux
2. Election des plus performantes (et élimination des autres)
3. Croisement entre elles pour donner une nouvelle population
4. retour en 1

On espère qu'on va peu à peu éliminer les défauts et obtenir des bébètes de plus en plus fortes. Si on a réussi, à la fin, les bébètes savent jouer le meilleur coup dans chaque situation.

Le morpion

Comme il est plus simple d'expliquer les notions sur un exemple, je vais d'abord prendre le cas simple du morpion.

Les situations

Au morpion, il y a un plateau de 9 cases (3*3), qui peuvent être chacune vide, blanche, ou noire

Fig. 1.

Fig. 2.

Fig. 3.

Les figures 1, 2 et 3 montrent différentes situations possibles. On veut trouver un génome qui indique, à chaque sitation possible, quelle coup jouer.

Pour cela, je propose de repérer chaque situation possible du plateau de morpion par un numéro. Le morpion a neuf cases, chacune pouvant être soit vide, soit blanche, soit noire. Au total donc 3^9=19683 configurations possibles.

Si on numérote les cases du plateau on peut considérer chaque configuration comme un nombre en base 3, avec les puissances de 3 comme indiquées sur le dessin:

On va décider arbitrairement des chiffres: vide=0, blanche=1, noire=2. Maintenant on est capable de calculer le numéro de chaque configuration: Par exemple, La figure 1 porte le numéro 0 (zéro), la figure 2 est la configuration numéro 1*3^4=81, et la figure 3 a le numéro 2*3^0=2.

Un exemple plus complexe est celui ci: Cette configuration porte le numéro 3^2 + 3^4 + 2*3^5 + 2*3^8 = 13698. Essayez donc de le retrouver, des fois que je me sois trompé (poil aux pieds)

Le génome

On a donc vu que chaque situation pouvait être représentée par un nombre entre 0 et 19682. Et on veut qu'un génome nous indique, pour chaque sitation, quoi jouer. Facile: il suffit d'associer, à chaque situation, le numéro (de 0 à 8) de la case dans laquelle jouer. Un génome sera donc une suite de 19683 chiffres.

Lorsqu'une bébète veut jouer, elle regarde la situation du plateau, calcule son numéro n, et va consulter son n-ième gène. Ce gène sera un chiffre entre 0 et 8, et la bébète jouera donc dans la case en question.

Par exemple, considérons une bébète qui a son génome qui commence par 1625324648156130223123113201514353320123751288312345236731363723073325624195...

Mettons qu'elle doive jouer, pour les noirs, alors qu'elle est dans la situation suivante : Elle va tout d'abord calculer le numéro de cette configuration: 3^1+3^2+2*3^3=66, puis regarder le soixante-sixième gène de son génome : ...1363723073325624195...

Notre bébète décidera donc de jouer au centre en bas, ce qui est un coup assez mauvais. Mais lors de la phase de sélection, avant la reproduction, seules les bébètes qui ont été performantes seront retenues. Les génomes inefficaces seront donc peu à peu éliminés au fil des générations, et des bébètes de plus en plus performantes verront le jour, typiquement, des bébètes qui auront un 0 comme soixante-sixième gène...

La compétition

L'étape importante dans le cycle d'évolution des bébètes est la confrontation : on fait concourir toutes les bébètes d'une génération pour sélectionner seulement les meilleures (oui, je sais c'est de l'eugénisme, mais c'est pour la bonne cause)

En pratique, cela consiste à choisir deux bébètes au hasard et à les faire jouer l'une contre l'autre. C'est assez simple, finalement, car le procédé est très mécanique : La première bébète à jouer obéit à son gène numéro 0, puisque le plateau initial est vide. Elle pose son pion, blanc ou noir, ce qui met la plateau dans une autre configuration. La seconde réplique, toujours selon ce que lui indique son génome, etc.

Au fil des matches, certaines bébètes vont s'avérer meilleures que d'autres. Pour déterminer lesquelles les plus simple est de faire un championnat (tout le monde joue contre tout le monde), ou des poules, ou que sais-je encore.

La reproduction

C'est bien beau d'avoir trouvé les 10 meilleures bébètes de notre population de 100 bébètes aléatoires, mais on n'est pas encore arrivé au bout de nos peines : en effet, il faut maintenant éliminer les 90 mauvaises (c'est la dure loi de la sélection naturelle), et faire se reproduire entre elles les autres, pour former une nouvelle population de 100 bébètes, censées être plus fortes que leur prédécesseuses.

Pour ce faire, on va recréer 90 nouvelles bébètes, chacune à partir de deux parents tirés au hasard parmi nos dix étalons reproducteurs. Choisissons donc deux parents au hasard. On va leur construire un enfant (ou plutôt, on va construire le génome de cet enfant) en combinant aléatoirement des gènes des deux parents.

La technique est diablement simple : on cherche à construire un génome de 19683 gènes, alors pour chaque gène, on tire à pile ou face, et suivant le résultat on copie le gène du père ou de la mère.

Démonstration :

le "père"	57160868027281840510003457062388216203115045130102...
la "mère"	21256737461463536668838381703725042736583631104871...
Pile ou Face ?	PPPPFPPPPFPPPPFFPPPFPFPFFFFPFPFPPPPPFPPPPFPPFPPPPP...
L'enfant	57166868067281530518033381763328216233115645130102...

Sur ce modèle, on construit 90 nouveaux enfants (pas tous des mêmes parents, hein !) et ensuite on recommence : on les fait jouer au morpion les uns contre les autres, on sélectionne les meilleurs, etc.

La convergence

L'eugénisme, c'est bien beau, mais qui nous dit que ça marche ?

A vrai dire, je n'en sais rien. Dans la pratique, je l'ai implémenté avec succès pour des jeux simples comme le morpion ou le jeu des bâtonnets Au début, les génomes jouent complètement n'importe comment. Mais, plus on avance dans les générations, plus ils deviennent intelligents. L'espace du jeu des bâtonnets est tellement restreint que l'ordinateur en vient à gagner à tous les coups. Au morpion aussi, les génomes se décantent bien et le résultat est rapidement acceptable.

Un jeu des bâtonnets

Variantes

En partant de cet exemple simple (qu'à l'époque j'avais codé sur ma calculatrice TI-89) on peut imaginer de nombreuses pistes qui sont peut-être intéressantes à explorer :

• construire les enfants à partir de plus que deux parents...
• utiliser différentes techniques d'élection des meilleurs

• introduire des mutations aléatoires lors de la reproduction, pour accélérer l'évolution, et ouvrir artificiellement de nouvelles pistes.

• adapter cette technique pour les jeux à un seul joueur. J'avais pensé à l'utiliser pour le jeu de solitaire (avec les billes), mais je crains que ça ne converge pas, du fait de la nature différente du problème. A voir.

Le Puissance Quatre

Introduction

Ici s'arrête l'archéologie et commence la science-fiction. J'ai récemment discuté de programmation génétique avec Pierre Wadier et il a pas mal d'idées sur la question. Cette section est donc librement adaptée (qui a dit "copiée-collée" ?) desdites idées.

La méthode présentée ci-dessus pour le cas du morpion n'est pas directement applicable au Puissance 4. En effet, l'espace des configurations est trop vaste, et les génomes seraient impossibles à manipuler.

Calculons

La grille du Puissance 4 mesuer 6*7 = 42 cases. Chaque case peut être soit vide, soit blanche, soit noire. Donc au total il y a 3^42 = 1.09e+20 configurations possibles, ce qui est beaucoup. Pour chacune de ces situations, le génome doit nous indiquer dans quelle colonne jouer, c'est à dire un nombre entre 0 et 6,ce qu'on peut confortablement coder en 3 bits. Donc, chaque génome occupperait un espace de (3^42)*3/8 = 35 Exa-octets = 35e+18 octets.

Pas facile, dès lors, de manipuler des populations de centaines de tels génomes.

- Mais, tu nous voles ! vous entends-je déjà crier. "Toutes tes configurations ne sont pas possibles, à cause de la gravité !" Vous avez raison. Et c'est justement de cette intelligente remarque qu'on va tirer parti pour rendre possible la génomisation du Puissance 4.

Réduction de la taille du génome

Vu qu'on a une méthode infaillible pour résoudre le problème (itérer sur les génomes pour les améliorer progressivement), le seul obstacle qui nous reste à surmonter est de rendre le génome plus compact, pour qu'on puisse en manipuler une population assez nombreuse.

Il faut donc trouver un moyen de réduire de beaucoup le nombre de configurations que le génome doit prendre en compte.

Une analyse locale

Notre point de départ est la remarque suivante : l'interaction des pions a une portée limitée. Par exemple un pion dans la colonne tout à gauche ne formera jamais de ligne de 4 pions avec un pion de la colonne tout à droite.

Nous allons donc essayer de restreindre la zone à faire analyser par le génome à une plus petite grille (4x4 par exemple). En effet, les bonnes occasions, comme les coups gagnants, seront visibles sur cette sous-grille. En contre partie, il faudra faire cette analyse locale en plusieurs endroits de la grille de jeu, de façon à ne pas rater un coup important.

Pour jouer un coup, la bébète doit :

1. Placer la sous-grille d'analyse à un endroit du jeu,
2. Produire son analyse (locale)
3. Retourner en 1 tant que toutes les positions de la sous-grille n'ont pas été étudiées
4. Faire une synthèse des analyses locales pour déterminer où jouer.

Si on décide d'utiliser une sous-grille de taille 4*4, il y a 12 façons de placer la sous-grille. Il nous reste donc à décrire comment faire l'analyse locale (sur une grille de 4*4), et comment faire la synthèse des 12 analyses.

Optimisation du codage

En réalité, l'espace des configurations est moins vaste qu'il n'y paraît : grâce à la gravité, les pions tombent au bas des colonnes, ce qui réduit considérablement le nombre de possibilités. Restreignons-nous d'abord à une colonne d'une grille de 4*4. Toutes les possiblités pour remplir une colonne sont figurées ci-dessous.

Les 31 manières de remplir la colonne.

Le nombre de configurations possibles sur cette grille est la puissance quatrième du nombre de possiblités sur une seule colonne. En un mot, 31^4 = 923521. C'est intéressant, parce qu'avec cette technique, on a seulement 900000 gènes à coder, et chacun étant une indication de colonne parmi 4, ce qui peut se coder sur deux bits seulement. Chouette ! Mais patience. Il reste encore à résoudre le problème de la synthèse des sous-analyses.

La synthèse

Pour jouer chaque coup, notre bébète demande à son génome qui lui donne pas moins de 12 réponses. En effet, chaque analyse locale va décider d'une colonne parmi les 6. Pour choisir la bonne, on va rajouter de l'information à chaque gène.

Rajoutons donc 6 bits de poids. Lorsque la bébète cherche à jouer un coup, elle fait séparément les 12 sous-analyses, qui lui répondent chacune un colonne et une poids à accorder à cette réponse. Pour les six colonnes de la grande grille, la bébète additionne les divers poids qu'elle a obtenus et décide de jouer dans la plus grande.

Bien sûr, au début, les colonnes comme les poids seront fantaisistes, mais nous prétendons qu'après un nombre assez grand de générations, les génomes seront devenus acceptables.

Implémentation

Chaque génome serait donc une série de 923521 octets, chaque octet codant, sur deux bits un numéro de colonne, entre 1 et 3, et sur six bits une valeur de poids. Des génomes de 1Mo, ce n'est pas grand-chose pour un PC moderne.

Le moteur de jeu ne serait pas très difficile à implémenter, à peine plus complexe que celui du morpion. A chaque tour, il faut faire les 12 sous-analyses, additionner les poids, puis jouer.

Comme d'habitude, et l'intérêt de la programmation génétique est là, on n'a pas besoin de se compliquer la vie pour la phase de reproduction: on mixe brutalement les génomes des parents, sans se soucier du sens ges gènes, et Mère Nature fait le reste.

Conclusion

La programmation génétique, ça marche. Pour le morpion et le jeu de Nim, l'intérêt reste limité. Mais pour le Puissance 4, je pense que l'idée des sous-grilles (© Pierre Wadier) est prometteuse.

En réduisant ainsi la taille du génome, on peut peut-être même s'attaquer à d'autres jeux très tactiques, et très locaux, comme les dames.

Maintenant, le plus amusant reste à faire : le code ! Des heures et des heures d'expérimentations passionnantes en perspectives.

Si vous avez des questions, des remarques, ou des corrections, ou si vous avez implémenté l'idée, faites-m'en part , et on en parlera ici même.

---

Ce qu'il reste à faire

• implémenter l'algorithme pour le Puissance 4
• rajouter un paragraphe sur le Solitaire
• Séparer en plusieurs pages ?