Granie W Gry

Wspomniałem już o próbach programowania komputerów do grania w gry planszowe, takie jak szachy i warcaby. Najbardziej udanym z nich był program do gry w warcaby Arthura Samuela. W 1967 r. Samuel opublikował artykuł opisujący ulepszoną wersję swojego programu. Ponownie zapoznał się z procedurą wyszukiwania programu i wprowadził lepsze możliwości "uczenia się książki", zamiast obliczać szacunkową wartość pozycji poprzez zsumowanie ważonych wartości cech , używał hierarchicznie zorganizowanych tabel. Według Richarda Suttona: "Ta wersja nauczyła się grać znacznie lepiej niż program z 1959 roku, choć wciąż nie jest na poziomie mistrzowskim". W latach 1959-1962 grupa studentów MIT, której doradzał John McCarthy, opracowała program szachowy. Został oparty na wcześniejszych programach dla IBM 704 napisanych przez McCarthy′ego. Jeden z członków grupy, Alan Kotok opisał program w swojej pracy licencjackiej MIT. Program został napisany w kombinacji kodu FORTRAN i kodu maszynowego (asemblera) i działał na komputerze IBM 7090 na MIT. Wykorzystano procedurę alfa-beta (jak omówiono wcześniej), aby uniknąć generowania gałęzi drzewa wyszukiwania, które można by wyeliminować bez zmiany końcowego wyniku. Kotok twierdził, że jego program nie ukończył żadnej gry, ale "rozegrał cztery długie fragmenty gry, w których grał w szachy porównywalne do amatora z około 100 doświadczeniami w grze "… Większość ruchów maszyny nie jest ani genialna, ani głupia. Trzeba przyznać że czasami się przewraca." Kiedy McCarthy przeprowadził się do Stanford, zabrał ze sobą program i kontynuował prace nad nim. W międzyczasie Georgi Adelson-Velskiy i współpracownicy w laboratorium Aleksandra Kronroda w Instytucie Fizyki Teoretycznej i Doświadczalnej (ITEP) w Moskwie opracowali program szachów komputerowych. Podczas wizyty w Związku Radzieckim w 1965 roku McCarthy podjął wyzwanie, aby program Kotok -McCarthy grał w program radziecki. Począwszy od 22 listopada 1967 r. I trwając około 9 miesięcy, program Kotok -McCarthy (działający na DEC PDP-6 w Stanford) grał w rosyjskim programie (działającym na rosyjskim komputerze M-20 w ITEP) - pierwszy mecz do gry przez komputer na komputerze. W każdej z pierwszych dwóch gier, program Stanford przeprowadził remis (przetwarzając do uzgodnionego limitu 40 ruchów) przeciwko słabej wersji rosyjskiego programu. Jednak przegrał ostatnie dwie gry z silniejszą wersją programu ITEP. McCarthy stwierdził później, że chociaż Stanford miał lepszy komputer, ITEP miał lepsze programy. Program ITEP był prekursorem znacznie ulepszonego programu Kaissa opracowanego później przez Misze Donskoya, Vladimira Arlazarova i Aleksandra Uszkowa w Instytucie Kontroli Nauki w Moskwie. Richard Greenblatt, ekspert programista w AI Lab w MIT, pomyślał, że może ulepszyć program szachowy Kotoka. Jego praca nad szachami komputerowymi ostatecznie doprowadziła do powstania programu, który nazwał MAC HACK VI.7. Jako ekspert szachowy był w stanie wprowadzić szereg doskonałych heurystyk do wybierania ruchów i oceny ruchów w swoim programie. MAC HACK VI, działający na DEC PDP-6 AI Lab i napisany wydajnym kodem maszynowym, był pierwszym programem do gry w turniejach przeciwko ludzkim szachistom. W turnieju z kwietnia 1967 r. Wygrał dwa mecze i zremisował dwa, uzyskując ocenę 1450 w skali ocen Federacji Szachowej USA, o poziomie amatorskiego gracza. (Zgodnie z międzynarodowym systemem ocen szachowych ludzi najwyższy poziom to Grand Masters. Potem są International Masters, National Masters, Experts, Class A, Class B itd. MAC HACK VI grał w wysokiej klasie C do niskiego poziomu klasy B, który wciąż jest dość daleki od gry mistrzowskiej.) Został honorowym członkiem Amerykańskiej Federacji Szachowej i Massachusetts Chess Association. W słynnym meczu na MIT w 1967, Program Greenblatta pokonał Huberta Dreyfusa, krytyka AI, który wcześniej zauważył, że "żaden program szachowy nie może grać nawet w szachy amatorskie". Chociaż obserwacja Dreyfusa prawdopodobnie była prawdziwa w 1965 roku, MAC HACK VI Greenblatta grał u amatora poziom dwa lata później Być może zachęcony umiejętnością MAC HACK, w 1968 roku Donald Michie i John McCarthy postawili po 250 $ za każdą z Davidem Levy, Scottish International Master, że komputer będzie w stanie go pokonać w ciągu dziesięciu lat (W następnym roku dołączył Seymour Papert, a w 1971 Ed Kozdrowicki z University of California w Davis również to zrobił, zwiększając łączny zakład do 1000 $. W 1974 roku Donald Michie podniósł sumę do 1250 $.) W 1978 roku Levy zebrał jego zakład {jak zobaczymy później. Około 1970 r. trzech studentów Northwestern University w Illinois, David Slate, Larry Atkin i Keith Gorlen, zaczęli pisać serię programów szachowych. Pierwszy z nich, CHESS 3.0, działający na komputerze CDC 6400, wygrał pierwszy turniej szachów komputerowych Association for Computing Machinery (komputery przeciwko komputerom) w Nowym Jorku w 1970 roku. Nie było wśród nich sześciu -MAC HACK VI. Według Davida Levy′a "CHESS 3.0 oceniał około 100 pozycji na sekundę i grał na poziomie 1400 w skali ocen Federacji Szachowej Stanów Zjednoczonych". Kolejne programy północno-zachodnie, aż do CHESS 4.6, osiągnęły szereg zwycięstw na tym dorocznym wydarzeniu. Tymczasem CHESS 4.2 został pokonany we wczesnej rundzie pierwszego świata. Turniej o mistrzostwo w szachach komputerowych, który odbył się na spotkaniu Międzynarodowej Federacji Towarzystw Przetwarzania Informacji (IFIPS) w Sztokholmie w 1974 r. Rosyjski program Kaissa wygrał wszystkie cztery gry w tym turnieju, stając się tym samym światowym mistrzem szachów komputerowych. W tych latach, od późnych lat sześćdziesiątych do połowy lat siedemdziesiątych, komputerowe szachy stopniowo się poprawiały, od gry na poziomie początkującym do gry na poziomie średnim. Praca nad szachami komputerowymi w ciągu następnych dwóch dziesięcioleci ostatecznie doprowadziłaby do osiągnięcia poziomu eksperckiego, co zobaczymy w następnym rozdziale. Pomimo tego szybkiego postępu stało się już jasne, że istnieje duża różnica między sposobem, w jaki komputery grają w szachy, a tym, jak ludzie grają w szachy. Hans Berliner, ekspert szachowy i programista szachowy, umieścił go w artykule w Nature, [człowiek] wykorzystuje ogromne ilości wiedzy w procesie rozpoznawania wzorców [do podjęcia decyzji o dobrym manewrze] i niewielka ilość obliczeń, aby zweryfikować fakt, że proponowane rozwiązanie jest dobre w obecnym przypadku… Jednak komputer wykonałby ten sam manewr, ponieważ pod koniec bardzo dużego poszukiwania stwierdził, że był to najkorzystniejszy sposób na skorzystanie z setek tysięcy możliwości, na które spojrzał. CHESS 4.6 do tej pory dokonał kilku dobrze znanych manewrów, nie mając najmniejszej wiedzy o manewrze, warunkach jego zastosowania itd.; ale tylko wiedząc, że końcowy wynik manewru był dobry. Berliner podsumował różnicę, mówiąc: "Podstawą ludzkiej gry w szachy, w przeciwieństwie do [komputerów], jest zgromadzona wiedza" (moja kursywą). Szczególna wiedza na temat rozwiązania problemu, w przeciwieństwie do zastosowania masowych poszukiwań w rozwiązywaniu problemu, stała się głównym tematem badań sztucznej inteligencji w tym okresie. (Później jednak masowe poszukiwania odzyskały część swojego znaczenia.) Być może najbardziej wpływowymi zwolennikami wykorzystania wiedzy w rozwiązywaniu problemów byli Edward Feigenbaum i jego koledzy ze Stanford. Odwrócę się do ich przełomowej pracy.