Heurystyki

Heurystyki

Definicja

Przeszukiwanie heurystyczne jest
procesem poszukiwania żądanego
stanu spełniającego zadane warunki
W zadaniach przeszukiwania mianem
“heurystyczne” określa się wszelkie
prawa, kryteria i zasady (również
takie których skuteczność nie jest
całkowicie pewna), które umożliwiają
wybranie najbardziej efektywnych
kierunków działania, jeśli chodzi o
osiągnięcie danego celu.

Heurystyki

Termin: heurystyka

Termin heurystyka jest rozumiany w
zagadnieniach sztucznej inteligencji
następująco.

●

Jest to praktyczna strategia poprawiająca

efektywność złożonych problemów.

●

Powinna prowadzić do rozwiązania wzdłuż

najkrótszej i najbardziej prawdopodobnej
drogi omijając mniej obiecujące ścieżki

●

Podaje proste kryterium wyboru kierunków

postępowania.

●

Powinna umożliwić uniknięcie badania tzw.

Ślepych uliczek i wcześniejsze wykorzystanie
zdobytych w trakcie badania informacji

Heurystyki

Rozwiązywanie problemu: taktyka postępowania

▪

Precyzyjna definicja problemu.

▸

Punkt startu

▸

Punkt docelowy

▪

Analiza problemu.

▪

Określenie i reprezentacja wiedzy

potrzebnej do rozwiązania problemu

▪

Wybór i zastosowanie najlepszej

techniki rozwiązania problemu.

Heurystyki

Analiza problemu: gra w szachy

Punkt wyjścia:

Heurystyki

Analiza problemu: gra w szachy

Punkt decelowy: definicja
wszystkich sytuacji w których
przeciwnik nie może wykonać
ruchu królem.

Heurystyki

Analiza problemu: gra w szachy

Definicja wszystkich możliwych
ruchów określa wszystkie możliwe
kombinacje posunięć tak aby z
punkty wyjściowego dojść do
któregoś z punktów docelowych.

Heurystyki

Gra w szachy definicja ruchów

Heurystyki

Analiza problemu: gra w szachy

Pionek jest w
Pole(e,2)
i
Pole(e,3) jest
puste
i
Pole(e,4) jest
puste

=
>

Przesuń
pionek z
Pole(e,2) do
Pole(e,4)

Heurystyki

Gra w szachy: problemy

●

Trudność w zdefiniowaniu wszystkich

reguł. Może to trwać zbyt długo.

●

Problem uwzględnienia tych reguł

przez program komputerowy (zasoby
efektywność)

Heurystyki

Zbiorniki z wodą: opis problemu

Problem zbiorników z wodą:

Są dwa zbiorniki o pojemności 3 i 4
litrów. Należy tak napełnić zbiorniki
wodą aby w zbiorniku 4 litrowym
znajdowały się dokładnie dwa litry wody.
Można przelewać wodę między
zbiornikami.

Heurystyki

Zbiorniki z wodą: opis problemu

Stany przestrzeni mogą być opisane
jako:
(x,y)

X= 0,1,2,3,4
Y= 0,1,2,3

Punkt wyjścia - (0,0)
Punkt docelowy - (2,0)

Heurystyki

Zbiorniki z wodą: stany przestrzeni

1. Jeśli X<4
2. Jeśli Y<3
3. Jeśli X>0
4. Jeśli Y>0
5. Jeśli X>0
6. Jeśli Y>0
7. Jeśli X+Y>=4 i
Y>0

8. Jeśli X+Y>=3 i
X>0

9. Jeśli X+Y<=4 i
X>0
10. Jeśli X+Y<=3
X>0
11. (0,2)
12. (2,Y)

-> (4,Y)
-> (X,3)
->(X-d,Y)
->(X,Y-d)
->(0,Y)
->(X,0)
->(4,Y-(4-
X))

->(X-(3-
Y),3)

->(X+Y,0)
->(0,X+Y)
->(2,0)
->(0,Y)

Napełnij poj. 4 L
Napełnijpoj 3L
Wylej trochę wody z
poj 4L
Wylej troche wody z
poj 3L
Opróżnij poj. 4L
Opróżnij poj. 3L
Przelej wodę z poj. 3L
do poj 4L dopóki nie
będzie pełen
Przelej wodę z poj 4L
do poj 3L dopóki nie
będzie pełen
Przelej wodę z 3L do
4L
Przelej wodę z 4L do
3L
Przelej 2L z 3L do 4L
Wylej 2L z poj. 4L

Heurystyki

Zbiorniki z wodą: opis problemu

Woda w poj.
4L

0

0

3

3

4

0

2

Woda w poj.
3L

0

3

0

3

2

2

0

Reguła

2

9

2

7

5

9 lub
11

Heurystyki

Strategie przeszukiwania przestrzeni rozwiazań

●

Postęp

●

Systematyczność

Wymagania:

Heurystyki

Strategie przeszukiwania: klasyfikacja

●

Strategie ślepe

▸

Strategia wszerz

