Przenieś kolejność

Skuteczność przycinania alfa-beta w dużym stopniu zależy od kolejności, w jakiej badane są stany. Na przykład na rysunku (e) i (f) nie mogliśmy w ogóle przyciąć żadnych następców D, ponieważ najgorsze następniki (z punktu widzenia MIN) zostały wygenerowane jako pierwsze.

Gdyby trzeci następca D został wygenerowany jako pierwszy, z wartością 2, bylibyśmy w stanie przyciąć dwóch pozostałych następców. Sugeruje to, że warto spróbować najpierw zbadać następców, którzy prawdopodobnie będą najlepsi. Gdyby można było to zrobić perfekcyjnie, alfa-beta musiałaby zbadać tylko O(bm/2) węzły, aby wybrać najlepszy ruch, zamiast O(bm) dla minimaksu. Oznacza to, że efektywnym współczynnikiem rozgałęzienia staje się pierwiastek b zamiast b – dla szachów około 6 zamiast 35. Innymi słowy, alfa-beta z doskonałą kolejnością ruchów może rozwiązać drzewo mniej więcej dwa razy głębsze niż minimax w tym samym czasie . Przy losowej kolejności ruchów całkowita liczba zbadanych węzłów będzie w przybliżeniu wynosić O(b3m/4) dla umiarkowanego b . Teraz oczywiście nie możemy osiągnąć idealnego uporządkowania ruchów – w takim przypadku funkcja zamawiania mogłaby zostać wykorzystana do rozegrania doskonałej gry! Ale często możemy podejść dość blisko. W przypadku szachów dość prosta funkcja porządkowania (taka jak próba najpierw przechwytów, potem zagrożeń, potem ruchów do przodu, a następnie ruchów do tyłu) pozwala uzyskać mniej więcej czynnik 2 od wyniku w najlepszym przypadku O(bm/2).

Dodanie dynamicznych schematów kolejności ruchów, takich jak wypróbowywanie najpierw ruchów, które w przeszłości uznano za najlepsze, zbliża nas do teoretycznego limitu. Przeszłość może być poprzednim posunięciem – często pozostają te same zagrożenia – lub może pochodzić z wcześniejszej eksploracji obecnego posunięcia poprzez proces iteracyjnego pogłębiania. Najpierw przeszukaj jedną warstwę głęboko i zapisz ranking ruchów na podstawie ich ocen. Następnie przeszukaj jedną warstwę głębiej, używając poprzedniego rankingu do informowania o kolejności ruchów; i tak dalej. Wydłużony czas wyszukiwania wynikający z iteracyjnego pogłębiania może być więcej niż nadrobiony dzięki lepszemu porządkowaniu ruchów. Najlepsze ruchy są znane jako zabójcze ruchy, a wypróbowanie ich w pierwszej kolejności nazywa się heurystyką zabójczych ruchów.

