Mayın Tarlası konsol oyununun uygulanması, s. Mayın Tarlası oyunu için bot mantık algoritmaları

Windows işletim sistemiyle çalışan herkes Mayın Tarlası oyununa aşinadır. Bu bölümde benzer bir program anlatılmaktadır.

Oyunun sonundaki program penceresinin bir örneği (oyuncu mayının bulunduğu hücreyi açtıktan sonra) Şekil 1'de gösterilmektedir. 10.7.

Pirinç. 10.7. Mayın Tarlası program penceresi

Oyun kuralları ve veri sunumu

Oyun alanı, her biri bir mayın içerebilen hücrelerden oluşur. Oyuncunun görevi tüm mayınları bulmak ve onları bayraklarla işaretlemektir.

Oyuncu, fare düğmelerini kullanarak bir hücreyi açabilir veya içine bir bayrak yerleştirebilir, böylece hücrenin bir mayın içerdiğini belirtebilir. Farenin sol tuşuna basılarak hücre açılır, sağ tuşuna basılarak onay kutusu işaretlenir. Oyuncunun açtığı hücrede bir mayın varsa, o zaman bir patlama meydana gelir (kazıcı bir hata yaptı ve bildiğimiz gibi sadece bir hata yapar) ve oyun biter. Bir hücrede mayın yoksa, o hücrede komşu hücrelerdeki mayın sayısına karşılık gelen bir sayı görünür.

Oyuncu, halihazırda açık olanların yanındaki hücrelerdeki mayın sayısı hakkındaki bilgileri analiz ederek tüm mayınları tespit edebilir ve bayraklarla işaretleyebilir. Bayraklarla işaretlenmiş hücrelerin sayısında herhangi bir kısıtlama yoktur. Ancak oyunu tamamlamak (kazanmak) için bayrakların yalnızca mayın bulunan hücrelere yerleştirilmesi gerekir. Yanlışlıkla seçilen bir onay kutusu, bulunduğu hücreye sağ tıklanarak kaldırılabilir.

Muhtemelen her birimiz Mayın Tarlası'nı oynamış veya en azından oynamayı denemişizdir. Oyunun mantığı basit ama bir zamanlar algoritmaya oyunu tamamlaması karşılığında bir ödül bile vaat etmişlerdi. Botumda mantığın sahadaki duruma göre kullanılan üç algoritması var. Ana algoritma, maden bulma olasılığı yüzde 100 ve yüzde 0 olan tüm hücreleri bulmanızı sağlar. Sadece bu algoritmayı kullanarak ve “Uzman” seviyesinde standart bir mayın tarama gemisinde güvenilir bir çözüm olmadığında rastgele hücreleri rastgele açarak %33 kazanç elde edebilirsiniz. Ancak bazı ek algoritmalar bu değeri %44'e çıkarabilir (Windows 7).

Temel algoritma

Temel algoritma aşağıdaki gibidir. Bir açık hücreye bitişik bilinmeyen hücreler (Hücre sınıfı), aynı zamanda bitişik olduğu hücrenin değerini de kaydeden bir grup (Grup sınıfı) halinde oluşturulur.

Şekilde bazıları örtüşen, hatta bazıları başka gruplar içeren dört grup gösterilmektedir. (123,1)'i gösterelim - grup 1,2 ve 3 numaralı hücrelerden oluşur ve aynı zamanda içlerinde 1 mayın bulunur. (5678.2) - Dört hücrede 2 mayın var.

Öncelikle grupları dönüştürmeniz gerekir. Bunun için:

