Codingly

L’effet Tetris en informatique

Posted in Posts by Romain Verdier on mai 20, 2008

Quand on est au niveau 3, ça va, on peut encore placer les pièces comme on le veut. Je veux dire par là qu’il est possible de les placer de façon presque optimale, pour faire un gros bloc bien compact sur la gauche de l’écran en attendant une grande barre pour dégager 4 lignes d’un coup. Les 4 lignes d’un coup, ça s’appelle un Tetris, d’ailleurs.

TetrisLorsqu’on arrive au niveau 10, par exemple, il devient plus dur d’enchainer les Tetris. Je suis certain qu’on peut trouver un japonais sur YouTube qui y parvient en chantant le générique de Naruto à l’envers, mais nous ne nous laisserons pas distraire pas les exceptions de ce genre aujourd’hui. Au niveau 10, on ne peut pas enchainer les Tetris, c’est tout. Pourtant, il y a pas mal de gens qui arrivent à tenir un moment au niveau 10, jusqu’au niveau 11 même, et beaucoup plus loin encore.

Parce qu’ils ne cherchent pas à enchainer les Tetris, justement. S’ils essayaient, le temps de réflexion nécessaire au placement de chaque pièce serait largement supérieur à celui qui leur serait accordé. Les pièces tomberaient alors les unes après les autres sans avoir été pilotées, en formant un petit tas famélique qui atteindrait rapidement le haut de l’écran.

La conclusion est la suivante : Le choix d’une solution « assez bonne » peut s’avérer plus rentable que d’investir beaucoup de temps et d’efforts dans la recherche d’une solution « très bonne », ou « parfaite ».

Et ça a même un nom : l’effet (ou stratégie) Tetris. On en trouve quelques bons exemples d’application dans le monde de l’informatique.

Les heuristiques

PVCLorsque j’ai découvert les algorithmes génétiques, j’ai été complètement bluffé. Ils permettent d’apporter des réponses non-optimales (mais exploitables) à des problèmes auxquels il n’existe aucune méthode de résolution déterministe capable d’être mise en application. Généralement, c’est parce que nous ne disposons pas de la puissance de calcul nécessaire. Les algorithmes génétiques – et plus globalement les métaheuristiques et les heuristiques – sont donc une illustration parfaite de l’effet Tetris. Si je prends l’exemple très scolaire du voyageur de commerce qui doit visiter N villes en optimisant son trajet, on peut constater que :

  • La façon de trouver le meilleur chemin est simple : on les mesure tous et on prend le plus court. Seulement, on est confronté à une explosion combinatoire puisque pour N villes il y a (N-1)! trajets possibles. Cette méthode, permettant de trouver la solution du problème, nécessite un investissement trop important. La plupart du temps, elle n’est donc pas rentable, voire inenviseagable.
  • Les algorithmes génétiques permettent de trouver une solution « acceptable ». On ne peut pas savoir si la solution trouvée est la meilleure solution, mais on sait qu’il s’agit d’une bonne solution. L’effet Tetris est remarquable ici, puisque dans ce cas, l’approche conduisant à déterminer rapidement une bonne solution est quasiment toujours préférable à celle qui donnerait la meilleure solution.

C’est une méthode qui est utilisée en IA, et dans pas mal d’autres domaines dans lesquels on préfère obtenir une réponse approchée rapidement plutôt qu’une réponse exacte au bout d’une heure. C’est peut-être pour ça que mes péons étaient aussi cons dans Age Of Empires.

Méthodes Agiles et refactoring

A un autre niveau, mais toujours dans l’ingénierie logicielle, les méthodes agiles et les idées qu’on y associe généralement sans pour autant qu’elles en soient originaires peuvent faire penser à la stratégie Tetris. Dans un processus TDD, par exemple, on invite à faire en sorte qu’un test unitaire donné passe, avant de procéder à une phase de refactoring. On privilégie ainsi la résolution fonctionnelle du problème avant sa résolution parfaite, qui impliquerait que le test passe et que la solution technique – l’implémentation – soit également idéale, si tant est que cela soit possible.

Perfect SoftwareAvec un peu de pratique on se rend compte qu’effectivement, en adoptant ce modèle itératif, on arrive à réaliser des solutions qui sont plus simples que celles qui auraient résulté d’une longue phase d’analyse préliminaire. Les périodes de refactoring successives ont entre autres pour but de garantir la qualité du design, et de ne pas compromettre les éventuelles évolutions ultérieures.

