Developpez.com - Delphi
X

Choisissez d'abord la catégorieensuite la rubrique :


Les Défis DELPHI - Jouer au démineur !

Les défis DELPHI

Date de publication : 25 Juillet 2006

Par Equipe DELPHI (Les Défis DELPHI)
 

L'équipe DELPHI vous propose de revivre le tout premier défi qui vous as été proposé sur le Forum DELPHI et qui a connu un très fort engouement !

Voici donc, tout ce que vous avez toujours voulu savoir sur le premier Défi DELPHI ;) !


I. Sujet du défi
I-A. Pré-requis
I-B. Les objectifs du défi
II. Le défi
III. La solution du défieur
IV. La solution du vainqueur
IV-A. Le témoignage du vainqueur
IV-A-1. Le Controle du démineur :
IV-A-2. Structure des données
IV-A-3. Algorithmes
IV-A-3-a. Principe général
IV-A-3-b. Algorithme simple - cellules indépendantes
IV-A-3-c. Algorithme de résolution d'un ilot.
IV-A-3-d. Autres Points
IV-A-4. Mode debug.
IV-A-5. Conclusion
IV-B. Les sources de la solution
V. Les solutions des challengers
V-A. La solution de titi
V-B. La solution de Toto


I. Sujet du défi

Pour le premier défi proposé par l'équipe Delphi il s'agissait de créer un logiciel qui joue au démineur... pas avec vous, non, à votre place ! ...avec le démineur intégré à Windows !


I-A. Pré-requis

Pour réaliser ce défi, une simple édition personnelle de Delphi suffisait. Pas besoin d'avoir les bibliothèques spécifiques aux versions Pro/Entreprise/Architecte !
Certaines versions personnelle de DELPHI sont disponible au téléchargement dans la page Freeware de la rubrique DELPHI de www.developpez.com !

Il était également nécessaire de savoir farfouiller sur le site de www.developpez.com dans la rubrique DELPHI et plus particulièrement dans la faq F.A.Q. DELPHI, dans les src SOURCES DELPHI, dans les tutoriels DELPHI et dans les forums DELPHI.


I-B. Les objectifs du défi

Les objectifs du défi sont très clairs, l'application doit savoir :

  1. lancer Winmine.exe
  2. cliquer sur les bonnes cases (donc analyser les cases déminées, non déminées, puis jouer le coup en conséquence.
  3. sélectionner le niveau de difficulté
  4. démarrer sa petite partie
  5. entrer son nom s'il gagne (si votre logiciel à gagné, c'est que vous êtes suffisamment doué en programmation pour ajouter cette fonctionnalité cruciale)
  6. fermer Winmine
  7. laissez libre court à votre imagination et proposez vos propres fonctionnalités.
Les participant doivent respecter les règles du défi, et le déroulement du défi et plus précisément que "l'utilisation de composantes ou bibliothèques autres que celles fournies en standard par Borland sont interdites, qu'elles soient commerciales, freewares, open-source etc. ..."


II. Le défi

Comme pour tout les défis, ce premier défi c'est déroulé sur le forum DELPHI.

Vous pouvez désormais retrouvez sur cette page l'archive du sujet concernant le défi du démineur.


III. La solution du défieur

Waskol, selon les règles du défi, a réussi à mettre au point un tel logiciel avant que le défi ne soit lancé sur le forum. Le code de son application a été révélé à l'issue du défi.


IV. La solution du vainqueur

Ce premier défi à été remporté par TicTacToe


IV-A. Le témoignage du vainqueur

TicTacToe nous présente la solution qu'il a mis en place afin de résoudre ce défi.


IV-A-1. Le Controle du démineur :

Le contrôle du démineur s'articule autour de ces éléments, j'ai appris à les utiliser pour certains, pour d'autres j'avais déjà mes propres outils.

