Pracownia Sztucznej Inteligencji - Łukasz Piwowar 91833

15.06.2001

Krechy - reguły gry

Reguły gry "Krechy"

Gra jest przeznaczona dla jednego gracza, którego celem jest wykonanie jak największej liczby ruchów. Gra toczy się na kratkowanej kartce papieru. Wymiary kartki nie są ograniczone. Konfiguracja początkowa planszy jest przestawiona na rysunku 1 i składa się z 36 kropek umieszczonych w centralnym miejscu planszy.
[Rys.1. Konfiguracja początkowa]

Rys.1. Konfiguracja początkowa

Ruch: składa się z dwóch faz:

narysowanie kropki na przecięciu linii kraty (oczywiście kropki nie mogą się na siebie nakładać),
narysowanie kreski (poziomej, pionowej lub ukośnej nachylonej pod kątem 45 stopni do poziomu), łączącej pięć kolejnych kropek.

Kreski mogą się przecinać, mogą mieć wspólne końce, ale nie mogą nakładać się.

Na rysunku 2 przedstawiono sytuację na planszy po wykonaniu czterech następujących ruchów:

Współrzędne kropki	Współrzędne końców kreski
(2,-5)	(2,-5) - (2,-1)
(3,-4)	(3,-4) - (-1,-4)
(1,-1)	(1,-1) - (5,-1)
(5,-2)	(5,-2) - (5,2)

Rys.2. Możliwa sytuacja na planszy po 4 ruchach
Plan projektu:

1. Cel:

Napisać program osiągający jak najlepszy wynik w jednoosobowej grze krechy.

2. Metody:

2.1. Napisać program, który szuka jak najlepszego rozwiązania, poprzez przeszukiwanie drzewa ruchów w głąb.

2.2. Zastosować różne heurystyki wyboru i przeszukiwania ruchów, oraz zbadać ich wpływ na osiągane przez
program wyniki.

2.3. Zastosować algorytm genetyczny w celu poprawy wyników programu.
Jako funkcje oceniającą przyjąć ilość ruchów, jakie uda się wykonać danemu osobnikowi.
Jako kod genetyczny przyjąć parametry heurystyk, które dany osobnik wykorzystuje lub nie.
Krzyżowanie przeprowadzić poprzez wybranie kilku parametrów z aktualnie najlepszego osobnika.
Mutacje przeprowadzić poprzez losowe wybranie części kodu (z określonych przedziałów)..

Co 5-15 sekund usuwać 2 najgorszych osobników i tworzyć 2 nowych.

3. Testowanie:

Do testów przygotować aplikacje, pozwalającą obserwować poczynania osobników.
Aplikacja powinna umożliwiać podgląd jednego z 10 osobników, uruchomionych jako
osobny wątek. Powinna także umożliwiać zapis najlepszych (rekordowych) rozgrywek
na dysk.

4. Ocena:

Jedynym czynnikiem wpływającym na ocenę sytuacji powinna być ilość ruchów, które wykonał zawodnik,
czyli wynik, jaki osiągnął w grze. Ponieważ gra jest jednoosobowa jest to wystarczający miernik
zaawansowania programu.

5. Wnioski:

Porównanie wyników finalnego programu z jego pierwotna wersja wykorzystująca jedynie przeszukiwanie w głąb.

Kolejno podejmowane kroki:

1. Granie w grę przy pomocy apletu testowego

Pierwszym krokiem pomagającym lepiej poznać reguły i zasady dotyczące gry było, wykorzystanie umieszczonego na stronie z grą apletu http://www.mimuw.edu.pl/oi/kacik/krechy.html. Symulował on rozgrywkę i pozwalał na grę w przeglądarce internetowej . Wynik nie był może satysfakcjonujący (64 ruchy), ale pozwolił mi poznać sposoby, na jakie można prowadzić rozgrywkę.

2. Przeszukiwanie w głąb

Następnym krokiem było napisanie prostego programu, który przeszukując kolejno wszystkie możliwości starał się znaleźć jak najlepsze rozwiązanie. Program działał bardzo powoli i znajdował najwyżej 28 ruchów.

3. Optymalizacja i heurystyka

Zoptymalizowałem główny moduł rozpoznający i wykonujący ruchy.
Wprowadziłem kilka heurystyk:

- program nie stawiał kropki, jeżeli w jej otoczeniu nie było innych kropek
- obszar przeszukiwania został ograniczony prostokątem, który jest poszerzany w momencie stawiania kropki lub kreski na jego brzegu
- program szukał miejsca postawienia kreski w kwadracie o boku 5 umiejscowionym w miejscu kropki (tzn. kreska była stawiana tylko w pobliżu postawionej poprzednio kropki)
- po określonym czasie, kiedy nie udawało się poprawić aktualnego rekordu, program cofał się o n ruchów