Il existe d’autres principes, comme KISS (Keep It Stupid Simple) ou YAGNI (You Ain’t Gonna Need It) qui semblent également reconnaitre une certaine pertinence à la stratégie Tetris. En rappelant au développeur qu’il n’est pas nécessaire d’anticiper à outrance ou d’imaginer des solutions qui ne répondent à aucun besoin réel, on lui évite de voir son travail et son effort balayés au cours de l’évolution du projet. Mieux, on évite que le projet lui-même soit pollué et complexifié sans raison.

Pour revenir à l’effet Tetris, essayons de détailler le parallèle :

  • Le niveau 10 correspond assez souvent au contexte dans lequel un projet informatique professionnel s’inscrit. Il y a des enjeux, des contraintes, des obligations, des engagements, de l’argent, de la pression, des deadlines, etc. En comparaison, le niveau 3, c’est l’implémentation de la classe Date en 2 semaines par des élèves de première année. (Qui gère les années bissextiles.)
  • Le passage au niveau 11 peut être considéré comme la réussite de la première version du projet. Ah, si tout était aussi évident, etc.
  • Vouloir dégager les lignes 4 par 4, ça correspond à vouloir mettre en place dès le début du projet une solution complexe capable de répondre à tous les besoins en s’appuyant sur une architecture idéale. C’est presque impossible, en fonction de la nature du projet. Donc, dans le meilleur des cas, on arrive à survivre jusqu’au niveau 11, mais l’écran est tellement encombré que le niveau 12 est à oublier (la version 2.0 du projet, si vous suivez…). Le reste du temps, on n’arrive même pas à passer le niveau 10.
  • Au contraire, rester raisonnable et chercher à faire disparaitre les lignes une par une, ça ressemble beaucoup aux itérations et au refactoring. On ne place pas les pièces de façon à préparer un éventuel Tetris : on les place de façon à garder l’écran dégagé. La plupart du temps, on y parvient en éliminant une ligne à la fois, mais parfois on se surprend à pouvoir en faire disparaitre 2 ou 3 d’un coup. Le parallèle que l’on peut faire avec le Refactoring Breakthrough dont parle Evans dans Domain Driven Design est assez étonnant.

Conclusion

Ok, le dernier exemple peut être considéré comme une digression en ce sens où il s’agit plus d’une métaphore que d’une illustration de l’effet Tetris. Mais il est intéressant de voir que le principe est à la base de nombreuses techniques et méthodes. Evidemment, si on sort du domaine de l’informatique, de nouvelles observations peuvent être conduites.

Que pensez-vous de la communication orale chez les humains, et plus précisément des dialogues, à ce sujet ?

4 Réponses

Subscribe to comments with RSS.

  1. bamboo said, on mai 20, 2008 at 7:40

    Très interessant. Une bonne raison de plus pour expliquer à mon chef que les conceptions détaillées, c’est à peu près aussi utile qu’un canard avec un revolver.

    Sinon pour les japonais, c’est complètement normal, ces gens n’ont pas d’âme.

  2. grozeille said, on mai 24, 2008 at 12:10

    Je suis informaticien donc par définition fainéant. Je ne fais que ce que j’ai besoin, seulement au moment ou j’en ai besoin. Anticiper c’est bien, mais en effet il ne faut pas imaginer faire 4 lignes de tetris d’un coup. Je suis plus que convaincu de la démarche, et les outils de refactoring nous rendent la tâche bien plus rapide qu’autre fois.

    « La communication orale chez les humains »? Haha ça me fait penser à ma sale manie de vouloir tout expliquer depuis le début (de l’univers) et je finis pas souler les gens avant d’arriver la ou je voulais en venir. Il faut que j’applique la même méthode: expliquer en quelques mots et si ça ne suffit pas reprendre l’explication plus détaillées (refactoring de ma pensé)…

  3. foufiane said, on janvier 22, 2009 at 11:23

    tout d’abord: excellent article
    je suis étudiant en économie, et ce concept m’intéresse beaucoup :il peut expliquer la non rationalité des choix par exemple…
    j’aimerais bien avoir une bibliographie sur cet effet ci possible (par email si possible)
    merci d’avance

  4. […] donné son nom à ce qu’on a appelé l’effet Tetris en intelligence artificielle. L’effet Tetris désigne le fait qu’une perception hâtive occasionnellement fausse peut se montrer plus […]


Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s

%d blogueurs aiment cette page :