Ukazał się interesujący artykuł w Guardianie :

technology.guardian.co...70,00.html

Artykulik niezły.
Ciekawe czy nie udałoby się połączyć obydwu podejść prezentowanych w artykule. Stworzyć ogrmoną bazę danych gier profesjonalistów i dołożyć uczenie komputery (sieci neuronowe, może fuzzy logic itp.).

Buduje jednak fakt, że są obszary niedoścignione przez maszyny.

Kolejny artykuł na temat, tym razem z The Economist :

www.economist.com/disp...id=8585017

I następny z Dziennika Internautów :

di.com.pl/news/15877,1.html

Komputery zaczną wygrywać w go

Opr: Marcin Maj
Opublikowano: 22.02.2007 r, 08:15

Nikogo już nie dziwi to, że algorytm komputerowy potrafi dobrze grać w szachy, ale wysoki poziom w innej strategicznej grze planszowej - go - przez dłuższy czas był dla maszyn nieosiągalny. Teraz zaczyna się to zmieniać dzięki osiągnięciom węgierskich naukowców.

Go to gra popularna przede wszystkim w kręgu kultury azjatyckiej, ale również i u nas nie brakuje jej miłośników. Sporo informacji na jej temat znajdziemy w internecie m. in. dlatego, że w go często gra się właśnie w Sieci. Komputery w go jak dotąd grały słabo, dlatego nie było obaw, że przeciwnik będzie oszukiwał za pomocą oprogramowania.

Niebawem jednak może się to zmienić i niewykluczone, że za jakiś czas przy rejestracji na serwerze go, użytkownicy będą musieli zobowiązać się do nieużywania w czasie gry programów komputerowych (jak ma to miejsce obecnie na serwerach szachowych). Algorytm, który może już pokonać człowieka stworzyli naukowcy z Węgierskiej Akademii Nauk - Levente Kocsis i Csaba Szepesvari.

Twórcy algorytmu uczciwie przyznają, że na dużej planszy do go (19 na 19 linii) algorytm ten nie ma jeszcze szans na wygranie z graczem-człowiekiem. Potrafi on już jednak wygrywać z ludźmi na treningowej planszy 9x9.

Wiadomo też, że algorytm wymaga dobrego, współczesnego sprzętu i jego możliwości znacznie wzrastają, kiedy komputer korzysta z dwóch procesorów. Ponadto sekret algorytmu tkwi w metodzie określanej przez naukowców skrótem UTC. Metoda ta pozwala na wybór optymalnych zestawów zagrań z tzw. drzewa gry (czyli z opisu wszystkich możliwych do osiągnięcia sytuacji po kolejnych ruchach). Oczywiście algorytm będzie teraz ciągle udoskonalany.

Wcześniejsze algorytmy go również korzystały z drzewa gry, ale kolejne warianty zagrań wybierały raczej losowo. Trzeba dodać, że analiza całego drzewa gry jest w go niemożliwa z dwóch powodów. Po pierwsze wszystkie piony są identyczne i są jedynie dostawiane na planszę (nie da się im przyporządkować cyfr jak figurom w szachach). Po drugie nawet treningowa plansza do gry w go ma więcej pól niż szachownica, nie mówiąc już o planszy pełnowymiarowej.

Na pocieszenie dla nas - ludzi - warto dodać, że nawet najwyższy poziom gry u komputerów tak naprawdę nic nie zmieni. Już wiele lat temu radziecki mistrz szachowy Michał Botwinnik zauważył, że czym innym jest obiektywna ocena gry, a czym innym jest gra człowieka z człowiekiem. Szachy, go i inne sporty umysłowe będą zawsze uprawiane pomiędzy ludźmi. Gra z człowiekiem to coś więcej niż szukanie najlepszego zagrania. Jest to często walka pomiędzy dwoma charakterami i różnymi rodzajami doświadczeń. Minie jeszcze wiele czasu, zanim komputery posiądą jakiś charakter, temperament i strukturę psychologiczną.

Hmm, zawsze mi się wydawało, że już w tej chwili komputery na planszy 9x9 są bardzo dobre. Poczekamy zobaczymy.

Tak czy inaczej i tak kluczowym jest dla mnie ostatni akapit. W pełni się z nim zgadzam i to nie zależnie czy w Go będzie mnie mógł pokonać mój telefon komórkowy czy nie

