Code du jeu Démineur sur c. Algorithmes de logique de bot pour le jeu Minesweeper. Méthode de création et de conversion de groupes

Tous ceux qui travaillent avec système opérateur Windows, le jeu Démineur est bien connu. Cette section traite d'un programme similaire.

Un exemple de la fenêtre du programme à la fin du jeu (après que le joueur a ouvert la cellule contenant la mine) est illustré à la Fig. 10.7.

Riz. 10.7. Fenêtre de démineur

Règles du jeu et présentation des données

Le terrain de jeu se compose de cellules, chacune pouvant contenir une mine. La tâche du joueur est de trouver toutes les mines et de les marquer avec des drapeaux.

À l'aide des boutons de la souris, le joueur peut ouvrir la cellule ou y placer un drapeau, indiquant ainsi qu'il y a une mine dans la cellule. La cellule est ouverte en cliquant sur le bouton gauche de la souris, la case à cocher est définie en cliquant sur le bouton droit de la souris. S'il y a une mine dans la cellule que le joueur a ouverte, une explosion se produit (le sapeur a fait une erreur et, comme vous le savez, ne fait qu'une seule erreur) et le jeu se termine. S'il n'y a pas de mine dans la cellule, alors un nombre apparaît dans cette cellule correspondant au nombre de mines situées dans les cellules voisines.

En analysant les informations sur le nombre de mines dans les cellules adjacentes à celles déjà ouvertes, le joueur peut trouver et signaler toutes les mines. Il n'y a aucune restriction sur le nombre de cellules marquées par des drapeaux. Cependant, pour terminer le jeu (pour gagner), les drapeaux doivent être placés uniquement dans les cellules qui ont des mines. Un drapeau sélectionné par erreur peut être supprimé en cliquant avec le bouton droit de la souris sur la cellule dans laquelle il se trouve.

Chacun de nous a probablement déjà joué, ou du moins essayé de jouer au démineur (MineSweeper). La logique du jeu est simple, mais à un moment donné, ils ont même promis une récompense pour l'algorithme de son passage. Dans mon bot, la logique a trois algorithmes qui sont utilisés en fonction de la situation sur le terrain. L'algorithme principal vous permet de trouver toutes les cellules avec une probabilité de 100 et 0 % de trouver une mine. En utilisant uniquement cet algorithme et en ouvrant des cellules arbitraires au hasard en l'absence de solution fiable dans un sapeur standard au niveau "Expert", vous pouvez obtenir 33% des gains. Cependant, certains algorithmes supplémentaires permettent de porter cette valeur à 44 % (Windows 7).

Algorithme de base

L'algorithme principal est le suivant. Les cellules inconnues (classe Cellule) adjacentes à une cellule ouverte forment un groupe (classe Groupe), qui contient également la valeur de la cellule à laquelle elle est adjacente.

La figure montre quatre groupes, dont certains se croisent, et certains contiennent même d'autres groupes. Dénotons (123,1) - le groupe se compose des cellules 1,2 et 3, et en même temps elles contiennent 1 mine. (5678.2) - il y a 2 mines dans quatre cellules.

Vous devez d'abord convertir les groupes. Pour ça:

1. Nous comparons chaque groupe avec chaque groupe suivant.
2. Si les groupes sont identiques, supprimez le second.
3. Si un groupe en contient un autre, soustrayez le plus petit du plus grand. C'est-à-dire qu'il y avait deux groupes (5678.2) et (5.1), c'est devenu (678.1) et (5.1) ; (2345.3) et (5.1) → (234.2) et (5.1)
4. Les groupes qui se croisent, par exemple (123.1) et (234.2), sont transformés selon le principe suivant :
   1. Créez un nouveau groupe de cellules qui se croisent (23, ?)
   2. Calculer le nombre de minutes dans nouveau groupe, égal au nombre de mines dans le groupe avec un grand nombre de mines (234,2) moins le nombre de cellules restantes dans l'autre groupe après séparation des cellules qui se chevauchent (1, ?). Autrement dit, 2-1 = 1. Nous obtenons (23.1)
   3. Si le nombre calculé de mines dans le nouveau groupe (23.1) n'est pas égal au nombre de mines dans le groupe avec moins de mines (123.1), alors arrêtez la conversion
   4. Nous soustrayons le groupe nouvellement formé des deux groupes qui se croisent. (123.1)-(23.1) = (1.0), (234.2)-(23.1) = (4.1).
   5. Ajout du groupe nouvellement formé à la liste des groupes
   Ainsi (234.2) et (123.1) → (1.0) et (23.1) et (4.1).
