headlogo

Le compte est (vraiment) bon

compte

Version anglaise

Le compte est bon est un des jeux télévisés les plus anciens à être diffusés dans le monde. Créé en France par Armand Jammot, il a commencé à être diffusé en 1965 dans un autre format (le mot le plus long) avant de connaitre sa forme actuelle en 1972. Un jeu similaire appelé countdown est diffusé depuis 1982 par la télevision britannique (channel 4). Pourtant, bien que ce jeu soit certainement un des plus connus en France comme en Grande Bretagne, il n'en existe aucune étude scientifique sérieuse.

On trouvera ici un long article (17 pages en anglais et en pdf) qui fait une présentation extrêmement détaillée du jeu et des différents algorithmes permettant de le résoudre, ainsi que des statistiques poussées. Il s'agit d'un preprint dont une version réduite sera probablement soumise à une conférence ou une revue scientifique, si j'ai le temps (Mise à jour du 10/2015: une version un peu plus courte de l'article a été acceptée pour publication à GCAI 2015 et les proceedings sont maintenant disponibles dans la série Epic Computing in Computer Sciences). Il est également disponible sur arxiv.
Une version html de l'article se trouve ici. Il est cependant préférable de lire le pdf, les formules mathématiques sont plus claires..
Cet article introduit un nouvel algorithme utilisant des tables de hachage qui permet d'améliorer considérablement les temps de calcul.

Il propose également des voies d'amélioration du jeu, permettant de le rendre plus difficile et plus intéressant, de diverses façons. Il est possible par exemple de sélectionner dans une base de données des problèmes connus pour être difficiles, ou de changer l'ensemble de tirage des 6 nombres.
Il est également possible d'ajouter aux quatre opérations disponibles normalement le carré, c'est à dire la possibilité de remplacer un nombre par son carré. Par exemple, alors qu'il est impossible de trouver 999 avec 1,2,3,4,5 et 6 cela devient possible en ajoutant le carré à la liste des opérations autorisées.

   Operations   Nombres restants 
                {1,2,3,4,5,6} 
  3 x  6 =  18  {1,2,4,5,18}
 18 x 18 = 324  {1,2,4,5,324}
  4 +  5 =   9  {1,2,9,324}
324 +  9 = 333  {1,2,333}
  1 +  2 =   3  {3,333}
333 x  3 = 999  {999}

Dans cette variante, le jeu n'est plus forcément décidable car il n'y a pas réduction du nombre d'éléments disponibles à chaque étape. L'article présente d'ailleurs des exemples sur lesquels la décidabilité n'est pas du tout claire. Les résolutions peuvent être extrêmement longues et utiliser des chiffres très élevés. Par exemple, pour trouver 862 avec 1,10,10,25,75 et 100 il faut au minimum 14 étapes, en utilisant des nombres aussi grand que 400000000.

            Opérations              Nombres restants
                                   {1,10,10,25,75,100}
       10 -        1 =         9   {9,10,25,75,100}
      100 x      100 =     10000   {9,10,25,75,10000}
        9 x        9 =        81   {81,10,25,75,10000}
       10 x       10 =       100   {81,100,25,75,10000}
      100 x      100 =     10000   {81,10000,25,75,10000}
    10000 +    10000 =     20000   {81,20000,25,75}
       75 x       75 =      5625   {81,20000,25,5625}
     5625 x     5625 =  31640625   {81,20000,25,31640625}
    20000 x    20000 = 400000000   {81,400000000,25,31640625}
400000000 - 31640625 = 368359375   {81,368359375,25}
       25 x       25 =       625   {81,368359375,625}
      625 x      625 =    390625   {81,368359375,390625}
368359375 /   390625 =       943   {81,943}
      943 -       81 =       862   {862}

Il reste 49 problèmes qui n'ont pas de solution connue pour cette variante du jeu. Ceci ne signifie pas qu'il n'en existe pas, mais que, avec les bornes numériques du programme, aucune solution n'a été trouvée. Ces 49 problèmes sont les suivants:

1 1 10 10 25 100: 858 
1 1 10 10 25  75: 863 
1 1 10 10 50 100: 433 453 547 683 773 853 
1 1 10 10 50  75: 793 853 978 
1 1 10 10 75 100: 433 453 457 478 547 618 653 682 708 718 778 793 822 853 892 907 958 978 
1 1 10 25 75 100: 853 863 
1 1 10 50 75 100: 793 813 853 978 
1 1  5  5 25 100: 813 953 
1 1  7  7 50 100: 830 
1 1  8  8  9   9: 662 
1 1  9 10 10 100: 478 573 587 598 
1 1  9  9 10 100: 867 
1 9  9 10 10 100: 867 947 957 958 967 

Vous pouvez lire l'article pour avoir plus de détails.

Le programme ci-dessous implante l'algorithme standard (sans le carré) pour résoudre le jeu "ordinaire", en proposant toutes les solutions possibles après élimination des solutions "identiques" (voir l'article):

On trouvera ci-dessous le programme utilisé pour générer les statistiques présentées dans l'article. Il permet d'apprécier la rapidité de l'algorithme puisque la version Linux 64 bits sur un core i7 980X génère l'ensemble des solutions et des statistiques en 13s pour le jeu standard (la version 32 bits donne le résultat en 23s; les versions Windows sont un peu plus lentes). A titre de comparaison un site en principe consacré au compte est bon donne un temps de calcul de 60 jours pour calculer toutes les solutions(!), et le site de kitsune donne un temps indicatif de quelques heures de calcul.

Il s'agit d'un programme à utiliser en ligne de commande. Il prend quatre paramètres:

Si l'on tape par exemple sous Windows

stats64.exe 6 100 1000 1000
on va générer les statistiques pour le problème à 6 plaques, en cherchant toutes les solutions entre 101 et 999, et en cherchant toutes les solutions approchées possibles, aussi loin soient-elles (c'est globalement le jeu "classique").

Le programme a été intensivement testé sous Linux en version 64 bits. Les autres versions fonctionnent pour 6 plaques, il n'y a pas de garantie pour le reste (en particulier pour les versions Windows, tout spécialement au niveau de l'allocation mémoire).

Le programme génère trois fichiers de statistiques:

L'article cite un programme écrit en 1986 qui résolvait déjà le jeu en moins de 30s sur AMIGA, le code source se trouve ici et ici; quand à l'exécutable pour amiga, il est

Cette page a été lue fois (en français ou en anglais).


Retour à ma page principale

Le téléchargement ou la reproduction des documents et photographies présents sur ce site sont autorisés à condition que leur origine soit explicitement mentionnée et que leur utilisation se limite à des fins non commerciales, notamment de recherche, d'éducation et d'enseignement.
Tous droits réservés.

Dernière modification: 00:36, 25/08/2016 xhtml validation