ChessMemory – nadal prosta gra z wykorzystaniem JavaScript i SVG (część 5)


Jeśli myślicie, że zapomniałem o swojej obietnicy złożonej w poprzednim artykule o powrocie do „wyrafinowanego” algorytmu rozstawienia figur na naszej szachownicy, to się mylicie. Wszak jeśli mężczyzna obieca, że coś zrobi, to znaczy, że to zrobi. Nie trzeba mu o tym co pół roku przypominać! Jednak nie wyznaczywszy sobie żadnych deadline’ów, wciąż to odkładałem na później… I tak, niepostrzeżenie, minął rok od publikacji poprzedniej części cyklu poświęconego ChessMemory. Dlatego w końcu się zmobilizowałem. Czytelników, którzy chcą się dowiedzieć, jak rozwiązałem problem „wypróbowywania” przez algorytm różnych sposobów rozstawienia figur, zapraszam do lektury.

Wprowadzenie

Na początku przypomnę zasady gry w ChessMemory. Polega ona na odkrywaniu ukrytych figur na szachownicy w taki sam sposób, jakbyśmy grali w zwykłe Memory. Różnica polega na tym, że figury są ustawione zgodnie z dwiema regułami.

  • Każda figura występuje dokładnie po osiem razy, w dwóch różnych kolorach (białym i czarnym), po cztery pary na kolor. Razem mamy 64 figury rozstawione na 64 polach szachownicy.
  • Każda figura może mieć tylko jedną figurę do pary – musi być taka sama, mieć ten sam kolor oraz stać w zasięgu bicia swojej pary. Jeśli figura nie ma żadnej pary lub ma więcej niż jedną, jest to błąd.

W poprzednim artykule opisałem dwa sposoby na losowe rozstawienie figur (prosty i wyrafinowany), po czym zaimplementowałem trzeci, pośredni sposób, niestety nie najbardziej efektywny.

Tym razem skupimy się na drugiej metodzie, którą poprzednio zilustrowałem ścieżką przechodzącą przez wszystkie elementy drzewa z wieloma rozgałęzieniami. Ponieważ ten sposób opisałem szczegółowo w poprzednim artykule, nie będę tu powtarzać całego algorytmu, chętnych odsyłam do jego przeczytania. Przypomnę tylko, że ten algorytm do pewnego stopnia ma naśladować sposób działania człowieka, czyli rozstawiać figury tak długo, jak to możliwe, a po natrafieniu na „ślepą uliczkę”, cofnąć się o krok lub dwa (tyle, ile trzeba), żeby w ten sposób „wypróbować” wszystkie możliwości danego ustawienia. Siła tego algorytmu tkwi właśnie w możliwości wycofania dowolnej liczby kroków.

Optymalizacja

Zanim przejdziemy do omówienia programu, chciałbym zwrócić uwagę na odświeżoną wersję pliku index.html, który został diametralnie „odchudzony”. Ze 120 kilobajtów (co nie było wcale przerażającą wielkością) w poprzedniej wersji jego objętość zmalała do zaledwie 16 kilobajtów. Skąd taka różnica? W drugiej części cyklu wspomniałem o możliwościach optymalizacji pliku SVG, z którego korzystamy do obsługi szachownicy. Przypomnę, że plik ten jest osadzony bezpośrednio w kodzie generowanej strony, jako węzeł <svg>. Pierwotnie plik SVG był utworzony za pomocą programu Inkscape, który ma możliwość zapisu w formacie „Zoptymalizowany SVG”. Pozwala to na znaczną optymalizację, bo tak utworzony plik miał około 31 kilobajtów. Jednak najwięcej oszczędności uzyskałem, edytując ten plik za pomocą programu Adobe Illustrator. Plik zapisany w Illustratorze zajmuje zaledwie 16kB. W związku z tym, że cały plik index.html ma teraz zaledwie nieco ponad 200 linijek, poniżej zamieszczam cały jego listing:

Jak widać, w stosunku do poprzedniego pliku nastąpiła też niewielka zmiana w wywołaniu samej funkcji losującej. Tym razem nie ma żadnej pętli, w której wołana jest funkcja losuj() do skutku. Teraz funkcję tę wywołuje się tylko raz. Żeby zachować spójność z poprzednią wersją programu, funkcja losuj() będzie zwracać taki sam wynik co poprzednio, czyli łańcuch tekstowy będący odwzorowaniem rozmieszczenia figur na szachownicy. Jest on następnie przekazany do funkcji init() obiektu gra.

Program właściwy

Plik app.js również jest niewielki, bo zawiera zaledwie około 380 linii kodu (z czego znaczna część to komentarze i puste linie). Zresztą w większości pokrywa się z poprzednią wersją pliku. Zmieniła się jedynie wspomniana wcześniej funkcja losuj(). Dlatego omówimy tylko tę część i tylko ten fragment kodu tu wklejam. Całe pliki oczywiście są dostępne do pobrania na końcu artykułu.

Tak jak poprzednio, dla potrzeb działania algorytmu tworzymy obiekt plansza, którego konstruktorem jest funkcja Plansza(). Zawiera on między innymi 64 obiekty typu Pole(), służące do przechowywania informacji o stanie szachownicy w każdej chwili działania programu.

Obiekt plansza zawiera też dwie metody, które służą do losowania wolych pól: losuj_pole() i losuj_bicie(). Obie są nieco zmienionymi wersjami podobnych metod, które były również w poprzedniej wersji tej funkcji. Całkowicie nowe są natomiast dwie tablice, które również umieściłem w obiekcie plansza: histXY1 oraz histXY2. Będą one przechowywać informację o tym jakie pola szachownicy były wylosowane na każdym kroku algorytmu, przy czym jako pełny krok rozumiemy przejście przez dwa etapy.

  1. Losowanie pola dla pierwszej figury z pary przy pomocy metody losuj_pole(). Lista wolnych pól ustalana jest w ten sposób, że pole nie może być zajęte przez żadną figurę, oraz dana figura może stanąć na tym polu. Ten drugi warunek weryfikujemy przez sprawdzenie, czy tablica możliwe[] przypisana do tego pola zawiera daną figurę.
  2. W drugiej kolejności wylosowanie wolnego pola przy pomocy metody losuj_bicie(). Tym razem Lista wolnych pól zawiera te pola, które nie są zajęte oraz znajdują się na liście pól bicia dla pola i figury z punktu 1. Przypomnę, że listę wszystkich pól bicia dla każdej figury zawiera plik bicia.js.

Algorytm

„Silnikiem” funkcji losującej, czyli naszym algorytmem „wyrafinowanym”, jest pętla do…while, której liczba powtórzeń determinuje zawartość zmiennej kolejka. Jak widać, zmienna ta zawiera 32 symbole oznaczające ilość par figur szachowych. Przypomnę, że symbole „h”, „s”, „g” i „w” oznaczają odpowiednio: hetmana, skoczka, gońca i wieżę. Wielka litera oznacza kolor biały, mała natomiast – czarny. Nasza pętla w najbardziej optymistycznej wersji (czyli wtedy, gdy nie trafimy na żadną „ślepą uliczkę”) wykona się 32 razy. Taki scenariusz jest jednak mało prawdopodobny, bo rzeczywista liczba powtórzeń zwykle jest znacznie większa. W praktyce pętla ta wykona się nawet kilka tysięcy razy.

Elementem sterującym liczbą powtórzeń pętli jest zmienna index. Zwiększa ona swoją wartość o jeden po każdym pełnym przebiegu pętli. Parę figur, która jest obsługiwana w aktualnym przebiegu pętli, odczytujemy ze wskazania kolejka[index]. W warunku while(index < kolejka.length) sprawdzamy, czy zmienna index nie osiągnęła wartości równej długości kolejki, co oznacza koniec algorytmu. Wewnątrz pętli mamy realizację pełnego kroku, opisanego powyżej – czyli losowanie pierwszego, a następnie drugiego pola dla aktualnej pary figur. Najciekawsze jest to, co się dzieje, gdy funkcja losuj_pole() lub losuj_bicie() nie zwróci żadnego pola. Omówmy każdy z tych przypadków.

Nie ma wolego pola dla pierwszej figury

