Jouer au démineur ! - La solution du défieur.

Date de publication : 10 Août 2006 , Date de mise à jour : 10 Août 2006

Par Equipe DELPHI (Les Défis DELPHI)
 

Téléchargement de l'article au format PDF

I. Les sources et resources disponibles

• 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)

• 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'exécutable ? Winmine.exe ou MineSweeper.exe ?)

• Dans le SDK de Microsoft, on trouve de nombreuses explications sur les API Windows (en anglais)
• Sur Internet, de nombreux sites parlent du jeu lui-même et donnent des astuces pour résoudre certaines positions (que j'ai appelées 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".)

• 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 choisis du petit smiley qui est tantôt souriant, tantôt 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 sont les cases encore inconnues, etc...--> Capturer l'écran, puis lire la couleur de quelques pixels bien choisis de la case correspondante.

II. La structure globale du programme

II-A. Les procédure et fonctions utilitaires qui exploitent les API Windows

• 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 frappes 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 a mieux marché en utilisant la fonction de l'API Windows keybd_event qui permet d'envoyer des évènements clavier à 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).

II-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ées 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

II-C. La boucle principale du programme

• 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;)
  • Initialiser les données nécessaires à la résolution du démineur (InitZoneJeu;)
  • Jouer tout seul comme un grand (Jouer;)
  • Si EtatDuJeu=Gagné ALORS Rentrer son nom (RentreScore;)

II-D. Démarrer le démineur

• 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)

II-E. La résolution d'une partie de démineur

• 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 sûrs 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

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

II-G. L'inventaire des cases "à Jouer"

• 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

begin
	JeuStatistique:=False;
	NBreAJouer:=0;
	RechercheCasesEvidentes;
	if NBreAJouer=0 then RechercheSchemas;
	if NBreAJouer=0 then RechercheCSP;
end;

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

III. Les algorithmes de résolution en détail

III-A. recheche de cases évidentes

• SI on a Nmines=NDeminees+NInconnues, ALORS les cases inconnues sont toutes des mines et sont marquées comme cases évidentes.
• SI on a NMines=NDeminees, ALORS aucune des cases inconnues qui se trouvent autour ne sont des mines. C'est alors la case que l'on est en train de tester qui est marquée comme étant une case évidente.

	1er cas : nous avons un "1" et une seule case mitoyenne (case verte). Le résultat est évident, la case verte est marquée comme "case à jouer" avec un clic droit.
	2ème cas : nous avons un "2" et deux cases mitoyennes (case verte). Le résultat est évident, les deux cases bleu ciel sont marquées comme "case à jouer" avec un clic droit.
	3ème cas : nous avons un "1" et une case déminée autour (la jaune). Cette case (entourée en rouge) est marquée comme case évidente avec le Clic combiné des deux boutons de la souris

III-B. recherche de schémas

• Nous avons trois cases inconnues, qui ont pour voisine des cases numérotées. Nous avons donc trois cases qui seront chacunes représentée par les trois premiers bits d'un entier. Nous allons alors faire prendre a notre entier, toutes les valeurs de 0 à 7, visuellement, cela donne :
        000
        001
        010
        011
        100
        101
        110
        111
  
  
  
  Un '1' représente une case avec une mine, un '0' une case sans mine. Chacune de ces combinaisons sera appelé un schéma de test.
  
  

• Ensuite nous avons six cases "découvertes", dont trois cases "chiffrées", nous devons déterminer pour chacune d'entre elles si ce sont des case à tester ou non.
  Une case sera dite "à tester" si elle répond à ces critères :
  
  
  • C'est une case "chiffrée" : c'est à dire une case découverte et dont le nombre de mines autour est supérieur à 0
  • Si le nombre de cases inconnues qui se trouvent autour, dans notre grille de recherche est supérieur à 0.
  Celà tombe bien, nos trois cases chiffrées répondent à ces critères.
  
  

