Jakiś czas temu siostra pokazała mi na swojej Nokii zręcznościową gierkę, w którą pyka sobie w rzadkich wolnych chwilach. Gierka nazywa się City Bloxx. Ponieważ spodobała mi się, natychmiast poszukałam jej w necie i znalazłam flashową wersję online. Idealne zajęcie np. podczas oglądania “Californication” czy innego serialu, który nie absorbuje mózgu w 100%.

Gra składa się z dwóch części, zręcznościowej i logicznej. W zręcznościowej, która zajmuje większość czasu gry, naszym celem jest upuszczanie kolejnych pięter z dźwigu i tym samym budowanie wieży. Następnie (tu jest ta wstawka logiczna) tak wybudowaną wieżę umieszczamy na planszy 5×5 wg następujących banalnych zasad: niebieskie mogą stać gdziekolwiek, czerwone trzeba stawiać obok niebieskich, zielone tak, aby sąsiadowały z niebieskim i czerwonym, żółte tak, aby sąsiadowały ze wszystkimi pozostałymi kolorami. Warunek musi być spełniony tylko w momencie stawiania, czyli np. można postawić czerwony koło niebieskiego, a potem ten niebieski zburzyć i postawić zamiast niego zielony.

Jak można się domyślić, wieża w każdym kolejnym kolorze mieści coraz więcej ludzików (swoją drogą animacja ludzików przylatujących na parasolach do nowozbudowanych pięter jest urocza). Już po kilkunastu minutach grania zaczęło mnie męczyć pytanie “jak optymalnie ustawić budynki, żeby pomieścić na planszy maksimum ludzi?”. Kartka w kratkę, ołówek, siedzę, smaruję… i dochodzę do wniosku, że problem jest nietrywialny.

Wtedy przypomniałam sobie o projekcie z piątego roku studiów. Pisząc wówczas projekt z algorytmów genetycznych, już wiedziałam, że w tam nie jest ciekawy sam algorytm, tylko wymyślenie genetycznej reprezentacji problemu. Dlatego kod odpowiedzialny za samą część genetyczną napisałam tak wydzielony, żeby dało się go jeszcze kiedyś wykorzystać. I proszę, właśnie nadarzyła się okazja wreszcie go odkopać!

[Tu podziękowania dla wszystkich, którzy przyczynili się do tego, że mam nawyk pisania czytelnego i skomentowanego kodu, podzielonego na klasy i metody. Przepraszam, że wtedy uważałam, że się czepiacie.]

3 godzinki przy klawiaturze (z czego większość to oczywiście testowanie i analizowanie wyników, a nie samo kodowanie) i już w drugim uruchomieniu algorytm znalazł rozwiązanie lepsze niż moje z kartki… Pomęczony jeszcze trochę na większej populacji i większej liczbie iteracji poprawił mój wynik o 20%. To doprawdy upokarzające, że parę układów krzemowych jest sprytniejszych ode mnie…

A oto opis genetycznego podejścia do problemu:

osobnik (chromosom) – lista kolejnych ruchów, gdzie przez ruch rozumiemy parę “pole na planszy + kolor”. Przykładowy osobnik mógłby wyglądać tak:
1. (1,1) – niebieski
2. (1,2) – czerwony
3. (1,3) – niebieski

krzyżowanie – intuicyjnie: budujemy osobnika potomnego, biorąc i-ty element losowo od jednego z rodziców

mutacja - dodanie losowego nowego ruchu na koniec listy lub podmiana dowolnego ruchu na nowy, losowy

populacja początkowa – osobniki z pustą listą ruchów

Do tego miejsca jest proste, ale pojawia się pytanie “a jak te ruchy będą nielegalne?”. O to zadbała brutalna funkcja oceniająca, która w miarę potrzeby również modyfikuje osobnika.

funkcja oceny – funkcja oceny tworzy planszę i wykonuje na niej kolejne ruchy, weryfikując ich poprawność. Jeżeli napotka ruch nielegalny, ucina listę w tym miejscu (tzn. modyfikuje osobnika) i ignoruje wszystkie dalsze ruchy. Następnie przyznaje punkty za budynki na planszy: 1 za niebieski, 2 za czerwony, 3 za zielony i 4 za żółty. Aby w przypadku remisu promować krótsze rozwiązania, dodaję też do tego składnik (n-liczba ruchów)/n. Oczywiście n trzeba przyjąc na tyle duże, żeby dodatkowy składnik był z zakresu 0-1, wzięłam 100.

Rezultat? Właśnie odpaliłam dla sprawdzenia aplikację testową. Populacja 100, 1000 er, za 22 razem algorytm pobił swój poprzedni rekord (73 punkty w 39 ruchach). Całość operacji (22 razy 1000 er) zajęła poniżej minuty, łącznie z wypisaniem najlepszych wyników do pliku i faktem, że to było w debugu. Moje “ręczne” najlepsze rozwiązanie to 58 punktów – program raczej nie schodzi poniżej 55…

Zachęcona tymi efektami zamierzam wykorzystać algorytm genetyczny w pracy, ale o tym ciii, konkurencja nie śpi…