Zauważyliśmy, że nadmiarowe ścieżki do powtarzających się stanów mogą powodować wykładniczy wzrost kosztów wyszukiwania, a prowadzenie tabeli stanów, które zostały wcześniej osiągnięte, może rozwiązać ten problem. W przeszukiwaniu drzewa gry mogą wystąpić powtarzające się stany z powodu transpozycji — różnych permutacji sekwencji ruchu, które kończą się w tej samej pozycji, a problem można rozwiązać za pomocą tabeli transpozycji, która buforuje wartości heurystyczne stanów. Załóżmy na przykład, że biały ma ruch w1, na który czarny może odpowiedzieć b1 i niepowiązany ruch w2 po drugiej stronie szachownicy, na który może odpowiedzieć b2 , i że przeszukujemy sekwencję ruchów [w1,b1,w2 ,b2 ] ; nazwijmy wynikowy stan . Po zbadaniu dużego poddrzewa poniżej znajdujemy jego kopię zapasową, którą przechowujemy w tabeli transpozycji. Kiedy później przeszukujemy sekwencję ruchów , znajdujemy się ponownie i możemy wyszukać wartość zamiast powtarzać wyszukiwanie. W szachach bardzo efektywne jest wykorzystanie tabel transpozycji, co pozwala nam podwoić osiągalną głębokość wyszukiwania w tym samym czasie. Nawet przy przycinaniu alfa-beta i sprytnym porządkowaniu ruchów minimax nie zadziała w grach takich jak szachy i Go, ponieważ wciąż jest zbyt wiele stanów do zbadania w dostępnym czasie. W pierwszym artykule na temat gier komputerowych, Programowanie komputera do gry w szachy, Claude Shannon rozpoznał ten problem i zaproponował dwie strategie: strategia typu A uwzględnia wszystkie możliwe ruchy do określonej głębokości w drzewie wyszukiwania, a następnie wykorzystuje heurystykę funkcja oceny do oszacowania użyteczności stanów na tej głębokości. Bada szeroką, ale płytką część drzewa. Strategia typu B ignoruje ruchy, które wyglądają źle i podąża za obiecującymi liniami „tak daleko, jak to możliwe”. Bada głęboką, ale wąską część drzewa. Historycznie, większość programów szachowych należała do Typu A (który omówimy w następnej sekcji), podczas gdy programy Go są częściej Typu B (omówione w Sekcji 5.4), ponieważ współczynnik rozgałęzienia jest znacznie wyższy w Go. Niedawno programy typu B pokazały grę na poziomie mistrzów świata w różnych grach, w tym w szachy

Przycinanie alfa-beta

Liczba stanów gry jest wykładnicza na głębokości drzewa. Żaden algorytm nie jest w stanie całkowicie wyeliminować wykładnika, ale czasami możemy przeciąć go o połowę, obliczając prawidłową decyzję minimaksową bez badania każdego stanu poprzez przycinanie dużych części drzewa, które nie mają wpływu na wynik. Konkretna technika, którą badamy, nazywa się przycinaniem alfa-beta. Rozważmy ponownie dwuwarstwowe drzewo gry . Przejdźmy jeszcze raz przez obliczenie optymalnej decyzji, tym razem zwracając szczególną uwagę na to, co wiemy na każdym etapie procesu. Kroki są wyjaśnione na rysunku. Wynikiem jest to, że możemy zidentyfikować decyzję minimax bez oceny dwóch węzłów liści.

Innym sposobem spojrzenia na to jest uproszczenie formuły MINIMAX. Niech dwa nieocenione następniki węzła C na rysunku mają wartości x i y . Wtedy wartość węzła głównego jest dana przez

Innymi słowy, wartość pierwiastka, a tym samym decyzja o minimaksie, są niezależne od wartości liści x i y i dlatego można je przycinać. Przycinanie alfa-beta może być stosowane do drzew o dowolnej głębokości i często można przycinać całe poddrzewa, a nie tylko liście. Ogólna zasada jest następująca: rozważ węzeł n gdzieś w drzewie, taki, że Gracz ma wybór przejścia do . Jeśli Gracz ma lepszy wybór albo na tym samym poziomie (np. m’ na rysunku 5.6 ) lub w dowolnym punkcie wyżej w drzewie (np. m na rysunku), to nigdy nie przejdzie do . Więc kiedy już wystarczająco dowiedzieliśmy się o n (poprzez zbadanie niektórych jego potomków), aby dojść do tego wniosku, możemy je przyciąć.

Pamiętaj, że wyszukiwanie minimaksowe jest na pierwszym miejscu, więc w dowolnym momencie musimy brać pod uwagę węzły wzdłuż pojedynczej ścieżki w drzewie. Przycinanie alfa-beta bierze swoją nazwę od dwóch dodatkowych parametrów w MAX-VALUE (stan α , β) , które opisują granice wartości kopii zapasowej, które pojawiają się w dowolnym miejscu na ścieżce:

α = wartość najlepszego (tj. najwyższej wartości) wyboru, jaki do tej pory znaleźliśmy w dowolnym punkcie wyboru na ścieżce dla MAX. Pomyśl: α = „przynajmniej”.