DEBUT
	REMPLACER CHAQUE "Case inconnue" DE LA "grille de test" PAR
	- "une case déminée" (une mine) SI on a un '1' DANS LE "schema de test"
	- "une case découverte" (une case vide, sans mine) SI on a un '0' DANS LE "schéma de test" 

	AFFIRMER "Le schéma est Valide"
	POUR CHAQUE "Case a tester"
		"Nbre de Mines Supposees Autour"=0
		POUR CHAQUE "Case autour de la case a tester" DANS "la Grille de Test"
			Si "Case Autour"="Case deminee" DANS LA "grille de test" MAIS PAS DANS "le terrain du démineur" ALORS INCREMENTER "Nbre de Mines Supposees Autour"

	//Premier test
	SI "Nbre de Mines Supposees Autour">"Nbre de mines Autour" (terrain du démineur) ALORS "Le schéma n'est pas valide"

	//2nd test
	SI (NbreMinesPotentiellesAutour=0) ALORS
	SI (NBredeMinesSupposeesAutour+NbreDemineeAutour)<>NbreMinesAutour ALORS "Le schéma n'est pas valide"

	//3ème test
	SI (NbreMinesPotentiellesAutour>0) ALORS	
	SI(NBredeMinesSupposeesAutour+NbreMinesPotentiellesAutour+NbreDemineeAutour)<NbreMinesAutour ALORS "Le schéma n'est pas valide"

FIN

Le Schéma 101

Le Schéma 110

• Dans les deux cas, seule la case de gauche est identique et représente une case déminée, cette case sera donc à coup sur une mine.
• Si dans plusieurs cas plausibles une case aurait toujours représenté une case "vide", cette case aurait été à coup sur une case sans mine.

• Pour identifier les cases minées, nous effectuons une succession de ET logiques :
  Résultat=111111111 and 101 and 110, d'où Résultat=100.
  Ceci signifie clairement que notre case de gauche est une case minée à coup sur.
  
  
  
• Pour identifier les cases non-minées, nous effectuons une succession de ET logiques avec la négation binaire de nos valeurs
  Résultat=111111111 and (not 101) and (not 110), d'où Résultat=000
  Ceci signifie clairement qu'aucune de nos case n'est à coup sur une case "vide" (sinon, on aurait eu au moins un 1).
  
  
  

III-C. Recheche CSP (Constraint Satisfaction Problem)

• Chacune de ces variables peut prendre soit la valeur 1, soit la valeur 0 : c'est ce que l'on appelle la contrainte du problème.
• Ensuite, nous obtenons un certain nombre d'équations, chacunes construite à partir des cases "Chiffrées". Pour ce faire, prenons un nouvel exemple et construisons quelques-unes de nos équations à partir des cases chiffrées marquées en rose :

	Equation A : X25+X26=1
	Equation B : X24+X25+X26=2
	Equation C : X24+X25=1
	Equation D : X24=1
	Equation E : X24=1
	Equation F : X24=1
	Equation G : X24+X25=1
	Equation H : X24+X25+X26+X27+X28=3
	Equation I : X27+X28+X29=1
	Equation J : X28+X29+X30=2
	Equation K : X29+X30=1
	Equation L : X30=1
	Equation M : X30=1

Ce genre de système, mis sous forme de matrice (ici un tableau d'entiers de 19 colonnes x 30 lignes) est résolu en utilisant un pivot de Gauss maison qui préserve les valeurs entières des coefficients : cela évite les erreurs d'arrondi que l'on rencontre dans l'algorithme habituel que l'on trouve sur internet

• Si le résultat de l'équation est positif, la somme des coefficients positifs de l'équation sera supérieure ou égale à ce résultat.
• Si le résultat est négatif, la somme des coefficients négatifs sera inférieure ou égale à ce résultat.

• Admettons que l'on obtienne Y=3, cela signifie que 3 mines se trouvent parmi 10 cases. Le schéma existera donc N0 fois pour ces 10 cases, N0 étant calculé par la fonction Combinatoire C(3,10) qui donne le nombre de façons de placer 3 mines parmis 10 cases :
• Comme je l'ai dit, les variables dépendantes ne seront pas toutes déterminées de façon unique, par exemple, suite au pivot, nous pouvons très bien nous retrouver avec une équation du style : X27+X28+X29=2. Le nombre de solutions à cette équation sera N1=C(2,3) (une mine parmis 3).
• Parfois on aura qu'une case et 0 mines : N2=C(0,1)
• etc...

• A chaque solution plausible, on totalisera le résultat N dans une variable (NTot dans le programme) qui nous permettra de calculer la probabilité de présence d'une mine pour une case donnée : P=(N1+N1'+N1''+...)/NTot

IV. Conclusion

V. Sources

Téléchargez le code source du défieur
Téléchargez l'exécutable du défieur