Les Défis DELPHI - Jouer au démineur ! 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  F.A.Q. DELPHI,
dans les  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 :
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.
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:
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. AlgorithmesIV-A-3-a. Principe général
Si la partie n'est pas finie, faire un tour de calcul qui se compose de:
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.
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.
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 solutionV. Les solutions des challengersV-A. La solution de titiV-B. La solution de Toto |
Copyright © 2006 NoisetteProd Developpez LLC. Tous droits réservés Developpez LLC. Aucune reproduction, même partielle, ne peut être faite de ce site ni 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.
