III - A - Le défi en lui même

III - A - 1 - D'où est venue l'idée d'un défi dans la rubrique Delphi ?

Tout est parti d'ici, en décembre 2005, suite à une histoire de popupmenu sur un popupmenu surlaquelle toute l'équipe s'est cassée les dents :aie:.

[Participez à la FAQ !] La question de la semaine


Devant l'impuissance générale pour ce genre de question tordue, Hauwke a proposé une idée de défi sur le forum :

Défis de prog sur le forum


Devant l'enthousiasme général, j'ai alors entamé les hostilité, avec un sujet qui tout bête sur lequel je m'était déjà creusé la tête :

[FAQ] [Défi] Amélioration d'un TMainMenu


Le succès rencontré par cette première épreuve officieuse, nous a amené à réfléchir sur la mise en place d'un défi officiel, avec des règles à respecter, etc... (voir Le défi Delphi)


Encore restait-il à trouver un sujet au moins aussi intéressant que cette customisation du TMainMenu.


L'idée m'est venu assez rapidement, mais nous avons (l'équipe d'administration), préféré attendre un peu en vous demandant si vous aviez des idées en réserve avant de griller ce qui était notre seule et unique cartouche.


III - A - 2 - Comment m'est venue cette idée de défi ?

L'idée m'est venue en jouant une partie de démineur (comme quoi...)... Je me suis dit alors qu'il serait assez marrant (l'était-ce ?) de réaliser un programme capable de jouer tout seul :p


En plus, en aidant les uns et les autres sur le forum, j'avais déjà plus ou moins abordé les différentes possibilités qui s'offraient à moi pour réaliser au moins une maquette du projet. Le code source final est très peu éloigné du premier jet que j'ai réalisé : j'ai en effet essayé de garder à l'esprit de préserver une certaine modularité pour la partie algorithmique (j'y reviens plus loin).


Lors donc et après avoir jeté un oeil attentif à notre FAQ, je me suis apperçu qu'en cherchant un peu sur le forum et la FAQ, il était tout à fait possible de trouver ça et là les différentes briques de code nécessaires à la réalisation d'un tel programme.



III - A - 2 - Les sources et resources disponibles

Voici tout d'abord quelques fils de discussion qui m'ont inspirés :

http://www.developpez.net/forums/showthread.php?t=161268


Après, la FAQ, regorgeait d'astuces utiles pour réaliser le programme :

Comment exécuter une application extérieure ?

Comment lancer et contrôler une application extérieure ?

Comment savoir si une application est en cours d'exécution ?

Comment fermer une application externe ?

Comment connaître la position de la souris ?

Comment simuler un clic de souris ?

Comment obtenir la version de Windows ? (Pour déterminer la Version du démineur Windows 95, 98, Me, NT, 2000 ou XP)

Comment obtenir des informations sur la langue de la session d'un utilisateur ? (Quel est le nom de l'éxécutable ? Winmine.exe ou MineSweeper.exe ?)


Sinon, les fichiers d'aide de Delphi, y compris ceux de la SDK Microsoft et les moteurs de recherche sont une source d'information extraordinaires pour réaliser ce genre de programme :


Au final, après diverses recherches, tout les solution au coté "Technique" du problême étaient là :

Pour le reste, c'est à dire la résolution elle même, c'était une question d'algorithme....



III - A - 3 - La structure globale du programme

III - A - 3 - a - Les procédure et fonctions utilitaires qui exploitent les API Windows

Ces fonctions sont pour la plupart regroupées dans l'unité UnitSystem.pas. Elle permettent entre autre :


Pour mesurer le temps mis par mon programme pour résoudre une partie, je me suis appuyé sur la fonction API GetTickCount (méthodes StartChrono et StopChrono de la classe TStatistiques). En passant tous les calcul des statistiques sur les pourcentages de réussite ou d'échec du Bot-démineur sont dévolues à la classe TStatistiques, implémentée dans la variable globale Statistiques de l'unité UnitStats.pas


III - A - 3 - b - La structure des données

III - A - 3 - c - La boucle principale du programme

La visite commence par l'évènement OnClic du bouton Jouer ! qui est en fait le programme principal : procedure TFormMain.ButtonJouerClick(Sender: TObject);


Voici l'algorithme en épurant toutes les fioritures :


III - A - 3 - d - Démarrer le démineur

C'est la méthode privée DemarrerWinMine qui s'occupe de cette tâche . Pour ce faire j'ai utilisé deux fonctions de l'API Windows :


III - A - 3 - e - La résolution d'une partie de démineur

