Udoskonalanie mojego algorytmu rozwiązywania problemów z saperami

Question

Zaimplementowałem w Pythonie algorytm do rozwiązywania gry "Minesweeper". Program działa w następujący sposób:

Załóżmy, że solver kliknie kwadrat o nazwie "a". Dla przykładu pozwól, aby liczba ta okazała się równa 2. Sąsiedzi kwadratu, którzy nie są jeszcze sklasyfikowani, są (ponownie na zasadzie przykładu) nazwani "b" i "c". Następnie program kojarzy kwadrat z wyrażeniem [2, {'b', 'c'}] i usuwa "a" ze wszystkich innych wyrażeń. Odliczenie, które kwadraty są kopalniami i które nie są dochodami przez parowanie uproszczeń takich wyrażeń w dwóch okolicznościach.

• Jeśli pola w jednej wypowiedzi są podzbiorem kwadratów drugiej wypowiedzi:

  [2, {'a', 'b', 'c'}], [1, {'a', 'b'}] -> [1, {'c'}], [1, {'a', 'b'}] 
  

• Jeżeli wszystkie pola w jednej wypowiedzi są ustalane za kopalnie:

  [2, {'a', 'b'}], [1, {'b', 'c'}] -> [2, {'a', 'b'}], [0, {'c'}] 
  

Następnie dla niektórych wyrażenie X, jeśli X[0] == 0, możemy swobodnie cl ick wszystkie kwadraty o nazwie w X[1], a jeśli X[0] == len(X[1]), możemy je oflagować.

Próbuję jednak uprościć identyfikację par , które są parami wyrażeń. Moje obecne podejście polega na utrzymywaniu stosu kwadratów; po kliknięciu kwadratu lub pomyślnym uproszczeniu jego wyrażenia zostaje on dodany do stosu (o ile go jeszcze nie ma). Kiedy kwadrat jest wyskakiwany ze stosu, próbuje się uprościć jego wyrażenie (X) i dowolne inne wyrażenia Y takie, że X[1] & Y[1] != set(). Algorytm kończy się, gdy stos zostanie wyczerpany. Obecnie jednak, mimo że działa to całkiem dobrze, nie jest w stanie poprawnie rozwiązać wszystkich jednoznacznych konfiguracji, a to, jak dobrze działa na danej planszy, zmienia się znacząco, jeśli zamieniam stos na kolejkę, lub użyję jakiegoś algorytmu do określenia, który kwadrat powinien być pop !

Byłbym bardzo wdzięczny za wszelkie przykłady precedensu mojego podejścia lub możliwości potencjalnej eksploracji.

Answer 1

To jest to, o czym pomyślałem, nie byłem w stanie w pełni wyobrazić sobie, jaka była twoja metoda.
Mam nadzieję, że prezentacja w formie graficznej pomoże Ci zaoszczędzić ten wysiłek.

Obrazy są wyświetlane w "kolejności czytania".

Wydaje się pasować do pracy ja zrobiłem od opublikowania tego, że dodanie do wartości podanej w nieznanym płytki liczba znanych płytek, które zyskuje jego wartość temp od mogłyby dodatkowo zwiększyć prawdopodobieństwo prawidłowego ryzyka modelowania.
(stosując tę ​​wartość temp 16 (lub 8 z pierwszej metody) jest znaczący, ponieważ jest to numer jeden kopalnia może osiągnąć sama)

---

czuję się trochę ślepy na nie widząc to szybciej .

Wszystko, co ma wartość normalizującą się do 100%, to we wszystkich przypadkach mogę znaleźć kopalnię.

Answer 2

Kilka lat temu napisałem Solvera, ale wydaje mi się, że straciłem kod od tego czasu. Pamiętam, że była to metoda brutalnej siły, która kompilowała zestawy potencjalnych min, zamiast pozostawić kombinacje spakowane tak jak wy.

Sądzę, że był on bardziej wydajny niż algorytm, z którym pracujesz. Twoje podejście może "rozwiązać" warunek, jeśli jest całkowicie wypełniony lub pusty z min, lub jeśli jest podzbiorem innego warunku. Istnieją jednak pewne dedukcje, które nie będą się z tym wiązały. Na przykład, rozważmy tę małą płytkę 7x2, gdzie a przez h płytki są nieznane:

a 2 1 2 1 2 i 
b c d e f g h 

Twoje warunki będą:

[2, {a, b, c, d}], 
[1, {c, d, e}], 
[2, {d, e, f}], 
[1, {e, f, g}], 
[2, {f, g, h, i}] 

