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

You created this PDF from an application that is not licensed to print to novaPDF printer (

http://www.novapdf.com

)

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)

You created this PDF from an application that is not licensed to print to novaPDF printer (

http://www.novapdf.com

)

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.

You created this PDF from an application that is not licensed to print to novaPDF printer (

http://www.novapdf.com

)

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ę.

You created this PDF from an application that is not licensed to print to novaPDF printer (

http://www.novapdf.com

)

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
a. M = MINIMAX (Ptrzeciwnik(Gracz), Poziom + 1, P)
b. 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)

You created this PDF from an application that is not licensed to print to novaPDF printer (

http://www.novapdf.com

)