Wroclaw 16.06.2006

Metody sztucznej inteligencji
Raport z "duzego" projektu

Problem 15-puzzle

Autor: Mariusz Zalewski
Kierunek: ARR
nr indeksu : 128547

Opis problemu:

Gra 15-puzzle zostala wynaleziona pod koniec XIX wieku przez Sam Loyd, jednego z najwiekszych tworcow roznorakich ukladanek. Poczatkowo zostala nazwana "Boss puzzle", pozniej zmieniono nazwe na "15-puzzle". Zasadniczo gra polega na tym, aby wymieszac klocki, a nastepnie przywrocic ustawienie poczatkowe. Plansza jest wymiarów 4x4, wiec jedno pole zawsze pozostanie puste. Przesuwajac klocki na puste pole trzeba tak manewrowac, aby ustawic calosc w zadanej kolejnosci. Dla niektorych ustawien poczatkowych rozwiazanie jest mozliwe, dla innych nie. Jednakze jezeli ustawienie poczatkowe zostalo wygenerowane przez przesuwanie klockow rozwiazanie zawsze jest osiagalne. Dla rozstawienia losowego nie musi tak byc. W kazdym momecnie mamy przynajmniej dwie mozliwosci ruchu (w naroznikach), trzy przy scianach, oraz cztery wewnatrz.

Metody rozwiazywanie problemu:

Do rozwiazywanie problemow tego typu doskonale nadaja sie konstrukcje typu drzewo. W kazdym kolejnym kroku ukladanki mozemy wykonac (w zaleznosci od polozenie pustego pola) od dwoch do czterech roznych przesuniec. Zakladajac ze nigdy nie bedziemy sie cofali, tj wracali do poprzedniego, liczba mozliwych posuniec spada do 1-3. Wiedzac, ze liczba mozliwych permutacji jest skonczona, sprawdzajac wszystkie mozliwe posuniecia powinnismy dotrzec do celu. W tym celu budujemy drzewo na ktorym zapisujemy wszystkie kolejne stany. W celu unikniecia powtorzen w kazdej kolejnej iteracji dokonujemy przegladu wszystkich lisci drzewa. Jezeli znajdziemy na nich taki sam stan jak obecny zamykame te galaz i przechodzimy do kolejnej. W ten sposob budujemy drzewo, az do znalezienia pozadanego stanu. Rozrozniamy dwie podstawowe strategie budowy drzewa:

• Przeszukiwanie wszerz (ang. Breadth-first search) to algorytm przeszukiwania grafu uzywany do przechodzenia lub przeszukiwania drzewa lub grafu. Algorytm zaczyna od korzenia i odwiedza wszystkie polaczone z nim wezly. Nastepnie odwiedza wezly polaczone z tymi wezlami i tak dalej, az do odnalezienia celu.
  
• Przeszukiwanie w glab (ang. Depth-first search) to w informatyce algorytm przeszukiwania grafu uzywany do przechodzenia lub przeszukiwania drzewa lub grafu. Przeszukiwanie zaczyna sie od korzenia i porusza sie w dól do samego konca galezi, po czym wraca sie o jeden poziom i próbuje kolejne galezie itd.
  Zlozonosc pamieciowa przeszukiwania w glab jest o wiele mniejsza niz przeszukiwania wszerz. Zlozonosc czasowa obu algorytmów jest proporcjonalna do liczby wiercholków plus liczby krawedzi w przeszukiwanym grafie.

  Przyklad:
  
  Zakladajac ze najpierw wybiera sie wezly z lewej strony, pózniej te z prawej, oraz zakladajac, ze przeszukiwanie bedzie pamietalo które wierzcholki sa juz odwiedzone, przeszukiwanie zaczynajac od A, odwiedzi sie wezly w tej kolejnosci: A, B, D, F, E, C, G.
  Przeszukujac bez pamietania które wierzcholki sie juz odwiedzilo, kolejnosc bedzie taka: A, B, D, F, E, A, B, D, F, E, itd. w nieskonczonosc, bedac uwiezionym w cyklu A, B, D, F, E i nigdy nie docierajac do C lub G.

 Zadna z w/w metod przeszukiwan nie daje zadowalajacych rezlutatow. Dzieje sie tak z bardzo prostej przyczyny - liczba ruchow potrzebna do rozwiazania najtrudniejszego przypadku 8-puzzle wynosi 30, zas dla 15-puzzle 90. Aby dotrzec do tak pesymistycznego rozwiazania potrzebujemy zbudowac drzewo o gleboskosci 90, a nie mozmey miec zadnych nadzieji, ze algorytm szybko trafi w galaz w ktorej znajdzie rozwiaznie. Natomiast budowa drzewa wszystkich mozliwych stanow (16!) nie jest mozliwa w skonczonym czasie t oraz niemozliwa do zapamietania dla wspolczesnych komputerow.