▸

Strategia w głąb

▸

Strategia z powracaniem

●

Strategie heurystyczne

▸

Strategia zachłanna (hill-climbing)

▸

Strategia najpierw najlepszy (best-first)

▸

Strategia A

*

Heurystyki

Strategie przeszukiwania: strategia wszerz

Strategia wszerz (breadh-first),
zakłada badanie kolejno poziomów
grafu o jednakowej głębokości,
przyznając wyższy priorytet węzłom o
mniejszej głębokości.

Heurystyki

Strategie przeszukiwania: strategia wszerz

●

W pamięci przechowywane są

wszystkie węzły o danej głebokości
przed wygenerowaniem
jakiegokolwiek węzła o głębokości o
jeden większej

●

W strategii tej występują duże

wymagania dotyczace pamięci

Heurystyki

Strategie przeszukiwania: strategia wszerz

(0,0
)

(4,0
)

(0,3
)

(4,3
)

(0,0
)

(1,3
)

(4,3
)

(0,0
)

(3,0
)

Heurystyki

Strategie przeszukiwania: strategia w głąb

Strategia w głąb (depth-first)- droga w
grafie jest wyznaczana dopóty dopóki
jej ostatni element nie zostanie
określony jako węzeł celu lub końcowy.
Przeszukiwanie jest zawsze
prowadzone od ostatniego
sprawdzanego węzła, którego nie
wszystkie gałęzie były jeszcze
rozwijane.

Heurystyki

Strategie przeszukiwania: strategia w głąb

(0,0
)

(4,0
)

(4,3
)

(0,0
)

(1,3
)

(0,3
)

(4,3
)

(0,0
)

(3,0
)

Heurystyki

Strategie przeszukiwania: strategia w głąb

●

W przypadku grafów o dużej

głębokości może być nieskuteczna

●

Jest często uzupełniana

mechanizmem kontroli głębokości

●

Jest właściwa dla tych problemów

dla których ocena właściwości
węzłów zależy ścisle od oceny
właściwości ich rodziców

●

W pamięci są przechowywane

tylko węzły z aktualnie badanej
ścieżki grafu

●

Oszacowane koszty tej strategii

nie są zazwyczaj osiągane w
rzeczywistości

Heurystyki

Strategie przeszukiwania: strategia z powracaniem

Strategia z powracaniem (backtracking)
jest modyfikacją algorytmu
przeszukiawania w głąb. Różnica polega
na tym że ekspansja danego węzła jest
zastąpiona jego rozszerzaniem
(generowaniem tylko jednego potomka).

Heurystyki

Strategie przeszukiwania: strategia z powracaniem

●

Oszczędność pamięci

●

Gwarancja że po zakończeniu

wszystkie wygenerowane węzły będą
przetestowane

●

Oszczędność pamięci odbywa się

kosztem dodatkowych obliczeń

Heurystyki

Strategie przeszukiwania: strategia zachłanna

(Hill-climbing)

1

Sprawdź punkt wyjściowy. Jeśli punkt

wyjściowy jest punktem docelowym zakończ. W
przeciwnym przypadku potraktuj punkt wyjściowy
jako bieżący

2

Wykonuj “w pętli” następujące operacje dopóki

nie znajdziesz rozwiązania, lub nie będzie więcej
operacji do przetwarzania

a

Wybierz nowy operator wynikajacy z stanu bieżącego

b

Analizuj operator

i

Jeśli jest to punkt docelowy to zakończ działanie

i

Jeśli nie jest to punkt docelowy ale jest lepszy niż stan bieżący

to zamień operator na stan bieżący

i

Jeśli operator nie jest lepszy niż stan bieżący to kontynuuj

“pętlę”

Heurystyki

Strategie przeszukiwania: strategia najpierw najlepszy

Strategia najpierw najlepszy
wykorzystuje peweną funkcję
heurystyczną , która wyraża ocenę
węzła ze względu na następujące
kryteria:

●

Zbieżności czyli osiągnięcia celu

●

Najmniejszej złożoności obliczeniowej

procesu przeszukiwania

Heurystyki

Strategie przeszukiwania: strategia najpierw najlepszy

1

Dodaj stan poczatkowy do zbioru stanów roboczych

R

2

Dopóki nie znaleziono rozwiązania lub zbiór R jest

pusty wykonuj:

a

Wybierz najlepszy stan ze zbioru R

b

Generuj jego węzły potomne

c

Dla każdego z węzłów potomnych wykonuj:

i

Jeżli nie był jeszcze generowany dodaj go do zbioru R i zapamiętaj

jego rodzica

i

Jeśli był już generowany. Sprawdź czy nowa ścieżka jest lepsza od

poprzedniej. Jeśli tak to sprawdzany węzeł zastępuje rodzica.

Heurystyki

Strategie przeszukiwania: algorytm A

*

Algorytm polega na wyznaczeniu
najtańszej drogi w grafie

F(w) = h(w) + g(w)