β = wartość najlepszego (tj. najniższej wartości) wyboru, jaki do tej pory znaleźliśmy w dowolnym punkcie wyboru na ścieżce dla MIN. Pomyśl: β = „co najwyżej”.

Wyszukiwanie alfa-beta aktualizuje wartości α i β w miarę postępu i usuwa pozostałe gałęzie w węźle (tj. kończy wywołanie rekurencyjne), gdy tylko wiadomo, że wartość bieżącego węzła jest gorsza niż bieżąca alfa lub wartość beta odpowiednio dla MAX lub MIN.

Optymalne decyzje w grach wieloosobowych

Wiele popularnych gier pozwala na więcej niż dwóch graczy. Przyjrzyjmy się, jak rozszerzyć ideę minimaxa na gry wieloosobowe. Jest to proste z technicznego punktu widzenia, ale rodzi kilka interesujących nowych kwestii koncepcyjnych. Najpierw musimy zastąpić pojedynczą wartość dla każdego węzła wektorem wartości. Na przykład w grze trzyosobowej z graczami A, B i C, wektor (vA.vB,vC) jest powiązany z każdym węzłem. W przypadku stanów końcowych wektor ten podaje użyteczność stanu z punktu widzenia każdego gracza. (W grach dla dwóch graczy o sumie zerowej dwuelementowy wektor można zredukować do pojedynczej wartości, ponieważ wartości są zawsze przeciwne). Najprostszym sposobem na zaimplementowanie tego jest zwrócenie przez funkcję UTILITY wektora narzędzi. Teraz musimy rozważyć stany nieterminalne. Rozważ węzeł zaznaczony X w drzewie gry pokazanym na rysunku.

W tym stanie gracz C decyduje, co robić. Te dwie opcje prowadzą do stanów końcowych z wektorami użyteczności (vA = 1.vB = 2 ,vC = 6) i (vA = 4 .vB = 2,vC = 3) . Ponieważ 6 jest większe niż 3, C powinien wybrać pierwszy ruch. Oznacza to, że jeśli stan X zostanie osiągnięty, kolejne odtwarzanie doprowadzi do stanu końcowego  z narzędziami (vA = 1.vB = 2 ,vC = 6)  . Dlatego wartością kopii zapasowej X jest ten wektor. Ogólnie rzecz biorąc, wartość węzła n w kopii zapasowej jest wektorem użyteczności stanu następcy z najwyższą wartością dla gracza wybierającego w n.

Każdy, kto gra w gry wieloosobowe, takie jak Dyplomacja czy Osadnicy z Catanu, szybko uświadamia sobie, że dzieje się o wiele więcej niż w grach dwuosobowych. Gry wieloosobowe zwykle obejmują sojusze, formalne lub nieformalne, między graczami. Sojusze są zawierane i łamane w miarę postępu gry. Jak mamy rozumieć takie zachowanie? Czy sojusze są naturalną konsekwencją optymalnych strategii dla każdego gracza w grze wieloosobowej? Okazuje się, że mogą.

Załóżmy na przykład, że A i B są na słabych pozycjach, a C na silniejszej pozycji. Wtedy często optymalne jest, aby zarówno A, jak i B atakowały C, a nie siebie nawzajem, aby C nie zniszczyło każdego z nich z osobna. W ten sposób współpraca wyłania się z czysto egoistycznego zachowania.