5. Répétez à partir de l'étape 1 jusqu'à ce qu'aucune modification ne soit apportée

Méthode de création et de conversion de groupes

/** * Crée une liste de groupes de cellules liées par une valeur de champ ouvert, et les divise également en plus petits, supprime les doublons. */ private void setGroups() (groups.clear(); for (int x = 0; x< width; x++) for (int y = 0; y < height; y++) field[x][y].setGroup(groups); // создание групп boolean repeat; do{ repeat=false; for (int i = 0; i < groups.size() - 1; i++) { // проходим по списку групп groupe groupe je = groupes.get(i); pour (int j = i + 1; j< groups.size(); j++) { // сравниваем ее с остальными меньшими группами Group groupJ=groups.get(j); if (groupI.equals(groupJ)) // удаляем mêmes groupes(groups.remove(j--);break;) Groupe parent ; // grand groupe Groupe enfant ; // groupe plus petit if (groupI.size()>groupJ.size()) // déterminer les groupes les plus grands et les plus petits par le nombre de cellules (parent=groupI;child=groupJ;) else (child=groupI;parent=groupJ ; ) if (parent.contains(child)) ( // si le plus grand contient le plus petit parent.subtraction(child); // puis soustraire le plus petit du plus grand repeat=true; // corrige le fait que les groupes ont changé ) else if (groupI.overlaps(groupJ ) > 0) ( // sinon, si les groupes se chevauchent if (groupI.getMines()>groupJ.getMines())// déterminer les groupes plus grands et plus petits par le nombre de mines (parent=groupI;child=groupJ;) else (child =groupI;parent=groupJ;) Group overlap = parent.getOverlap(child);// alors on prend le résultat de l'intersection if (overlap != null ) ( // et si cela a du sens (à la suite de l'intersection, des cellules avec 0 % ou 100 ont été révélées %) groups.add(overlap); // alors nous apportons les ajustements appropriés à la liste parent.subtraction(overlap ); child.subtraction(overlap); repeat=true; ) ) ) ) ) while(repeat); )

En conséquence, nous aurons trois types de groupes.

• le nombre de mines est nul
• le nombre de mines est égal au nombre de cellules du groupe
• un nombre de minutes non nul est inférieur au nombre de cellules dans le groupe

En conséquence, toutes les cellules du premier groupe peuvent être ouvertes en toute sécurité et marquées du deuxième groupe. C'est l'essence de l'algorithme principal.

S'il n'y a pas de solution fiable

Mais souvent, il y a des situations où il n'y a pas de solution fiable à la situation. Puis vient l'aide algorithme suivant. Son essence est d'utiliser la théorie des probabilités. L'algorithme fonctionne en deux étapes :

1. Détermination de la probabilité dans des cellules individuelles, compte tenu de l'influence de plusieurs cellules ouvertes
2. Correction des probabilités, en tenant compte de l'influence mutuelle des groupes avec des cellules communes les uns sur les autres

Considérons comment cette méthode fonctionne sur l'exemple d'une situation où seules deux cellules adjacentes avec les valeurs 4 et 2 sont ouvertes. Les probabilités de trouver des mines à partir des cellules 4 et 2 séparément sont de 4/7 = 0,57 et 2/7 = 0,28 , respectivement.

Pour calculer la probabilité de trouver une mine dans une case à côté de plusieurs cases ouvertes, on utilise la formule de calcul de la probabilité d'au moins un événement :

La probabilité de survenance d'un événement A, consistant en la survenance d'au moins un des événements A 1 , A 2 ,..., A n , indépendants dans l'agrégat, est égale à la différence entre l'unité et le produit des probabilités d'événements opposés. A=1- (1-A 1)*(1-A 2)*....*(1-A n)

Dans les cellules adjacentes, après application de cette formule, le résultat est 1-(1-0.57)*(1-0.28)=0.69.

Cependant, il convient de rappeler que la somme des probabilités dans chaque groupe de cellules doit être égale au nombre de mines dans le groupe. Par conséquent, toutes les valeurs de chaque groupe doivent être multipliées pour qu'au final leur somme soit égale au nombre de minutes. Ce nombre est égal au nombre de mines dans le groupe, divisé par la somme actuelle des probabilités des cellules du groupe :

4/(0,57+0,57+0,57+0,69+0,69+0,69+0,69)=0,895
0,57*0,895=0,485 0,69*0,895=0,618

Maintenant, les cellules qui avaient une probabilité de 0,57 ont 0,485, et celles qui ont 0,69 → 0,618
Nous effectuons un calcul similaire pour le deuxième groupe, en tenant compte de l'ajustement du précédent.

2/(0,28+0,28+0,28+0,618+0,618+0,618+0,618)=0,604
0,28*0,604=0,169 0,618*0,604=0,373

Nous voyons que la probabilité dans les cellules communes a de nouveau changé, donc cet ajustement pour chaque groupe doit être répété plusieurs fois jusqu'à ce que le système atteigne des valeurs stables, qui seront les vraies probabilités de trouver des mines dans les cellules.

4/(0,485+0,485+0,485+0,373+0,373+0,373+0,373)=1,357
0,485*1,357=0,658 0,373*1,357=0,506
2/(0,169+0,169+0,169+0,506+0,506+0,506+0,506)=0,79
0,169*0,79=0,134 0,506*0,79=0,4

… etc.

Il ne reste plus qu'à choisir l'une des cellules avec la probabilité minimale et à bouger.

Cette méthode dans le code

/** * La méthode corrige les valeurs des probabilités de trouver des mines dans les cellules, en tenant compte de l'influence mutuelle des probabilités des cellules voisines les unes sur les autres */ private void correctPosibilities())( Map cellules = nouveau HashMap<>(); // la boucle définit une seule valeur de probabilité dans chaque cellule, en tenant compte des différentes probabilités dans la cellule de différents groupes for (Group group : groups)( for (Cell cell: group.getList())( Double value ; if ( (value=cells. get(cell))==null) // si la cellule n'est pas encore dans la carte cells.put(cell,(double) group.getMines()/ group.size()); // alors ajoutez-le avec la valeur du groupe else / /s'il est déjà dans la carte, alors nous corrigeons sa valeur selon la théorie des probabilités cells.put(cell,Prob.sum(value,(double) group.getMines()/ group.size())); ) ) // la boucle corrige les valeurs en tenant compte du fait que la somme des probabilités dans le groupe doit être égale au nombre de mines dans le groupe booléen répété; do( repeat=false; for (Group group: groups)( // pour chaque groupe List prob=group.getProbabilities(); // prend une liste de probabilités de toutes les cellules du groupe en pourcentage Double sum=0.0; for (double elem:prob)sum+=elem ; // calcule sa somme int mines= group.getMines()*100; // multiplie le nombre de mines dans le groupe par cent (à cause des pourcentages) if (Math. abs(sum-mines)>1)( // si la différence entre elles est grande, alors on fait un ajustement repeat=true ; // corrige le fait de l'ajustement Prob .correct(prob,mines);//corrige la liste pour (int i=0;i< group.size();i++){ // заносим откорректированные значения из списка в ячейки double value= prob.get(i); group.getList().get(i).setPossibility(value); } } } } while (repeat); for (Cell cell:cells.keySet()){ // перестраховка if (cell.getPossibility()>99)cell.setPossibility(99); si (cell.getPossibility()<0)cell.setPossibility(0); } }

Derniers coups

Au stade final du jeu, le nombre de mines non marquées joue un grand rôle. Connaissant ce nombre, vous pouvez les remplacer par des cellules inconnues par la force brute et marquer les options appropriées. Dans le processus d'énumération des options appropriées pour chaque cellule, nous comptons le nombre de points. En divisant les valeurs résultantes par le nombre total de marques, nous obtenons la probabilité de trouver des mines pour chaque cellule. Par exemple, dans cette situation, qui semble n'avoir qu'une seule solution fiable, la dernière méthode (LastTurns) a trouvé 3 cellules avec une probabilité de 0% de trouver une mine.

LastTurns(9,21) a testé 144 combinaisons correspondantes sur 293930 possibles et a trouvé 3 cellules avec une probabilité minimale de 0%

Du point de vue de la complexité de la compréhension de l'idée, cette méthode est la plus simple, je ne vais donc pas encore l'analyser en détail.

Sa mise en œuvre

/** * Un algorithme de calcul indépendant par énumération banale. Ne peut être utilisé que si le nombre de cellules inconnues est inférieur à 30 * @return */ public ArrayList GetLastTurns() ( int minesLeft = countMinesLeft(); // nombre de mines non marquées ArrayList cellules inconnues = getUnknownCells(); // liste des cellules inconnues int notOpened = unknownCells.size(); // nombre de cellules inconnues Combinaisons d'entiers = new Sequence6().getSequensed(minesLeft, notOpened); // un tableau de diverses combinaisons d'un nombre donné de mines dans un nombre donné de cellules ArrayList liste = nouvelle ArrayList (); // liste des combinaisons possibles pour (int i = 0; i< combinations.length; i++) { // в этом цикле проходит подстановка мин из каждой комбинации и проверка на реальность такой игровой ситуации String combination = Integer.toBinaryString(combinations[i]); // преодбразование целого десятичного числа в двоичное, а затем в строку if (combination.length() < notOpened) { // добавляем необходимое количество "0" перед строковым выражением числа, чтобы длина строки равнялась количеству неизвестных ячеек String prefix = ""; for (int k = combination.length(); k < notOpened; k++) prefix += "0"; combination = prefix + combination; } for (int j = 0; j < notOpened; j++) { // расстановка мин по неизвестным ячейкам if (combination.charAt(j) == "1") unknownCells.get(j).setMine(); if (combination.charAt(j) == "0") unknownCells.get(j).setUnknown(); } if (test()) list.add(combination); // если при такой расстановке нет противоречий с известными ячейками, то заносим комбинацию в список возможных } clear(unknownCells); // возвращаем неизвестные ячейки в исходное состояние String comb = new String; list.toArray(comb); // преобразовываем список в массив, и далее работаем с массивом int possibilities2 = new int; // массив по числу неизвестных ячеек, содержащий количество вариантов, где может располагаться мина в заданной ячейке for (int i = 0; i < comb.length; i++) // цикл заполняет массив possibilities2 for (int j = 0; j < notOpened; j++) if (comb[i].charAt(j) == "1") possibilities2[j]++; // если в комбинации в определенном месте есть мина, то увеличиваем соответствующий элемент массива на 1 int min = Integer.MAX_VALUE; ArrayListminIndices = nouvelle ArrayList<>(); // liste des index avec la valeur minimale dans les possibilités2 pour (int i = 0; i< possibilities2.length; i++) { if (possibilities2[i] == min) minIndices.add(i); if (possibilities2[i] < min) { min = possibilities2[i]; minIndices.clear(); minIndices.add(i); } unknownCells.get(i).setPossibility(100*possibilities2[i]/comb.length); // устанавливаем найденные значения вероятностей в неизвестных ячейках } double minPossibility = 100.0 * possibilities2 / comb.length; System.out.println("LastTurns(" + minesLeft + "," + notOpened + ") проверил " + comb.length + " подходящих комбинаций из " + combinations.length + " возможных и нашел " + minIndices.size() + " ячеек" + " с минимальной вероятностью " + (int) minPossibility + " %"); ArrayListRésultat = nouvelle ArrayList (minIndices.size());// liste des coordonnées de cellule avec probabilité minimale pour (int index : minIndices) ( result.add(unknownCells.get(index).getPoint()); ) return result; )

Conclusion

En pratique, avec un nombre suffisant d'échantillons, les valeurs calculées et réelles des probabilités de trouver une mine dans une cellule coïncident presque. Le tableau suivant montre les résultats du bot exécuté sur Minesweeper sous Windows XP pendant une nuit, où

1. Estimé %
2. Nombre total d'ouvertures de cellules avec % calculé
3. Nombre de hits par mine
4. Réel %

1.	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
2.	31	55	117	131	304	291	303	339	507	435	479	1201	152	146	118	143	164	141	367	3968	145	63	47	26	92
3.	1	4	9	6	20	19	27	29	56	43	60	147	15	25	14	20	33	26	65	350	14	5	12	4	23
4.	3	7	7	4	6	6	8	8	11	9	12	12	9	17	11	13	20	18	17	8	9	7	25	15	25

1.	26	27	28	29	30	31	32	33	34	35	36	37	38	39	40	41	42	43	44	45	46	47	48	49	50
2.	18	10	24	18	9	11	6	135	8	2	4	2	1	3	16		2	2			1				462
3.	1	9	2	3	3	2	1	43	1	0	1	0	0	1	4		1	1			0				210
4.	5	37	11	30	33	18	16	31	12	0	25	0	0	33	25		50	50			0				45

Le grand écart dans la zone de 20-22% est probablement dû au fait que souvent ce pourcentage avait des cellules qui n'en avaient pas déjà ouvertes à proximité (par exemple, au début du jeu), et Démineur ajusté au joueur, retirant parfois une mine sous la cellule ouverte. L'algorithme de travail a été implémenté en java et testé sur un sapeur Windows standard (7 et XP), une application en VK et sur le jeu. D'ailleurs, après plusieurs jours de "problèmes techniques" lors de l'accès à mon compte depuis mon IP, le jeu a changé les règles de rémunération pour l'ouverture d'une partie du terrain : initialement il retournait 10% de la mise pour 10% du terrain ouvert, puis 5%, puis 2%, et quand j'ai arrêté de jouer, j'ai ensuite retourné 5%.