Afiliacja: Wydział Matematyki, Informatyki i Mechaniki, Uniwersytet Warszawski
Czytelnicy, którzy mieli styczność ze starszymi wersjami systemu operacyjnego Windows, z pewnością korzystali z dostępnych tam pasjansów Solitaire i FreeCell oraz gier: zręcznościowej Pinball, karcianej Kierki czy logicznej Saper. W artykule przyjrzymy się bliżej ostatniej z nich.
Zasady
Gra w Sapera polega na odkrywaniu pól prostokątnej planszy \(m\times n,\) na której ukryto \(k\) min (liczba ta jest znana uczestnikowi przed rozpoczęciem rozgrywki). Miny rozmieszczone są losowo – każdy układ pojawia się w grze z takim samym prawdopodobieństwem. Gdy pole z miną zostanie odkryte, dochodzi do wybuchu, a gracz przegrywa. W przeciwnym razie na odkrytym polu pojawia się liczba sąsiednich pól, na których są ukryte miny (pola sąsiadują, jeśli stykają się bokiem lub wierzchołkiem). Celem gry jest zlokalizowanie wszystkich min. Dla przejrzystości, pola z zerem wyświetlane są jako puste, a żeby przyspieszyć rozgrywkę, odkrycie takiego pola automatycznie odsłania również wszystkie pola sąsiednie. Gracz ma możliwość stawiania flag na polach – oznacza w ten sposób miejsca, w których znajduje się mina.
Przykładowa pozycja końcowa na planszy \(7\times 5,\) na której ukryto \(6\) min.
Podstawowe techniki
Liczby na odsłanianych polach dają graczowi informacje, które można wykorzystać do lokalizacji min. Często ze stuprocentową pewnością uda nam się odkryć pole lub oznaczyć je flagą. Przydatne są następujące dwie proste obserwacje.
Jeśli na polu jest liczba \(j\) i pole to sąsiaduje z dokładnie \(j\) nieodkrytymi polami, to na każdym z nich jest mina.
Jeśli na polu jest liczba \(j\) oraz postawiliśmy już \(j\) flag na polach sąsiednich, to można odkryć pozostałe sąsiednie pola.
Na zaznaczonych polach znajdują się miny.
Zaznaczone pola można odsłonić.
Na tym diagramie można odsłonić jeszcze dwa pola, ale wymaga to innych obserwacji niż powyższe. Które to pola?
Co najmniej, co najwyżej, dokładnie…
Następujący łatwy do uzasadnienia fakt daje przydatną regułę wnioskowania.
Fakt. Załóżmy, że \(a_i \leqslant b_i\) dla każdego \(i=1,2,\ldots,j\) oraz \(\sum_{i=1}^j a_i = \sum_{i=1}^j b_i.\) Wówczas \(a_i=b_i\) dla każdego \(i=1,2\ldots,j.\)
Zobaczmy, jak zastosować ten fakt na powyższym przykładzie. Oznaczmy niektóre pola literami A, B i C, tak jak przedstawiono to na diagramie. Wówczas pola A łącznie skrywają co najwyżej jedną minę (gdyż sąsiadują z polem z jedynką), pole B skrywa co najwyżej jedną minę (jest to oczywiste – mina albo jest, albo jej nie ma), a pola C – łącznie co najwyżej jedną minę (analogicznie jak dla pól A). Ale łączna liczba min w polach A, B i C to trzy. Z faktu wynika więc, że we wszystkich powyższych szacowaniach zachodzą równości. Stąd mina jest na jednym z pól A, na polu B oraz na jednym z pól C. Co za tym idzie, można postawić flagę na polu B, a pokolorowane pola – odsłonić.
Końcówka gry
Rozważmy sytuację przedstawioną na poniższym diagramie.
Wygląda na to, że jesteśmy skazani na ślepy strzał, gdyż miny można umieścić na trzy różne sposoby: w dwóch skrajnych polach lub w jednym ze środkowych pól.
Jeżeli jednak jest to końcówka gry i są to jedyne nieodkryte pola na planszy, to gra jest wygrana. Wiemy bowiem, ile min zostało do znalezienia. Jeśli do zlokalizowania zostały dwie miny, to znajdują się one w skrajnych polach – odkrywamy dwa środkowe pola i wygrywamy. Jeśli do znalezienia została jedna mina, to znajduje się ona w jednym ze środkowych pól. Odkrywamy skrajne pola i na podstawie ujawnionych liczb lokalizujemy minę.
W trakcie rozgrywki nad planszą wyświetlana jest liczba min pomniejszona o liczbę postawionych flag.
Rzućmy okiem na inny przykład.
Miny można umieścić na cztery różne sposoby. Jeśli do zlokalizowania została jedna lub trzy miny, to gra kończy się zwycięstwem. Jeśli zaś zostały dwie miny, jesteśmy zmuszeni do odkrycia losowego pola i wygrywamy z prawdopodobieństwem \(\frac 12.\)
Jak tu grać?
Często nie da się bezpiecznie odkryć żadnego pola ze stuprocentową pewnością. W takiej sytuacji pozostaje tylko strzał w niepewne pole. Przy odrobinie szczęścia nie trafimy w minę i gra toczy się dalej. Jak pomóc szczęściu? To jasne – należy odkrywać pola o niskim prawdopodobieństwie posiadania miny.
Weźmy pod uwagę następujący przykład. Gramy na poziomie początkującym (\(10\) min na planszy \(9\times 9\)). W pierwszym ruchu odsłoniliśmy lewe górne pole i ujrzeliśmy jedynkę. W tym momencie prawdopodobieństwo, że na sąsiednim polu jest mina, wynosi \(\frac 13,\) a na polu niesąsiadującym – \(\frac{9}{77} \approx 11{,}69\%.\) Aby zminimalizować ryzyko przegranej, odsłoniliśmy pole niesąsiadujące z narożnym polem, a konkretnie w pierwszym wierszu i trzeciej kolumnie. Znowu odkryta została jedynka. Które pole teraz najlepiej odsłonić? Przed przeczytaniem dalszej części tekstu proponujemy Czytelnikowi zastanowić się nad tym samodzielnie.
W grze dostępne są też: poziom średniozaawansowany (\(16\times 16,\) \(40\) min), poziom ekspert (\(30\times 16,\) \(99\) min) oraz gra na planszy o wymiarach i liczbie min wybranych dowolnie przez gracza.
Obliczmy. Oznaczmy pola literami A, B, C tak jak na diagramie. Jeśli pole A nie zawiera miny, to jedno z pól B zawiera minę i wtedy pola C są puste – dwie możliwe opcje. Jeśli zaś pole A zawiera minę, to pola B są puste i jedno z pól C zawiera minę – trzy możliwości w tym przypadku. Łącznie mamy pięć scenariuszy, z których wynika, że pole A zawiera minę z prawdopodobieństwem \(p_{\textbf{A}}=\frac 35 = 60\%,\) a pola B i C z prawdopodobieństwem \({p_{\textbf{B}}=p_{\textbf{C}}=\frac 15 = 20\%}.\) Jakie jest prawdopodobieństwo, że pole nieoznaczone literą ma minę? W dwóch z pięciu opisanych scenariuszy prawdopodobieństwo to wynosi \(\frac{9}{73},\) a w trzech pozostałych \(\frac{8}{73}.\) Szukane prawdopodobieństwo wynosi \({\frac 25 \cdot \frac{9}{73} + \frac 35 \cdot \frac{8}{73} = \frac{42}{365} \approx 11{,}51\%}.\) Najlepiej więc odsłonić pole niesąsiadujące z odkrytymi dotąd polami.
Czy doszedłeś, Drogi Czytelniku, do takich samych wniosków? Jeżeli tak, to… pomyliłeś się! Okazuje się, że powyższe wyliczenia są niepoprawne i prowadzą do błędnej odpowiedzi. Co poszło nie tak?
Układy, w których mina znajduje się na jednym z pól B, występują znacznie częściej niż pozostałe układy. Dlaczego? Po umieszczeniu miny na jednym z dwóch pól B pozostaje \(9\) min do ustawienia na \(73\) polach. Liczba takich układów to \(2\cdot \binom{73}{9}.\) Jeśli zaś pozostawimy oba pola B bez min, to musimy postawić minę na polu A oraz drugą minę na jednym z trzech pól C. Pozostało \(8\) min do umieszczenia na \(73\) polach – takich układów jest \(3\cdot \binom{73}{8}.\)
Poprawnie obliczone prawdopodobieństwa to: \[\begin{aligned} p_{\textbf{A}} & =\frac{3 \cdot \binom{73}{8}}{3 \cdot \binom{73}{8} + 2 \cdot \binom{73}{9}} = \frac{27}{157} \approx 17{,}20\%, \\ p_{\textbf{B}} & =\frac{\binom{73}{9}}{3 \cdot \binom{73}{8} + 2 \cdot \binom{73}{9}} = \frac{65}{157} \approx 41{,}40\%, \\ p_{\textbf{C}} & =\frac{\binom{73}{8}}{3 \cdot \binom{73}{8} + 2 \cdot \binom{73}{9}} = \frac{9}{157} \approx 5{,}73\% . \end{aligned}\] Przy tym prawdopodobieństwo, że pole nieoznaczone żadną literą zawiera minę, jest zbliżone do zagęszczenia min na planszy, czyli równe około \(\frac{10}{81}\approx 12{,}35\%.\)
Można obliczyć, że wynosi dokładnie \(\frac{1386}{11461} \approx 12{,}09\%\) – przeprowadzenie stosownego rachunku pozostawiamy Czytelnikowi Pracowitemu.
Mamy werdykt: najbezpieczniej jest odkryć jedno z pól C.
Wybierz mądrze
Rozważmy poniższą sytuację.
Szybka analiza pokazuje, że brakuje dwóch min i mogą być one rozmieszczone na trzy sposoby.
Wynikają stąd takie oto prawdopodobieństwa trafienia na minę.
\(p_{\textbf{A}}=\frac 23\)
\(p_{\textbf{B}}=p_{\textbf{C}}=p_{\textbf{D}}=p_{\textbf{E}}=\frac 13\)
Wygląda na to, że najbardziej opłaca się strzelić w jedno z pól B, C, D, E i nie ma znaczenia, które z nich wybierzemy.
Czy aby na pewno? Okazuje się, że odsłonięcie pola D lub pola E jest tak samo nierozsądne, jak odsłonięcie pola A! Najlepszy ruch to odkrycie pól B i C.
Przyczyna jest następująca: po strzale w pole D bądź E, jeśli nie trafimy w minę, znowu trzeba strzelać! Prawdopodobieństwo wygranej wynosi \(\frac 23 \cdot \frac 12 = \frac 13.\)
Jeśli pole D nie ma miny, to ma czwórkę.
Jeśli pole E nie ma miny, to ma dwójkę.
Z kolei przy strzałach w pola B i C, jeśli nie trafimy w minę, to jedna mina jest na polu A, a druga na jednym z pól D, E. Na którym? O tym dowiadujemy się na podstawie liczby odsłoniętej na polu B. Nie ma potrzeby strzelania, a szansa na sukces wynosi \(\frac 23\) – jest dwa razy większa niż dla pozostałych pól.
Jeśli pola B i C nie mają miny, to w C jest trójka, a w B czwórka lub trójka.
Na deser
Ten przydługi tekst zakończymy zadaniem do samodzielnego rozwiązania.
Znajdź wszystkie pola, które można bezpiecznie odkryć, oraz wszystkie pola, które na pewno zawierają minę:
Zakolorowane pola można odsłonić. Krzyżyki wskazują miejsca, w których na pewno jest mina.
Gdzie pograć w Sapera? W sieci dostępnych jest wiele implementacji gry. Autor artykułu gorąco poleca stronę minesweeper.online.