Rubrique Principe Utilisation
Démarrage et fermeture de l'application Démarrage API d'une application ShellExecute()
Récupération du Handle (identifiant) du démineur Recherche de la bonne fenêtre dans Windows EnumWindows()
Reconnaissance des cellules Lecture d'un ou plusieurs pixels sur case démineur GetPixel()
Clic dans une cellule (gauche ou droit) Envoie d'un message avec attente de retour SendMessage()
Niveau / nouveau jeu Envoie d'un message touche (sans retour) et parcours dans le menu keybd_event()

Pour rendre fiable l'application, toutes ces fonctions dites 'de bas niveau', sont rassemblées et ont chacune un validation ou non avant de s'exécuter.
Ceci afin de ne pas perdre le contrôle de l'application en cas d'anomalies (clics fous, Windows bloqué etc...).


IV-A-2. Structure des données

Pour pouvoir travailler sur le démineur, en minimisant les accès externes, il faut une structure de données qui puisse non seulement refléter la fenêtre du démineur, mais aussi accueillir ses propres données de travail. De surcroit, la taille de la grille est dynamique selon le niveau.

Par habitude, j'utilise trop les TList et les TStringList.

Les différentes structures sont résumées ici:

Elément Structure
La grille de cellules Liste de lignes avec 1 ligne = liste de cellules
Une cellule Classe TCellule avec propriétés et actions propre à une cellule
Les ilots Liste des ilots avec les cellules associées (voir algo.)
Les solutions Liste des solutions pour chaque ilot (voir algo)

A noter que pour s'affranchir du problème des cellules sur un bord ou dans les coins, des listes de cellules adjacentes propres à chaque cellule sont construites une fois pour toute.

Par exemple: une cellule au centre du jeu possède une liste de 8 cellules adjacentes. Une cellule dans un coin possède une liste de 3 cellules adjacentes.

Cela simplifie grandement les parcours et autres tests tout au long du programme ou il y a totalement abstraction des positions relatives des cellules.


IV-A-3. Algorithmes


IV-A-3-a. Principe général

Si la partie n'est pas finie, faire un tour de calcul qui se compose de:

  • Lire l'état du démineur et le stocker dans la structure de données
  • Etablir à l'aide d'un algo. simple, la statistique de présence d'une bombe sur une cellule vierge (taux = 0% = aucune bombe) (voir 3.2)
    2 conclusions:

    • des cellules sont à un taux de 0% ou 100%: de manière certaine, on peut poser un drapeau ou déminer : TOUR FINI
    • sinon, recherche de solutions
      • construction des ilots
      • recherche des solutions (combinaison) sur chaque ilots (voir 3.3)
        2 conclusions:

        • Un ilot à une seule solution : on démine les cellules trouvées: TOUR FINI
        • Un ilot, contient N solutions, alors on effectue un comptage pour chaque cellule des drapeaux apparaissant dans les solutions:
          • Ventilation sur N tours de toutes les cellules de l'ilot
          • Incrémentation pour chaque tours et chaque cellule de 1 si un drapeau est prévu dans la solution
            2 conclusions:

            • Des cellules ont un compteur à 0: le drapeau n'apparait jamais quelque soit les solutions trouvées: on démine : TOUR FINI (*exemple)
            • Des cellules ont un compteur à N: le drapeau apparait systématiquement quelque soit la solution: on pose un drapeau : TOUR FINI (*exemple)
            • Sinon, on établit un nouveau taux de présence de mine, à l'aide de N, du nombre de cellules de l'ilot, et du nombre de drapeaux moyen des solutions dans l'ilot puis
              • on démine la cellule à taux le plus bas: TOUR FINI (ou PERDU!)

Qu'est-ce qu'un ilot ?

C'est l'ensemble des cellules, dont le changement d'état (drapeaux ou pas) d'une seule cellule, remet en question 1 ou plusieurs cellules de l'ilot.
Il est construit par prise d'une cellule initiale et propagation des cellules adjacentes reliées au moins par une cellule numérotée.