Aby nie przegladac galezi nie wrozacych szybkiego djscia do prawidlowego rozwiazania wprowadzono specjalne funkcje oceny. Dla kazdego stanu obliczamy funkcje oceny. Funkcja ta okresla jak blisko (daleko) od rozwiazania znajdujemy sie. Nastepnie rozwijamy te galaz dla ktorej funkcja ta przyjmuje najnizsze wartosci. Unikamy w ten sposob rozwijania "slepych" galezi. Kluczowe jest znalezienie takich funkcji oceny, dla ktorych bez zbednych rozgalezien algorytm szybko trafi do rozwiazania.

Pomimo zastosowania funkcji oceny, algorytm nadal chodzi po niepotrzebnych stanach. Czy zapamietywanie galezi tych stanow jest na do czegos potrzebne? Jezeli w kazdej kolejnej iteracji zapewnimy wejscie w inna galaz niz do tej pory nie bedziemy potrzebowali sprawdzac wszystkich poprzednich stanow, oszczedzajac tym samym spore poklady pamieci komputera. W tym celu potrzebujemy zapamietywac tylko dwie galezie, poprzednio wykonywana i obecna. Wiedzac jakimi kryteriami kierowalismy sie wybierajac poprzednia sciezke zawsze wybierzemy taka ktorej jeszcze nie analizowalismy.

Zastosowane kryteria oceny (heurystyki):

• liczba elementow nie sa swoim miejscu
  for(int i=0; i<size; i++)
  if (block[i] != goal_block[i]) to_return++;
  return to_return;
• suma odleglosci od punktu docelowego kazdego elementu w normie manhattanu
  for(int i=0; i<size; i++) {
  to_return += abs((goal_block[i]/pierw) - (block[i]/pierw));
  to_return += abs(((goal_block[i]-1)%pierw) - ((block[i]-1)%pierw));
  }
  return to_return
• jak wyzej, oraz dodatkowy punkt jezeli prawy sasiad jest inny niz nakazuje to rozwiazanie
  for(int i=0; i<size; i++) {
  to_return += abs((goal_block[i]/pierw) - (block[i]/pierw));
  to_return += abs(((goal_block[i]-1)%pierw) - ((block[i]-1)%pierw));
  if ((i%4)!=3)
  if (block[i]!=block[i+1]+1)
  to_return++;
  }
  return to_return
• odleglosci w normie manhattanu oraz dodatkowe sprawdzenie czy wiersz pierwszy lub pierwszy i drugi jest uporzadkowany zgodnie z ustawieniem docelowym
  for(int i=0; i<size; i++)
  {
  to_return += abs((goal_block[i]/pierw) - (block[i]/pierw));
  to_return += abs(((goal_block[i]-1)%pierw) - ((block[i]-1)%pierw));
  }
  for (int i=0;i<pierw;i++)
  {
  if (goal_block[i]!=block[i]) {l1=0; l2=0; break;}
  if (goal_block[pierw+i]!=block[pierw+i]) {l2=0; break;}
  }
  if (l1==0) to_return+=5;
  if (l2==0) to_return+=5;
  break;
  }
  return to_return;