1. Her grubu sonraki gruplarla karşılaştırırız.
2. Gruplar aynıysa ikinciyi silin.
3. Bir grup diğerini içeriyorsa, küçük olanı büyük olandan çıkarın. Yani iki grup (5678.2) ve (5.1), şimdi (678.1) ve (5.1) vardı; (2345.3) ve (5.1) → (234.2) ve (5.1)
4. Kesişen grupları, örneğin (123,1) ve (234,2) aşağıdaki prensibe göre dönüştürüyoruz:
   1. Kesişen hücrelerden oluşan yeni bir grup oluşturun (23,?)
   2. Maden sayısını hesaplıyoruz yeni Grup, çok sayıda mayının bulunduğu gruptaki mayın sayısından (234.2) kesişen hücreleri (1,?) ayırdıktan sonra diğer gruptaki kalan hücre sayısının çıkarılmasına eşittir. Yani 2-1 = 1. (23,1) elde ederiz.
   3. Yeni gruptaki hesaplanan mayın sayısı (23,1), daha az mayın bulunan gruptaki mayın sayısına (123,1) eşit değilse dönüşümü durdururuz.
   4. Yeni oluşan grubu her iki kesişen gruptan çıkarıyoruz. (123.1)-(23.1) = (1.0), (234.2)-(23.1) = (4.1).
   5. Yeni oluşturulan grubu gruplar listesine ekleyin
   Böylece (234.2) ve (123.1) → (1.0) ve (23.1) ve (4.1).
5. Hiçbir değişiklik yapılmayana kadar 1. adımdan itibaren tekrarlayın

Grup oluşturma ve dönüştürme yöntemi