Oczywiście, gdy tylko C słabnie pod wspólnym natarciem, sojusz traci swoją wartość, a A lub B mogą naruszyć porozumienie. W niektórych przypadkach jawne sojusze jedynie konkretyzują to, co i tak by się wydarzyło. W innych przypadkach zerwanie sojuszu wiąże się z piętnem społecznym, więc gracze muszą zrównoważyć bezpośrednią przewagę zerwania sojuszu z długoterminową wadą bycia postrzeganym jako niegodny zaufania. Jeśli gra nie ma sumy zerowej, współpraca może również mieć miejsce tylko z dwoma graczami. Załóżmy na przykład, że istnieje stan terminala z narzędziami (vA = 1000 i vB = 1000), że 1000 jest najwyższą możliwą użytecznością dla każdego gracza. Wtedy optymalna strategia polega na tym, aby obaj gracze zrobili wszystko, co możliwe, aby osiągnąć ten stan – to znaczy, że gracze będą automatycznie współpracować, aby osiągnąć wspólnie pożądany cel.

Algorytm wyszukiwania minimax

Teraz, gdy możemy obliczyć MINIMAX(y), możemy przekształcić to w algorytm wyszukiwania, który znajduje najlepszy ruch dla MAX, próbując wszystkie działania i wybierając to, którego wynikowy stan ma najwyższą wartość MINIMAX. Rysunek przedstawia algorytm. Jest to algorytm rekurencyjny, który przechodzi aż do liści drzewa, a następnie tworzy kopię zapasową wartości minimax w drzewie, gdy rekurencja się rozwija. Na przykład na rysunku wcześniej algorytm najpierw przechodzi w dół do trzech dolnych lewych węzłów i używa na nich funkcji UTILITY, aby odkryć, że ich wartości wynoszą odpowiednio 3, 12 i 8. Następnie pobiera minimalną z tych wartości, 3, i zwraca ją jako kopię zapasową wartości node . Podobny proces daje w kopii zapasowej wartości 2 dla i 2 dla C . Na koniec przyjmujemy maksymalnie 3, 2 i 2, aby uzyskać kopię zapasową wartości 3 dla węzła głównego.

Algorytm minimax wykonuje pełną eksplorację drzewa gry w głąb. Jeżeli maksymalna głębokość drzewa wynosi m i w każdym punkcie są dozwolone ruchy, to złożoność czasowa algorytmu minimax wynosi O(bm) . Złożoność przestrzeni wynosi O(bm) dla algorytmu, który generuje wszystkie akcje na raz, lub O(m) dla algorytmu, który generuje akcje pojedynczo. Wykładnicza złożoność sprawia, że MINIMAX jest niepraktyczny dla złożonych gier; na przykład szachy mają współczynnik rozgałęzienia około 35, a średnia gra ma głębokość około 80 warstw i nie jest możliwe przeszukanie 3580 ≈ 10123 stanów. MINIMAX służy jednak jako podstawa do matematycznej analizy gier. Aproksymując analizę minimaksową na różne sposoby, możemy uzyskać bardziej praktyczne algorytmy.

Optymalne decyzje w grach

MAX chce znaleźć sekwencję działań prowadzących do wygranej, ale MIN ma na ten temat coś do powiedzenia. Oznacza to, że strategia MAX musi być planem warunkowym – strategią warunkową, określającą reakcję na każdy z możliwych ruchów MIN. W grach, które mają wynik binarny (wygrana lub przegrana), możemy użyć wyszukiwania AND–OR (strona 125), aby wygenerować plan warunkowy. W rzeczywistości w takich grach definicja strategii wygrywającej w grze jest identyczna z definicją rozwiązania niedeterministycznego problemu planowania: w obu przypadkach pożądany wynik musi być zagwarantowany bez względu na to, co zrobi „druga strona”. W przypadku gier z wieloma wynikami, potrzebujemy nieco bardziej ogólnego algorytmu zwanego wyszukiwaniem minimaksowym.

Rozważ trywialną grę z rysunku 5.2. Możliwe ruchy dla MAX w węźle głównym są oznaczone jako a1, a2 i a3. Możliwe odpowiedzi na a1 dla MIN to b1 , b2 , b3 i tak dalej. Ta konkretna gra kończy się po jednym ruchu, każdy o MAX i MIN. (UWAGA: W niektórych grach słowo „ruch” oznacza, że ​​obaj gracze podjęli działanie; dlatego słowo ply jest używane do jednoznacznego oznaczenia jednego ruchu jednego gracza, co przenosi nas o jeden poziom głębiej w drzewo gry). stany terminali w tej grze wahają się od 2 do 14.

