----

Le Master Mind

----

This page is also available in english.

En mai 2005, l'association Evolution Artificielle a organisé un concours de master mind dont le but était de résoudre le problème 10x10 (10 couleurs, 10 trous) en respectant une contrainte de temps, et en minimisant le nombre d'essais nécessaires.

Nous avions déjà étudié dans le passé le problème du master mind pour des problèmes de plus petite taille (jusqu'au 8x8), et constaté que pour ces dimensions des algorithmes énumératifs déterministes étaient extrèmement efficaces, et que la meilleure méthode consistait à travailler sur la minimisation de l'espérance du nombre de coups restant.

Pour le problème 10x10, de telles solutions n'étaient pas applicables, mais il nous semblait toujours clair qu'un algorithme déterministe bien conçu devait pouvoir résoudre le problème de façon extrèmement rapide. Nous avons donc développé deux programmes (l'un en C, l'autre en OCAML), qui résolvait le 10x10 en 4/100 de seconde (en C), et en 2/10 (en OCAML), de façon purement brutale. Devant ces résultats la règle du concours a changé et il a été décidé de passer à un master mind 13x13.

Dans le cadre du 13x13, la méthode brute pure ne s'appliquait pas aussi facilement, et nous avons essayé des techniques de programmation par contraintes. Notre librairie "maison" (FACILE) semblait un peu limitée, et nous avons alors décidé de reprendre le programme de 10x10, mais en l'adaptant "intelligemment" pour qu'il fonctionne en 13x13 (le résultat du concours a cependant montré que l'approche par contraintes était probablement la bonne).

Nous avons en fait réalisé un programme adaptatif dont le comportement se décompose en deux phases. Lors de la première, il commence par chercher les 13 bonnes couleurs par une succession de tests qui essaient également de créer un maximum de contraintes (plusieurs stratégies furent essayées); lors de la seconde phase, l'algorithme tente de trouver une solution admissible en fonction des contraintes passées de façon "brutale", mais uniquement pendant un certain laps de temps. Si ce temps est dépassé, il propose une solution "presque" bonne, et recommence en utilisant les informations supplémentaires.

Le programme s'adapte donc au temps dont il dispose. Lorsqu'il dispose d'autant de temps qu'il le souhaite, il trouve en un peu moins de 16 coups en moyenne. Pour le concours, il avait été calibré de façon plutôt "juste", et a tourné en un peu plus de 17 coups.

Un de nos regrets est d'avoir seulement "porté" le programme OCAML en 13x13, et non le programme C, qui était plus rapide (x4) et aurait peut-être permis de nous rapprocher de la première place. Mais on programme plus vite en OCAML qu'en C... On tachera donc de faire mieux la prochaine fois...

PS: contrairement au certificat joint, l'auteur principal du programme est Nicolas Durand que vous pouvez contacter pour de plus amples renseignements...


Page réalisée par Jean-Marc Alliot, qui avait également écrit le programme en C pour le 10x10, et eut la paresse de le porter en 13x13...


Last Update: Wednesday, 28-Mar-2007 12:40:10 CEST

[an error occurred while processing this directive]
[an error occurred while processing this directive] [an error occurred while processing this directive]