Le choix des ilots a été effectué pour tenter un découpage maximum des différentes zones indépendantes à résoudre dans le démineur. Ceci restreint le nombre de cellules dont il faut trouver des combinaisons de drapeaux valides.

Exemple d'un ilot, avec ses 4 solutions possibles de dépôt de drapeaux.

L'ilot
L'ilot
Ilot: toutes les cellules avec '?' ( et Cote = toutes les cellules numérotées)

Ce cas est précisément celui noté par (*exemple).

Aucune solution évidente à priori.

Il y a 4 solutions trouvées par l'algorithme.


Après comptage des drapeaux virtuels pour chaque solution, il y a:
3 cellules qui ont un compteurs à 4.
6 cellules avec un compteurs à 0.
le reste des cellules est entre 1 et 3.

On peut déminer sans risque les 6 cellules à compteur=0
On peut poser un drapeaux sans risque sur les 3 cellules à compteur=4.

Solution 0
Solution 0
Solution 1
Solution 1
Solution 2
Solution 2
Solution 3
Solution 3

Une fois cet algorithme global mis en place, le point critique se situe dans la manière de trouver les solutions dans un minimum de temps et pour un ilot donné.


IV-A-3-b. Algorithme simple - cellules indépendantes

Principe: établir un taux statistique pour chaque cellule (vierge) de trouver une bombe - de 0 à 100%.

Autour d'une cellule numérotée: on compte les drapeaux présents, les drapeaux restant et la statistique est triviale.

Taux = ( Numéro - Bombes présentes ) / Cellules vierges autour du numéro.


IV-A-3-c. Algorithme de résolution d'un ilot.

1ère version: Chercher des combinaisons de drapeaux à l'aide d'un parcours de type CNP.
dont on ne connait pas à l'avance le 'P' symbolisant le nombre de drapeaux, mais dont on connait le 'N' qui est le nombre de cellules dans l'ilot.
L'objectif est de ventiler et d'établir toutes les combinaisons possibles des drapeaux sur un ilot.

Or, dès que le nombre de cellules d'un ilot dépasse un seuil critique (ce seuil est très souvent dépassé, surtout en Expert), le nombre d'itérations à effectuer devient draconien.
Soit on laisse calculer de nuit, soit on coupe le calcul au bout d'un certain temps. Mais cela renvoie un résultat (très) erroné.

De plus, il ne faut pas perdre de vue que, dans la plupart des cas, l'ensemble des combinaisons trouvées dans un ilot servira a ré-établir des statistiques, et parfois seulement des résultats certains. Donc trouver un résultat EXACT par rapport à un résultat APPROCHANT (en terme de nombre de solution trouvées) n'aura que peu d'impact au final.

2ème version: Recherche de solutions non exhaustives, mais le plus possibles.

Au lieu de trouver des solutions en choisissant les cellules ou il faut poser des drapeaux par combinaison, autant essayer par des parcours simples.

