ChessMemory – piszemy prostą grę w JavaScript (część 4)


Od publikacji poprzedniego artykułu z serii ChessMemory minęło już grubo ponad rok. Zdążyłem prawie zapomnieć o tej grze, nie wspominając o generatorze losowego ustawienia figur, który wciąż czeka na napisanie. Ta dodatkowa funkcjonalność, o której wspominałem w poprzednich wpisach, dopełniłaby całości, dzięki czemu ChessMemory mogłaby się stać pełnoprawną grą, a nie tylko „silnikiem”. Długie zimowe wieczory sprzyjają programowaniu, dlatego postanowiłem zmierzyć się z wyzwaniem i napisać wreszcie prosty generator losowego rozstawienia figur na szachownicy – oczywiście przy zachowaniu wszystkich reguł gry ChessMemory.

Na początek przypomnijmy zasady prawidłowego rozstawienia figur na planszy.

  • 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.

Gra polega na odkrywaniu par figur na tej samej zasadzie, co w „zwykłej” grze Memory. Różnica sprowadza się tylko do nieco innego ustawienia figur, które po prostu nie jest całkowicie przypadkowe.

Zastanawiałem się nad tym, jak ma działać algorytm, który losowo poustawia prawidłowo figury na planszy. Pod uwagę brałem dwie skrajne możliwości.

Pierwszy sposób (łatwy)

Losowo rozstawiamy wszystkie dostępne figury na dowolnych polach szachownicy, po czym weryfikujemy poprawność ustawienia. Można to łatwo sprawdzić, wykorzystując w tym celu funkcję sprawdz_figury() opisaną w poprzednim artykule. Jeśli ustawienie jest nieprawidłowe, powtarzamy losowanie od nowa – i tak do skutku. Sposób dość prymitywny i już na pierwszy rzut oka widać, że musi być bardzo nieefektywny. Zgaduję, że zanim wylosuje się takie ustawienie, które wreszcie okaże się prawidłowym, wcześniej trzeba będzie odrzucić setki tysięcy albo i miliony nieprawidłowych losowań. Nawet przez chwilę mnie kusiło, żeby napisać taki program z czystej ciekawości, ile czasu zajmie losowanie. Doszedłem jednak do wniosku, że najprawdopodobniej nie doczekam się wyników pierwszego losowania. Uznałem więc, że szkoda czasu…

Drugi sposób (wyrafinowany)

Drugi sposób naśladuje w pewnym stopniu działanie człowieka, co pociąga za sobą zdecydowanie więcej złożoności niż w poprzednim przypadku. Albo raczej wyrafinowania – żeby nie mylić ze złożonością obliczeniową algorytmów. Zaczynamy od pustej szachownicy i pełnej listy dostępnych figur. Kolejność ustawiania figur może mieć znaczenie, więc – naśladując prawdopodobny wybór człowieka – zaczynamy od hetmanów. Co do pozostałych figur, nie ma pewności, jaka kolejność jest najbardziej efektywna. Szczerze mówiąc, wypróbowałem wielu różnych kolejności i wyniki były na tyle rozbieżne, że nie wskazały jednoznacznie najlepszej. Zapewne do wiarygodnych wniosków można by dojść po przebadaniu wszystkich możliwości na próbce kilkuset tysięcy losowań. Ale przecież nie zamierzamy się doktoryzować, tylko napisać prosty generator losowy. Dlatego wybór kolejności ustawiania figur następuje w sposób ekspercki: najpierw hetmany, potem skoczki, następnie gońce i na końcu wieże.

Oczywiście będziemy się posiłkować plikiem bicia.js, zawierającym wszystkie możliwości bicia każdej z czterech figur na każdym z 64 pól szachownicy. Tego samego pliku używaliśmy również w poprzednich artykułach. Wspominam o tym tutaj, żeby mieć pewność, że gdy za chwilę będę mówić o „polach bicia”, to wszyscy czytelnicy odgadną, w jaki sposób zamierzam to osiągnąć – nawet ci, którzy nie czytali poprzednich artykułów z cyklu ChessMemory.

