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

La recherche de cases évidentes est triviale.

Il consiste pour chaque case du terrain qui affiche un chiffre qui représente le nombre de mines qui se trouvent autour de vérifier si ce chiffre (appelons le Nmines) est égal au nombre de cases déminées qui se trouvent autour (Ndeminees) et au nombre de cases inconnues qui se trouvent autour (Ninconnues).

Selon que la case evidente est une mine ou non, l'algorithme indique qu'elle méthode de clic sera envisagée (Clic-droit si c'est une case à déminer, Clic simultané Gauche+Droite pour faire de la place autour de la case).


Prenons cet exemple :



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.

2è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




C'est, somme toute, la méthode de jeu que la plupart d'entre nous adopte en jouant au démineur sans trop réfléchir.


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

La recherche de schémas est beaucoup plus complexe !!!

L'algorithme commence par construire une grille de 3 x3 cases, cette grille est déplacée "au -dessus" du terrain de Jeu pour le scanner entièrement et effectue une recopie des cases qui se trouvent "en dessous". A chaque fois que la grille de recherche est déplacée, toutes les solutions "locales" sont envisagées. Dès que le scan trouve une case AJouer, il rend la main au programme, sinon il continue.

Si le scan de 3x3 à échoué, le programme effectue alors un scan avec une grille de 4x4, puis 5x5 et enfin 6x6.

Si à ce stade, la recherche est encore un échec, cet algorithme rend la main et c'est l'algorithme suivant (recherche CSP) qui prend la relève.


Pour ce qui est de la recherche de schéma dans la grille du scan, voici comment l'algorithme procède, du moins dans son principe :


Reprenons notre exemple et imaginons que notre programme est en train de passer un scan avec une grille de 3x3 :



Voici donc notre grille de recherche :



Ce que nous pouvons dire, c'est que :

- Nous avons trois cases inconnues, qui ont pour voisines des cases numérotées. Nous avons donc trois cases qui seront chacunes représentées par les trois premiers bits d'un entier. Nous allons alors faire prendre a notre entier, toutes les valeurs de 0 à 7, visuellement, celà 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 chacunes d'entre elles si ce sont des case à tester ou non.

Une case sera dite "à tester" si elle répond à ces critères :

Celà tombe bien, nos trois cases chiffrées répondent à ces critères.


Maintenant, que nos cases à tester sont identifiées, nous devons ré-examiner le chiffre qui s'y trouve.


En fait, pour chacunes de nos trois cases nous allons déterminer le nombre de mines potentiellement présentes, c'est-à-dire le nombre de cases encore inconnues sur la grille du terrain autour de notre grille de recherche :


NbreMinesPotentiellesAutour:=NbreInconnuesAutour-NbreInconnuesAutourDansSchema; -->NbreInconnuesAutour inclue les cases du terrain

if NbreMinesAutour<NbreMinesPotentiellesAutour then NbreMinesPotentiellesAutour:=NbreMinesAutour


Celà nous donne :

Pour la case...

Nbre de Mines Potentielles Autour

...de gauche

1

..du milieu

0

..de droite

1


Ensuite, nous devons tester la validité de chacun des schemas (000, 001, ..., 111), voici l'algorithme pour tester si un schéma est valide :


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


A partir de la nous savons si un schéma de jeu est plausible ou non, celà nous donne, pour chaque schéma de test concernant notre exemple :

Schéma de test

Case à tester

Nbre de Mines
Supposees autour

Nbre Mines Potentielles autour

Nbre de Mines autour

Nbre de cases déminees autour

Schéma valide pour la case à tester

Le Schéma passe le test de validité (donc schéma plausible)

0 0 0

Gauche

0

1

2

0

Non (au Test 3)

NON

Milieu

0

0

2

0

Non (au Test 2)

Droite

0

1

1

0

Oui

0 0 1

Gauche

0

1

2

0

Non (au Test 3)

NON

Milieu

1

0

2

0

Non (au Test 2)

Droite

1

1

1

0

Oui

0 1 0

Gauche

1

1

2

0

Oui

NON

Milieu

1

0

2

0

Non (au Test 2)

Droite

1

1

1

0

Oui

0 1 1

Gauche

1

1

2

0

Oui

NON

Milieu

2

0

2

0

Oui

Droite

2

1

1

0

Non (au Test 1)

1 0 0

Gauche

1

1

2

0

Oui

NON

Milieu

1

0

2

0

Non (au Test 2)

Droite

0

1

1

0

Oui

1 0 1

Gauche

1

1

2

0

Oui

OUI

Milieu

2

0

2

0

Oui

Droite

1

1

1

0

Oui

1 1 0

Gauche

2

1

2

0

Oui

OUI

Milieu

2

0

2

0

Oui

Droite

1

1

1

0

Oui

1 1 1

Gauche

2

1

2

0

Oui

NON

Milieu

3

0

2

0

Non (au Test 1)

Droite

2

1

1

0

Non (au Test 1)



Nous avons donc ici, deux schémas valides qui sont 101 et 110.

C'est-à-dire que, à coup sur, seules deux dispositions éventuelles dans notre grille de démineur sont plausibles :


Le Schéma 101


Le Schéma 110



Pour identifier ces cases "invariantes" nous effectuons une succession d'opérations bit à bit sur un masque égal à 111111111111 avec nos valeurs de schémas trouvés:


Du coup, nous obtenons à l'issue de notre algorithme un certain nombre de "Cases à Jouer" , soit avec un clic gauche, soit avec un clic droit (selon qu'il s'y trouve une mine ou non)


Bref, celà fut un vrai casse-tête à trouver l'algorithme, puis à le coder !!!


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

Sans vraiment rentrer dans les détails de l'algorithme qui est suffisemment commenté dans la procédure TFormMain.RechercheCSP;, en voici son principe de fonctionnement.

Ce dernier repose un principe qui consiste à représenter chaque "case inconnue" du plateau de jeu par une variable Xi.



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


Pour les cases chiffrées du "haut" la même mise en équations est également effectuée, ces équations impliqueront donc les variables de X10 à X14, etde X19 à X23.


Nous remarquons alors, que certaines inconnues ne sont pas encore mises en équation : de X1 à X7 et de X15 à X18.

Nous allons tout d'abord placer ces dernières inconnues, dans une seule variable qui les regroupe toutes : Y=X1+...+x7+X15+...+X18. Comme de toute façon ces variables ne peuvent être évaluées directement (elles dépendent de toutes les autres), je les ai qualifié de "non-devinables".


Puis nous allons obtenir notre toute dernière équation qui correspond à la somme de TOUT nos X, qui en toute logique, est égal au nombre de mines restant à découvrir sur le plateau : Y+X10+..+X14+X19+..+X30=10


Celà nous donne un systême de 23 équations à 30 inconnues, avec des équations dupliquées.


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 : celà évite les erreurs d'arrondi que l'on rencontre dans l'algorithme habituel que l'on trouve sur internet :aie:

A l'issue de ce pivot, certaines inconnues ne le seront plus, comme les inconnues allant de X19 à X30


D'autres seront encore sous forme d'équations. Parmis ces dernière, ont pourra identifier un bon nombre d'entre elles comme étant "dépendantes" de quelques unes que j'ai nommé dans mon code "dépendances". Les "dépendances" se retrouvent dans plusieurs équations du système, alors que les "dépendantes" ne se retrouvent que dans un seule équation à la fois.


En testant toutes les valeurs possibles des dépendances (0 ou 1), on obtiendra des solutions plausibles (comme dans la recherche de schémas) où les variables dépendantes prennent éfectivement les valeurs 0 ou 1. Celà se traduira par le fait que :

- 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éfatif, la somme des coefficients négatifs sera inférieure ou égale à ce résultat.

Sinon, on obtiendrait des solutions abhérantes où les variables dépendantes prennent des valeurs qu'elles ne devrait pas avoir (-10, -1, 2, 3, 8 par exemple).

Si toutes les équations sont valide, le système est cohérent, et on a alors un schéma (ou solution) plausible.


Lorsque l'on sera confronté à une solution plausible, il s'agira alors de dénombrer le nombre de cas de figure ou le schéma apparait dans l'ensemble de toutes les combinaisons possible. C'est là ou rentre en jeu le nombre de cases "non devinables" que j'ai cité précédemment.


- Admettons que l'on obtienne Y=3, celà signifie que 3 mines se trouve parmis 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çon 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...

Le nombre solutions que représente effectivement notre schéma sera égal à N=N0xN1xN2x...xNm


Comme avec ce genre de fonctions qui normalement fait intervenir les factorielles, on se retrouve confronté à des nombres gigantesques, il a fallu "bidouiller" les mathématique officielles pour que l'algorithme de calcul sache simplifier les divisions "à la main" et utilise les propiétés du triangle de Pascal pour éviter les multiplications à n'en plus finir et les dépassements de capacité qui en résultent.


Revenons a nos cases : dans l'équation X27+X28+X29=2, chacune des cases aura 2 chances sur 3 de prendre la valeur 1, donc parmis N1=C(2,3) combinaisons différentes, la valeur prendra N1*2/3 fois la valeur 1.


- 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


Et voilà, nous obtenons ainsi des statistiques exactes pour toutes les cases de notre plateau.


Fin de l'algorithme.


Il faut préciser que cet algorithme abandonne sa recherche de lui-même s'il estime dépasser ses capacités de résolution (matrice trop grande, calcul statistique impossible, etc...) et dans le cas d'un echecs passe la main à l'algorithme le plus simple du lot : celui qui joue, dépité, une case au hasard....


III - A - 5 - Conclusion

Non seulement ce défi fut une rude épreuve, mais écrire ces lignes en fut une autre tout aussi douloureuse :aie:

Les concurrents, et en particulier TicTacToe, ont été des challengers hors-pair. Je ne peux qu'applaudir les trésors d'ingéniosité qu'ils ont déployés et la ténacité dont ils ont fait preuve. Il m'en on vraiment fait voir de toutes les couleurs !!!


80% du temps passé à développer ce logiciel aussi inutile que surprenant a été de trouver les mécanismes qui permettait de résoudre une grille de démineur..

Par ailleurs, tout comme mes concurrents j'ai moi-même appris certains aspects de la programmation que je ne connaissais pas, et ça a été vraiment enrichissant.

Par exemple je ne m'était jamais vraiment penché sur les différences notoires qu'impliquait l'utilisation de PostMessage, à la place de SendMessage.


J'ai vraiment passé un bon moment, et je ne compte plus le nombre de fous rires qui m'ont pris en voyant mon programme faire n'importe quoi !