granie komputera na 9x9 a na 19x19 to różnica jak między kółko i krzyżyk a szachami. Więc na pewno jeszcze poczekamy, zanim komputery zaczną nas ogrywać, a co dopiero jakiś silnych amatorów czy prosów.

Po lekturze powyższego nasuwa się jeden wniosek.
Ale może od początku. Od dawna wiadomo, że komputery są przeznaczone do rozwiązywania pewnej klasy problemów. Są to problemy posiadające jednoznaczne rozwiązanie - wynik obliczeń. Komputer jest w stanie dużo szybciej niż człowiek wykonać nawet najbardziej skomplikowane działania arytmetyczne i przy tym się nie myli. Człowiek natomiast, pomimo że nie jest w stanie tak szybko przetwarzać danych, zdolny jest do szybszej i pewniejszej oceny sytuacji np. rozpoznawania obrazu.
Myślę, że problem gry w go przez komputer jest takim nie do końca określonym zadaniem. Po pierwsze nikt nie "pokaże" komputerowi jak prawidłowo grać w go. Po drugie zaś człowiek grając w go dokonuje oceny sytuacji na podstawie kształtów jakie kamienie tworzą na gobanie, dla komputera jest to trudne do zrealizowania.
Jak pokazuje jednak artykuł, szybsze komputery znacznie lepiej grają w go - bo mogą w tym samym czasie dokonać większej liczby operacji. A ponieważ szybkie komputery robią szybsze komputery, więc chyba możemy być pewni, że kiedyś komputer pokona człowieka w tę piękną grę.
Na pocieszenie pozostaje jednak fakt, że komputer od początku do końca jest dziełem człowieka.

znajmomy podesłał mi linki niedawno, temat powyższy, w pdfie troche dokładniej o UTC, przyznam że jeszcze nie doczytałem ale chyba warto

www.zdnetindia.com/new...72306.html
www.weddslist.com/kgs/...index.html
zaphod.aml.sztaki.hu/p...ecml06.pdf

a tak z czystego ludzkiego egocentryzmu wolałbym żeby komputery za mojego życia nie pokonywały zawodowców, ani danowców

lukasz wrote:

Myślę, że problem gry w go przez komputer jest takim nie do końca określonym zadaniem.

Mi problem wydaje się dość jasno określony, jeśli przyjąć, że chodzi w Go chodzi o wygraną. Tak samo jak w kółko i krzyżyk jedne liście drzewa rozwiązań oznaczają wygraną białego drugie czarnego. Tylko, że w Go jest ono trochę większe.

Określony jasno jest problem, ale nie sposób jego rozwiązani - przynajmniej to miałem na mysli
Co do wielkości drzew, to w zupełności się zgadzam...

Faktycznie komputery na 9x9 robia sie coraz lepsze, ale jaka to jest moc obliczeniowa ?
Pewnie za jakies 10 lat doczekamy w koncu w miare dobrego programu komputerowego do grania w ta piekna gre.
Kiedy komputer wygra z profesjonalnym graczem turniej wtedy mozemy sie juz martwic
Ale narazie to czlowiek jest lepszy.

Ja takim optymistą nie jestem.
Moc obliczeniowa komputera - a raczej jej wzrost praktycznie nie ma znaczenia.
Zakładając, że algorytmy się nie zmienią i bazując tylko na mocy komputera, to możemy poczekać min kilkaset lat.

Jednyna nadzieja to zmiana algorytmów. Ja wiem, że dziś powszechne jest stanowisko - coś słabo działa - użyj lepszego komputera. W Go to nie przejdzie. Myślę, że podłączająć gnugo pod superkomputer może będzie ono miało poziom 1k. Do 1d pewnie byśmy potrzebowali tysiące superkomputerów.

Wzrost liczby operacji wraz ze wzrostem siły gry jest wykładniczy.

W algorytmach stosuje się metodę drzewa przebiegu gry (np szachy) - liczy się ruchy w głąb i ocenia czy pozycja jest dobra (nie liczy się całej gry). Jeśli pozycja jest dobra - komputer wybiera dane drzewko.
Ulepszone algorytmy nazywają się "alfa, beta" - i zakładają, że nie analizujemy wszystkich możliwości - tylko te najbardziej obiecujace - i tak wyglądają własnie zaawansowane algorytmy.

