Teoria logiki i wyszukiwania heurystyczne

Tuż przed warsztatami w Dartmouth Newell, Shaw i Simon mieli zaprogramował wersję LT na komputerze w firmie RAND Corporation o nazwie JOHNNIAC (nazwany na cześć Johna von Neumanna). Późniejsze artykuły opisywały, w jaki sposób udowodniono niektóre twierdzenia w logice symbolicznej, które zostały udowodnione przez Russella i Whitehead w tomie I ich klasycznej pracy, Principia Mathematica. LT pracował nad transformacjami pięciu aksjomatów logiki zdaniowej Russella i Whiteheada, reprezentowanych dla komputera przez "struktury symboli", aż do wytworzenia struktury odpowiadającej twierdzeniu, które ma zostać udowodnione. Ponieważ istnieje wiele różnych transformacji, które można wykonać, znalezienie odpowiednich do udowodnienia danego twierdzenia wiąże się z tym, co ludzie informatyki nazywają "procesem wyszukiwania". Aby opisać działanie LT i innych symbolicznych programów AI, muszę najpierw wyjaśnić, co należy rozumieć przez "strukturę symboli", a co przez "ich przekształcanie". W komputerze symbole można łączyć w listy, takie jak (A; 7; Q). Symbole i listy symboli to najprostsze rodzaje struktur symboli. Bardziej złożone struktury składają się z list symboli, takich jak ((B; 3); (A; 7; Q)), oraz list list list symboli i tak dalej. Ponieważ takie listy list itp. Mogą być dość złożone, nazywane są "strukturami". Można pisać programy komputerowe, które przekształcają struktury symboli w inne struktury symboli. Na przykład za pomocą odpowiedniego programu struktura "(suma siedmiu i pięciu)" może zostać przekształcona w strukturę "(7 + 5)", którą można przekształcić w symbol "12." Przekształcanie struktur symboli i poszukiwanie odpowiedniej sekwencji rozwiązywania problemów leży u podstaw pomysłów Newella i Simona dotyczących mechanizacji inteligencji. W późniejszym artykule (tym, który dostali przy okazji otrzymania prestiżowej nagrody Turinga), podsumowali proces w następujący sposób:

Rozwiązania problemów są reprezentowane przez struktury symboli. Za fizyczny system symboli ćwiczy inteligencję w rozwiązywaniu problemów przez wyszukiwanie {to znaczy, generując i stopniowo modyfikując struktury symboli, aż wytworzy strukturę rozwiązania.

…

Stwierdzenie problemu oznacza wyznaczenie (1) testu dla klasy struktur symboli (rozwiązania problemu) i (2) generatora struktur symboli (potencjalne rozwiązania). Aby rozwiązać problem, należy wygenerować strukturę za pomocą (2), która spełnia test (1).

Zrozumienie szczegółowo, w jaki sposób sam LT użył struktur symboli i ich transformacji do udowodnienia twierdzeń, wymagałoby matematycznego i logicznego tła. Proces ten jest łatwiejszy do wyjaśnienia przy użyciu jednego z ulubionych "problemów z zabawkami" AI - "piętnastu zagadek". Piętnaście łamigłówek jest jednym z kilku rodzajów łamigłówek. Problem polega na przekształceniu tablicy płytek z początkowej konfiguracji w "cel" konfiguracji przez kolejne ruchy płytki do sąsiedniej pustej komórki.

Użyję prostszej wersji układanki {takiej, która używa tablicy 3 x 3 osiem przesuwanych płytek zamiast układu 4 x 4. (Badacze AI eksperymentowali również z programami do rozwiązywania większych wersji układanki, takimi jak 5 x 5 i 6 x 6.). Załóżmy, że chcieliśmy przenieść płytki z ich konfiguracji po lewej stronie na te po prawej. Zgodnie z podejściem Newella i Simona musimy najpierw przedstawić pozycje kafelków dla komputera za pomocą struktur symboli, z którymi komputer może sobie poradzić. Będę reprezentować pozycję początkową według następującej struktury, która jest listą trzech podlist:

((2; 8; 3); (1; 6; 4); (7; B; 5)):

Pierwsza lista podrzędna, a mianowicie (2; 8; 3), wymienia osoby zajmujące pierwszy rząd tablicy układanek i tak dalej. B oznacza pustą komórkę w środku trzeciego rzędu. W ten sam sposób konfiguracja celu jest reprezentowana przez następującą strukturę:

((1; 2; 3); (8; B; 4); (7; 6; 5)):

Następnie musimy pokazać, w jaki sposób komputer może przekształcać struktury, które skonfigurowaliśmy w sposób, który odpowiada dozwolonym ruchom układanki. Zauważ, że kiedy kafelek jest przenoszony, zamienia miejscami pustą komórkę; to znaczy, że pusta komórka również się porusza. Pusta komórka może się poruszać w obrębie wiersza lub zmieniać wiersze. Odpowiednio do tych ruchów pustej komórki, gdy kafelek przesuwa się w swoim rzędzie, B zamienia miejsca z liczbą na lewo na liście (jeśli jest) lub na prawo (jeśli jest). Komputer może łatwo wykonać dowolną z tych transformacji. Gdy pusta komórka przesuwa się w górę lub w dół, B zamienia miejsca z liczbą na odpowiedniej pozycji na liście po lewej stronie (jeśli istnieje) lub na liście po prawej stronie (jeśli istnieje). Przekształceń tych można również dokonać dość łatwo za pomocą programu komputerowego. Stosując podejście Newella i Simona, zaczynamy od struktury symboli reprezentującej początkową konfigurację ośmiu puzzli i stosujemy dozwolone transformacje, aż do osiągnięcia celu. Istnieją trzy transformacje początkowej struktury symboli. Tworzą one następujące struktury:

((2; 8; 3); (1; 6; 4); (B; 7; 5));

((2; 8; 3); (1; 6; 4); (7; 5; B));

i

((2; 8; 3); (1; B; 4); (7; 6; 5)):

Żadne z nich nie reprezentuje konfiguracji celu, dlatego nadal stosujemy transformacje do każdego z nich i tak dalej, aż do osiągnięcia struktury reprezentującej cel. My (i komputer) możemy śledzić dokonane transformacje, ustawiając je w strukturze przypominającej treble, takiej jak pokazano w



(Groty strzałek na obu końcach linii reprezentujących transformacje wskazują, że każda transformacja jest odwracalna)

Ta wersja ósemki jest stosunkowo prosta, więc nie trzeba próbować wielu transformacji, zanim cel zostanie osiągnięty. Zazwyczaj jednak (szczególnie w większych wersjach układanki) komputer byłby zalany przez wszystkie możliwe transformacje {tak bardzo, że nigdy nie generowałby wyrażenia celu. Aby ograniczyć coś, co później nazwano "eksplozją kombinatoryczną" transformacji, Newell i Simon zasugerowali użycie "heurystyki" do wygenerowania tylko tych transformacji, które prawdopodobnie są na drodze do rozwiązania. W jednym ze swoich artykułów na temat LT napisali: "proces, który może rozwiązać problem, ale nie daje żadnych gwarancji, nazywa się to heurystyką dla tego problemu". Zamiast ślepo uderzać we wszystkie strony w poszukiwaniu dowodu, LT użył wyszukiwania kierowanego heurystyką lub \ heurystycznego wyszukiwania. "Zwykle, tak jak w przypadku LT, nie ma gwarancji, że wyszukiwanie heurystyczne zakończy się powodzeniem, ale kiedy jest skuteczny (i to dość często) eliminuje wiele innych bezowocnych poszukiwań . Poszukiwanie rozwiązania problemu złożonego z ośmiu puzzli polega na powiększeniu drzewa struktur symboli poprzez zastosowanie transformacji do "liści" drzewa, a tym samym przedłużenie Aby ograniczyć wzrost drzewa, powinniśmy użyć heurystyki, aby zastosować transformacje tylko do tych liści, które są na drodze do rozwiązania. Jednym z takich heurystyk może być zastosowanie transformacji do tego liścia z najmniejszą liczbą płytek pozycji w porównaniu do konfiguracji bramkowej. Ponieważ problemy z przesuwanymi płytkami zostały dokładnie zbadane, istnieje szereg heurystyk, które okazały się przydatne - te znacznie lepsze niż prosta liczba płytek z pozycją poza pozycją, którą właśnie zasugerowałem. Wykorzystanie heurystyki kluczem do rozwiązania problemu stało się głównym tematem sztucznej inteligencji, co dało początek tak zwanemu programowaniu heurystycznemu. "Być może idea poszukiwania heurystycznego była już w powietrzu" w czasie warsztatów w Dartmouth. Było to dorozumiane we wcześniejszej pracy Claude'a Shannona. W marcu 1950 r. Zapalony szachista Shannon opublikował artykuł proponujący pomysły na zaprogramowanie komputera do gry w szachy. W swoim artykule Shannon rozróżniał strategie nazywane "typem A" i "typem B". Strategie typu A badają każdą możliwą kombinację ruchów, podczas gdy strategie typu B wykorzystują specjalistyczną wiedzę o szachach, aby skupić się na liniach gry, które są uważane za najbardziej produktywne. Strategie typu B zależały od tego, co Newell i Simon nazwali później heurystyką. A Minsky jest cytowany jako "…. Już uważałem pomysł poszukiwań heurystycznych za oczywisty i naturalny, tak więc teoretyk logiki nie był dla mnie imponujący". Dość wcześnie w AI stwierdzono, że sposób skonfigurowania problemu, jego "reprezentacja" ma kluczowe znaczenie dla jego rozwiązania. Jednym z przykładów wpływu reprezentacji na rozwiązywanie problemów jest John McCarthy i nazywa się to problemem "okaleczonej szachownicy". Oto problem: "Dwa szachownice po przeciwnych rogach są usuwane z szachownicy. Czy to możliwe aby pokryć pozostałe kwadraty domino? "(Domino to prostokątna płytka, która pokrywa dwa sąsiednie kwadraty.) Naiwnym sposobem poszukiwania rozwiązania byłoby próba umieszczenia domina na wszystkie możliwe sposoby nad szachownicą. Ale jeśli ktoś używa informacja, że szachownica składa się z 32 kwadratów jednego koloru i 32 innego koloru oraz, że przeciwległe narożne kwadraty są tego samego koloru, wtedy uświadomimy sobie, że okaleczona deska składa się z 30 kwadratów jednego koloru i 32 drugiego. domino obejmuje dwa kwadraty przeciwnych kolorów, nie ma sposobu, aby zestaw ich mógł pokryć pozostałe kolory. McCarthy był zainteresowany tym, czy ludzie mogą wymyślić "kreatywne" sposoby na ułożenie układanki, aby można ją było rozwiązać przez komputery wykorzystujące metody oparte na logicznej dedukcji. Kolejną klasyczną łamigłówką, która została wykorzystana do badania efektów różnych reprezentacji, jest problem "misjonarzy i kanibali": Trzej kanibale i trzej misjonarze muszą przekroczyć rzekę. Ich łódź może pomieścić tylko dwie osoby. Jeśli liczba kanibali przewyższy liczbę misjonarzy, po obu stronach rzeki, misjonarze po tej stronie zginą. Każdy misjonarz i każdy kanibal może wiosłować łodzią. Jak cała szóstka może bezpiecznie przeprawić przez rzekę? Większość ludzi nie ma problemów z sformułowaniem tej układanki jako problemu wyszukiwania, a rozwiązanie jest stosunkowo łatwe. Ale wymaga to jednego nieintuicyjnego kroku. Informatyk i badacz sztucznej inteligencji Saul Amarel (1928-2002) napisał obszerny artykuł analizujący tę łamigłówkę i różne jej rozszerzone wersje, w których może być różna liczba misjonarzy i kanibali. (Wydaje się, że wersje rozszerzone nie są takie proste.) Po przejściu z jednej reprezentacji do drugiej Amarel ostatecznie opracował reprezentację dla uogólnionej wersji problemu, którego rozwiązanie praktycznie nie wymagało wyszukiwania. Naukowcy zajmujący się sztuczną inteligencją wciąż badają, jak najlepiej przedstawiać problemy, a co najważniejsze, w jaki sposób zmusić systemy AI do stworzenia własnych reprezentacji.

Udowadnianie twierdzeń w geometrii

Nathan Rochester powrócił do IBM po warsztatach Dartmouth podekscytowanych dyskusjami, które prowadził z Marvinem Minsky′m na temat pomysłów Minsky′ego na temat możliwego programu komputerowego do dowodzenia twierdzeń w geometrii. Opisał te pomysły nowemu pracownikowi IBM, Herbowi Gelernterowi. Gelernter wkrótce rozpoczął projekt badawczy mający na celu opracowanie maszyny do dowodzenia twierdzeń geometrycznych. Przedstawił artykuł na temat pierwszej wersji swojego programu na konferencji w Paryżu w czerwcu 1959,8, potwierdzając, że sam projekt badawczy jest konsekwencją Letniego Projektu Badawczego Inteligencji Sztucznej Dartmouth z 1956 r., podczas którego M. L. Minsky wskazał potencjalną użyteczność schematu dla maszyny dowodzącej twierdzeń geometrycznych. Program Gelernter wykorzystał dwa ważne pomysły. Jednym z nich było jawne użycie subgoals (czasem nazywanych "rozumowaniem wstecznym lub "dziel i rządź"), a drugim było użycie diagramu do zamykania daremnych ścieżek wyszukiwania.

trategia nauczana w szkole średniej w celu udowodnienia twierdzenia z geometrii wiąże się z ustaleniem dodatkowych faktów geometrycznych, z których, jeśli to prawda, twierdzenie powstałoby natychmiast. Na przykład, aby udowodnić, że dwa kąty są równe, wystarczy wykazać, że odpowiadają one kątom dwóch "przystających" trójkątów. (Trójkąt jest zgodny z innym, jeśli można go przetłumaczyć i obrócić, a nawet obrócić, w taki sposób, aby dokładnie pasował do drugiego.) Tak więc pierwotny problem przekształca się w problem pokazania, że dwa trójkąty są przystające . Jednym ze sposobów (między innymi) pokazania, że dwa trójkąty są zgodne, jest pokazanie, że dwa odpowiadające boki i zamknięty kąt dwóch trójkątów mają te same rozmiary. Ten proces rozumowania wstecznego kończy się, gdy to, co pozostaje do wykazania, należy do przesłanek twierdzenia. Czytelnicy zaznajomieni z geometrią będą mogli podążać za ilustracyjnym przykładem pokazanym na rysunku.



Tam po lewej stronie otrzymujemy trójkąt ABC o boku AB równym boku AC i musimy udowodnić, że kąt ABC jest równy kątowi ACB. Trójkąt po prawej stronie to odwrócona wersja trójkąta ABC. Oto dowód: jeśli moglibyśmy udowodnić, że trójkąt ABC jest przystające do trójkąta , wówczas nastąpiłoby to twierdzenie, ponieważ dwa kąty są odpowiednimi kątami dwóch trójkątów. Te dwa trójkąty można udowodnić, że są zgodne, gdybyśmy mogli ustalić, że bok AB (trójkąta ABC) jest równy bokowi (trójkąta ) i ten bok AC (trójkąta ABC) jest równy bokowi (trójkąta ) i że kąt A (trójkąta ABC) jest równy kątowi A (trójkąta ). Ale przesłanki twierdzą, że bok AB jest równy bokowi AC, a te długości nie zmieniają się w trójkącie ipped-over. Podobnie, kąt A jest równy jego wersji ipped-over {więc mamy nasz dowód. Przed kontynuowaniem mojego opisu programu Gelerntera, krótka historia dygresja jest w porządku. Udowodnione właśnie twierdzenie o geometrii jest słynne {jest piątą propozycją w Księdze I Elementów Euklidesa. Ponieważ dowód twierdzenia Euklidesa był trudnym problemem dla początkujących, stał się znany jako most pons asinorum lub most głupców. "Dowód podany tutaj jest prostszy niż Euklidesa - jego wersję podał Pappus z Aleksandrii (około 290-350 lat) "Symulacja ręki" Minsky'ego programu do dowodzenia twierdzeń w geometrii, omówiona w Dartmouth, przyniosła ten właśnie dowód (pomijając to, co uważam za pomocny krok do przeskoczenia trójkąta). Minsky napisał

"W 1956 roku napisałem dwie notatki o ręcznie symulowanym programie do dowodzenia twierdzeń w geometrii. W pierwszej notatce procedura znalazła prosty dowód, że jeśli trójkąt ma dwa równe boki, to odpowiednie kąty są równe. zauważając, że trójkąt ABC przystaje do trójkąta CBA z powodu "boku-kąta-boku". Co ciekawe, znaleziono to po bardzo krótkim wyszukiwaniu {bo przecież nie było wiele rzeczy do zrobienia. może powiedzieć, że program był zbyt głupi, aby zrobić to, co ktoś mógłby zrobić, to znaczy pomyśleć: "Och, oba są tym samym trójkątem. Na pewno nic dobrego nie wyniknie z nadania mu dwóch różnych nazw. "(Program posiada zbiór heurystycznych metod dowodzenia twierdzeń podobnych do Euklidesa, a jednym z nich było to, że jeśli chcesz udowodnić, że dwa kąty są równe, pokaż, że są to odpowiadające sobie części przystających trójkątów. "Wtedy miał też kilka sposobów na zademonstrowanie zgodności. Nie było nic więcej w tym pierwszym niż symulacja.) Ale nigdzie nie mogę znaleźć tej notatki. "

Jak powiedział Minsky, jest to bardzo łatwy problem dla komputera. Program Gelernter okazał się znacznie trudniejszymi twierdzeniami, a do tego jego użycie diagramu było niezbędne. Program dosłownie nie narysował i nie spojrzał na schemat. Zamiast tego, jak napisał Gelernter,

"[Program] jest dostarczany ze schematem w postaci listy możliwych współrzędnych dla punktów wymienionych w twierdzeniu. Tej liście punktów towarzyszy kolejna lista określająca punkty połączone segmentami. Współrzędne są wybierane, aby odzwierciedlić największa możliwa ogólność w postaciach. "

Na przykład punkty wymienione w problemie dotyczącym udowodnienia równości dwóch kątów są wierzchołkami trójkąta ABC, a mianowicie punkty A, B i C. Wybrano współrzędne dla każdego z tych punktów i zadbano o to, aby upewnić się, że współrzędne te nie spełniają żadnych specjalnych nienazwanych właściwości. Program Gelerntera działał, konfigurując podzadania i podzadania, takie jak te, których użyłem w podanym przykładzie, a następnie szukał łańcucha tych zakończonych podzadaniami, które można byłoby ustalić bezpośrednio z lokalu. Jednak zanim program został wybrany do pracy z jakimkolwiek podzadaniem, najpierw przetestowano go, aby sprawdzić, czy jest on utrzymany na schemacie. Jeśli tak się stanie, może być możliwe do udowodnienia i dlatego może być uważany za możliwą drogę do dowodu. Ale gdyby nie było tego na schemacie, nie mogłoby być prawdą. W ten sposób można go wyeliminować z dalszych rozważań, tym samym "przycinając" drzewo wyszukiwania i oszczędzając, co z pewnością byłoby bezowocnym wysiłkiem. Późniejsze prace w AI wykorzystywałyby również tego rodzaju "semantyczne" informacje. Widzimy podobieństwa między strategiami stosowanymi w programie geometrii a strategiami stosowanymi przez ludzi podczas rozwiązywania problemów. Powszechne jest dla nas działanie wstecz - przekształcanie trudnego problemu w podproblemy i te w podproblemy i tak dalej, aż w końcu problemy są trywialne. Kiedy podproblem składa się z wielu części, wiemy, że musimy rozwiązać je wszystkie. Rozumiemy również, kiedy proponowany podproblem jest ewidentnie niemożliwy i dlatego możemy go odrzucić. Następny program, który opisuję, opierał się wyraźnie na tym, co jego autorzy uważali za ludzkie strategie rozwiązywania problemów.

Ogólne rozwiązanie problemu

Na tej samej konferencji w Paryżu w 1959 r., Na której Gelernter przedstawił swój program, Allen Newell, J.C. Shaw i Herb Simon napisali artykuł opisujący ich ostatnie prace nad mechanizacją rozwiązywania problemów. Ich program, który nazwali "General Problem Solver (GPS)", było ucieleśnieniem ich pomysłów na temat rozwiązywania problemów przez ludzi. Rzeczywiście twierdzili, że sam program był teorią ludzkich zachowań związanych z rozwiązywaniem problemów. Newell i Simon byli wśród tych, którzy byli równie zainteresowani (być może nawet bardziej zainteresowani) wyjaśnianiem inteligentnego zachowania ludzi podczas budowania inteligentnej maszyny Napisali

"Często twierdzi się, że należy wytyczyć ostrożną granicę między próbą wykonania na maszynach tych samych zadań, które wykonują ludzie, a próbą symulacji procesów, których ludzie faktycznie używają do osiągnięcia tych celów zadania ... GPS maksymalnie myli oba podejścia - z obopólną korzyścią. "

GPS był rezultatem wcześniejszej pracy nad teorią logiki, ponieważ polegał na manipulowaniu strukturami symboli (w co, jak wierzyli, ludzie również). Ale GPS miał ważny dodatkowy mechanizm wśród swoich strategii manipulacji symbolami. Podobnie jak program geometrii Gelerntera, GPS przekształcił problemy w podproblemy i tak dalej. Innowacja GPS polegała na obliczeniu "różnicy" między problemem do rozwiązania (przedstawionym jako struktura symbolu) a tym, co już było znane lub podane (przedstawione również jako struktura symbolu). Następnie program próbował zmniejszyć tę różnicę poprzez zastosowanie operatora manipulującego symbolami (znanego jako istotny dla tej różnicy) do początkowej struktury symboli. Newell i Simon nazywali tę strategię "oznacza - kończy analizę." (Należy zwrócić uwagę na podobieństwo do systemy kontroli sprzężenia zwrotnego, które nieustannie starają się zmniejszyć różnicę między bieżącym ustawieniem a pożądanym ustawieniem.) Aby to zrobić, musiałby wykazać, że spełniono warunki zastosowania operatora {podproblem. Następnie program uruchomił kolejną wersję pracować nad tym podproblemem, szukam różnicy i tak dalej. Załóżmy na przykład, że celem jest, aby Sammy był w szkole, gdy wiadomo, że Sammy jest w domu. GPS oblicza różnicę, a mianowicie, że Sammy jest w niewłaściwym miejscu i szuka operatora odpowiedniego do zmniejszenia tej różnicy, a mianowicie: kierowanie Sammy do szkoły. Aby prowadzić Sammy′go do szkoły, samochód musi być sprawny. Aby problem był interesujący, przypuszczamy, że akumulator samochodu jest rozładowany, więc GPS nie może zastosować operatora samochodu, ponieważ ten operator wymaga działającej baterii. Uzyskanie działającej baterii jest podproblemem, do którego GPS może zastosować własną wersję. Ta "niższa" wersja GPS oblicza różnicę, a mianowicie zapotrzebowanie na działającą baterię, i określa operatora, a mianowicie , wzywając mechanika, by przyszedł i zainstalował nową baterię. Aby zadzwonić do mechanika, trzeba mieć numer telefonu (i załóżmy, że go mamy), więc GPS stosuje operatora mechanika wywoływania, co powoduje, że mechanik nadchodzi, aby zainstalować nową baterię. Niższa wersja GPS z powodzeniem rozwiązała problem, więc nadrzędny GPS może teraz wznowić {zauważając, że warunek prowadzenia samochodu, a mianowicie posiadanie działającego akumulatora, jest spełniony. Tak więc GPS stosuje tego operatora, Sammy dostaje się do szkoły, a pierwotny problem został rozwiązany. (Ten przykład ilustruje ogólne działanie GPS. Prawdziwy, wykorzystujący rzeczywiste struktury symboli, różnice i operatorów z ich warunkami itd. Byłby uciążliwy, ale nie bardziej odkrywczy.) Gdy GPS działa na podproblemy, uruchamiając nową wersję siebie , wykorzystuje bardzo ważny pomysł w informatyce (i matematyce) o nazwie "rekurencja". Być może znasz pomysł, że programiści komputerowi organizują złożone programy w sposób hierarchiczny. Oznacza to, że programy główne ponownie uruchamiają podprogramy, które mogą ponownie uruchamiać podprogramy i tak dalej. Kiedy program główny "wywołuje" podprogram, program główny zawiesza się, dopóki podprogram nie dokończy tego, co powinien zrobić (ewentualnie przekazując dane do programu głównego), a następnie program główny wznowi pracę. W sztucznej inteligencji (a także w innych aplikacjach) często program główny wywołuje swoją wersję - uważając, aby nowa wersja działała na prostszym problemie, aby uniknąć niekończących się powtórzeń i "zapętlania". Samo wywołanie programu nazywa się "rekurencją". Czy ludzie używają podprogramów i rekurencji we własnym myśleniu? Całkiem możliwe, ale ich zdolność do przypominania sobie, jak wznowić to, co robił pewien proces myślowy wyższego poziomu, gdy proces ten rozpoczyna łańcuch procesów niższego poziomu, jest z pewnością ograniczona. Nie wierzę, że GPS próbował naśladować to ograniczenie ludzkiego myślenia. Newell i Simon wierzyli, że metody stosowane przez GPS mogą być wykorzystane do rozwiązania wielu różnych problemów, tworząc w ten sposób pojęcie "ogólne". Aby zastosować go do konkretnego problemu, należałoby dostarczyć "tabelę różnic" dla tego problemu. W tabeli wymieniono wszystkie możliwe różnice, które mogą się pojawić, i dopasowano je do operatorów, co w przypadku tego problemu zmniejszyłoby odpowiadające różnice. GPS został w rzeczywistości zastosowany do szeregu różnych problemów logicznych i zagadek i zainspirował późniejsze prace zarówno w zakresie sztucznej inteligencji, jak i kognitywistyki. Jego długowieczność jako samego programu rozwiązywania problemów i jako teorii rozwiązywania problemów ludzkich była jednak krótka i przetrwała tylko dzięki różnym potomkom (o których więcej omówimy później). W wielu programach AI opracowanych na początku lat 60. XX wieku zastosowano procedury wyszukiwania heurystycznego. Na przykład inny doktor Minsky'ego studenci, James Slagle, zaprogramowali system o nazwie SAINT, który może rozwiązywać problemy rachunku różniczkowego, odpowiednio reprezentowanego jako struktury symboli. Rozwiązano 52 z 54 problemów zaczerpniętych z rachunku pierwszego stopnia MIT. Wiele programów heurystycznych wykorzystano w programach, które mogły grać w gry planszowe, a teraz zajmę się nimi.

Programy gier

Wspomniałem już o niektórych wczesnych pracach Shannona i Newella, Shawa i Simona nad programami do gry w szachy. Gra w doskonałe szachy wymaga inteligencji. W rzeczywistości Newell, Shaw i Simon napisali, że "jeśli można opracować udaną maszynę do gry w szachy, wydaje się, że przeniknął do rdzenia ludzkich wysiłków intelektualnych". Myślenie o programach do gry w szachy wraca przynajmniej do Babbage. Według Murraya Campbella, badacza IBM, który pomógł zaprojektować mistrzowski program do gry w szachy (o którym wspomnę później), książka Babbag′a z 1845 r., życie filozofa, zawiera pierwszą udokumentowaną dyskusję na temat programowania komputera do gry w szachy . Konrad Zuse, niemiecki projektant i konstruktor komputerów Z1 i Z3, wykorzystał swój język programowania o nazwie Plankalkul do zaprojektowania programu do gry w szachy na początku lat 40. XX wieku. W 1946 r. Turing wspomniał o komputerze pokazującym "inteligencję", którego paradygmatem jest gra w szachy. W 1948 r. Turing i jego były kolega ze studiów, D. G. Champernowne, zaczęli pisać program do gry w szachy w 1952 r., nie mając komputera wystarczająco mocnego, aby uruchomić program, Turing grał w grę, w której symulował komputer, zabierając około pół godziny na ruch. (Gra została nagrana. Można ją zobaczyć na stronie :
http://www.chessgames.com/perl/chessgamegid=1356927.
Program przegrał z kolegą Turinga, Alickem Glennie; mówi się jednak, że program wygrał mecz z żoną Champernowne. Po tych wczesnych programach prace nad komputerowymi programami szachowymi były kontynuowane, z wysiłkiem od początku do końca, przez następne kilka dekad. Według Johna McCarthy'ego Alexander Kronrod, rosyjski badacz sztucznej inteligencji, powiedział: "Szachy to Drosophila AI" - co oznacza, że służy lepiej niż bardziej otwarte zadania intelektualne jako przydatny okaz laboratoryjny do badań. Jak powiedział Minsky:

"Nie chodzi o to, że gry i problemy matematyczne są wybierane, ponieważ są jasne i proste; raczej dlatego, że dają one najmniejszym strukturom początkowym największą złożoność, dzięki czemu można zaangażować się w naprawdę groźne sytuacje po względnie minimalnym przejściu na programowanie "

. Szachy stanowią bardzo trudne problemy dla AI i dopiero w połowie lat 60. pojawiły się pierwsze kompetentne programy szachowe. Bardziej wczesny sukces osiągnięto jednak w przypadku prostszej gry w warcaby (lub warcabów, jak ta gra znana jest w brytyjskim angielskim). Arthur Samuel zaczął myśleć o programowaniu komputera do gry w warcaby pod koniec lat 40. na University of Illinois, gdzie był profesorem inżynierii elektrycznej. W 1949 roku dołączył do laboratorium Poughkeepsie Laboratory w IBM i ukończył swój pierwszy program sprawdzania działania w 1952 roku na komputerze IBM 701. Program został przekodowany dla IBM 704 w 1954 r. Według Johna McCarthy′ego, "Thomas J. Watson Sr., założyciel i prezes IBM, zauważył, że demonstracja [programu Samuela] podniesie cenę akcji IBM o 15 punktów. Tak. ". [Najwyraźniej Samuel nie był pierwszym, który napisał program do gry w warcaby. Według Encyklopedii Brittanica, Online," Pierwszy udany program sztucznej inteligencji został napisany w 1951 r. przez Christophera Stracheya, późniejszego dyrektora Programming Research Group w University of Oxford. Program warcabów (szkiców) Stracheya działał na komputerze Ferranti Mark I na University of Manchester, Anglia. Do lata 1952 r. Program ten mógł zagrać w pełną grę w warcaby z rozsądną prędkością"] .Głównym zainteresowaniem Samuela w programowaniu komputera do grania w warcaby było zbadanie, jak zdobyć komputer do nauki. Uznanie" czasochłonnej i kosztownej procedury " "zaangażowany w programowanie, Samuel napisał:" Programowanie komputerów w celu uczenia się na podstawie doświadczenia powinno ostatecznie wyeliminować potrzebę znacznej części tych szczegółowych prac programistycznych. "Wysiłki Samuela były jednymi z pierwszych, które miały stać się bardzo ważną częścią sztucznej inteligencji, a mianowicie: "uczenie maszynowe". Jego pierwszy program obejmujący uczenie się został ukończony w 1955 r. i zademonstrowany w telewizji 24 lutego 1956 r. Przed opisaniem jego metod uczenia się opiszę ogólnie, w jaki sposób Program Samuela wybrał ruchy. Technika ta jest bardzo podobna do tego, w jaki sposób wybrano ruchy w ośmiu puzzlach opisanych wcześniej. Z wyjątkiem teraz należy przewidzieć fakt, że przeciwnik również wybiera ruchy. Ponownie powstaje drzewo wyrażeń symbolicznych reprezentujących pozycje na planszy. Począwszy od konfiguracji początkowej, rozważane są wszystkie możliwe ruchy programu (przy założeniu, że program porusza się jako pierwszy). Rezultatem są wszystkie możliwe wynikające z tego konfiguracje rozgałęziające się od konfiguracji początkowej. Następnie z każdego z nich brane są pod uwagę wszystkie możliwe ruchy przeciwnika - w wyniku czego powstaje więcej gałęzi i tak dalej. Gdyby takie drzewo można było zbudować dla całej gry, ruch wygrywający można by obliczyć na podstawie badania drzewa. Niestety oszacowano, że istnieje około 5 x 10²⁰ możliwych pozycji kontrolerów. Wiodący ekspert w programowaniu komputerów do grania w gry, Jonathan Schaeffer, był w stanie "rozwiązać" warcaby (pokazując, że optymalna gra obu graczy kończy się remisem) poprzez czasochłonną analizę około 10¹⁴ pozycji. Napisał mi, że "Był to wynik licznych ulepszeń ukierunkowanych na wyszukiwanie w tych częściach przestrzeni wyszukiwania, w których najprawdopodobniej znaleźliśmy to, czego potrzebowaliśmy". Program Samuela mógł koniecznie skonstruować tylko część drzewa - to znaczy, mógł patrzeć tylko o kilka ruchów do przodu. To, jak daleko to wyglądało, wzdłuż różnych gałęzi, zależało od wielu czynników, które nie muszą nas tutaj dotyczyć. (Dotyczyły one takich kwestii, czy możliwe było natychmiastowe złapanie). Typowe jest patrzenie w przyszłość z wykorzystaniem trzech ruchów, chociaż niektóre gałęzie mogą być eksplorowane (rzadko) na głębokość aż dziesięciu ruchów. Schemat z pracy Samuela przedstawia ogólny pomysł. Samuel powiedział, że "faktyczne rozgałęzienia są znacznie liczniejsze". Jak więc program wybiera ruch z tak niekompletnego drzewa? Problem ten napotykają wszystkie programy do grania i wszystkie wykorzystują metody polegające na obliczaniu wyniku dla pozycji na końcach lub "liściach" drzewa (to znaczy liści niekompletnego drzewa wygenerowanych przez program ), a następnie "migruje" ten wynik z powrotem do pozycji wynikających z ruchów z bieżącej pozycji. Najpierw opiszę, jak obliczyć wynik, a następnie jak go przenieść z powrotem, a następnie w jaki sposób Samuel zastosował metody uczenia się w celu poprawy wydajności. Program Samuela najpierw obliczył punkty, które mają być przyznane pozycjom na liściach drzewa na podstawie ich ogólnej \ dobroci "z punktu widzenia programu. Wśród cech, które przyczyniły się do punktów, była względna przewaga w kawałkach (królowie byli warti więcej niż zwykłe elementy), ogólna "mobilność" (swoboda poruszania się) elementów programu i sterowanie centralne (program miał dostęp do 38 takich funkcji, ale wykorzystał tylko 16 z nich w tym samym czasie.) Punkty wniesione przez każda cecha została następnie pomnożona przez "wagę" (odzwierciedlając względną ważność odpowiadającej jej cechy), a wynik został zsumowany, aby dać ogólny wynik dla pozycji. Zaczynając od pozycji bezpośrednio powyżej pozycji na końcu drzewa, jeśli jest to pozycja, dla której nadeszła kolej na program, możemy założyć, że program chciałby przejść do tej pozycji z najwyższym wynikiem, aby najwyższy wynik został przeniesiony z powrotem do tej pozycji "bezpośrednio powyżej". Jeśli jednak , jest to pozycja, z której kolej ruchu przeciwnika, zakładamy, że przeciwnik chciałby przejść do tej pozycji z najniższym wynikiem. W takim przypadku najniższy wynik jest migrowany z powrotem do tego miejsca bezpośrednio powyżej pozycji. Ta naprzemiennie "najwyższa - najniższa" strategia migracji jest kontynuowana aż do końca drzewa i nazywa się strategią minimax. [Prosta modyfikacja tej strategii, zwana procedurą "alpha -beta", służy do wnioskowania ( poprawnie) z już migrowanych wyników, że niektóre gałęzie nie muszą być wcale badane {umożliwiając w ten sposób głębsze zbadanie innych gałęzi. Różni się opinie na temat tego, kto pierwszy pomyślał o tej ważnej modyfikacji. McCarthy, Newell i Simon wszyscy roszczą o uznanie. Samuel powiedział mi, że go użył, ale że jest zbyt oczywiste, aby o nim pisać.] Jeśli założymy, że koleją programu jest przejście z bieżącej pozycji i że wyniki zostały już przeniesione z powrotem do pozycji tuż pod nią, program przesunąłby się na tę pozycję z najwyższym wynikiem. A potem gra będzie kontynuowana, gdy przeciwnik wykona ruch, kolejny etap wzrostu drzewa, obliczania wyniku i migracji itd., Dopóki jedna strona nie wygra lub przegra. Jedna z metod uczenia się w programie Samuela dostosowała wartości wag stosowanych przez system punktacji. (Przypomnijmy, że korekty masy w Pandemonium i sieciach neuronowych były sposobami uczenia się tych systemów). Wagi zostały dostosowane tak, aby wynik pozycji planszy (obliczony na podstawie sumy ważonych ocen cech) zbliżył się do wartości f migrowany wynik po zakończeniu wyszukiwania. Na przykład, jeśli wynik początkowej pozycji został obliczony (przy użyciu wag przed dostosowaniem) jako 22, a migrowany wynik tej pozycji po wyszukiwaniu wynosił 30, to wagi użyte do obliczenia wyniku początkowej pozycji zostały dostosowane w sposób, dzięki któremu nowy wynik (przy użyciu skorygowanej wartości wag) został przybliżony do 30, powiedzmy 27. (Ta technika zapowiedziała bardzo ważną metodę uczenia się, sformułowaną później przez Richarda Suttona, zwaną "uczeniem się różnic czasowych"). Pomysł tutaj migracja wyniku, zależnie od tego, jak wyglądało w przyszłości, była lepsza niż pierwotna ocena. W ten sposób poprawiono procedurę szacowania, dzięki czemu uzyskano wartości bardziej spójne z wynikiem "wybiegającym w przyszłość". Samuel zastosował także inną metodę zwaną "rote learning", w której program zapisywał różne pozycje planszy i migrowane wyniki napotkane podczas rzeczywistej gry. Następnie, pod koniec wyszukiwania, czy napotkana pozycja liścia była taka sama jak jedna z tych zapisanych pozycji , jego wynik był już znany (i nie musiałby być obliczany przy użyciu wag i cech). Znany wynik, oparty na poprzednim badaniu, prawdopodobnie byłby lepszym wskaźnikiem wartości pozycji niż wynik obliczony. Program Samuela również skorzystał z użycia \ book games, które są zapisami gier głównych graczy w warcaby. Komentując pracę Samuela, John McCarthy napisał, że gracze w warcaby mają wiele gier z komentarzami, w których dobre ruchy odróżniają się od złych. Program edukacyjny Samuela wykorzystał Przewodnik po warcabach Lee, aby dostosować kryteria wyboru ruchów, tak aby program wybrał te dobrze przemyślane przez ekspertów sprawdzania tak często, jak to możliwe. " Program Samuela grał bardzo dobrze w warcaby, a latem 1962 roku pokonał Roberta Nealeya, mistrza niewidomych warcabów z Connecticut. (Możesz zobaczyć grę rozgrywaną pomiędzy Mr. Nealey a programem Samuela na stronie http: // www. Erz.ch/samuel.htm.) Ale, według Jonathana Schaeffera i Roberta Lake'a: "W 1965 r. Program grał po cztery gry przeciwko Walterowi Hellmanowi i Derekowi Oldbury (następnie grając w meczu o mistrzostwo świata) i przegrali wszystkie osiem gier "