Po dodaniu heurystyk, program poprawił nieco działanie i potrafił znajdować do 85 ruchów, co było w miarę dobrym wynikiem (samemu udało mi się dotrzeć do 65 ruchu). Pozwoliło mi to przypuszczać, że algorytm jest dobry i wystarczy pozwolić na dłuższe obliczenia, aby poprawić ten wynik. Niestety po 10 godzinach program znalazł jedynie 90 ruchów. Pomimo rozczarowania, upewniło mnie to w przekonaniu, że problem nie poddaje się brutalnej sile obliczeniowej.

4. Wielowątkowość

Kolejnym usprawnieniem i przygotowaniem do algorytmu genetycznego, było dodanie możliwości uruchamiania, kilku zawodników jako osobnych wątków. Od tego momentu mogłem śledzić poczynania graczy którzy rozpoczynali grę na różne sposoby (pierwszy ruch nie był wyszukiwany), oraz porównywać ich aktualne ruchy jak i wyniki rekordowe.

5. Parametryzacja

Następnie sparametryzowałem algorytm gracza tak, aby wartości liczbowe mogły wpływać na charakter jego gry. Kolejne parametry oznaczają odpowiednio:

Rozbryzg:
- Prawdopodobieństwo rozszerzenia obszaru poszukiwań
Rozbryzg - zasięg:
- Wartość liczbowa określająca promień obszaru poszukiwań od aktualnej pozycji.
Death
- Prawdopodobieństwo wystąpienia śmierci układu (wyjścia n ruchów wstecz)
Death size
- Ilość ruchów wstecz przy wyjściu z aktualnego układu
Symetria
- prawdopodobieństwo wykonania ruchu symetrycznego z poprzednim

6. Krzyżowanie

Następnie dodałem losowe krzyżowanie najsłabszego gracza z najlepszym. Co 2 sekundy aktualnie najgorszy z graczy (z najmniejszym rekordem ruchów) przejmował cześć parametrów od najlepszego (to, które parametry przejmował było losowane).

7. Mutacje

Jeżeli akurat nie była wykonywana krzyżówka, co 2 sekundy była przeprowadzona mutacja na najgorszym z graczy, to znaczy losowa ilość jego parametrów, zostawała zamieniana na wartości losowane z odpowiednich przedziałów.

8. Wyniki

Program przy zastosowaniu losowej mutacji i krzyżowania osiągnoł najlepszy wynik (103 ruchy). Co ciekawe, ta sytuacja nie jest powtarzalna (na co ma wpływ losowanie wiekszości z parametrów). Po dość krótkim czasie, wszyscy zawodnicy byli na podobnym poziomie (nie było zawodników wyraźnie słabych), co ciekawe rozgrywki poszczególnych graczy bardzo się różniły. Co jakiś czas tworzył się nowy lider, który podciągał grupę do góry. Im dłużej ta sytuacja trwała tym wolniej ten proces przebiegał... Algorytm genetyczny okazał się o 200% (65 ruchów) lepszy od najprostszego algorytmu przeszukującego drzewo ruchów w głąb. Oraz 12% (13 ruchów) lepszy od przeszukiwania z ustalonymi z góry heurystykami. Oznaczało by to, że parametry heurystyk dobrane podczas działania okazały się lepsze od tych ustalonych z góry. Program eliminując słabych zawodników oraz nagradzając dobrych, dobierał optymalne parametry.

Próbowałem także krzyżowania poprzez przekazywanie części rozwiązania, ale okazywało się, że rozwiązania są bardzo zbieżne, w tym przypadku większość zawodników skupiała się na jednej części drzewa poszukiwań, często powielając obliczenia.

9. Program testujący

Dostępne opcje:

Usuń:
- Usuwa gracza z listy
Dodaj:
- Dodaje nowego gracza
Mutuj słabego:
- Mutuje najsłabszego z graczy
Losuj słabego:
- Losuje parametry najsłabszego z graczy
Załaduj gracza:
- Pozwala załadować przebieg rozgrywki gracza z dysku
Mutowanie ON/OFF:
- Włącza/wyłącza cykliczne mutowanie graczy
Podgląd ON/OFF:
- Włącza/wyłącza cykliczny (co 1 sekundę) podgląd aktualnego ruchu wybranego gracza

Po lewej stronie znajduje się lista aktywnych graczy, wybór jednego z nich pozwala obejrzeć aktualne rozwiązanie.
Na górze ekranu po prawej stronie od obrazu planszy, znajdują się paski reprezentujące aktualną oraz rekordową ilość ruchów poszczególnych graczy.
Program automatyczne zapisuje na dysku rekordowe rozgrywki graczy, którym udało się uzyskać ponad 90 ruchów.

10. Uwagi na temat programu:

Program jest rozwijany w środowisku Visual C++ 6.0.
Program jest pisany obiektowo.
Glówny moduł jest odpowiedzialny za uruchamianie/zatrzymywanie wątków poszczególnych graczy. Implementacja klasy zawodnika znajduje się w pliku gracz.cpp. Klasa CDotsDialog jest implementacją panelu kontrolnego umożliwiającego sterowanie poszczególnymi wątkami.

Program testowy:
Dots.exe