Jak wspomniałem, na początku mamy do dyspozycji pustą szachownicę oraz listę dostępnych figur. Mamy też określoną kolejność ustawiania figur, czyli jest to lista odpowiednio posortowana. Na potrzeby algorytmu będziemy również przechowywać listę możliwych figur (czyli takich, które mogą zostać ustawione na danym polu) dla każdego pola oddzielnie. Każde pole szachownicy będzie mieć własną listę, która w trakcie trwania programu będzie się zmniejszać (będą z niej wykreślane kolejne elementy). Na początku (przed pierwszym krokiem) wszystkie pola na szachownicy potencjalnie mogą „przyjąć” dowolną figurę. W kolejnych krokach powtarzamy kilka czynności.

  1. Dla kolejnej figury z listy dostępnych losujemy wolne pole na szachownicy. Wolne pole oznacza takie, na którym nie stoi żadna figura, a dana figura znajduje się na liście możliwych figur tego pola. Przypisujemy tę figurę do wylosowanego pola. Lista możliwych figur tego konkretnego pola odtąd przestaje mieć znaczenie, co jest zrozumiałe, ponieważ pole to właśnie zostało zajęte.
  2. Drugą taką samą figurę musimy ustawić na wolnym polu (czyli niezajmowanym przez żadną figurę, oraz takim, które może daną figurę przyjąć), wylosowanym spośród dostępnych pól bicia pierwszej figury. Pola bicia weryfikujemy za pomocą pliku bicia.js.
  3. Po ustawieniu obydwu figur wszystkie odpowiadające im pola bicia oznaczamy jako niemożliwe do przyjęcia kolejnej takiej figury. Czyli w praktyce dla wszystkich pól bicia usuwamy tę konkretną figurę z listy możliwych.

Powyższe kroki powtarzamy aż do wyczerpania wszystkich figur. W ten sposób zapełniamy całą szachownicę. Koniec.

Nie tak szybko…

Przed każdym losowaniem może się okazać, że lista wolnych pól spełniających wymagane warunki okaże się pusta, mimo że szachownica jeszcze nie została zapełniona. Może się tak stać w trzech przypadkach:

  1. wszystkie niezajęte pola na szachownicy nie mogą już przyjąć danej figury (krok A);
  2. wszystkie pola bicia już są zajęte (krok B);
  3. wszystkie niezajęte pola bicia nie mogą przyjąć danej figury (krok B).

W takim przypadku docieramy do „ślepej uliczki”, w której dalsze wykonanie algorytmu jest niemożliwe. W tym momencie powinniśmy cofnąć się o jeden krok i wypróbować kolejne losowanie. Ponadto, program musi działać tak, by dało się cofnąć o dowolną ilość kroków. Ślepe uliczki mogą bowiem „zaczynać” się wiele ruchów wcześniej, zanim dotrzemy do ostatniego pola. Przedstawiając to działanie za pomocą grafu, powiemy, że jeśli w danym rozgałęzieniu wszystkie liście drzewa okażą się nietrafione, musimy wrócić kilka poziomów wyżej, aby przejść do kolejnej gałęzi.

Rys 1. Przechodzenie przez wszystkie elementy grafu (czerwoną linią zaznaczono pierwsze kilkanaście kroków)

I tutaj zaczynają się schody, bo żeby móc cofnąć się o dowolną liczbę kroków, 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. Dla jasności – nie twierdzę, że jest zbyt trudne do realizacji, tylko zanim zabierzemy się do kodowania czyste lenistwo nakazuje mi znaleźć jakieś prostsze rozwiązanie. A przynajmniej spróbować jakoś to uprościć.

I tak dochodzimy do trzeciego sposobu, czyli wersji pośredniej pomiędzy pierwszymi dwoma.

Trzeci sposób, kompromisowy

Tym razem przyjmujemy prostą zasadę: stosujemy wszystkie zasady z drugiego sposobu do momentu, gdy dotrzemy do „ślepej uliczki”. Gdy taka sytuacja nastąpi – niezależnie od tego, na jakim etapie – resetujemy szachownicę i zaczynamy cały proces od nowa. Losujemy aż do skutku. Za którymś „przebiegiem” w końcu uda się wylosować prawidłowe ustawienie. Ktoś może spytać: a czym się to różni od pierwszego sposobu, skoro i tak za każdym razem losujemy nowe ustawienie? Otóż różnica jest zasadnicza: w pierwszym sposobie już po kilku krokach może się okazać, że dalsze losowanie jest pozbawione sensu. Tutaj natomiast ułożenie wszystkich figur jest prawidłowe zawsze. Dopiero gdy dołożenie kolejnej figury jest niemożliwe, przerywamy pracę. W praktyce taki problem pojawia się dopiero przy kilku ostatnich figurach, gdy szachownica jest już prawie całkowicie zapełniona.

