생산 

콘솔 게임 지뢰찾기 구현 페이지. 지뢰찾기 게임용 봇 논리 알고리즘. 이 방법은 코드에서

아마도 우리 각자는 MineSweeper를 플레이해 본 적이 있거나 적어도 플레이해 본 적이 있을 것입니다. 게임의 논리는 간단하지만 한때는 알고리즘을 완성하면 보상을 약속하기도 했습니다. 내 봇의 로직에는 현장 상황에 따라 사용되는 세 가지 알고리즘이 있습니다. 기본 알고리즘을 사용하면 지뢰를 찾을 확률이 100%와 0%인 모든 셀을 찾을 수 있습니다. "전문가" 수준의 표준 지뢰 찾기에서 신뢰할 수 있는 솔루션이 없는 경우 이 알고리즘만 사용하고 임의의 셀을 무작위로 열면 33%의 승리를 얻을 수 있습니다. 그러나 일부 추가 알고리즘은 이 값을 44%(Windows 7)로 높일 ​​수 있습니다.

기본 알고리즘


기본 알고리즘은 다음과 같습니다. 하나의 열린 셀에 인접한 미지의 셀(Cell 클래스)은 그룹(Group 클래스)으로 구성되며, 이는 인접한 셀의 값도 기록합니다.

그림은 4개의 그룹을 보여줍니다. 그 중 일부는 겹치고 일부는 다른 그룹을 포함하기도 합니다. (123,1)을 표시해 보겠습니다. 그룹은 셀 1,2, 3으로 구성되며 동시에 그 안에 1개의 광산이 있습니다. (5678.2) - 4개의 셀에 2개의 지뢰가 있습니다.

먼저 그룹을 변환해야 합니다. 이를 위해:

  1. 각 그룹을 각 후속 그룹과 비교합니다.
  2. 그룹이 동일하면 두 번째 그룹을 삭제하십시오.
  3. 한 그룹에 다른 그룹이 포함되어 있으면 큰 그룹에서 작은 그룹을 뺍니다. 즉, 두 그룹(5678.2)과 (5.1)이 있었는데, 지금은 (678.1)과 (5.1)입니다. (2345.3) 및 (5.1) → (234.2) 및 (5.1)
  4. 다음 원칙에 따라 교차 그룹(예: (123,1) 및 (234,2))을 변환합니다.
    1. 교차하는 셀의 새로운 그룹 생성(23,?)
    2. 우리는 광산 수를 계산합니다 새 그룹, 지뢰 수가 많은 그룹의 지뢰 수(234.2)에서 교차하는 셀을 분리한 후 다른 그룹의 남은 셀 수(1,?)를 뺀 것과 같습니다. 즉, 2-1 = 1입니다. 우리는 (23.1)을 얻습니다.
    3. 새 그룹의 계산된 지뢰 수(23.1)가 지뢰가 더 적은 그룹의 지뢰 수(123.1)와 같지 않으면 변환을 중지합니다.
    4. 교차하는 두 그룹에서 새로 형성된 그룹을 뺍니다. (123.1)-(23.1) = (1.0), (234.2)-(23.1) = (4.1).
    5. 그룹 목록에 새로 형성된 그룹을 추가합니다.
    따라서 (234.2) 및 (123.1) → (1.0) 및 (23.1) 및 (4.1).
  5. 변경 사항이 없을 때까지 1단계부터 반복합니다.

그룹 생성 및 변환 방법