gdzie
f(w) - koszt drogi
h(w) - koszt drogi łączącej węzęł w
z węzłem celu
g(w) - koszt drogi łączącej węzeł w
węzłem początkowym

Heurystyki

Strategie przeszukiwania: algorytm A

*

Algorytm A

*

zakłada istnienie funkcji

heurystycznej pozwalającej okreslić
odłegłośc węzła w od stanu docelowego

Heurystyki

Pojedynek Kasparow - Big Blue

1997 Gari Kasparow przegrywa
pojedynek szachowy z komputerem IBM
Big Blue.

Heurystyki

Historia komputerowych systemów szachowych

▪

1949 - opracowanie podstaw teoretycznych

automatu szachowego, Alan Turing, David
Champernown

▪

1949 - Claude Shanon - konstrukcja maszyny

“Caissac” do rozwiązywania “końcówek
szachowych”

▪

MADM (Manchaster Automatic Digital Machine)-

program zdolny do rozegrania całej partii. Autor -
Alan Turing

▪

1956 - Maniac I - potrafił grać na podstawowym

poziomie

▪

Lata 60-te - szachowe programy komputerowe

reprezentują poziom początkujących graczy

▪

1967 - pierwszy pojedynek szachowy programów

komputerowych, pomiędzy USA i ZSRR - wynik
2.5:0.5

Heurystyki

Historia komputerowych systemów szachowych

▪

Początek lat 70-tych - problemem szachów

komputerowych zaczęło się interesować
amerykańskie towarzystwo ACM (Association for
Computing Machines)

▪

1974 - mistrzostwa świata w kategorii szachów

komputerowych, wygrał program opracowany w
ZSRR przy udziale Michaiła Botwinnika (mistrza
świata z lat 1948, 1951, 1954, 1958, 1961)

▪

Lata 80-te podejście techniczne

▪

Początek lat 80-tych - komputer przewidujący do

4 ruchów do przodu (firma Bell)

▪

Połowa lat 80-tych program Cray Blitz pracujący

na superkomputerze Cray mógł analizować 100
000 pozycji na sekundę.

Heurystyki

Historia komputerowych systemów szachowych

▪

1985 - Chińczyk Feng-Hsiung Hsu - opracował

specjalizowany układ scalony wielkiej integracji
(VLSI), mogący generować 2 mln ruchów
szachowych w ciągu sekundy

▪

1987 - powstaje komputer ChipTest - potrafi

analizować 50 000 na sekundę (pracował na
stacji roboczej SUN 3/160)

▪

1989 - prace badawcze w laboratorium IBM nad

zbudowaniem komputera , który pokona mistrza
świata. Powstaje Deep Thought II (2 mln pozycji na
sekundę)

▪

Deep Blue - komputer przygotowany do

pokonania mistrza świata

Heurystyki

Charakterystyka Deep Blue

▪

256 specjalizowanych układow VLSI

▪

Komputer IBM RS/6000 SP2, 32 procesory

▪

Każdy z 32 węzłów systemu wykorzystywał kartę

microchannel wyposażoną w 8 dedykowanych
procesorów szachowych

▪

Waga systemu 1.5 tony

Heurystyki

1996 - pojedynek o mistrzostwo świata

Kasparow - Big Blue

▪

Pojedynek składał się z trzech partii

▪

I partia wygrywa Deep Blue

▪

II partia wygrywa Kasparow

▪

III ,IV partia remis

▪

V i VI partia wygrywa Kasparow

Heurystyki

1997 - pojedynek o mistrzostwo świata

Kasparow - Big Blue

▪

6 partii

▪

2 godziny dla kazdego z graczy na pierwsze 40

ruchów

▪

30 minut ostateczny czas na wszystkie kolejne

ruchy

▪

Deep Blue obsługiwany przez operatora

wskazanego przez IBM

▪

Ewentualny czas awarii miał byc odliczany od

czasu ruchu komputera

Heurystyki

1997 - pojedynek o mistrzostwo świata

Kasparow - Big Blue

1

- wygrywa Kasparow

2

- wygrywa Deep Blue

3

Remis

4

Remis

5

Remis

6

Kasparow poddaje się po 19 posunięciu

Heurystyki

Technika gry Deep Blue

●

Początkowo - system ekspercki ktory

korzystając ze zgromadzonych zasobów wiedzy
szachowej miał wyliczać najlepszą odpowiedź na
ruch przeciwnika

●

Wykorzystanie złożonej funkcji oceny pozycji

na szachownicy. Funkcja oceny analizowała cztery
podstawowe wartości

▸

Materialna (pion -1, skoczek i goniec - 3, wieża 5,

królowa 9

▸

Pozycja na szachownicy (zliczanie bezpiecznych pól)

▸

Bezpieczeństwo króla

▸

Tempo gry

Heurystyki

Blue Gene następca Big Blue

●

Masowe przetwarzanie równoległe

●

Wydajność ponad 1 petaflopa (kwadrylion

operacji na sekundę)

●

Przeznaczenie modelowanie występujace w

organizmach żywych (procesy zwijania białek)