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

   }

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