/** * 단일 값으로 관련된 셀 그룹 목록을 만듭니다. 개방 구역, 또한 작은 항목으로 나누고 중복 항목을 제거합니다.< 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++) { // проходим по списку групп */ private void setGroups() ( groups.clear(); for (int x = 0; x그룹 그룹< groups.size(); j++) { // сравниваем ее с остальными меньшими группами Group groupJ=groups.get(j); if (groupI.equals(groupJ)) // удаляем одинаковые группы {groups.remove(j--);break;} Group parent; // I = groups.get(i); for (int j = i + 1; j


대규모 그룹
  • 단체 아동; // 더 작은 그룹 if (groupI.size()>groupJ.size()) // 셀 수에 따라 더 큰 그룹과 작은 그룹 결정 (parent=groupI;child=groupJ;) else (child=groupI;parent=groupJ ; ) if (parent.contains(child)) ( // 더 큰 것이 더 작은 것을 포함하는 경우 parent.subtraction(child); // 더 큰 것에서 더 작은 것을 뺍니다.peat=true; // 그룹이 변경되었습니다. ) else if (groupI.overlaps(groupJ ) > 0) ( // 그렇지 않은 경우 그룹이 교차하는 경우 if (groupI.getMines()>groupJ.getMines())// 숫자로 더 큰 그룹과 작은 그룹을 결정합니다. 광산 중 (parent=groupI;child=groupJ;) else (child =groupI;parent=groupJ;) Groupoverlap = parent.getOverlap(child); // 그런 다음 교차점의 결과를 가져옵니다. if (overlap != null) ( // 그리고 그것이 타당한 경우(교차의 결과로 0% 또는 100인 셀이 %로 나타남) groups.add(overlap) // 그런 다음 목록을 적절하게 조정합니다. parent.subtraction(overlap) child; .뺄셈(겹침);
  • )
  • 결과적으로 우리는 세 가지 유형의 그룹을 가지게 됩니다.
광산 수는 0입니다
광산의 수는 그룹의 셀 수와 같습니다
0이 아닌 광산 수는 그룹의 셀 수보다 적습니다.
  1. 따라서 첫 번째 그룹의 모든 셀을 안전하게 오픈할 수 있으며, 두 번째 그룹의 모든 셀을 마킹할 수 있습니다. 이것이 주요 알고리즘의 본질입니다.
  2. 확실한 해결책이 없는 경우
그러나 상황에 대한 확실한 해결책이 없는 상황이 종종 있습니다. 그런 다음 다음 알고리즘이 구출됩니다. 그 본질은 확률 이론의 사용입니다. 알고리즘은 두 단계로 작동합니다.


여러 개의 열린 셀의 영향을 고려하여 개별 셀의 확률 결정
총체적으로 독립적인 사건 A 1, A 2,..., An 중 적어도 하나의 발생으로 구성된 사건 A의 발생 확률은 1과 다음의 곱의 차이와 같습니다. 반대 사건의 확률. A=1-(1-A 1)*(1-A 2)*....*(1-A n)
인접한 셀에서 이 공식을 적용하면 결과는 1-(1-0.57)*(1-0.28)=0.69입니다.


그러나 각 셀 그룹의 확률 합계는 그룹의 지뢰 수와 동일해야 한다는 점을 기억해야 합니다. 따라서 각 그룹의 모든 값은 결국 그 합계가 분 수와 같도록 곱해야 합니다. 이 숫자는 그룹의 지뢰 수를 그룹 셀의 현재 확률 합계로 나눈 값과 같습니다.
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

이제 확률이 0.57인 셀은 0.485이고 확률이 0.69 → 0.618인 셀은 0.618입니다.
이전 그룹의 조정을 고려하여 두 번째 그룹에 대해서도 유사한 계산을 수행합니다.
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

일반 셀의 확률이 다시 변경되었으므로 시스템이 안정적인 값에 도달할 때까지 각 그룹에 대한 이러한 조정을 여러 번 반복해야 하며, 이것이 셀에서 지뢰를 발견할 실제 확률이 됩니다.
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

… 등.


남은 것은 최소한의 확률로 셀 중 하나를 선택하고 이동하는 것입니다.

이 방법은 코드에서

/** * 이 방법은 인접한 셀이 서로에게 미치는 확률의 상호 영향을 고려하여 셀에서 지뢰를 발견할 확률을 조정합니다. */ private void rightPosibilities())( Map 셀= 새 HashMap<>(); 문제=group.getProbabilities(); // 그룹에 있는 모든 셀의 확률 목록을 백분율로 가져옵니다. Double sum=0.0;< group.size();i++){ // заносим откорректированные значения из списка в ячейки double value= prob.get(i); group.getList().get(i).setPossibility(value); } } } } while (repeat); for (Cell cell:cells.keySet()){ // перестраховка if (cell.getPossibility()>for (이중 요소:prob)sum+=elem; // 합계를 계산합니다. intmines= group.getMines()*100; // 그룹의 광산 수에 100을 곱합니다(백분율로 인해) if (Math.abs(sum-mines)>1)( // 둘 사이의 차이가 크면 조정합니다.peat=true ; // 조정 사실을 기록합니다. Prob .cordirect(prob,mines) // 목록을 수정합니다(int i=0;i)<0)cell.setPossibility(0); } }

99)cell.setPossibility(99);
if (cell.getPossibility()


마지막 움직임

게임의 마지막 단계에서는 표시되지 않은 지뢰의 수가 큰 역할을 합니다. 이 번호를 알면 이를 알 수 없는 셀에 무차별 대입하여 대체하고 적절한 옵션을 표시할 수 있습니다. 각 셀에 적합한 옵션을 검색하는 과정에서 마크 수를 계산합니다. 결과 값을 총 마크 수로 나누어 각 셀에 대해 지뢰를 찾을 확률을 얻습니다. 예를 들어 신뢰할 수 있는 솔루션이 하나만 있을 것 같았던 이 상황에서 마지막 방법(LastTurns)은 지뢰를 찾을 확률이 0%인 셀 3개를 발견했습니다.

LastTurns(9,21)는 가능한 293930개의 조합 중 144개의 적합한 조합을 확인하고 최소 확률이 0%인 3개의 셀을 찾았습니다.

아이디어 이해의 복잡성 측면에서 볼 때 이 방법이 가장 쉬우므로 아직 자세히 분석하지는 않겠습니다. 구현 /** * 진부한 무차별 대입을 사용한 독립적인 계산 알고리즘. 알 수 없는 셀의 수가 30개 이하인 경우에만 사용할 수 있습니다. * @return */ public ArrayList GetLastTurns() ( intminesLeft = countMinesLeft(); // 표시되지 않은 채로 남아 있는 지뢰 수 ArrayList 알 수 없는Cells = getUnknownCells(); // 알 수 없는 셀 목록 int notOpened =knownCells.size(); // 알 수 없는 셀 수 정수 조합 = new Sequence6().getSequensed(minesLeft, notOpened); // 주어진 수의 ArrayList 셀에 있는 지정된 수의 지뢰의 다양한 조합 배열< 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; ArrayList목록 = 새로운 ArrayList<>(); // (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 + " %"); ArrayListminIndices = 새 ArrayList (); //possistance2에서 최소값을 갖는 인덱스 목록 for (int i = 0; i

결과 = 새로운 ArrayList
실제로 충분한 수의 샘플을 사용하면 셀에서 광산을 찾을 확률의 계산된 값과 실제 값이 거의 일치합니다. 다음 표는 Windows XP의 Minesweeper에서 하룻밤 동안 실행된 봇의 결과를 보여줍니다.
  1. 추정된 %
  2. 계산된 %가 포함된 총 셀 개구부 수
  3. 지뢰당 적중 횟수
  4. 실제 %
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% 영역의 큰 불일치는 아마도 이 백분율에 근처에 아직 열려 있지 않은 셀이 있는 경우가 많고(예: 게임 시작 시) "Mineweeper"가 플레이어에 맞게 조정되었기 때문일 것입니다. 열린 셀 아래에서 광산을 제거합니다. 작업 알고리즘은 Java로 구현되었으며 VK 및 게임의 응용 프로그램인 표준 Windows 지뢰 찾기(7 및 XP)에서 테스트되었습니다. 그건 그렇고, 내 IP에서 내 계정에 액세스할 때 며칠 동안 "기술적 문제"가 발생한 후 게임은 필드 개방 부분에 대한 보상 규칙을 변경했습니다. 처음에는 개방 필드의 10%에 대해 베팅의 10%를 반환한 다음 5%, 그 다음 2%, 그리고 게임을 중단했을 때 5%를 반환했습니다.

Windows 운영 체제를 사용하는 사람이라면 누구나 지뢰 찾기 게임에 익숙할 것입니다. 이 섹션에서는 유사한 프로그램에 대해 설명합니다.

게임 종료 시(플레이어가 광산이 있는 셀을 연 후) 프로그램 창의 예가 그림 1에 나와 있습니다. 10.7.

쌀. 10.7. 지뢰찾기 프로그램 창

게임 규칙 및 데이터 프레젠테이션

플레이 필드는 셀로 구성되며 각 셀에는 지뢰가 포함될 수 있습니다. 플레이어의 임무는 모든 지뢰를 찾아 깃발로 표시하는 것입니다.

플레이어는 마우스 버튼을 사용하여 셀을 열거나 그 안에 깃발을 배치하여 셀에 지뢰가 있음을 나타낼 수 있습니다. 마우스 왼쪽 버튼을 클릭하면 셀이 열리고 오른쪽 버튼을 클릭하면 확인란이 선택됩니다. 플레이어가 연 셀에 광산이 있으면 폭발이 발생하고 (공병은 실수를 저질렀으며 우리가 알고 있듯이 그는 단 한 번의 실수만 범함) 게임이 종료됩니다. 셀에 지뢰가 없으면 인접한 셀의 지뢰 수에 해당하는 숫자가 해당 셀에 나타납니다.

플레이어는 이미 열린 지뢰와 인접한 셀의 지뢰 수에 대한 정보를 분석하여 모든 지뢰를 감지하고 플래그로 표시할 수 있습니다. 플래그가 표시된 셀 수에는 제한이 없습니다. 그러나 게임을 완료하려면(승리하려면) 지뢰가 있는 셀에만 깃발을 배치해야 합니다. 잘못 선택된 확인란은 해당 확인란이 위치한 셀을 마우스 오른쪽 버튼으로 클릭하여 제거할 수 있습니다.