Mając dane drzewo gry, optymalną strategię można określić, wyliczając wartość minimaksową każdego stanu w drzewie, którą zapisujemy jako MINIMAX(y). Wartość minimax to użyteczność (dla MAX) bycia w tym stanie, przy założeniu, że obaj gracze grają optymalnie od tego momentu do końca gry. Wartość minimax stanu terminala to tylko jego użyteczność. W stanie nieterminalnym MAX woli przejść do stanu o maksymalnej wartości, gdy nadchodzi kolej MAXa na ruch, a MIN preferuje stan o minimalnej wartości (czyli minimalnej wartości dla MAX, a tym samym maksymalnej wartości dla MIN). Więc mamy:

Zastosujmy te definicje do drzewa gry na rysunku 5.2. Węzły końcowe na dolnym poziomie uzyskują swoje wartości użytkowe z funkcji UTILITY w grze. Pierwszy węzeł MIN, oznaczony etykietą , ma trzy stany następcze o wartościach 3, 12 i 8, więc jego wartość minimax wynosi 3. Podobnie pozostałe dwa węzły MIN mają wartość minimax 2. Węzeł główny jest węzłem MAX; jego stany następcze mają wartości minimax 3, 2 i 2; więc ma wartość minimaksową równą 3. Możemy również zidentyfikować decyzję minimaksową u korzenia: akcja a1 jest optymalnym wyborem dla MAX, ponieważ prowadzi do stanu o najwyższej wartości minimaksowej.

Ta definicja optymalnej gry dla MAX zakłada, że ​​MIN również gra optymalnie. Co jeśli MIN nie gra optymalnie? Wtedy MAX poradzi sobie co najmniej tak dobrze, jak przeciwko optymalnemu graczowi, a może nawet lepiej. Nie oznacza to jednak, że zawsze najlepiej jest zagrać optymalny ruch minimaksowy w obliczu nieoptymalnego przeciwnika. Rozważ sytuację, w której optymalna gra obu stron doprowadzi do remisu, ale jest jeden ryzykowny ruch dla MAX, który prowadzi do stanu, w którym jest 10 możliwych ruchów odpowiedzi na MIN, które wydają się rozsądne, ale 9 z nich to strata dla MIN, a jeden to strata dla MAX. Jeśli MAX uważa, że ​​MIN nie ma wystarczającej mocy obliczeniowej, aby odkryć optymalny ruch, MAX może chcieć spróbować ryzykownego ruchu, ponieważ szansa 9/10 na wygraną jest lepsza niż pewien remis.

Gry dwuosobowe o sumie zerowej

Gry najczęściej badane w ramach sztucznej inteligencji (takie jak szachy i go) to gry, które teoretycy gier nazywają deterministycznymi, dwuosobowymi, rozgrywającymi się na zmianę, z doskonałą informacją, grami o sumie zerowej. „Doskonała informacja” jest synonimem „w pełni obserwowalnej”, a „suma zerowa” oznacza, że to, co jest dobre dla jednego gracza, jest tak samo złe dla drugiego: nie ma wyniku „wygrana-wygrana”. W grach często używamy terminu move jako synonimu „akcji” i pozycji jako synonimu „stanu”. Zadzwonimy do naszych dwóch graczy MAX i MIN, z powodów, które wkrótce staną się oczywiste. MAX porusza się jako pierwszy, a następnie gracze na zmianę poruszają się, aż gra się skończy. Na koniec gry zwycięski gracz otrzymuje punkty, a przegrany otrzymuje kary. Gra może być formalnie zdefiniowana za pomocą następujących elementów:

* S0 : Stan początkowy, który określa, jak gra jest skonfigurowana na początku.

* TO-MOVE(s): Gracz, którego kolej ma się poruszyć w stanie .