Jeżeli funkcja losuj_pole() zwróci umowną, pustą wartość (dokładnie ‘00’), oznacza to, że dla pierwszej figury z pary nie ma już wolnego miejsca na szachownicy. Wolnego, czyli takiego, które nie jest zajęte oraz nie koliduje z żadną inną taką samą figurą (nie leży w zasięgu jej bicia). Jak wspomniałem, ten drugi warunek weryfikujemy przez sprawdzenie tablicy możliwe[] dla danego pola. Zauważmy jednak, że tablica ta zapisywana jest oddzielnie dla każdego kroku algorytmu, a sprawdzana jest przez odczyt tablicy z numerem indeksu: możliwe[index]. W ten sposób możemy w każdej chwili cofnąć się o dowolną liczbę kroków, żeby ponowić losowanie. Kiedy zatem nastąpi sytuacja, w której nie ma już gdzie postawić kolejnej pary figur, musimy wrócić do poprzedniego kroku. W tym celu wycofujemy z planszy parę figur ustawioną w poprzednim kroku:

Następnie dla pola, które zawierało drugą figurę, usuwamy tę figurę z listy możliwych. Warto zauważyć, że ta zmiana dotyczy listy możliwych dla danego pola (plansza.histXY2[index-1]), dla danego kroku (możliwe[index-1]) oraz dla danej figury (kolejka[index-1]). Wszystko to oczywiście dotyczy kroku oznaczonego numerem index-1.

Co w ten sposób uzyskaliśmy? Krok index-1 zostanie powtórzony, a dokładniej – powtórzymy losowanie drugiej figury. Jednak tym razem figura ta nie będzie mogła znaleźć się na polu, które było wylosowane poprzednio (aktualnie jest ono zapisane w zmiennej zawierającej historię losowań: plansza.histXY2[index-1]). Kilka kolejnych linijek kodu służy do przygotowania zmiennych przed powrotem do poprzedniego kroku:

Dlaczego w zmiennej XY1 ustawiamy pole wylosowane w poprzednim kroku, mimo że usunęliśmy tę figurę z planszy? Ponieważ może się okazać, że wystarczy przestawić tylko drugą figurę. Pamiętajmy, że druga figura jest ustawiana na losowym polu spośród wszystkich wolnych pól bicia figury pierwszej. Czyli może ich być więcej niż jedno. Czemu nie mielibyśmy „wypróbować” wszystkich? A obie figury zostały usunięte z planszy, ponieważ po cofnięciu się o jeden krok może również się okazać, że wszystkie możliwości zostały wyczerpane i trzeba się cofnąć o kolejny. Dlatego też plansza jest zapełniana dopiero wtedy, gdy wylosujemy dwa pola dla obydwu figur, a nie tylko jednego. Dodatkowo, dla porządku czyścimy też historię, chociaż w tym kroku jest to nadmiarowe. Na koniec zmniejszamy o jeden wartość zmiennej index i przechodzimy do ponownego wykonania pętli instrukcją continue.

Nie ma wolnego pola dla drugiej figury

Inaczej postępujemy, gdy funkcja losuj_bicie() nie zwróci żadnego wolnego pola bicia. Co się dzieje w takiej sytuacji? Tym razem chcemy cofnąć losowanie pierwszej figury, co możemy osiągnąć przez powtórzenie tego samego kroku. Tym razem więc nie zmienimy wartości zmiennej index przed wywołaniem instrukcji continue. Zanim do tego dojdziemy, najpierw pomniejszamy listę możliwych figur dla wylosowanego wcześniej pola. W ten sposób mamy pewność, że ponowne losowanie zwróci inne pole dla pierwszej figury (albo nie zwróci żadnego, co zostało opisane wcześniej). Następnie zerujemy pierwsze pole i dla porządku czyścimy historię. Jesteśmy gotowi do powtórzenia kroku.

Historia

Po skutecznym wylosowaniu obydwu pól możemy przypisać aktualną figurę do odpowiednich współrzędnych na planszy:

Następnie zapisujemy wylosowane pola w tablicach zawierających historię wszystkich dotychczasowych par figur:

Te informacje będą wykorzystane przy wejściu w „ślepą uliczkę”, co zostało opisane powyżej. W dalszej części przygotowujemy się do przejścia do kolejnego kroku, czyli dla każdego pola na planszy, przepisujemy wszystkie informacje zawarte w tablicach mozliwe[] z kroku index do kroku index+1:

W tym celu korzystamy z notacji wielokropka, czyli tzw. składni rozwinięcia, który w tym miejscu pomaga „przepchać” za pomocą instrukcji push wszystkie elementy tablicy zapisanej wewnątrz mozliwe[index]. Jak widać, jest to tablica dwuwymiarowa, gdzie pierwszy wymiar oznacza numer kroku algorytmu. To właśnie ta struktura, wraz z historią losowań (tablice histXY1 oraz histXY2), odpowiada za prawidłowy wybór pól podczas losowania we wszystkich powtórzonych iteracjach algorytmu.

Dokładniej rzecz ujmując, historia losowań pomaga prawidłowo wycofywać poszczególne kroki, natomiast tablica mozliwe[] przypisana do każdego pola planszy i każdego kroku oddzielnie, pomaga prawidłowo „wypróbowywać” kolejne losowania. Na koniec jeszcze nie zapominamy pomniejszyć listy figur możliwych dla każdego pola z listy pól bicia obydwu wylosowanych pól. Oczywiście robimy to dla kroku index+1.

Pętla kończy się wyczyszczeniem obydwu wylosowanych pól przed kolejnym krokiem, a na samym końcu – zwiększeniem indeksu o 1 (index++).

Podsumowanie

I to już koniec. Chyba nie było to zbyt trudne? Wiem, że w poprzednim artykule trochę demonizowałem stopień skomplikowania tego algorytmu – „(…) musimy zaprojektować taką strukturę danych, która będzie przechowywać kompletną informację o wszystkich dotychczasowych krokach, łącznie z rozstawieniem wszystkich figur na każdym etapie algorytmu. To zadanie wydaje się być dość karkołomne i już na etapie opracowania koncepcji stopień jego skomplikowania jest odstraszający”. Okazało się jednak, że wystarczyło dobrze przemyśleć wszystkie kroki algorytmu, żeby znaleźć możliwe najprostsze rozwiązanie.

Oczywiście łatwo jest powiedzieć, trudniej zrobić. Zapewniam, że opracowanie tej koncepcji zajęło mi znacznie dłużej, niż trwało napisanie tego artykułu. Sama implementacja również nie byłaby zbyt długa, jeśli nie liczyć frustrującej i mozolnej diagnozy błędów. Podczas pisania programu niestety popełniłem dwie banalne pomyłki, których wykrycie wymagało wielokrotnie „ręcznego” przejścia przez kilkadziesiąt iteracji algorytmu, co zajęło z przerwami kilka dni. Ostatecznie jednak cała gra nadal jest bardzo prosta, do czego nawiązuje tytuł niniejszego artykułu.

Na koniec dwa słowa o wydajności. Czy nowa wersja algorytmu rzeczywiście jest lepsza od poprzedniej? W praktyce różnicę widać gołym okiem. Można to zaobserwować otwierając ten i poprzedni artykuł w osobnych zakładkach. Nie robiłem dokładniejszych pomiarów, jednak zaryzykuję stwierdzenie, że nowy sposób jest o rząd wielkości szybszy od poprzedniego.

Linki

  1. Cykl artykułów opublikowanych z tagiem „memory”: https://blog.atena.pl/tag/memory
  2. Strona kierunku „Aplikacje i usługi internetowe”: http://eti.pg.edu.pl/katedra-architektury-systemow-komputerowych/studia-podyplomowe/
  3. Pliki wykorzystane w tym artykule: https://github.com/jarfos/blog.atena.pl/tree/master/ChessMemory_part5

Jarosław Fostacz

O Jarosław Fostacz

Od 2003 roku jestem związany z firmą ATENA - początkowo jako programista, następnie projektant. Aktualnie jestem kierownikiem Zespołu Badań i Rozwoju oraz opiekunem niniejszego blogu. Moją siłą napędową jest nieustanne poszukiwanie innowacji oraz nowych technologii.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *