Projet EMP E2

De Wiki LOGre
Aller à : navigation, rechercher


Principe

Le but de ce projet est de fournir des outils pour étudier les EMP (Edge Matching Puzzle) et en particulier E2 (Eternity II) dont j ai réussi a me procurer l intégralité via des sites de petites annonces

Technos utilisées

Ressources

Code source

Le projet se base sur mon framework FSM mais son cote "générique" risque d être un handicap pour les performances donc il est possible que je fasse des développements customs que j essaierai de réintégrer dans le framework FSM


Cas d EMPs

Exemples

Afin de tester les algorithmes de résolution je m appuie sur les 3 niveaux de l excellente application pour smartphone EMPv0.6.2. (Lien a rajouter )

  • Easy : dimensions 3 * 3
  • Medium : dimensions 4 * 4
  • Difficult : dimensions 5 * 5

Ils sont de tailles suffisamment réduite pour faire des tests et j espère qu ils sont relativement représentatifs des EMP

E2

E2 est le cas qui m intéresse. Il est compose des 3 problèmes suivants :

  • H1 : dimensions 6 * 6
  • H2 : dimensions 6 * 12
  • Complet : dimensions 16 * 16

H1 et H2 sont de taille limitée donc il est possible de trouver une solution dans un temps relativement raisonnable pour peu que l algorithme de résolution ne soit pas trop bourrin. Je compte m appuyer sur eux pour orienter mes essais sur E2 mais les conclusions que je pourrais en tirer ne seront pas forcement exploitables pour E2. Actuellement j arrive a parcourir tout l espace de H1 mais cela n est pas encore envisageable pour H2.

Vocabulaire

  • Edge : arrête d'une pièce
  • Voisins : pièces ayant un Edge en commun
  • Pièces de type Corner : pièces situées aux angles de l EMP. Elles ont 2 Edges significatifs partages avec des pièces de type Border
  • Pièces de type Border : pièces formant le périmètre de l EMP qui ne sont pas de types Corner. Elles ont 2 Edges significatifs partagés avec des pièces de type Corner ou Border et un Edge partagé avec une pièce de type Center
  • Pièces de type Center : pièces qui ne sont ni Corner ni Border
  • Couleur : Motif remplissant un triangle dont le sommet est le centre de la piece et la base est un Edge de la pièce
  • Corner Couleur : Couleur présente sur le edge d une pièce Corner
  • Border Couleur : Couleur présente sur l'un des deux edge d une pièce Border partages avec des pièces de type Corner ou Border
  • Border2Center Couleur : Couleur présente sur l'un des quatre edge d une pièce Center et sur le edge d une pièce Border partagé avec des pièces de type Center
  • Center Couleur : Couleur présente sur l'un des quatre edge d une pièce Center et sur aucun edge d une pièce Border partagé avec des pièces de type Center
  • Pièces similaires : pièces identiques éventuellement par rotation
  • Auto-similaire : se dit d une pièce si elle est identique a elle même par rotation
  • Liens : possibilité que 2 pièces soit voisines


EMPs étudiés

Cette section est destinée a résumer les informations obtenues sur les EMPs grâce aux différentes évolutions de l application. Le nombre de situation s entend par nombre de situations explorées, y compris les situations finales, avec le coin de départ fixe arbitrairement et un algorithme qui garantit qu une situation n est explorée qu une fois.

Information Easy Medium Difficult H1 H2 E2
Largeur 3 4 5 6 12 16
Hauteur 3 4 5 6 6 16
Pieces Center 1 4 9 16 40 196
Pieces Border 4 8 12 16 28 56
Pieces Corner 4 4 4 4 4 4
Nombres de Edges communs 12 24 24 60 126 480
Pieces auto-similaires 0 0 0 2 3 0
Pieces similaires 0 0 0 13 47 0
Couleurs 4 5 7 7 8 22
Corner couleurs 2 2 3 3 3 4
Border couleurs 2 2 3 4 4 5
Border2Center couleurs 2 3 4 2 4 17
Center couleurs 0 0 0 1 0 0
Liens 64 205 405 1.436 6.181 21.636
Nombre de solutions 2 12 1 29.852.184 > 313.327.326  ???
Nombre de situations 36 3283 37937 5.333.232.960  ????  ???
Nombre de bords TBF TBF TBF TBF  ????  ???


Application

Premiers essais

Principe

  • Création d une représentation FSM générique pouvant être utilisée pour n importe quel EMP
  • Utilisation intensive des conteneurs STL pour les structures de donnees, notamment la base de pieces
  • Application bourrine des algorithmes de recherche en largeur en profondeur de base fournis par le framework FSM