* ACTIONS : Zestaw prawidłowych ruchów w stanie .

* RESULTS(s,a): Model przejścia, który definiuje stan wynikający z podjęcia działań w stanie .

* IS-TERMINAL(s): Test terminala, który jest prawdziwy po zakończeniu gry i fałszywy w przeciwnym razie. Stany, w których gra się zakończyła, nazywane są stanami końcowymi.

* UTILITY(s,p) : Funkcja użyteczności (nazywana również funkcją celu lub funkcją wypłaty), która definiuje ostateczną wartość liczbową dla gracza, gdy gra kończy się w stanie terminala. W szachach wynikiem jest wygrana, przegrana lub remis z wartościami 1 , 0 lub 1/2 . Niektóre gry mają szerszy zakres możliwych wyników – na przykład wypłaty w tryktraku wahają się od 0 do 192 .

Podobnie jak wcześniej , stan początkowy, funkcja AKCJE i funkcja WYNIK definiują graf przestrzeni stanów – graf, w którym wierzchołki są stanami, krawędziami są ruchami, a stan może być osiągnięty wieloma ścieżkami. Możemy nałożyć drzewo poszukiwań na część tego wykresu, aby określić, jaki ruch wykonać. Kompletne drzewo gry definiujemy jako drzewo wyszukiwania, które podąża za każdą sekwencją ruchów aż do stanu terminala. Drzewo gry może być nieskończone, jeśli sama przestrzeń stanów jest nieograniczona lub jeśli reguły gry pozwalają na nieskończenie powtarzające się pozycje. Rysunek przedstawia część drzewa gry w kółko i krzyżyk (kółko i krzyżyk). Od stanu początkowego MAX ma dziewięć możliwych ruchów. Gra naprzemiennie polega na tym, że MAX umieszcza X MIN, umieszcza O, aż dotrzemy do węzłów liści odpowiadających stanom końcowym, tak że jeden gracz ma trzy kwadraty z rzędu lub wszystkie kwadraty są wypełnione. Liczba na każdym węźle liścia wskazuje wartość użytkową stanu końcowego z punktu widzenia MAX; wysokie wartości są dobre dla MAX, a złe dla MIN (w ten sposób gracze otrzymują swoje nazwy).

W przypadku gry w kółko i krzyżyk drzewo gry jest stosunkowo mniejsze niż 9! = 362 880 węzłów końcowych (tylko 5478 różnych stanów). Ale w szachach istnieją ponad węzły, więc drzewo gry najlepiej traktować jako konstrukt teoretyczny, którego nie możemy zrealizować w świecie fizycznym.

Teoria gier

Istnieją co najmniej trzy stanowiska, które możemy przyjąć w stosunku do środowisk wieloagentowych. Pierwszym stanowiskiem, odpowiednim w przypadku bardzo dużej liczby podmiotów, jest rozważenie ich łącznie jako gospodarki, co pozwala nam na przewidywanie, że rosnący popyt spowoduje wzrost cen, bez konieczności przewidywania działania jakichkolwiek indywidualny agent. Po drugie, moglibyśmy traktować podmioty przeciwne tylko jako część środowiska – część, która sprawia, że ​​środowisko jest niedeterministyczne. Ale jeśli modelujemy przeciwników w taki sam sposób, w jaki, powiedzmy, deszcz czasami pada, a czasami nie, tracimy ideę, że nasi przeciwnicy aktywnie próbują nas pokonać, podczas gdy deszcz rzekomo nie ma takiego zamiaru. Trzecie stanowisko polega na wyraźnym modelowaniu przeciwników za pomocą technik przeszukiwania drzew przeciwnika. To właśnie obejmuje ten rozdział. Zaczynamy od ograniczonej klasy gier i definiujemy optymalny ruch oraz algorytm do jego znajdowania. Przeszukiwanie minimaksowe, uogólnienie przeszukiwania AND–OR. Pokazujemy, że przycinanie sprawia, że ​​wyszukiwanie jest bardziej wydajne, ignorując części drzewa wyszukiwania, które nie mają wpływu na optymalny ruch. W nietrywialnych grach zwykle nie mamy wystarczająco dużo czasu, aby znaleźć optymalny ruch (nawet przy przycinaniu); w pewnym momencie będziemy musieli przerwać poszukiwania. Dla każdego stanu, w którym postanowiliśmy przestać szukać, pytamy, kto wygrywa. Aby odpowiedzieć na to pytanie, mamy wybór: możemy zastosować heurystyczną funkcję oceny, aby oszacować, kto wygrywa na podstawie cech stanu, lub możemy uśrednić wyniki wielu szybkich symulacji gry z tego stanu wszystkie droga do końca . Omawiamy gry, które zawierają element losowy (poprzez rzucanie kośćmi lub tasowanie kart), i omawiamy gry z niedoskonałymi informacjami (takie jak poker i brydż, gdzie nie wszystkie karty są widoczne dla wszystkich graczy).