Czy wobec tego rozwiązanie to ma sens? Skoro jesteśmy tak blisko końca (czyli zapełnienia szachownicy), czy nie lepiej zaimplementować cofanie się o kilka kroków i „dokończenie” tego losowania, przy którym jesteśmy? Innymi słowy, czy nie lepiej od razu zaimplementować drugi sposób? Odpowiedź tkwi w słowie „kompromis” – jeżeli trzeci sposób okaże się wystarczająco wydajny, po co kombinować? W myśl zasady, że „jeśli coś jest głupie, ale działa, to nie jest głupie” – może przyjmiemy ten sposób jako wystarczająco dobry dla potrzeb prostego generatora losowego?

W praktyce okazało się, że zwykle po kilku – kilkunastu tysiącach losowań trafiamy na prawidłowe ustawienie.  Czasem po kilkudziesięciu. Z rzadka zdarzają się też takie losowania, które trafiają dopiero po kilkuset tysiącach powtórzeń. Dużo? Nawet bardzo! Ale weźmy pod uwagę fakt, że ten proces wykonujemy tylko raz na początku gry i tylko wtedy może wystąpić zauważalne, chociaż chwilowe spowolnienie w pracy przeglądarki. To zaledwie kilka sekund podczas ładowania strony…

Nie byłbym sobą, gdybym to tak zostawił, dlatego umówmy się, że „wyrafinowany” sposób zostawimy sobie na osobny artykuł, żeby mieć porównanie. W tym artykule zaimplementujemy sposób „kompromisowy”.

Program właściwy

Jako bazę wykorzystamy pliki opublikowane w drugiej części „przygód” z ChessMemory. Właściwie nasza praca sprowadzi się do napisania jednej nowej metody w obrębie obiektu: gra.losuj(). Zmieniamy zatem inicjację obiektu i dodajemy wywołanie nowej funkcji w pliku index.html.

Powyższy fragment kodu powtarza wywołanie funkcji losuj() tak długo, aż zmienna ustawienie przyjmie inną wartość niż umowne ‘00’, które będziemy zwracać, jeśli algorytm zabrnie w „ślepą uliczkę”. Dodatkowo w zmiennej licz odkładamy liczbę powtórzeń. Po wylosowaniu prawidłowego ustawienia wynik ten pojawi się w konsoli. Reszta zmian będzie mieć miejsce już tylko w pliku app.js.

Zanim zabierzemy się za funkcję właściwą, najpierw dodamy dwie funkcje pomocnicze, które będą pomocne przy operacjach na tablicach. W tym celu rozszerzymy zestaw metod obiektu Array korzystając z możliwości, jakie daje prototyp. Pierwsza z nich zwraca losowy element tablicy. Będziemy tej funkcji używać do losowego wyboru pola na planszy. Druga metoda natomiast usuwa z tablicy element przekazany jako argument funkcji. Dokładniej, usuwany jest pierwszy napotkany element o podanej wartości, ale dla naszych potrzeb to w zupełności wystarczy. Funkcji tej będziemy używać do zawężania listy możliwych figur przypisanych do każdego pola na szachownicy.

Poniżej znajduje się listing całej funkcji losuj(), w dalszej części artykułu omówimy poszczególne jej fragmenty.

Jak widać, funkcja losuj() zawiera kilka mniejszych funkcji, z których dwie są konstruktorami obiektów. Pierwszą z nich jest Pole(), w której definiujemy strukturę dostosowaną do przechowywania informacji o zawartości pola, polach bicia oraz dodatkową listę możliwych figur, które dane pole może przyjąć. Funkcja-konstruktor Plansza() jest nieco bardziej skomplikowana, ponieważ tworzy obiekt składający się z 64 pól. Każde z pól zostaje zapisane w oddzielnej właściwości, której nazwa odwzorowuje współrzędne pola na szachownicy (zmienna XY). Dwie następne funkcje, czyli losuj_z_planszy() i losuj_z_bicia() zawierają kod potrzebny do wyboru losowego pola z listy dostępnych pól. Listę dostępnych pól (zmienna wolne) w obydwu funkcjach tworzymy nieco inaczej. W pierwszym przypadku do tej listy trafiają wszystkie puste pola, które mogą „przyjąć” daną figurę (tzn. figura ta znajduje się na liście możliwych). W drugiej funkcji występuje dodatkowe ograniczenie, mianowicie wolne pole musi się znajdować na liście pól bicia. Ostatnia funkcja pomocnicza przypisz_figure(), zgodnie z nazwą służy do przypisania danej figury do wylosowanego pola.