Résultats Obtenus

  • L application trouve des résultats pour les 3 exemples et le temps de résolution n est déjà pas instantané pour le 5 * 5

Limitations

  • Consommation mémoire beaucoup trop importante
  • Temps de calcul trop long pour arriver a trouver une solution de H1 en temps raisonnable
  • Pas assez de pré-calcul, trop de calcul a la volée
  • Pas de prise en compte des pièces similaires et auto-similaires

V0.1

Principe

  • L'ordre de pose des pièces est imposée et garantit qu on ne peut pas arriver 2 fois a la même situation
  • Prise en compte des pièces similaires et auto-similaires
  • Utilisation d un algorithme ne nécessitant pas de mémoriser toutes les situations grâce a l unicité des chemins
  • Réalisation de certains calculs en fonction de l ordre des pièces au démarrage de l appli pour limiter les calculs en cours d exécution
  • Amélioration des structures de données : remplacement des conteneurs STL par des structures customs moins génériques et plus spécialisées

Dumper/Reader

Les informations suivantes sont enregistrées:

  • Version du format de fichier
  • Largeur de la grille
  • Hauteur de la grille
  • Séquence des situations:
    • Composee de paires : compteur 64 bits codant le numero de la situation , situation )
    • Les situations sont enregistrees directement par l ecriture du contenu du bitfield representant la situation
  • En queue de fichier un entier 64 bits codant le nombre total de situations rencontrees

Du point de vue du reader

  • La restauration d une situation correspond a lire le contenu du bitfield et a l affecter a la situation courante
  • A partir de la taille du fichier et connaissant la taille des enregistrements grâce aux dimensions de la grille le reader peut déterminer le nombre de situations enregistrées et savoir si le fichier est tronque ou non

Format du fichier:

Champ Nombre d occurences Taille en byte Description
Version 1 4 Version du format = 0
Width 1 4 Largeur de la grille
Height 1 4 Hauteur de la grille
Items n somme des tailles des champs Enregistrement d une paire compteur/situation
Items.counter 1 par Item 8 Compteur indiquant le numero de la situation codée dans l item
Items.situation 1 par Item taille du bitfield<uint32_t> codant la situation Contenu du bitfield representant la situation
Total 1 8 Nombre total de situations rencontrees pendant le run

Résultats Obtenus

  • L application trouve une solution pour H1 en quelques secondes et H2 en une dizaine de secondes.
  • Ensemble des solutions de H1 trouvé en 7h08 min de calcul et 47 223 Milliards d instructions
  • Meilleur résultat obtenu pour E2 : 99/256 malgré plusieurs jours de calculs
  • Prototype d un calcul de métrique pour évaluer les situations prometteuses qui semble relativement pertinent

Limitations

  • Observations suite au profilage par Valgrind et KCachegrind
    • L appli passe beaucoup de temps dans le calcul des transitions. Il faut encore améliorer les structures de données utilisées pour le calcul de transition ( Abandon complet des conteneurs STL ? meilleure organisation des données ? )
    • Beaucoup de temps passe dans la gestion de mémoire dynamique, il faudrait passer par de la mémoire allouée statiquement autant que possible
  • L algorithme de recherche en profondeur effectue des vérifications qui ne sont plus utiles du fait de l ordre des pièces imposées
  • Essai des pièces dans l ordre de leur déclaration : cela introduit peut être un biais qui fait que certaines pièces sont testées des le début entrainant un blocage prématuré
  • Le calcul de métrique pour évaluer si une situation est prometteuse ou non est trop long

V0.2

Principe

  • Remplacement de l allocation dynamique de mémoire en cours de résolution par de l allocation statique
  • Version light de l algorithme de recherche en profondeur
  • Randomisation de l ordre des pièces pour voir si cela fait sauter le blocage ( remis a plus tard )
  • Métrique d évaluation de pertinence d une situation optimisée grâce a l algorithme de dénombrement ( remis a plus tard )
  • Création de générateur de stratégie pour configurer facilement l ordre de pose des pièces
  • Nouveau format de dump optimise pour la vitesse
  • Serveur web embarque permettant d interroger l appli afin de connaitre son statut. Cela evite d avoir a rafraichier une GUI en permanence
  • Optimisation du calcul des transitions
    • Simplification de la représentation des pièces pour améliorer le calcul de contrainte
    • Utilisation de tables pré-calculées a la place des conteneurs STL pour la recherche des pièces répondant a une contrainte
    • Pre-calcul en fonction de l ordre de pose des pièces

Représentation binaire d une pièce

  • p le nombre de bits nécessaires pour coder l Id d une piece ( avec Id=0 pour la piece 1)
  • c le nombre de bits nécessaires pour coder l Id d une couleur ( avec Id=0 signifiant absence de couleur, Id avec tous les bits a 1 signifiant couleur de bordure)
Bits [4 * c + 1 + p : 4 * c + 2] [4 * c + 1 : 4 * c] [4 * c - 1 : 3 * c] [3 * c - 1 : 2 * c] [2 * c - 1 : c] [c - 1 : 0]
Champ Piece Id Orientation West color South Color East Color North Color
  • En considérant que E2 soit le cas le plus complexe a traiter alors un p=8 et c=5 donc la représentation binaire peut être stockée dans un entier 32 bits

Représentation binaire d une contrainte

  • p le nombre de bits nécessaires pour coder l Id d une pièce ( avec Id=0 pour la piece 1)
  • c le nombre de bits nécessaires pour coder l Id d une couleur ( avec Id=0 signifiant absence de couleur, Id avec tous les bits a 1 signifiant couleur de bordure)
Bits [4 * c + 1 + p : 4 * c + 2] [4 * c + 1 : 4 * c] [4 * c - 1 : 3 * c] [3 * c - 1 : 2 * c] [2 * c - 1 : c] [c - 1 : 0]
Champ Reserved Reserved East color North Color West Color South Color
  • En considérant que E2 soit le cas le plus complexe a traiter alors c=5 donc la représentation binaire peut être stockée dans un entier 32 bits
  • Le calcul des contraintes générées par les pièces posées sur le plateau est exécuté un grand nombre de fois. Afin de le simplifier l'orientation des couleurs de contrainte est inversée par rapport au codage des pièces. Cela permet de calculer la contrainte grâce une simple AND
// Example of constraint computation from neighbour pieces with c=4
constraint = (piece & 0x00F0)| (south_piece & 0x0F0)| (east_piece & 0x00F0)| (north_piece & 0x000F)
  • Le remplissage des tables de contrainte est lui effectue une seule fois en début d exécution donc il n est pas gênant de devoir effectuer quelques calcul supplémentaire dus a l inversion
// Example of constraint matched by a piece with c=4
constraint = ((piece & 0x00F0) << 8) | ((piece & 0x000F) << 8))| ((piece & 0xF000) >> 8) | ((piece & 0x0F0) >> 8)

Liste de transitions

  • Soit n le nombre de pieces de l EMP, chaque piece peut etre oriente de 4 facons differentes, il y a donc 4 * n transitions possibles au maximum
  • La liste de transition est représentée par un champ de bit de 4 * n bits ou chaque bit represente une transition possible ( bit a 1 ) ou impossible ( bit a 0 )
  • Les 2 bits de poids faible de l index du bit codent l orientation ( 0 => North, 1 => East, 2 => South, 3 => West)
  • Les log2(n) bits de poids fort de l index du bit codent l ID de la piece
  • La suppression d une transition se resume a passer le bit correspondant a 0
transition_list &= ~(1 << transition_id)
  • Dans le cas des pieces similaires il faut un champ de bit additionnel pour chaque transition id avec tous les bis a 1 sauf ceux pour chaque transition produisant le meme effet
  • Lorsque l on applique une transition il faut faire un AND entre le champ de bit additionnel et la liste des transitions de maniere a supprimer toutes les transitions indentiques a celle choisie
transition_list &= similar_pieces[transition_id]

Liste de pieces disponibles

  • Le codage est identique a celui des listes de transitions. Un bit a 1 signifie pièce disponible, a 0 pièce indisponible
  • Lorsque qu une pièce est posée les 4 bits représentant cette pièce doivent être mis a zéro ce qui se fait par une simple AND
pieces_dispo &= (0xF) << (4 * piece_id);

Table de contrainte

  • Il s agit d un tableau dont l index est de type Représentation binaire d une contrainte et les valeurs sont des listes de transition
  • Pour chaque pièce et chaque orientation qu elle peut prendre on calcule les contraintes correspondantes, qu on utilise comme index dans la table de contrainte et on va mettre a 1 le bit correspondant a la pièce et son orientation
  • Une pièce peut correspondra a 16 contraintes ( 4 bits avec 1 bit codant pour la présence/absence d une pièce voisine)
  • Le calcul de transitions possibles a un instant donne revient donc a chercher les transitions théoriques possibles dans la table des contraintes et a faire un AND avec la liste des pièces disponibles
possible_transitions = constraint_table[constraint] & available_pieces;

Générateur de stratégie

  • Il indique pour chaque étape a quelle position poser la pièce
  • Pour une position donnée il indique a quelle étape la pièce sera posée

Pré-calcul de contrainte

  • Étant donne une stratégie définie par un générateur de stratégie on peut calculer a l avance pour chaque étape:
    • qu elles positions seront occupées ou pas par une pièce
    • a quelles étapes les pièces voisines seront posées
  • Ces informations sont stockées pour chaque étape
  • A l exécution on va stocker la représentation binaire de la pièce posée et se baser sur les informations pré-calculées pour calculer la contrainte

Dumper/Reader

  • Introduction du format v1 qui ajoute les fonctionnalités suivantes:
    • Enregistrement d un champ dans le header indiquant si on dump des solutions ou des situations intermédiaires ([0...n] avec 0 pour l absence pièces
      • Codage des solutions : on enregistre les IDs des pièces valeurs [1..n] - 1
      • Codage des situations intermédiaires : on enregistre les IDs des pièces valeurs [1..n] et 0 pour indiquer qu il n y a pas de pièces
    • Enregistrement de la stratégie. Cela permet de dumper directement la situation sans la réordonner. La remise en ordre sera faite a la lecture du dump quand les perfs sont moins critiques
    • Les champs de bits sont maintenant basés sur du uint64_t


  • Le reader est capable de relire les formats v0 et v1
  • Le dumper n enregistre qu en format v1


Format du fichier:

Champ Nombre d occurences Taille en byte Description
Version 1 4 Version du format = 1
Width 1 4 Largeur de la grille
Height 1 4 Hauteur de la grille
Solution Dump 1 4 0 si l on peut dumper des situations intermédiaires, 1 si l on ne dump que des solutions
Strategy Items Width * Height somme des tailles des champs Enregistrement de la stratégie utilisée
Strategy Items.X 1 par Strategy Item 4 Abscisse de la case dans la séquence de case de la stratégie
Strategy Items.Y 1 par Strategy Item 4 Ordonnée de la case dans la séquence de case de la stratégie
Items n somme des tailles des champs Enregistrement d une paire compteur/situation
Items.counter 1 par Item 8 Compteur indiquant le numero de la situation codée dans l item
Items.situation 1 par Item taille du bitfield<uint32_t> codant la situation Contenu du bitfield representant la situation
Total 1 8 Nombre total de situations rencontrees pendant le run

Résultats Obtenus

  • L application trouve une solution pour H1 et H2 en quelques secondes
  • Ensemble des solutions de H1 trouvé en 3min de calcul et 1 065 Milliards d instructions

Limitations

  • Pour E2 complet l algo reste bloque a 99 pièces avec la stratégie en spirale

V0.3 ( en cours de développement )

  • Randomisation de l ordre des pièces pour voir si cela fait sauter le blocage ( a implémenter )
  • Métrique d évaluation de pertinence d une situation optimisée grâce a l algorithme de dénombrement ( a implémenter )
  • Nouvelle stratégie consistant a d abord chercher a disposer les pièces de type Center en tenant compte du nombre de Border2Center couleurs a exposer puis seulement ensuite chercher un cadre qui respecte les contraintes ( a implémenter )


Detail des EMPs étudiés

Exemples

Easy

  • Largeur : 3
  • Hauteur : 3
  • Pieces Center : 1
  • Pieces Border : 4
  • Pieces Corner : 4
  • Nombres de Edges communs : 12
  • Pieces auto-similaires : 0
  • Couleurs : 4
  • Corner couleurs : 2
  • Border couleurs : 2
  • Border2Center couleurs : 2
  • Center couleurs : 0
  • Liens : 64
  • Nombre de solutions : 2
  • Nombre de situations : 36

Medium

  • Largeur : 4
  • Hauteur : 4
  • Pieces Center : 4
  • Pieces Border : 8
  • Pieces Corner : 4
  • Nombres de Edges communs : 24
  • Pieces auto-similaires : 0
  • Couleurs : 5
  • Corner couleurs : 2
  • Border couleurs : 2
  • Border2Center couleurs : 3
  • Center couleurs : 0
  • Liens : 205
  • Nombre de solutions : 12
  • Nombre de situations : 3283

Difficult

  • Largeur : 5
  • Hauteur : 5
  • Pieces Center : 9
  • Pieces Border : 12
  • Pieces Corner : 4
  • Nombres de Edges communs : 24
  • Pieces auto-similaires : 0
  • Couleurs : 7
  • Corner couleurs : 3
  • Border couleurs : 3
  • Border2Center couleurs : 4
  • Center couleurs : 0
  • Liens : 405
  • Nombre de solutions : 1
  • Nombre de situations : 37937

E2

H1

  • Largeur : 6
  • Hauteur : 6
  • Pieces Center : 16
  • Pieces Border : 16
  • Pieces Corner : 4
  • Nombres de Edges communs : 60
  • Pieces auto-similaires : 2 ( pieces 2 et 19 qui sont semi-similaires )
  • Pieces similaires :
    • 1 <==> { 8, 24}
    • 3 <==> { 5}
    • 4 <==> { 33}
    • 5 <==> { 3}
    • 8 <==> { 1, 24}
    • 9 <==> { 27}
    • 24 <==> { 1, 8}
    • 26 <==> { 36}
    • 27 <==> { 9}
    • 32 <==> { 35}
    • 33 <==> { 4}
    • 35 <==> { 32}
    • 36 <==> { 26}
  • Couleurs : 7
  • Corner couleurs : 3
  • Border couleurs : 4
  • Border2Center couleurs : 2
  • Center couleurs : 1
  • Liens : 1436
  • Nombre de solutions : 29852184
  • Nombre de situations : 5333232960

H2

  • Largeur : 12
  • Hauteur : 6
  • Pieces Center : 40
  • Pieces Border : 28
  • Pieces Corner : 4
  • Nombres de Edges communs : 126
  • Pieces auto-similaires : 2 ( pieces 38 et 43 qui sont semi-similaires ) + 1 ( 8 qui est completement auto-similaire )
  • Pieces similaires :
    • 1 <==> { 4, 8}
    • 2 <==> { 8, 33, 50, 52, 65}
    • 3 <==> { 8}
    • 4 <==> { 1, 8}
    • 5 <==> { 8, 26}
    • 6 <==> { 8, 41}
    • 8 <==> { 1, 2, 3, 4, 5, 6, 38, 43}
    • 9 <==> { 34, 63}
    • 14 <==> { 38, 43}
    • 15 <==> { 40}
    • 18 <==> { 71}
    • 19 <==> { 24, 46, 51, 60, 64, 68}
    • 20 <==> { 69}
    • 21 <==> { 49}
    • 23 <==> { 53}
    • 24 <==> { 19, 46, 51, 60, 64, 68}
    • 25 <==> { 38, 43}
    • 26 <==> { 5}
    • 27 <==> { 67}
    • 28 <==> { 32}
    • 29 <==> { 48}
    • 31 <==> { 42}
    • 32 <==> { 28}
    • 33 <==> { 2, 50, 52, 65}
    • 34 <==> { 9, 63}
    • 37 <==> { 72}
    • 38 <==> { 8, 14, 25, 43}
    • 40 <==> { 15}
    • 41 <==> { 6}
    • 42 <==> { 31}
    • 43 <==> { 8, 14, 25, 38}
    • 46 <==> { 19, 24, 51, 60, 64, 68}
    • 48 <==> { 29}
    • 49 <==> { 21}
    • 50 <==> { 2, 33, 52, 65}
    • 51 <==> { 19, 24, 46, 60, 64, 68}
    • 52 <==> { 2, 33, 50, 65}
    • 53 <==> { 23}
    • 60 <==> { 19, 24, 46, 51, 64, 68}
    • 63 <==> { 9, 34}
    • 64 <==> { 19, 24, 46, 51, 60, 68}
    • 65 <==> { 2, 33, 50, 52}
    • 67 <==> { 27}
    • 68 <==> { 19, 24, 46, 51, 60, 64}
    • 69 <==> { 20}
    • 71 <==> { 18}
    • 72 <==> { 37}
  • Couleurs : 8
  • Corner couleurs : 3
  • Border couleurs : 4
  • Border2Center couleurs : 4
  • Center couleurs : 0
  • Liens : 6181
  • Nombre de solutions : ???
  • Nombre de situations : ?????

Complet

  • Largeur : 16
  • Hauteur : 16
  • Pieces Center : 196
  • Pieces Border : 56
  • Pieces Corner : 4
  • Nombres de Edges communs : 480
  • Pieces auto-similaires : 0
  • Pieces similaires : 0
  • Couleurs : 22
  • Corner couleurs : 4
  • Border couleurs : 5
  • Border2Center couleurs : 17
  • Center couleurs : 0
  • Liens : 21636
  • Nombre de solutions : ???
  • Nombre de situations : ?????