Jeśli mam rozumieć go prawidłowo, algorytm nie może dokonać jakichkolwiek odliczeń na ten temat. Jednakże, jeśli jesteś doświadczonym graczem Saper, można uznać, że wzór w centrum 1 2 1 ma tylko jedno rozwiązanie, z kopalni poniżej tych 1 S:

a 2 1 2 1 2 i 
b 2 * 2 * 2 h 

Jest jeszcze kilka niewiadomych, z kopalni pod numerem a lub i innym pod h lub i, ale jeśli był to element większej układanki, może być w stanie wymyślić je później (lub może trzeba zgadywać).

wierzę mój zestaw podejścia kopalni pracował tak:

Dla każdej płytki, która została poszerzona, zbieranie jeden zestaw wszystkich niespienionych sąsiadów (dalej „obszar”), a listę zawierającą wszystkie zestawy kopalnie, które mogą wystąpić w tym obszarze. Tak na przykład, 5 znane kafelki w powyższym przykładzie będzie generować (od lewej do prawej):

({a, b, c, d}, [{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d}]) 
({c, d, e}, [{c}, {d}, {e}]) 
({d, e, f}, [{d, e}, {d, f}, {e, f}]) 
({e, f, g}, [{e}, {f}, {g}]) 
({f, g, h, i}, [{f, g}, {f, h}, {f, i}, {g, h}, {g, i}, {h, i}]) 

W każdym razie, aby połączyć dwa warunki bym najpierw sprawdza, czy były one pokrywają, przez przecinające się zestawy powierzchnia. Jeśli nie ma nakładania się, warunki nie mogą być użytecznie połączone.

Jeśli jednak nakładało się, nowy warunek obejmowałby połączenie ich obszarów. Jeśli chodzi o zestawy kopalni, zrobiłbym kartezjański produkt z zewnętrznych zestawów, by uzyskać pary wewnętrznych zestawów, a następnie sprawdzić, czy istnieje sprzeczność. Sprzeczność polegałaby na tym, że w przecięciu obszarów dwa zbiory nie miały dokładnie tych samych min. Gdyby nie było sprzeczności, powstałby nowy zestaw łączony ze związku lokalizacji kopalni. Oto jak pierwsze dwa rzędy powyższe łączyłby:

Intersection of areas: {a, b, c, d} & {c, d, e} = {c, d} 
New combined area: {a, b, c, d} | {c, d, e} = {a, b, c, d, e} 
Cartesian product of mine sets (with X marking contradictions): 
    | {a, b} {a, c} {a, d} {b, c} {b, d} {c, d} 
---+------------------------------------------------- 
{c}|  X  {a, c} X  {b, c} X  X 
{d}|  X  X  {a, d} X  {b, d} X 
{e}| {a, b, e} X  X  X  X  X 

New condition: ({a, b, c, d, e}, [{a, b, e}, {a, c}, {b, c}, {a, d}, {b, d}]) 

Można obliczyć szanse na każdej płytki w całym obszarze Warunkiem jest bycie kopalni przez zliczenie ile zestawów jest to część, w stosunku do tego, jak wiele zestawów są w sumie. Biorąc pod uwagę powyższy warunek, można stwierdzić, że a jest kopalnią 3/5 części czasu, podczas gdy e to tylko 1/5 czasu. Ta informacja jest ważna, gdy program musi odgadnąć lokalizację, która ma się rozwinąć, gdy nie ma żadnych gwarantowanych bezpiecznych płytek. Wydaje mi się, że wykonałem również skomplikowaną kombinatorykę, aby uwzględnić liczbę wykorzystanych min (tak, że powyższy przypadek {a, b, e} byłby ważony nieco inaczej niż w innych przypadkach, ponieważ wykorzystuje trzy miny zamiast dwóch), ale obawiam się, że nie pamiętam szczegółów.

Minesweeper to dość wymagająca gra.Uważam, że mój program był w stanie rozwiązać deski odpowiadające trudnościom "trudnym" w około 50-60% przypadków, przy czym większość strat miała miejsce w pobliżu początku (kiedy trzeba zgadywać przy niewielkiej ilości informacji do wykonania) lub bezpośrednio przy koniec (gdy często jest kilka nierozwiązywalnych obszarów, na które trzeba się domyślić). Zwykle było dość szybko, ale czasami pojawiał się wzór płytek, który powodował trzęsienie przez 10 lub 15 sekund przed wykonaniem następnego ruchu. (Minesweeper is NP-complete, więc nie jest zaskakujące, że niektóre dane wejściowe nie mogą być szybko rozwiązane!)