Statki

Powiedzmy że jesteś bardzo dociekliwy i chcesz wiedzieć jaka jest najlepsza strategia do grania w statki. Powiedzmy nawet że chcesz wiedzieć więcej – chcesz wiedzieć jak bardzo jest ona efektywna w stosunku do pozostałych. Powiem ci jedno. Nie wiesz na co się piszesz.

Czemu to mówię? Bo sam spróbowałem. No i otrzymanie rezultatu było bolesne, zarówno dla mojego mózgu, jak i (no, może nie tak bardzo) dla portfela. Ale może od początku.

Czym są statki?

Jest spora szansa że większość osób czytających ten wpis wie co to i/lub grało w statki. Dla tych co o tej grze nie słyszeli (są tacy, jak wynika z mojego researchu!), małe streszczenie zasad:

Grę w statki zaczyna się z dwoma identycznymi planszami, zwykle 10×10, gdzie wiersze są ponumerowane liczbami 1 – 10, a kolumny oznaczone literami A – J. Jedna z nich jest naszą planszą, druga jest planszą przeciwnika – wygląda to mniej więcej tak:

Dalej należy ustawić na swojej planszy (powiedzmy że tej po lewej) swoje statki. Najczęściej wybieranym przez wszystkie pytane przeze mnie osoby ustawieniem statków jest 4-3-2-1 (4 jednomasztowce, 3 dwumasztowce, 2 trójmasztowce i jeden czteromasztowiec). Są dwie najważniejsze reguły stawiania statków:

  • Statek nie może kolidować z innym statkiem, tj. nie mogą się one stykać ani bokami, ani rogami
  • Statek nie może „zakręcać” (musi być ustawiany w linii prostej, prawdziwe statki też nie są krzywe – ma to sens, prawda? 😉

Zastosujmy więc te reguły i ustawmy nasze statki:

Po tym jak my i nasz przeciwnik ustawimy swoje statki przychodzi czas na główną część gry – bitwę. Jeden z graczy zaczyna, podając koordynaty punktu w który chce strzelić (przykładowo – G4). Drugi gracz ma obowiązek spojrzeć na swoją planszę z statkami i powiedzieć graczowi strzelającemu czy na polu w którym strzelił był statek, oraz jeżeli był – czy go zatopił. Najczęściej używa się po prostu słów pudłotrafiony, i zatopiony. Jak wygląda nasza plansza po tym ruchu, zakładając że jesteśmy graczem strzelającym?

„.” na planszy w tym wypadku oznacza pudło. Teraz strzela drugi gracz:

Trafił! W mojej wersji nie można strzelać znowu gdy już się trafi – trzeba czekać na swoją kolej (to upraszcza analizę, BARDZO upraszcza). No i tak gra toczy się, aż jeden z graczy zatopi wszystkie statki przeciwnika. Gra jest prosta w zasadach – jednak by w nią wygrać potrzeba strategii. No i tu zaczyna się prawdziwa zabawa…

Analiza strategii

Najpierw potrzebna jest nam metoda by analizować nasze strategie pod względem ich efektywności. Są dwie możliwości, które pierwsze przychodzą na myśl:

  • Stworzenie łańcuchu Markowa dla każdej z nich i zredukowanie go
  • Symulacja metodą Monte Carlo

Chyba nietrudno się domyślić co wybrałem, sądząc po ostatnich wpisach na moim Facebooku… Była to oczywiście metoda symulacji gier (dla każdej strategii 10^6). Napisałem silnik gry oraz silnik symulujący efektywność strategii – to nie było trudne. Całość programu używanego w tym wpisie znajdziesz na moim GitHubie – dokładnie tu. W README opisane jest wszystko – jak tworzyć swoje strategie, oraz jak je testować.

Trochę zabawy z pisaniem było – najpierw należało napisać silnik samej gry, potem silnik testujący strategie (oba z tych zadań były bardzo proste) – potem przyszła pora na zaimplementowanie testowych strategii.

Walenie gdzie popadnie, czyli RandomStrategy

Pierwsza strategia, którą napisałem to RandomStrategy. Właściwie napisałem ją dla testu oraz po to, by można było łatwo porównać efektywność grania ze strategią do kompletnego braku strategii.

Implementacja jest na tyle prosta, że nie muszę cię odsyłać do githuba – mogę ją zacytować:

Nic skomplikowanego, prawda? Jedyne co robię, to losuję koordynaty punktu w który zamierzam strzelić i sprawdzam jednocześnie, czy punkt nie został już przeze mnie wcześniej zestrzelony – jeżeli wszystko jest ok, strzelam.

Oczywiście to bardzo nieefektywna strategia. Zanim spojrzymy na wykres, pomyślmy. Jaka jest szansa na wygranie gry w idealnie 20 ruchów, zakładając że na planszy jest 20 pól statków? Można ją wyrazić tak:

\displaystyle\prod_{n=0}^{19} \frac{20-n}{100-n} = \frac{20}{100} * \frac{19}{99} * ... * \frac{2}{82} * \frac{1}{81}

Czemu w ten sposób? Na początku musisz trafić dowolne z 20 pól, na których znajdują się statki. Gdy to zrobisz, pól całej planszy zostaje ci 99, a pól statków do trafienia jest już 19. Kontynuujemy oczywiście do momentu gdy zostanie nam 0 pól statków na planszy, a to stanie się po tym jak zestrzelimy ostatni punkt z 81 pozostałych mnożymy, gdyż są to zdarzenia zależne od siebie – gdy na planszy zostanie nam 99 pól do zestrzelenia, w tym 19 pól statków, wtedy jasne jest, że wcześniej musieliśmy zestrzelić jedno pole statku, inaczej nie doszłoby do takiej sytuacji.

Jak obliczyć to dokładnie? WolframAlpha może pomóc:

 

Czyli raz na 535 983 370 403 809 682 970 gier możemy spodziewać się wygranej w 20 strzałów, bez pomyłek.

Dla porównania:

  • liczba kombinacji kostki rubika 2×2 to 3674160, (to ponad 1.458*10^{14} mniej niż liczba teoretycznie wymaganych gier)
  • liczba wszystkich ludzi na świecie to około 7 220 000 000 (ponad 7.423*10^{10} razy mniej)
  • liczba kombinacji kostki rubika 3×3 to 43 252 003 274 489 856 000 (ponad 12 razy mniej)
  • liczba wszystkich atomów w obserwowalnym wszechświe dobra, stop. To po prostu gigantyczna liczba.

Zobaczmy więc wykresy (po kliknięciu większy obrazek):

Jedną z ciekawych rzeczy na tym wykresie jest to, że wykres wygranych zatrzymuje się praktycznie na 200 000 (200 026, żeby być dokładnym), a zatem \frac{1}{5} oryginalnej ilości przeprowadzonych gier (przypominam – 10^6). Zatem, \frac{1}{5} gier kończyła się dokładnie w 100 strzałów. Czemu się tak dzieje? To zostawiam tobie do sprawdzenia, wystarczy skojarzyć fakty 😉

Ta strategia, tak jak widać, za bardzo efektywna nie jest – 50% gier wymaga co najmniej 97 strzałów do zakończenia, a 99% gier będzie wymagać co najmniej 74 strzałów. Jest, no, słabo.

Oczywiście mam na to radę…

Zatrudnijmy człowieczy mózg!

Statystyczny człowiek wie jak usprawnić tą taktykę wielokrotnie – wystarczy strzelać losowo tylko do momentu, gdy nie natrafimy na statek. Gdy to się stanie, człowiek wykonuje następującą sekwencję czynności:

  1. Strzela w pola bezpośrednio stykające się w pole obok dopiero co trafionego, dopóki znowu nie trafi w pole ze statkiem,
  2. Jeżeli statek nie jest zatopiony, na podstawie tych dwóch pól określa płaszczyznę statku (pion lub poziom),
  3. Losowo strzela w pole zgadzające się z kierunkiem statku po jednej lub po drugiej stronie odkrytych pól,
  4. Jeżeli trafia, a statek nie jest zatopiony, idzie dalej w tym samym kierunku, do póki nie trafi w pustkę,
  5. Jeżeli trafił w pustkę, wraca się, i strzela z drugiej strony odkrytych pól, dopóki nie zatopi statku,
  6. Po wszystkim można otacza statek znacznikami „nie tykaj, nie ma statku na 100%” – nie może być tam statku, bo jedną z naszych reguł jest to, że statki nie mogą się stykać.

I po tym wszystkim człowiek wraca do starego, poczciwego losowego wybierania pól do strzału. Dokładnie ten algorytm implementuje moja klasa HumanStrategy – bez zbędnego przedłużania, zobaczmy jak się sprawuje:

O wiele lepiej! I jakoś ładniej to wygląda teraz, krzywa wygranych jest taką piękną krzywą dzwonowatą <3 Teraz wskaźniki są zupełnie inne – 50% gier będzie wymagało co najwyżej 58 ruchów by je wygrać, 80% wygranych gier zmieści się w 62 ruchach – to już rozumiem!

Co dało taki skok efektywności? Głównie oznaczanie pól, na których statku nie ma na 100% – będzie ich aż 2(l+2) + 2 (gdzie l to długość statku), o ile statek jest oddalony od brzegu planszy o co najmniej jedno pole z każdej strony. Chyba na pierwszy rzut oka widać, jaką przewagę to daje 😀

Ale, ale – czy można to jeszcze jakoś ulepszyć? Ano można.

I tu moc obliczeniowa komputera naprawdę wchodzi do gry.

Myślałem nad tym jak można wykorzystać moc obliczeniową komputera tak, by poprawić efektywność strategii. Wykorzystanie większej ilości mocy obliczeniowej komputera wiąże się też, oczywiście, z większym wysiłkiem w obliczaniu gier. Do tej pory efektywność obliczeniowa przedstawia się następująco (procesor i5-2410M, 2 rdzenie, 4 wątki, 4 procesy workerów):

  • RandomStrategy – 235.0 gier/s
  • HumanStrategy – 169.1 gier/s

Nie jest źle, powiedziałbym że nawet ok – takie tempo obliczania wyników gier mi pasuje. Teraz należy wymyślić strategię, która da mi lepszą efektywność pod kątem wygranych… Okazało się że wcale nie jest to trudne. Strategia którą wymyśliłem opiera się na obliczaniu prawdopodobieństwa bytności statku na danym polu dla każdym polu planszy. Jak to najłatwiej zrobić?

Chwyć sobie statek za jego początkowe pole, obróć go poziomo. Zaczynając od lewego górnego rogu planszy, przykładaj statek do kolejnych jej pól i sprawdzaj czy pasuje, tj. czy może tam być. Jeżeli tak – zwiększ licznik wszystkich pól na których mógłby być statek o 1. Tak samo zrób dla statku obróconego pionowo, oraz dla statku każdej długości, która może jeszcze istnieć na planszy. Jeżeli pole na którym akurat chcesz położyć pierwsze pole statku ma zapewnione, że pola statku tam nie będzie – nawet nie próbuj sprawdzać, czy statek może tam być. Tyle! Jeżeli chcesz zobaczyć kod implementujący ten algorytm – zobacz tu.

Teraz wystarczy postępować tak samo jak przy człowieczej taktyce, ale zamiast strzelać losowo, strzelać w pole, którego licznik posiada największą wartość! Można by jeszcze dodatkowo obliczać prawdopodobieństwa podczas szukania kierunku statku, to dodatkowo ulepszyłoby strategię – ja jednak zdecydowałem się na nieuwzględnianie tego finalnie (ale pewnie po publikacji tego wpisu i tak to zrobię). Czemu?

Wydajność. Niestety, takie masowe obliczanie matrycy prawdopodobieństwa dla całej planszy jest czasochłonne… Odbiło się to na czasie symulacji gry. Wersja po wszystkich optymalizacjach algorytmu (tak, ten algorytm o którym mówię na górze był przeze mnie modyfikowany kilka razy, by poprawić wydajność) osiąga na moim komputerze zawrotny wynik… 4.08 gier/s. Żeby uświadomić skalę – to prawie 41.5 raza wolniej niż człowiecza strategia. Gdybym miał wygenerować dane dla 10^6 gier musiałbym poświęcić 2.83 dnia ciągłych obliczeń (to i tak lepiej od poprzedniej wersji, gdzie potrzebowałem około 11 dni…). Raczej nie zamierzałem czekać tyle na dane – postanowiłem więc wynająć chmurę obliczeniową. Tak, chmurę obliczeniową. Sam nie sądziłem, że będzie to potrzebne – a jednak…

Ale głowa do góry – IaaS (Infrastructure as a Service) w dzisiejszych czasach wcale nie jest drogie ani trudne do zdobycia. Ja skorzystałem z chmurki od Oktawave – polskiego providera IaaS. Wybrałem maszynę z Debianem w konfiguracji 4 VCPU (po 2.5 GHz każdy) oraz 2 GB RAM – choć RAM akurat najpotrzebniejszą rzeczą tutaj nie był, całość mieściła się w około 100 MB. Cena – wliczając przestrzeń dyskową – to 0.2114985 zł/h. Do tych nieprzyzwyczajonych do takich cen – zwykle chmury obliczeniowe zamawiają firmy, rozliczając się w większym wymiarze godzin niż ja, szary konsument – dlatego też cena ma tyle miejsc po przecinku.

Zmodyfikowałem nieco skrypt testujący moją strategię, teraz wysyłał on mi maila, gdy tylko skończył obliczenia. Włączyłem chmurkę, przesłałem jej wszystkie dane oraz silnik testujący oraz uruchomiłem symulację.

Długo nie musiałem czekać – po kilku godzinach dostałem maila oznajmującego, że wszystkie dane zostały wygenerowane. Oto jak się prezentują:

Kształtem wykres przypomina ten poprzedni – są praktycznie identyczne. Ale czy na pewno? Porównajmy je ze sobą:

Tu już chyba widać różnice – nasza nowa strategia jest efektywniejsza od tej starej! Tak prawdę mówiąc, to byłaby jeszcze troszeczkę efektywniejsza, gdyby zaimplementował analizę prawdopodobieństwa także w momencie, gdy już próbujemy zestrzelić statek – ale myślę że nie zmieniłoby to wykresu mocno, czubek krzywej dzwonowatej przesunąłby się pewnie troszeczkę na lewo, wygładzając prawą i wyostrzając lewą stronę krzywej.

Jak tam wskaźniki wygranych? 50% gier wygramy w maksymalnie 54 ruchy (o 4 lepiej niż w przypadku poprzedniej strategii), tym razem aż 90% gier (nie 80%) zmieści się w 62 ruchach. Pozostawię tobie, czytelnikowi, ocenę tych wyników – czy było warto aż tak namęczyć się dla tego wyniku? Na koniec, warto pokazać jaką drogę przeszedłem – od czegoś kompletnie nierealnego, do realnej poprawy efektywności grania w tą prostą grę – finalne porównanie efektywności prezentuje się następująco:

I to by było na tyle! Oczywiście zapraszam do proponowania własnych ulepszeń do strategii czy tworzenia nowych – chętnie usłyszę jak wy zmierzylibyście się z tym problemem. Cały kod dostępny jest tu – gotowy do ściągnięcia i zabawy. Można zmieniać ilość i konfigurację statków w której chodzi symulacja, dopisywać własne strategie, oraz uruchamiać testowanie na kilku procesach – wszystko jest opisane w README.

Jeżeli tu dotarłeś – gratuluję. Przebrnąłeś przez ponad 1800 słów tego artykułu aż do jego końca. No ale w końcu po tak długiej przerwie musiałem wrzucić coś większego 🙂

  • Darek

    Jeszcze jest strategia na szachownice lub sito , ale nwm czy bardzo sie różni od losowania chociaż jest chyba jej ulepszona wersją. Losujesz 1 pole i strzelasz losowo (wg. prawdopodobienstwa) na krzyż / plus (tak jak wygląda szachownica) , gdy trafiasz na statek to go ostrzeliwujesz (i oznaczasz na około). Na koniec zostają 1-masztowce które juz trzeba losowo zestrzelić.

    • Niestety niczym się nie różni od tej typowej strategii człowieka, nawet powiem że może być mniej efektywna w rzeczywistości, bo człowiek nie rozstawia statków w pełni losowo 😛