Cette lourde tâche est dévolue à la méthode privée Jouer qui appelle bien d'autres méthodes.

Voici l'algorithme :


III - A - 3 - f - Pourquoi "ScreenshotToZoneJeu" (qui signifie Capture d'écran vers ZoneJeu) ? Il n'y a pourtant pas de capture d'écran...

Initialement, cette méthode effectuait une capture d'écran de la fiche du démineur (ce qui m'a permis de tester le bon fonctionnement de mes tests de pixels ainsi que la localisation correcte de mes clics de souris.

Une fois cette partie au point, j'ai éliminé la capture de la fiche du démineur et lu directement la couleur des pixels à l'écran (beaucoup plus rapide).

A ce propos, j'ai tout de même laissé les trois fonctions à titre indicatif qui m'ont permis de faire des captures d'écran, d'une fenètre complête (barre de titre+bordure), ou de de la zone cliente d'une fenètre (fenètre complète - barre de titre - bordure) : ScreenShotDesktop, CopyWindowRectToBitmap et CopyClientRectToBitmap. C'est procédures se trouvent dans l'unité UnitSystem.pas


III - A - 3 - f - L'inventaire des cases "à Jouer"

la méthode InventaireCasesAJouer s'articule autour de trois algorithmes qui s'enchaînent ou non successivement selon qu'a chacune des étapes des cases "jouables" ont été trouvées ou non :


Mieux qu'un algorithme, le code qui tient en quelque ligne illustre la modularité de cette recherche de cases :

begin

JeuStatistique:=False;

NBreAJouer:=0;

RechercheCasesEvidentes;

if NBreAJouer=0 then RechercheSchemas;

if NBreAJouer=0 then RechercheCSP;

end;

Le premier algorithme que j'ai mis au point est celui de recheche de cases évidentes, assez simple à mettre en oeuvre, c'est l'algorithme le plus rapide, mais aussi le moins "intelligent".


Le deuxième algorithme est exécuté, lorsque le premier échoue (Nbre de cases à jouer=0).

Celui-ci découpe la ZoneDeJeu en zones plus petites et effectue une recherche systématique de toutes les combinaisons concernant les cases encore inconnues de cette zone en fonction des cases déjà connues. C'est l'algorithme que j'ai eu le plus de mal à mettre au point :aie:

A partir de là, mon bot à commencé à être un joueur "futé". Les participants du défi avait du souci à se faire à ce moment là... Jusqu'a ce que TicTacToe arrive :p


L'idée du dernier algorithme m'est arrivée que tardivement. Après de multiples recherche sur les méthodes de résolution statistique sur internet, je suis "tombé" sur un code (pas en Delphi) parlant de "Programmation par satisfaction de Contraintes" pour résoudre le démineur, de site disant que le démineur était un problème "P-Complete" et j'en passe. J'avoue ne pas avoir tout compris tout de suite, j'en rigole encore...

Toujours est-il que le dit code, utilisant un langage de programmation "ensembliste" n'était pas du tout, mais alors vraiment pas transposable en Delphi. Et puis je me suis documenté et compris que l'on avait tout bêtement affaire à la résolution d'un système à N inconnues (N cases inconnues) et M équations (M1 cases indiquant un nombre de mines, 1 équation contabilisant le nombre de mines restant à découvrir) avec N>M. Du coup on se retrouve avec plusieurs solutions, et il reste à dénombrer l'état des inconnues pour chacune de ces solution ("mine" ou "pas mine" ?). Lorsque l'on divise par le nombre total de solution valides (toutes les inconnues valent 1 ou 0 et rien d'autre), on se retrouve avec la probabilité d'avoir une mine (J'aime quand les maths sont présentés simplement, on comprend mieux)

Après avoir résolu plusieurs détails techniques question "dénombrement de solutions" (Dites, on fait comment avec les factorielles quand les nombres sont trop grand pour Delphi ? Comment éviter les erreurs d'arrondi lors d'un pivot de Gauss ? etc...), j'ai commencé à coder... J'y ai cru jusqu'à ce que je fasse un malaise dû à un trop grand surmenage (trop d'activités à la fois, trop de boulot, trop de tout...).

Heureusement, j'ai pu le finaliser mais par contre, santé oblige, je ne me suis pas attardé sur son optimisation.... ça marche, c'est le principal.


III - A - 4 - Les algorithmes de résolution en détail

III - A - 4 - a - recheche de cases évidentes

blabla

III - A - 4 - b - recheche de schémas

blabla

III - A - 4 - c - recheche CSP (Constraint Satisfaction Problem)

blabla