Elementy Sztucznej Inteligencji (Wykład 2)

Drzewo przeszukiwania grafu

Lista OPEN - lista węzłów do przeanalizowania

Lista CLOSED - lista odwiedzonych węzłów, które nie są rozwiązaniami problemu

Szkielet klasycznego algorytmu

OPEN = {pusta} CLOSED = {pusta}

1. Umieszczamy w OPEN węzeł początkowy

2. Wyjmujemy z listy OPEN węzeł W

3. Sprawdzamy czy jest on rozwiązaniem problemu. Jeśli tak to kończymy algorytm

4. Umieszczamy W na liście CLOSED, a jego potomków dodajemy do listy OPEN

5. Przechodzimy do punktu 2.

Lista OPEN (Dodawanie i zdejmowanie węzłów)

Dodajemy i zdejmujemy z początku

W = A

OPEN = {B, C, D} CLOSED = {A}

W = B

OPEN = {E, F, C, D} CLOSED = {A, B}

Powyższy algorytm opiera się o przeszukiwanie wgłąb

Można go zaimplementować rekurencyjnie

Odmianą tego algorytmu jest:

Przeszukiwanie wgłąb z iteracyjnym pogłębianiem (do pewnej głębokości / pewnego poziomu)

Jeśli nie znajdziemy rozwiązania to zwiększamy głębokość

Istnieje też przeszukiwanie wszerz (dodajemy węzły na koniec)

OPEN = {B, C, D, E, F, G, H} CLOSED = {A, ... }

W metodach sztucznej inteligencji interesują nas algorytmy heurystyczne. W nich znajduje się funkcja oceniająca (szacująca) jak blisko jesteśmy rozwiązania

Przykład na podstawie puzzli

Prawidłowe ustawienie elementów

1	2	3
8	0	4
7	6	5

Pomieszane ustawienie elementów

1	2	3
8	4	5
0	7	6

0 - puste pole

Chcemy znaleźć ciąg operacji doprowadzający do rozwiązania.

Trzeba sprawdzić, które klocki są na złych miejscach i jak daleko są od swoich miejsc (ile trzeba wykonać ruchów aby umieścić je na właściwym miejscu).

Jeśli funkcja heurystyczna zakłada, że możemy ustawiać klocek na klocku to:

1 - dobre miejsce

2 - dobre miejsce

3 - dobre miejsce

4 - złe miejsce (potrzebny 1 ruch)

5 - złe miejsce (potrzebny 1 ruch)

6 - złe miejsce (potrzebny 1 ruch)

7 - złe miejsce (potrzebny 1 ruch)

1 + 1 + 1 + 1 = 4 - wartość funkcji heurystycznej zakładającej, że możemy ustawiać klocek na klocku

Inna funkcja heurystyczna może zakładać, że klocki są wyjmowane i wkładane na właściwe miejsce

Na podstawie funkcji heurystycznych konstruujemy graf

Istnieją różne algorytmy heurystyczne, np. „Hill Climbing”

Jest to algorytm naiwny, w którym generujemy potomków i jak znajdziemy lepszego potomka to do niego przechodzimy.

Przykładowo jesteśmy w górach i wchodzimy na szczyt krok po kroku. Generując następnego potomka (nasz następny krok) sprawdzamy o ile jesteśmy wyżej i wybieramy tego potomka, który wygenerował najwyższą liczbę. Kontynuujemy algorytm. Niestety „Hill Climbing” nie gwarantuje nam sukcesu, ponieważ możemy „wejść w ślepy zaułek” którym jest jakiś pagórek, który nie generuje potomka dzięki któremu znajdziemy się wyżej w kolejnym kroku.

Algorytm „Best First Search”

Ma cechy przeszukiwania wszerze z funkcją heurystyczną

Lista OPEN jest kolejką priorytetową. Wyjmujemy węzeł o najwyższym priorytecie. W przypadku puzzli, im mniejsza wartość funkcji heurystycznej, tym wyższy priorytet.

OPEN = {A(5)} CLOSED = {pusta}

OPEN = {B(3), C(2), D(4)} CLOSED = {A}

OPEN = {B(3), D(4), G(5), H(6)} CLOSED = {A, C}

OPEN = {D(4), G(5), H(6), E(2), F(1)} CLOSED = {A, C, B}

Algorytm A*

Funkcja heurystyczna h*(w) = f(w) + g*(w)

* - wartość przybliżona

f(w) - ilość kroków (połączeń węzłów). Przykładowo w powyższym rysunku od A do C ilość kroków jest równa 1, a od A do F ilość króków jest równa 2. Jest to też nazywane kosztem dotarcia do węzła w

g*(w) - stara funkcja heurystyczna, czyli jak daleko węzeł w znajduje się od rozwiązania. Jeśli jest równa 0 to znaleźliśmy rozwiązanie.

Można ograniczyć ilość używanej pamięci do listy OPEN poprzez ograniczenie wielkości listy analizowanych węzłów, ale to nie gwarantuje znalezienia rozwiązania

W grach też występują algorytmy przeszukiwania

Algorytm MINIMAX

MINI - ruchy przeciwnika

MAX - nasze ruchy

Wartości w nawiasach oznaczają liczbowo ile mamy pionków na planszy (Szachy)

Na podstawie powyższego grafu możemy wyczytać, ze dla nas najlepszym wyjściem jest pójście w kierunku C.

Wyjaśnienie: Jeśli pójdziemy w kierunku B (zostanie nam 5 pionków) to przeciwnik pójdzie w kierunku F (zostaną nam 3 pionki). Jeśli pójdziemy w kierunku D (zostanie nam 10 pionków) to przeciwnik pójdzie w kierunku I (zostaną nam 2 pionki). Najlepszy wyjście jest pójście w kierunku C, bo po ruchu przeciwnika zostanie nam 5 (G) pionków.

W tym algorytmie analizujemy drzewo do któregoś poziomu i aktualizujemy wartości w górę.

Algorytm NEGAMAX (?)

Funkcja heurystyczna STATIC (Gracz, Plansza) zwraca wartości <-N, N>

STATIC(Gracz, Plansza) = - STATIC(Przeciwnik(Gracz), Plansza)

MOVEGEN (Gracz, Plansza) - zwraca listę plansz

MINIMAX (Gracz, Poziom, Plansza) - zwraca strukturę S, która składa się z dwóch części

• VALUE (S) - wartość (oblicza wartość planszy, w której byśmy się znaleźli)

• PATH (S) - ścieżka czyli lista plansz optymalnych

MINIMAX (Gracz, Poziom, Plansza)

1. If(KONIEC (POZIOM) ) return (VALUE: STATIC (Gracz, Plansza), PATH = {pusta})

2. POTOMKOWIE = MOVEGEN(Gracz, Plansza) //lista plansz, do których moglibyśmy się udać

3. If (POTOMKOWIE == {pusta}) return (VALUE: STATIC (Gracz, Plansza), PATH = {pusta})

4. /* trzeba wyszukać potomka o wartości MAX */

BEST_VALUE = -N

BEST_PATH = {pusta}

//dla każdego P z listy POTOMKOWIE policzymy sobie

1. M = MINIMAX (Ptrzeciwnik(Gracz), Poziom + 1, P)

2. If (VALUE (M) >= BEST_VALUE)

{

BEST_VALUE = VALUE (M)

BEST_PATH = {P, PATH (M)}

//dodajemy P na początek, a na koniec to co zwróciła lista MINIMAX

}

5. Return (VALUE: - BEST_VALUE, PATH: BEST_PATH)

---