Wyszukiwanie i gry przeciwników

Badamy środowiska, w których inni agenci spiskują przeciwko nam. W tym rozdziale omówimy środowiska konkurencyjne, w których dwóch lub więcej agentów ma sprzeczne cele, co powoduje problemy z wyszukiwaniem przeciwników. Zamiast zajmować się chaosem potyczek w prawdziwym świecie, skoncentrujemy się na grach, takich jak szachy, Go i poker. Dla badaczy sztucznej inteligencji uproszczona natura tych gier jest plusem: stan gry jest łatwy do przedstawienia, a agenci są zwykle ograniczeni do niewielkiej liczby działań, których efekty są określone przez precyzyjne reguły. Gry fizyczne, takie jak krokiet czy hokej, mają bardziej skomplikowane opisy, większy zakres możliwych akcji i raczej nieprecyzyjne reguły określające legalność działań. Z wyjątkiem robotów piłkarskich, te fizyczne gry nie wzbudziły dużego zainteresowania społeczności AI.

Streszczenie

Zbadaliśmy algorytmy wyszukiwania problemów w środowiskach częściowo obserwowalnych, niedeterministycznych, nieznanych i ciągłych.

* Lokalne metody wyszukiwania, takie jak wspinaczka górska, przechowują w pamięci tylko niewielką liczbę stanów. Zostały one zastosowane w problemach optymalizacyjnych, gdzie ideą jest znalezienie stanu o wysokiej punktacji, bez martwienia się o ścieżkę do tego stanu. Opracowano kilka stochastycznych algorytmów wyszukiwania lokalnego, w tym symulowane wyżarzanie, które zwraca optymalne rozwiązania przy odpowiednim harmonogramie chłodzenia.

* Wiele lokalnych metod wyszukiwania stosuje się również do problemów w przestrzeniach ciągłych. Programowanie liniowe i zagadnienia optymalizacji wypukłej podlegają pewnym ograniczeniom dotyczącym kształtu przestrzeni stanów i charakteru funkcji celu oraz dopuszczają algorytmy wielomianowe, które często są niezwykle wydajne w praktyce. W przypadku niektórych matematycznie dobrze sformułowanych problemów możemy znaleźć maksimum za pomocą rachunku różniczkowego, aby znaleźć, gdzie gradient wynosi zero; w przypadku innych problemów musimy zadowolić się gradientem empirycznym, który mierzy różnicę sprawności między dwoma pobliskimi punktami.

* Algorytm ewolucyjny to stochastyczne poszukiwanie wspinaczki, w którym utrzymywana jest populacja stanów. Nowe stany generowane są przez mutację oraz przez crossover, który łączy pary stanów.

* W środowiskach niedeterministycznych agenci mogą zastosować wyszukiwanie AND-OR, aby wygenerować plany warunkowe, które osiągną cel, niezależnie od tego, jakie wyniki wystąpią podczas wykonywania.