/** * Bir açık alan değeriyle ilişkili hücre gruplarının bir listesini oluşturur ve aynı zamanda bunları daha küçük hücrelere bölerek kopyaları kaldırır. */ özel void setGroups() ( group.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++) { // проходим по списку групп Grup grubu ben = group.get(i); for (int j = i + 1; j< groups.size(); j++) { // сравниваем ее с остальными меньшими группами Group groupJ=groups.get(j); if (groupI.equals(groupJ)) // удаляем одинаковые группы {groups.remove(j--);break;} Group parent; // büyük grup Grup çocuğu; // daha küçük grup if (groupI.size()>groupJ.size()) // daha büyük ve daha küçük grupları hücre sayısına göre belirler (ebeveyn=grupI;çocuk=grupJ;) else (çocuk=grupI;ebeveyn=grupJ ; ) if (parent.contains(child)) ( // eğer büyük olan küçük olanı içeriyorsa parent.subtraction(child); // sonra küçük olanı büyük olandan çıkarın tekrar=true; // şunu kaydedin: gruplar değişti ) else if (groupI.overlaps(groupJ ) > 0) ( // aksi takdirde gruplar kesişirse if (groupI.getMines()>groupJ.getMines())// sayıya göre daha büyük ve daha küçük grupları belirleyin mayın sayısı (ebeveyn=grupI;çocuk=grupJ;) else (çocuk =grupI;ebeveyn=grupJ;) Grup örtüşmesi = parent.getOverlap(çocuk); // sonra kesişimin sonucunu alın if (overlap != null) ( // ve eğer mantıklıysa (kesişme sonucunda %0 veya 100'lük hücreler ortaya çıktı) group.add(overlap); // sonra listede uygun ayarlamaları yapın parent.subtraction(overlap); .çıkarma(örtüşme); )

Sonuç olarak üç tür grubumuz olacak.

• mayın sayısı sıfır
• mayın sayısı gruptaki hücre sayısına eşittir
• sıfır olmayan bir mayın sayısı gruptaki hücre sayısından azdır

Buna göre birinci gruptaki tüm hücreler güvenli bir şekilde açılabilir, ikinci gruptaki tüm hücreler işaretlenebilir. Ana algoritmanın özü budur.

Güvenilir bir çözüm yoksa

Ancak çoğu zaman duruma güvenilir bir çözüm bulunmadığı durumlar da vardır. Sonra aşağıdaki algoritma kurtarmaya geliyor. Özü olasılık teorisinin kullanılmasıdır. Algoritma iki aşamada çalışır:

1. Birkaç açık hücrenin etkisi dikkate alınarak tek tek hücrelerdeki olasılığın belirlenmesi
2. Ortak hücreli grupların birbirleri üzerindeki karşılıklı etkileri dikkate alınarak olasılıkların ayarlanması

Sadece 4 ve 2 değerlerine sahip iki bitişik hücrenin açık olduğu bir durum örneğini kullanarak bu yöntemin nasıl çalıştığına bakalım. 4 ve 2 numaralı hücrelerden ayrı ayrı mayın bulma olasılıkları 4/7=0,57 ve 2/7= Sırasıyla 0,28.

Birkaç açık hücrenin yanındaki bir hücrede mayın bulma olasılığını hesaplamak için en az bir olayın olasılığını hesaplamaya yönelik formülü kullanırız:

Toplamda bağımsız A 1, A 2,..., A n olaylarından en az birinin meydana gelmesinden oluşan bir A olayının meydana gelme olasılığı, bir ile çarpımı arasındaki farka eşittir. Zıt olayların olasılıkları. A=1- (1-A 1)*(1-A 2)*....*(1-A n)

Bitişik hücrelerde bu formül uygulandıktan sonra sonuç 1-(1-0,57)*(1-0,28)=0,69 olur.

Ancak her hücre grubundaki olasılıkların toplamının gruptaki mayın sayısına eşit olması gerektiği unutulmamalıdır. Bu nedenle, her gruptaki tüm değerlerin çarpılması gerekir, böylece sonuçta toplamları dakika sayısına eşit olur. Bu sayı, gruptaki mayın sayısının grup hücrelerinin olasılıklarının mevcut toplamına bölünmesine eşittir:

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

Şimdi olasılığı 0,57 olan hücrelerde 0,485 var ve olasılığı 0,69 → 0,618 olan hücrelerde
Benzer bir hesaplamayı ikinci grup için de bir öncekinden yapılan ayarlamaları dikkate alarak yapıyoruz.

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

Genel hücrelerdeki olasılığın yeniden değiştiğini görüyoruz, dolayısıyla her grup için böyle bir ayarlamanın, sistem hücrelerde mayın bulmanın gerçek olasılıkları olacak bazı kararlı değerlere ulaşana kadar birkaç kez tekrarlanması gerekiyor.

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

… vesaire.

Geriye kalan tek şey hücrelerden birini minimum olasılıkla seçip hamle yapmaktır.

Bu yöntem kodda

/** * Yöntem, komşu hücrelerin olasılıklarının birbirleri üzerindeki karşılıklı etkisini dikkate alarak hücrelerde mayın bulma olasılıklarında ayarlamalar yapar */ Private void CorrectPosiibility())( Map hücreler = yeni HashMap<>(); // döngü, bir hücrede farklı gruplardan farklı olasılık değerlerini dikkate alarak her hücrede tek bir olasılık değeri ayarlar for (Grup grubu: gruplar)( for (Hücre hücresi: group.getList())( Double value; if ((value=cells.get(cell))==null) // eğer hücre henüz haritada değilse Cells.put(cell,(double) group.getMines()/ group.size()); sonra bunu else / / grubundan gelen değerle ekleriz, eğer haritada zaten varsa, değerini olasılık teorisine göre ayarlarız Cells.put(cell,Prob.sum(value,(double) group.getMines()/) group.size()) ) ) // döngü, gruptaki olasılıkların toplamının grup boole tekrarındaki mayın sayısına eşit olması gerektiğini dikkate alarak değerleri düzeltir; do( tekrar=yanlış; for (Grup grubu: gruplar)( // her grup için Liste prob= group.getProbability(); // gruptaki tüm hücrelerin olasılık listesini yüzde cinsinden al Çift toplam=0.0; for (Çift eleman:olasılık)toplam+=elem; // toplamını hesapla int mines= group.getMines()*100; // gruptaki mayın sayısını yüz ile çarpın (yüzdelerden dolayı) if (Math.abs(sum-mines)>1)( // aralarındaki fark büyükse bir ayarlama yaparız tekrar=true ; // ayarlamanın gerçekliğini kaydedin Prob .correct(prob,mines); (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); if (cell.getPossibility()<0)cell.setPossibility(0); } }

Son hamleler

Oyunun son aşamasında işaretlenmemiş mayınların sayısı büyük rol oynuyor. Bu sayıyı bildiğinizde, bunları bilinmeyen hücrelere kaba kuvvetle yerleştirebilir ve uygun seçenekleri işaretleyebilirsiniz. Her hücre için uygun seçenekleri arama sürecinde işaret sayısını sayarız. Ortaya çıkan değerleri toplam işaret sayısına bölerek her hücre için mayın bulma olasılığını elde ederiz. Örneğin tek güvenilir çözümü var gibi görünen bu durumda, son yöntem (LastTurns) mayın bulma olasılığı %0 olan 3 hücre buldu.

LastTurns(9,21) mümkün olan 293930 kombinasyondan 144'ünü kontrol etti ve minimum %0 olasılıkla 3 hücre buldu

Fikri anlamanın karmaşıklığı açısından bu yöntem en kolay yöntemdir, bu yüzden henüz ayrıntılı olarak analiz etmeyeceğim.

Onun uygulanması

/** * Sıradan kaba kuvvet kullanan bağımsız hesaplama algoritması. Yalnızca bilinmeyen hücre sayısı 30'dan fazla değilse kullanılabilir * @return */ public ArrayList GetLastTurns() ( int minesLeft = countMinesLeft(); // işaretlenmemiş kalan mayın sayısı ArrayList bilinmeyenCells = getUnknownCells(); // bilinmeyen hücrelerin listesi int notOpened = bilinmiyorCells.size(); // bilinmeyen hücrelerin sayısı Tamsayı kombinasyonları = new Sequence6().getSequensed(minesLeft, notOpened); // belirli sayıda ArrayList hücresinde belirli sayıda mayının farklı kombinasyonlarından oluşan bir dizi liste = yeni DiziListesi (); // (int i = 0; i) için olası kombinasyonların listesi< 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 = yeni ArrayList<>(); // olasılıklar2'deki minimum değere sahip indekslerin listesi for (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 + " %"); ArrayListSonuç = yeni ArrayList (minIndices.size());// minimum olasılığa sahip hücre koordinatlarının listesi (int index: minIndices) ( result.add(unknownCells.get(index).getPoint()); ) dönüş sonucu; )

Çözüm

Uygulamada, yeterli sayıda örnekle, bir hücrede mayın bulma olasılıklarının hesaplanan ve gerçek değerleri neredeyse örtüşmektedir. Aşağıdaki tabloda, botun Windows XP altında Mayın Tarlası'nda bir gece çalıştırılmasının sonuçları gösterilmektedir;

1. Tahmini %
2. Hesaplanan % ile toplam hücre açıklığı sayısı
3. Mayın başına isabet sayısı
4. Gerçek %

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

%20-22'lik alandaki büyük tutarsızlık muhtemelen bu yüzdedeki hücrelerin genellikle yakınlarda açık olmayan hücrelere sahip olmasından (örneğin, oyunun başında) ve bazen oyuncuya uyarlanmış "Mayın Tarlası"ndan kaynaklanmaktadır. açılan hücrenin altından bir mayının çıkarılması. Çalışma algoritması java'da uygulandı ve standart bir Windows mayın tarama gemisi (7 ve XP), VK'daki bir uygulama ve oyun üzerinde test edildi. Bu arada, IP'mden hesabıma erişirken birkaç gün süren "teknik sorunlar" sonrasında oyun, sahanın bir bölümünü açma ödül kurallarını değiştirdi: başlangıçta açık alanın %10'u için bahsin %10'unu geri verdi, sonra %5, sonra %2 ve oynamayı bıraktığımda %5'e geri döndüm.