Implementacja algorytmu:

Algorytm zostal zaimplementowany w jezyku C++ w srodowisku Borland C++ Builder v6.0. Jak powiedziano w poprzednim punkcie zapisywane sa tylko dwie kolejne galezie. Zrealzowano to na listach jednokierunkowych.

Przykladowe wywolania programu:

Wywolanie programu dla ponizszych danych wczytanych z pliku:

16
6 5 2 4
9 1 3 7
14 11 8 12
10 13 0 15

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
50

Struktura plku wejsciowego:
n-rozmiar (dopuszczalne 9,16)
p1,p2,...,p16 - polozenia poczatkowe kolejnych elementow
k1,k2,...,k16 - ustawienie koncowe
max - maksymalna glebokosc przeszukiwania.

15-Puzzle!
Wybierz czy chcesz wczytac z pliku czy z klawiatury
1.Z klawiatury
2.Z pliku
2
Podaj nazwe pliku ktory chcesz wczytac:
9p1.txt
Wybierz heurystyczna funkcje oceny: 1
Pracuje...0
1 u
2 ul
2 uu
3 uur
3 uul
4 uuld
5 uuldr
Zrobione.
Znaleziono rozwiazanie w <5> krokach
Czy chcesz zobaczyc poszczegolne kroki poszukiwan rozwiazania ?(T/N)?
-------------
|2|8|3
-------------
|1|6|4
-------------
|7|0|5

-------------
|2|8|3
-------------
|1|0|4
-------------
|7|6|5

-------------
|2|0|3
-------------
|1|8|4
-------------
|7|6|5

-------------
|0|2|3
-------------
|1|8|4
-------------
|7|6|5

-------------
|1|2|3
-------------
|0|8|4
-------------
|7|6|5

-------------
|1|2|3
-------------
|8|0|4
-------------
|7|6|5

Wyswietlanie plansz zakonczone.
Nastepujace kroki to: (Ruchy: u=up, d=down, l-left, r=right)
uuldr
Nacisnij dowwlony klawisz, abu kontynuowac . . .

Zestawienie i omowienie wynikow:

Ponizej przedstawiono wyniki czasowe dla poszczegolnych danych przy zastosowaniu roznych funkcji heurystycznych

Zadanie 16p3.txt mozna rozwiazac w 46 posunieciach. Zaimplementowany algorytm nie radzi sobie juz z takim przypadkiem. Pozostale mniej skomplikowane daja sie rozwiazac zaimplementowanymi metodami.

Wnioski:

Zaimplementowany przeze mnie algorytm bez problemu radzi sobie z ukladanka 8-puzzle. Dla problemu 15-puzzle program potrafi rozwiazac mniej skomplikowane przypadki w sesnownym czasie. Trudno okreslic jak dlugo zajeloby obliczenie przykladu 16p3.txt, jednakze prawdopodobnie program zwrocilby poprawna odpowiedz. Kluczem do szybkiego rozwiazania problemu jest znalezienie takiej heurystycznej funkcji oceny ktora zapewni szybka zbieznosc do pozadanego stanu. Sposrod zaimplementowanych metod oceny najlepiej radzi sobie bardzo prosta ocena odleglosci w normia manhattanu. Z pozoru lepsze funkcje H2 i H3 radza sobie znacznie gorzej. Natomiast funkcja licz elementy na swoich miejscach zgodnie z przewidywaniami radzi sobie kiepsko.

Bibliografia:

• http://bd.thrijswijk.nl/15puzzle/15puzzen.htm
• http://www.ic-net.or.jp/home/takaken/e/15pz/index.html
• http://www.heyes-jones.com/astar.html
• http://sequoia.ict.pwr.wroc.pl/~witold/aiarr/