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 :
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 :
Pour
simuler l'appui de touche de clavier :
Handle
mais pas classname
Problème
avec send message et WM_CHAR
CreateProcess,
ShellExecute
Pour
simuler les clics de souris :
le
bouton milieu de la souris
Récupérer le canvas de n'importe quelle fenêtre (afin de le copier dans un bitmap puis de lire les pixels qui le composent :) ) :
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 :
Dans la SDK de Microsoft, on trouve de nombreuses explication sur les API Windows (en anglais)
Sur Internet, de nombreux site parlent du jeu lui même et donnent des astuces pour résoudre certaines positions (que j'ai appelé shémas), d'autres proposent des astuces pour tricher, et à travers ces astuces fournissent des renseignement sur les différentes versions de démineur (Par exemple, selon la version de Windows, les scores sont situés dans un fichier .ini ou plutôt dans la base de registre; parfois le fichier éxécutable s'appelle s'appelle winmine.exe, parfois minesweep.exe; le titre de la fenètre dans la version française est "Démineur", dans la version anglaise "MineSweeper".)
Au final, après diverses recherches, tout les solution au coté "Technique" du problême étaient là :
Lancer/Fermer le démineur --> lancer/Détecter/fermer une application extérieure
Cliquer sur une mine, rentrer un nom dans la fenètre des scores, choisir un niveau --> Simuler clics de souris et clavier.
Déterminer si le jeu est en cours, gagné ou perdu --> Capturer l'écran, puis lire la couleur de quelques pixels bien choisi du petit smiley qui est tantot souriant, tantot dépité ou tout fier d'avoir gagné avec ses lunettes.
Déterminer quelles sont les cases qui contiennent une indication (chiffre indiquant le nombre de mines), quelles sot les cases encore inconnues, etc...--> Capturer l'écran, puis lire la couleur de quelques pixels bien choisi de la case correspondante.
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 :
de fermer une application externe si on connait le Handle de sa fiche principale (FermerApplication). Cette fonction est utilisée dans le OnClose de la fiche principale.
de simuler des clics de souris de deux façons différentes : clic réel et clic virtuel (voir les procédures MouseClickOnScreen et VirtualMouseClickOnWindow). La première procédure utilise la fonction de l'API mouse_event, la seconde utilise le sytème d'envoi de messages Windows classique avec PostMessage.
de simuler les frappe de clavier (voir les procédures SimulateKeyDown, SimulateKeyUp, SimulateKeystroke, et SendKeys). On doit noter ici que l'on trouve sur internet une unité SendKeys.pas, beaucoup plus complexe, sans doute plus aboutie, mais que je n'ai pas réussi à utiliser. Ici, j'ai essayé de rester simple et ça mieux marché en utilisant la fonction de l'API Windows keybd_event qui permet d'envoyer des évènement claviers à la fenètre de Windows qui possède le Focus...
....Comment mettre le Focus sur une fenètre ? En cliquant sur sa barre de titre (voir la procédure ActiverFenetre)
d'obtenir la couleur d'un pixel d'une fenètre particulière (voir la fonction CouleurPixel qui utilise l'API Windows GetPixel).
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
Chaque case du jeu est représentée par un type record que j'ai appelé TCase (original non ?).
Le terrain de jeu est un tableau dynamique à deux dimensions appelé ZoneJeu contenant des TCase. Les coordonnées d'une case sont représentéees par les lettres u et v. (J'ai choisi de réserver x et y pour les coordonnées des pixels sur l'écran).
D'autres tableaux à une dimension apparaissent ça et là afin de faciliter l'inventaire de certaines cases particulières (
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 :
Prise en compte des paramètres choisis par l'utilisateur
Pour toutes les parties à Jouer : (for i:=1 to ... do)
Démarrer WinMine si il y a lieu de le faire (DemarrerWinMine;) (voir III-A-3-d)
Initialiser les données nécessaires à la résolution du démineur (InitZoneJeu;)
Jouer tout seul comme un grand (Jouer;) (voir III-A-3-e)
Si EtatDuJeu=Gagné ALORS Rentrer son nom (RentreScore;)
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 :
CreateProcess (Démarrage d'une application )
FindWindow (s'assurer de l'existence de la fenètre d'une application en connaissant son titre, et récupération de son Handle)
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 :
Désactiver le Jeu Statistique (JeuStatistique:=false;)
Affirmer que l'on joue le premier coup qui necessite un clic aléatoire puisque aucune case n'est connue (PremierCoup:=true;)
Remplir le tableau ZoneJeu avec des données actualisées (ScreenshotToZoneJeu;)
Affirmer que la partie à commencé (EtatDuJeu:=edjEnCours;)
TANT QUE la partie n'est pas terminée (UnEtatDuJeu=edjEnCours) FAIRE
SI on en est au premier coup ALORS
Démarrer le Chronomètre
Jouer une case au Hasard (JoueAuHasard;)
Affirmer que l'on est plus au premier coup
SINON
SI l'utilisateur à choisi le Mode "Triche" ALORS
on utilise l'algorithme qui triche (JoueTriche;)
on Joue les cases "candidates", c'est à dire les cases marquées "à Jouer" (JoueCasesAJouer;)
SINON on joue sérieusement :) :
Remplir le tableau ZoneJeu avec des données actualisées (ScreenshotToZoneJeu;)
Compter le Nombre de cases déminées et le nombre de cases découvertes (InventaireCases;)
Faire un inventaire des différentes cases à Jouer à travers les trois algorithmes mis au point (InventaireCasesAJouer;)
SI la fonction précédente (InventaireCasesAJouer) n'a pas trouvé de coups évidents et que l'algorithme de jeu statitique n'a pas échoué, alors le JeuStatistique est actif et dans ce cas on joue la case la moins risquée grace à JoueStatistiques
SINON
SI on a trouvé des coups surs ou évidents (NBreAJouer>0)
ALORS on Joue les cases "candidates", c'est à dire les cases marquées "à Jouer" (JoueCasesAJouer;)
SINON on Joue une case au Hasard (JoueAuHasard;)
FIN TANT QUE
Remplir le tableau ZoneJeu avec des données actualisées (ScreenshotToZoneJeu;) afin de faire un bilan de ce que l'on vient de Jouer.
Compter le Nombre de cases déminées et le nombre de cases découvertes (InventaireCases;)
Obtenir le nouvel état du jeu en testant la tête du smiley du démineur (fonction EtatduJeu;)
FIN
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 :
la recherche de cases évidentes
la recherche de cases moins évidentes (découverte de schémas)
la recherche de case par des méthodes statistiques
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