Une ventilation d'un ilot se compose de:
- La pose d'un drapeau sur une cellule X d'un ilot (toujours possible par définition de l'ilot)
- La ventilation des autres cellules de l'ilot, et pose d'un drapeau à chaque fois que c'est possible
Un parcours se compose de N ventilations, avec X variant sur toutes les cellules afin de donner à chaque cellule sa chance d'avoir un drapeau.

Il s'agit maintenant de trouver les meilleurs ordres de parcours, pour pouvoir ventiler efficacement les cellules.

1er cycle: Ventiler les cellules, en passant à la suivante avec un incrément variable. Dans ce 1er cycle, cet incrément est un nombre 1er afin de faire varier au maximum l'ordre de prise des cellules et de ne pas retomber sur des parcours identiques.

2eme cycle: alternative au 1er cycle.

3eme cycle: Ventiler les cellules aléatoirement (après le dépôt sur 1ère cellule X toujours), pour trouver des solutions supplémentaires.

La majorité des solutions sont trouvées dans le cycle 1. En traçant la courbe du nombre de solutions trouvées (sur Y) par rapport au nombre de parcours de l'algo (X), la courbe est un hyperbole.

Le reste des solutions, 20% grosso-modo sont trouvées dans les cycles 2 et 3.


IV-A-3-d. Autres Points

Il se peut que pour de gros ilots, ces ventilations ne trouvent pas TOUTES les solutions d'un ilot. Cela a peu d'impact au final, car cela débouchera sur un calcul de taux par cellule, et se taux ne sera que grossier au lieu d'être exact... mais ce n'est qu'un taux de probabilité utilisé comme tel par la suite...

Vu la tête des parcours, les ventilations ont de fortes chances de retomber sur des solutions identiques. Pour ne pas stocker 2 fois la même solution, une liste d'Identificateur de solutions est maintenue à jour. Cette liste garde un CRC pour chaque solution trouvée, basé sur une somme de nombres premiers.

Les ilots sont traités indépendamment. Mais à l'approche de la fin du jeu, il se peut que la somme des drapeaux des solutions des 3 ilots restants par exemple, dépasse le nombre de mines restantes à trouver. Dans ce cas, on fusionne ces 3 ilots en 1 seul et on refait partir l'algorithme normalement (qui lui controle toujours qu'il n'y a pas dépassement).


IV-A-4. Mode debug.

Il permet de visualiser les solutions trouvées avec l'algorithme présenté.

Taper 'dvp' dans la zone réservée aux nombre de parties, puis valider avec 'ENTER'.
Puis cliquer sur le logo bombe.

  • Lancer Winmine d'abord avec le bouton pour tout initialiser correctement (même si le démineur est déjà ouvert).
  • Le bouton 'Jouer un tour' simule 1 tour de calcul comme présenté en section 3.1
  • Pour visualiser (et construire!) tous les ilots en cours, cliquer sur le bouton 'Créer et voir ilots'
    • Attention, si la modification (clic cellule) a été faite par l'utiliseur, cliquer au préalable sur le bouton 'MajGrille'.
  • Pour visualiser l'ensemble des solutions de tous les ilots, cliquer sur 'Résoudre Ilots'
    • Attention, les ilots doivent avoir été créés avant cette action
    • Chaque ligne représente 1 solution pour 1 ilot donné. Les lignes sont au format 'N°ilot | Nombre de drapeaux de la solution'
    • Cliquer sur une ligne pour faire apparaitre la solution dans le démineur (sous forme de point d'interrogation sur les cellules)
    • Eventuellement, recliquer sur 'Résoudre Ilot' pour constater que l'algo ne trouve pas les mêmes solutions (!), notamment pour les gros ilots.

IV-A-5. Conclusion

Le développement m'a bien pris quelques journées pleines, si on compte les premiers algorithmes combinatoires que j'ai jetés par la suite...

A peu près 5-10% du temps pour la partie technique et 90% pour la recherche du meilleur algo pour la résolution.

Sacré prise de tête pour... un programme qui ne sert à rien ;)

La manipulation technique du démineur et la résolution basique dépassées, il n'y avait finalement aucune limite à chacun pour faire mieux que son voisin.
C'est ce qui a donné tout l'intérêt de ce défi je pense. Et nous avons d'ailleurs tous des solutions assez différentes :).

TicTacToe le 28 juillet 2006


IV-B. Les sources de la solution


V. Les solutions des challengers


V-A. La solution de titi


V-B. La solution de Toto



Valid XHTML 1.1!Valid CSS!

Copyright © 2006 NoisetteProd Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents et images sans l'autorisation expresse de Developpez LLC. Sinon vous encourez selon la loi jusqu'à trois ans de prison et jusqu'à 300 000 € de dommages et intérêts.

Responsables bénévoles de la rubrique Delphi : Gilles Vasseur - Alcatîz -