* Gdy środowisko jest częściowo obserwowalne, stan przekonań reprezentuje zestaw możliwych stanów, w których może znajdować się agent. * Standardowe algorytmy wyszukiwania można zastosować bezpośrednio do przestrzeni stanów przekonań, aby rozwiązać problemy bezczujnikowe, a wyszukiwanie stanów przekonań AND–LUB potrafi rozwiązywać ogólne, częściowo obserwowalne problemy. Algorytmy przyrostowe, które konstruują rozwiązania stan po stanie w stanie przekonań, są często bardziej wydajne.

* Problemy z eksploracją pojawiają się, gdy agent nie ma pojęcia o stanach i działaniach swojego otoczenia. W środowiskach, w których można bezpiecznie eksplorować, agenci wyszukiwania online mogą zbudować mapę i znaleźć cel, jeśli taki istnieje. Aktualizacja szacunków heurystycznych na podstawie doświadczenia zapewnia skuteczną metodę ucieczki od lokalnych minimów.

Nauka w wyszukiwaniu online

Początkowa ignorancja agentów wyszukiwania online daje kilka możliwości uczenia się. Po pierwsze, agenci uczą się „mapy” środowiska – a dokładniej wyniku każdego działania w każdym stanie – po prostu przez rejestrowanie każdego ze swoich doświadczeń. Po drugie, lokalni agenci wyszukiwania uzyskują dokładniejsze oszacowania kosztów każdego stanu za pomocą lokalnych reguł aktualizacji, jak w LRTA*. Pokazujemy, że te aktualizacje ostatecznie zbiegają się do dokładnych wartości dla każdego stanu, pod warunkiem, że agent we właściwy sposób eksploruje przestrzeń stanów. Gdy znane są dokładne wartości, optymalne decyzje można podejmować po prostu, przechodząc do następcy o najniższych kosztach — to znaczy, że czysta wspinaczka górska jest wówczas optymalną strategią. Jeśli zastosowałeś się do naszej sugestii, aby prześledzić zachowanie ONLINE-DFS-AGENT w środowisku z rysunku 4.19, zauważysz, że agent nie jest zbyt jasny. Na przykład, po zobaczeniu, że akcja W górę przechodzi od (1,1) do (1,2), agent nadal nie ma pojęcia, że ​​akcja W dół wraca do (1,1) lub że akcja W górę również przechodzi od (2,1) do (2,2), od (2,2) do (2,3) i tak dalej. Ogólnie rzecz biorąc, chcielibyśmy, aby agent dowiedział się, że Up zwiększa współrzędną -, chyba że na drodze jest ściana, że ​​Down ją zmniejsza i tak dalej. Aby tak się stało, potrzebujemy dwóch rzeczy. Po pierwsze, potrzebujemy formalnej i wyraźnie manipulowalnej reprezentacji tego rodzaju ogólnych reguł; do tej pory ukrywaliśmy informacje w czarnej skrzynce zwanej funkcją RESULT. Temu zagadnieniu poświęcone są rozdziały od 8 do 11. Po drugie, potrzebujemy algorytmów, które potrafią skonstruować odpowiednie reguły ogólne na podstawie konkretnych obserwacji dokonanych przez agenta. Zostały one omówione później. Jeśli przewidujemy, że będziemy wezwani do rozwiązania wielu podobnych problemów w przyszłości, warto zainwestować czas (i pamięć), aby ułatwić te przyszłe poszukiwania.

Można to zrobić na kilka sposobów, z których wszystkie należą do kategorii wyszukiwania przyrostowego. Moglibyśmy zachować drzewo wyszukiwania w pamięci i ponownie wykorzystać jego niezmienione części w nowym problemie. Moglibyśmy zachować heurystyczne wartości h i aktualizować je w miarę zdobywania nowych informacji — albo dlatego, że świat się zmienił, albo dlatego, że obliczyliśmy lepsze oszacowanie. Lub możemy zachować wartości g najlepszej ścieżki, używając ich do złożenia nowego rozwiązania i aktualizując je, gdy świat się zmieni.