Gdy już mamy wszystkie potrzebne narzędzia pomocnicze, możemy przystąpić do wypełniania szachownicy. Po zadeklarowaniu zmiennej obiektowej plansza wykonujemy powtarzające się czynności, które będą wykonane w dwóch pętlach. Pierwsza z nich jest powtarzana dla wszystkich figur zgodnie z wybraną wcześniej kolejnością: HhSsGgWw: hetmany, skoczki, gońce, wieże. Wielka litera oznacza białą figurę, mała – czarną. Druga pętla (wewnątrz pierwszej) oznacza 4 powtórzenia dla każdej pary figur. W efekcie każda figura wystąpi po 8 razy.

Wyliczmy czynności, które powtarzają się dla każdej pary figur.

  1. Losowanie wolnego pola z planszy, czyli takiego, które spełnia warunki:
    • nie jest zajmowane przez żadną figurę,
    • może daną figurę „przyjąć” (posiada ją na liście możliwych).
  2. Przypisanie pierwszej figury do wylosowanego pola.
  3. Losowanie wolnego pola z listy pól bicia, która wynika z powyższego przypisania pierwszej figury do pola. Wylosowane pole zatem musi spełniać następujące warunki:
    • przede wszystkim musi znajdować się na liście pól bicia wylosowanego wcześniej pola i pierwszej figury,
    • nie może być zajęte przez żadną figurę,
    • może daną figurę „przyjąć”.
  4. Przypisanie drugiej figury do wylosowanego pola.
  5. Na koniec oznaczamy wszystkie pola, które występują na listach pól bicia obydwu figur jako niemożliwe do „przyjęcia” kolejnej takiej figury. Usuwamy więc tę figurę z listy możliwych dla każdego pola z listy pól bicia obydwu ustawionych przed chwilą figur.

Po wywołaniu funkcji losującej pole z planszy lub z listy pól bicia sprawdzamy, czy wylosowano jakiekolwiek pole. Jeśli np. lista pól bicia była pusta, funkcja zwróci umowną wartość ‘00’. W takim przypadku kończymy działanie algorytmu. Na koniec jeszcze przepisujemy dane zawarte w zmiennej obiektowej do ciągu znaków, który posłuży do wywołania funkcji gra.init().

W tym momencie można uznać, że gra jest skończona, albo dokładniej: jest gotowa do testów. Zachęcam zatem do wypróbowania swoich sił z całkowicie losowym ustawieniem, uzyskanym przy pomocy opisanego w tym artykule algorytmu:

Gdyby to był projekt komercyjny, powiedzielibyśmy, że obecnie mamy do czynienia z wersją beta, która wymaga jeszcze optymalizacji… J My od samego początku wiemy, na czym ta optymalizacja powinna polegać – trzeba zaimplementować drugi sposób zapełniania szachownicy, czyli algorytm „wyrafinowany”. Do tego trzeba będzie obsłużyć możliwość cofania się o kilka kroków w przypadku trafienia do „ślepej uliczki”. Ale to już materiał na osobny artykuł, który na razie dopiero krystalizuje się w mojej głowie. Zachęcam więc do śledzenia naszego profilu na FB, gdzie ogłaszamy publikację wszystkich artykułów na naszym blogu.

Na zakończenie mały bonus dla tych Czytelników, którzy oprócz przeczytania artykułu, „bawią się” również w programowanie na podstawie załączonych kodów. Wylosowane ustawienie figur na szachownicy pozostaje prawidłowe także wtedy, gdy obrócimy szachownicę o 90 stopni. Czyli jedno losowanie daje nam tak naprawdę 4 różnie ustawienia, które różnią się tylko orientacją szachownicy. Ponadto każde z tych ustawień ma również swoje lustrzane odbicie, które nadal pozostaje prawidłowe, czyli zgodne z regułami gry ChessMemory. Poniżej znajduje się dodatkowa funkcja przeksztalc(), która dla podanego ustawienia figur zwraca listę wszystkich ośmiu jego wariacji.

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: index.html, app.js, bicia.js, chesspieces.ttf.

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 *

Komentarz do “ChessMemory – piszemy prostą grę w JavaScript (część 4)