Tu też jest problem z Go - w jaki sposób komputer ma policzyć czy dana pozycja jest dobra. To właśnie ewaluacja pozycji jest największym problemem komputerów.
Dlatego też w Go drzewka decyzyjne stosuje się do bijatyk i sytuacji lokalnych. Do globalnych rzeczy wymyśla się różne algorytmy, które niestety nie są wcale najlepsze.

Jestem ogromnym sceptykiem jeśli chodzi o Go. I sukcesy na 9x9 sa dla mnie marginalne. Różnica między 19x19 a 9x9 w ilości operacji jest ogromna.
nie jest to 10x, nie jest to 1.000.000 razy ale raczej coś koło 10^50 razy, a może i więcej.

Na szczęście Go jest dużo bardziej skomplikowaną grą niż warcaby 64-polowe, które ponoć zostały już rozwiązane :

di.com.pl/news/17060,1.html

Naukowcy z University of Alberta stworzyli program, z którym nie da się wygrać w warcaby. Można więc powiedzieć, że tajemnica gry znanej ludziom w obecnym kształcie od średniowiecza została rozwiązana. Mimo sukcesu naukowcy mówią, że odkrycie tajemnicy kolejnych gier nie będzie proste.

Z programem o nazwie Chinook nie da się wygrać, można co najwyżej zremisować. Program potwierdził też to, czego arcymistrzowie domyślali się od dawna - przy idealnie prowadzonej grze po obu stronach zawsze skończy się ona remisem.

To, co odróżnia Chinooka od innych programów to metoda obliczania ruchów. Dotychczas tworzone programy korzystały z tzw. reguły kciuka. Pozwala ona określić, która część drzewa decyzji należy rozwijać. Reguła kciuka wskazuje wyniki dobre według pewnego kryterium, ale może pomijać inne, dobre rozwiązania.

Gdy tworzono program Chinook, naukowcy pozwalali grać komputerowi z jednym kamieniem na planszy po każdej stronie, potem z dwoma, z trzema itd. Działanie programu na bieżąco analizowano i aktualizowano z pomocą silnych warcabistów. Przy analizowaniu każdej pozycji pracowało średnio 50 komputerów dziennie (czasem liczba maszyn zaangażowanych do pracy wynosiła nawet 200).

Naukowcy pod kierownictwem Jonathana Schaeffera dotarli wreszcie do momentu, gdy przeanalizowane zostały wszystkie pozycje przy 10 kamieniach na planszy po każdej stronie. Zajęło to ponad 18 lat. Teraz za każdym razem gdy w grze pozostanie 10 kamieni, Chinook nie musi już wybierać najlepszych ruchów - on po prostu "wie", który ze wszystkich możliwych ruchów jest w określonej pozycji najwłaściwszy i każda jego decyzja jest optymalna.

Twórcy programu podkreślili, że ich osiągnięcie było możliwe dzięki rozwojowi jaki nastąpił w dziedzinie sprzętu. W ich ocenie podobny sukces w przypadku szachów długo jeszcze nie będzie możliwy, a nawet zdobycie wiedzy na temat absolutnie wszystkich pozycji warcabowych nie jest jeszcze możliwe. Z pewnością jednak sukces ekipy z University of Alberta zachęci do dalszych badań w tym kierunku.

Warto dodać, ze warcaby to obecnie najbardziej skomplikowana gra, jaką udało się rozwiązać. Wcześniej naukowcy odkryli tajemnicę takich gier jak awari (wariant mankali) i czwórki (gra znana również jako "połącz cztery").

Czy "rozwiązanie" warcabów oznacza ich koniec? Ależ nie! Warcaby nadal pozostaną sportem umysłowym, który będzie dostarczał przyjemności i emocji. Już w przeszłości wielcy szachiści (np. Lasker, Botwinnik) podkreślali, że gra człowieka z człowiekiem to nie tylko walka o obiektywnie lepszą pozycję w grze, ale także zmaganie się na poziomie psychologicznym i kondycyjnym. Niezależnie od sukcesów maszyn warcaby i inne gry pozostaną dla ludzkości wartościowe. Wystarczy tylko spojrzeć na nie jak na grę ludzi, a nie tylko grę figur czy kamieni na planszy.