Po szachach nadchodzi czas na grę "go"

[facet123]

Kilka lat temu, po tym gdy jasne stało się, że komputery (nawet biurkowe) przerosły w grze w szachy profesjonalnych mistrzów podjęte zostało następne wyzwanie - gra Go.
Gra ta ta o wiele prostrze (i matematycznie bardziej eleganckie) zasady, a jest przy tym o wiele bardziej złożona z obliczeniowego punku widzenia - o wiele większy branching factor, jakies 10^100 RAZY więcej kombinacji niż w szachach, wiecej ruchów na rozgrywke (około 200), większaplansza (361 pól), trudniejsza evaluacja stanu planszy.
O samej grze więcej tutaj: en.wikipedia.org/wiki/Go_%28game%29.

Jeszcze kilka lat temu najlepsze programy grające w Go nie były w stanie nawiązac równej gry nawet z amatorem. Były beznadziejne. Dosłownie 2-3 lata temu dzięki nowej metodzie - Monte Carlo Tree Search udało się znacznie poprawić jakość gry. Małe klastry obliczeniowe osiągają już siłę około 4dan amatorskie grając z ludźmi na serwerach internetowych, a wiekszy klaster zdołał wygrać grę z zawodowcem gdy otrzymał od niego 7 tzw. "handicapów" . Handicapy to sposób ułatwiania gdy słabszemu graczowi, aby rozgrywka była bardziej interesująca (choć nie jest wtedy sprawiedliwa). Komputer (w uproszczeniu) otrzymuje możliwość wykonania pierwszych kilku ruchów na które przeciwnik nie odpwowiada. 7 handicapów dało komputerowi gigantyczną przewagę i nie ma co tutaj mówić o równiej grze, ale jeszcze niedawno nawet to było nie do pomyślenia. System handicapów jest często stosowany podczas treningów w Go, ponieważ gra ta oferuje tak wielkie zróżnicowanie poziomów graczy, że wiekszość gier towarzyskich była by mało ciekawa - ciut silniejszy gracz łoiłby słabszego, tak że ten nie wiedziałby co się dzieje.
Tradycyjnie za maksymalną liczbę handikapów uznaje się 9, co nie oznacza, że wygranie z azjatyckim zawodowcem na 9 handicapach jest łatwe. Zejście poniżej 9 handikapów podczas gry z zawodowcem to już olbrzymi sukces - można piwiedzieć, że komputery "wiedzą już o co chodzi" w Go. Do nawiązania równej walki jeszcze długa droga, zwłaszcza, że mówi się, że najtrudniejsza bariera trudności to ta pomiędzy 1 handicapem, z równą grą. Czekam na dalsze sukcesy.

Aha, Ilośc kobminacji jest tak wielka, że postęp w przyspieszaniu i zrównoleglaniu komputerów niewiele tutaj wnosi. Sposób na lepszą grę komputera w Go musi opierać się na coraz sprytniejszym algorytmie, a nie coraz wiekszej mocy obliczeniowej.

O komputerach i go: en.wikipedia.org/wiki/Computer_Go#Recent_results

Swoją drogą ciekawe, że mózg zawodowego gracza w Go (większośc mieszka w Azji, bo tylko tamtejsze kraje utrzymnują ligi w tym sporcie) jest w stanie tak bardzo zdystansować najlepsze komputery i najbardziej wyrafinowane algorytmy, zwłaszcza, że umiejętność gry w Go to czysto matematyczno-kombinatoryczna zdolność, a nie biologiczno-kulturowo-ewolucyjna umiejetność jak np. rozumienie języka (z którym komputery też mają problem).

Strzelałbym, że minie jeszcze kilkanaście lub kilkadziesiąt lat zanim komputer wygra w Go z zawodowcem w równej grze.

[asteroida2]

To ciekawe. Ja podejrzewam, że w ciągu kilkunastu lat komputery ograją zawodowców, ale zapewne będzie to wymagało nowych podejść. Bo nie oszukujmy się: Monte Carlo Tree Search to nie jest szczególnie wyrafinowana metoda. A ponieważ zapamiętanie stu milionów rozgrywek samo w sobie nie pomaga w zwycięstwie, nie da się tego zrobić podobnymi metodami, jak przy szachach. Zapewne algorytm musi umieć tworzyć jakieś "pojęcia", opisujące sytuacje i określające strategie. Ten temat jest też intensywnie badany, w szczególności w grach, w których liczba kombinacji jest o wiele rzędów wielkości większa, niż w Go:

tech.wp.pl/kat,1009779,title,Komputer-sam-nauczyl-sie-grac-w-Cywilizacje-czytajac-instrukcje,wid,13600587,wiadomosc.html

[facet123]

> Bo nie oszukujmy się: Monte Carlo Tree Search to nie jest szczególnie wyrafinowana metoda.

Sama metoda Monte Carlo nie jest wyrafinowana, ale ma tę zaletę, że pozwala na implementację algorytmu który w ogóle nie posiada "wiedzy dziedzinowej" na temat gry - nie zna teorii otwarć ani żadnych strategii, zna tylko zasady wykonywania ruchu zgodnego z zasadami i warunek uznania gry za za zakończoną.
Akurat w przypadku Go otwarcia i strategia są tak ważne i tak trudne, że sama metoda Monte Carlo nie dała by dobrych wyników. Programy grające w Go niezależnie od metody Monte Carlo korzystają z baz danych otwarć oraz list predefiniowanych fragmentarycznych układów którymi się posiłkują. Same losowe rozgrywki nie są też zupełnie losowe, ale wspomagane heurystykami tak żeby rozwarzać tylko te prawdopodobne ciągi ruchów, a nie zupełnie losowe.

> Zapewne algorytm musi umie ć tworzyć jakieś "pojęcia", opisujące sytuacje i określające
> strategie.

Tak, z tym, że najlepiej by było gdyby algorytm tworzył te pojęcia na zasadzie uczenia się, a nie na zasadzie wprowadzania mu jakiejś predefiniowanej wiedzy eksperckiej.
Np. w Go teoria otwarć i różne strategie wypracowane przez setki lat zawodowego Go w krajach azjatyckich bardzo wyrafinowane i dają wielką przewagę graczowi który je zna. Nie wyobrażam sobie żeby ktokolwiek (nieważne jak utalentowany) był w stanie wywnioskować te otwarcia (tzw. Joseki: senseis.xmp.net/?Joseki) i strategie sam z siebie w ciągu swojego życia, tylko na podstawie rozegraych przez siebie partii.
Rówież obecne programy grające w Go mają tą wiedzę wpisaną na stałe.

Za to komputer ma tutaj przewagę polegającą na tym, że może grać przez internet z wieloma ludźmi jednocześnie, uczyć się z rozagranych partii lub grać sam ze sobą. W ten sposób teoretycznie możliwe było by aby komputer sam zbudował własną bazę wiedzy eksperckiej wywodząc ją wyłącznie z zasad gry...

> w których liczba kombi nacji jest o wiele rzędów wielkości większa, niż w Go:

Naprawę większa? Liczba kombinacji w Go jest gigantyczna. Po za tym jak liczyć kombinacje w Cywilizacji? Kombinacje mają dla mnie sens w grach z pełną informacją i suma zerową.

[asteroida2]

> Np. w Go teoria otwarć i różne strategie wypracowane przez setki lat zawodowego
> Go w krajach azjatyckich bardzo wyrafinowane i dają wielką przewagę graczowi który
> je zna. Nie wyobrażam sobie żeby ktokolwiek (nieważne jak utalentowany) był w stanie
> wywnioskować te otwarcia (tzw. Joseki) i strategie sam z siebie w ciągu swojego życia,
> tylko na podstawie rozegraych przez siebie partii.

Człowiek na pewno nie, bo człowiek może rozegrać w ciągu całego życia pewnie co najwyżej kilkaset tysięcy partii. Komputer mógłby rozegrać kilkaset tysięcy partii w ciągu jednego dnia. I gdyby z tych rozgrywanych partii wyciągał wnioski, to osiągnięcie poziomu wyższego niż zawodowiec powinno być dla niego łatwo osiągalne.

Tak sobie myślę, że być może Go jest wciąż niewystarczająco doceniane jako tester algorytmów uczenia maszynowego. Bo jak sam piszesz, jest to problem czysto kombinatoryczny i dobrze zdefiniowany. Wydawałoby się, że powinien być łatwiejszy do rozwiązania niż np. chodzenie albo rozpoznawanie obrazów. Skoro komputery wciąż grają w Go słabo, to znaczy, że wciąż ich umiejętności kręcą się wokół tego, co im zaimplementują z góry programiści. "Wpisywanie wiedzy na stałe" najwyraźniej wystarcza, żeby wygrać z człowiekiem w szachy, ale nie prowadzi do żadnego postępu. Potrzeba algorytmów, które osiągną wysoki poziom wyłącznie na podstawie obserwacji rozgrywek.

> > w których liczba kombi nacji jest o wiele rzędów wielkości większa, niż w Go:
>
> Naprawę większa? Liczba kombinacji w Go jest gigantyczna. Po za tym jak liczyć
> kombinacje w Cywilizacji? Kombinacje mają dla mnie sens w grach z pełną informa
> cją i suma zerową.

Liczba kombinacji w Go to co najwyżej 3^361.

Cywilizacja jest grą z sumą zerową, bo ostatecznie jeden gracz wygrywa, a pozostali przegrywają. Liczbę kombinacji możesz oszacować ograniczając się do rozgrywek z pełną informacją (gdy każdy z graczy widzi całą planszę) i z dwoma graczami. Jeśli plansza ma rozmiary np. 100x100, a każdy gracz jest np. ograniczony do 1000 jednostek, to już samego rozstawienia jednostek jest ponad 9000^1000. Możesz jeszcze uwzględnić np. rozbudowę terenu: 20 różnych sposobów rozbudowy na każdym polu daje 20^10000 kombinacji.

[facet123]

> Człowiek na pewno nie, bo człowiek może rozegrać w ciągu całego życia pewnie co
> najwyżej kilkaset tysięcy partii. Komputer mógłby rozegrać kilkaset tysięcy pa
> rtii w ciągu jednego dnia.

Właśnie. Problem w tym, że brakuje odpowiedniego modelu (odpowiedniego sposobu reprezentacji aktualnego stanu wiedzy algorytmu). Reprezentacje takie jak drzewa uczące się, zbiory reguł decyzyjnych, lub sieci neuronowe są albo zbyt mało pojemne (pierwsze 2) albo zbyt wolno uczące się i wpadające w minima lokalne (jak sieci neuronowe).
Dlatego dzisiejsze algorytmy sprowadzają się do heurystycznego przeszukiwania drzewa.
Jeżeli już przeszukujemy drzewo, to przynajmniej funkcja ewaluacji stanu planszy (oceniająca, czy dany stan jest pożądany czy nie) powinna byc fukcją zdolną do elastycznego uczenia się.
Prawdopodobnie algorytm dorze grający w Go musiałby opierać się na jakiejś nowej, nieodkrytej jeszcze lub niedocenianej metodzie reprezentacji.

> Tak sobie myślę, że być może Go jest wciąż niewystarczająco doceniane jako test
> er algorytmów uczenia maszynowego

Częściowo wynika to z tego, że w świecie zachodnim jako jedyny symbol poważnej umysłowej gry sportowej z sumą zrową i pełną informacją wystepują szachy. O Go mało kto na zachodzie słyszał, mimo tego, że szachy w porównaniu z GO są jak kółko i krzyżyk.

> o 1000 jednostek, to już samego rozstawienia jednostek jest ponad 9000^1000. Mo
> żesz jeszcze uwzględnić np. rozbudowę terenu: 20 różnych sposobów rozbudowy na
> każdym polu daje 20^10000 kombinacji.

Ok, faktycznie. Tymbardziej algorytm grający w cywilizacje musiałby korzystać z jakiejś wiedzy dziedzinowej (a nie przeglądania wszystkich możliwości) tyle, że ciekawsze było by gdyby tę wiedzę dziedzinową sam tworzył.
Problemem może być również to, że jeżeli założyć, że początkowo program nie ma żadnej wiedzy dziedzinowej, a kombinacji i możliwości ruchu jest tak dużo, to trudno mu będzie tylko za pomocą prób i błędów trafić w jakąkolwiek sensowną strategię. Np. człowiek siadając po raz pierwszy do rozgrywki w Cywilizację, nawet jeśli jeszcze nigdy nie grał, to ma mnóstwo dziedzinowych pojęć i wiedzy z nauki historii i życia codziennego - komputer nie miałby nic - dla niego miasta i jednostyki były by symbolami pozbawionymi skojarzeń z czym kolwiek, zatem jedyne co mógłby na początku robic, to wykonywać losowe ruchy...

gra w kropki

[llukiz]

Pamiętam że cała podstawówkę spędziłem na graniu w kropi, czyli grze podobnej do GO

pl.wikipedia.org/wiki/Kropki_%28gra%29
Parę lat temu siadłem na jakiejś stronie i próbowałem grać w GO z ludźmi i generalnie większej różnicy między grami nie widziałem. Wygrałem wszystkie pięć partii i stwierdziłem że to nie ma sensu. Teraz ściągnąłem se program do gry w kropi i zauważyłem że gra on nieźle jeśli chodzi o planowanie trzech/czterech ruchów do przodu. Jeśli chodzi o szerszy pogląd na sytuacje na planszy, to widać że o tym myśli, ale też tak jakoś w kontekście czterech ruchów w przód.

Co do meritum, to ta gra wcale taka trudna nie jest (choć może mówię z pozycji laika). Moim zdaniem nikt dobry po prostu nigdy się tym na serio nie zajął. Przy czym musiałby być zarówno dobrym graczem w go jak i dobrym programistą. Wydaje mi się że w ciągu roku potrafiłbym stworzyć program który zawsze mnie pokona w GO/kropki. Tylko kto mi za tę pracę zapłaci? :)

[facet123]

> Pamiętam że cała podstawówkę spędziłem na graniu w kropi, czyli grze podobnej d
> o GO
>
> rel="nofollow">pl.wikipedia.org/wiki/Kropki_%28gra%29

Pasjonat GO pewnie obraziłby się za takie porówanie, ale fatycznie na pierwszy rzut oka gry mają wspólne cechy. Wydaje mi się jednaj, że to iluzja - GO jest o wiele barzdziej złożone, choć nie przeprowadzałem analizy gry w kropki.

> Parę lat temu siadłem na jakiejś stronie i próbowałem grać w GO z ludźmi i gene
> ralnie większej różnicy między grami nie widziałem. Wygrałem wszystkie pięć par
> tii i stwierdziłem że to nie ma sensu.

W takim razie albo grałeś z graczami który podobnie jak ty rozgrywali pierwsze swoje gry, albo nie było to GO. W go praktycznie niemożliwe jest aby początkujący wygrał z kimś choćby ciut zaawansowanym.
Uwież mi. Prawdziwa partia GO rozgrywana na planszy 19x19 ma tyle różnych subetlności, wymaga tyle planowania strategii ile nie mógłbyś ogarnąć tylko na podstawie partii kropek granych w szkole na przerwach.

> Co do meritum, to ta gra wcale taka trudna nie jest (choć może mówię z pozycji
> laika). Moim zdaniem nikt dobry po prostu nigdy się tym na serio nie zajął.

Mylisz się tutaj zupełnie. Gra w GO była analizowana przez zawodowych graczy od casów starożytnych w krajach azjatyckich. Cesarz utrzymywał coś co nazwalibyśmy teraz ligą zawodową - dzieci zdradzające talant był od najmłodszych lat trenowane tylko w tym jednym zajęciu - grze w GO, a najlepsi mieli zaszczyt szkolić w GO cesarzy (uważano, że ta gra strategiczna polepsza zdolności rządzenia). Najlepszi gracze utrzymywali się z GO i mieli z tego spore pieniądze. Tak jest do dzisiaj - najlepszi zawodowi gracze w GO w turniejach sponsorowaych przez prywatne firmy (np. Toyota) zarabiają około miliona dolarów za wywalczenie tytułu.
Przez setki lat konkurencja była ogromna i każdy nowy pomysł, jeżeli poleszał szanse wygtanej, był zapamiętywany.
Np. trudno było by samodzielnie wymyśleć, że najlepszy pierwszy ruch to ruch w punkt 4x4 lub jego okolice. Tzw. Joseki, czyli sekwencje pierwszych kilku ruchów wyglądają dla laika jak losowe ruchy, ale gdyby tylko zawodowiec zagrał któryś z tych róchów inaczej, jego preciwnik byłby w stanie boleśnie wyeksploatować błąd.
Po kilku ruchach zaczyna się jednak "wolna amerykanka" i kombinacji jest tyle, że tylko intuicja, doświadczenie i talent w odczytywaniu pozycji pozwalają na wysoki poziom gry.
Analityczne zdolności programistów niewiele tu pomogą - większość programistów biorących udział w tworzeniu programów do GO gra na wysokim, (tyle, że amatorskim) poziomie.

> Wydaj e mi się że w ciągu roku potrafiłbym stworzyć program który zawsze mnie pokona
> w GO/kropki. Tylko kto mi za tę pracę zapłaci? :)

Jeżeli program miał by pokonać gracza który gra po raz pierwszy, to faktycznie pewnie by ci się to udało. Gryby miał pokonać gracza któy rozegrał już 100 partii i przeczytał jakąś książkę o strategii i taktyce w GO zadanie było by bardzo trudne i wątpie żyby ci się udało.
Jakby co, to za zwyciąstwo komputera z zawodowcem ufundowano nagrode 1mln $ dla programisty.

[llukiz]

> wiele barzdziej złożone, choć nie przeprowadzałem analizy gry w kropki.

Granie w kropki jest najlepszą możliwą analizą gry w kropki. Ktoś kto grał w kropki przez kilka lat na pewno nie może o sobie powiedzieć że jest początkującym graczem w go. To bardzo pomaga. Wszystko to co piszesz w odniesieniu do GO, tyczy się też zapewne gry w kropki. Ta gra jest genialna. Masz za sobą kilkaset godzin doświadczenia, a przychodzi sytuacja i myślisz minutę gdzie kropkę postawić. Stawiasz w końcu i nie wiesz czy postąpiłeś słusznie. Dopiero gdy przeciwnik stawia swoją już widzisz czy się pomyliłeś czy nie.

Spytam prosto z mostu. Grałeś kiedyś w kropki?

[facet123]

Nie grałem.
Faktycznie branching factor, liczba ruchów na partię i rozmiar planszy są tego samego rzędu co w GO, więc złożoność jest chyba podobna.
Jeżeli tak, to możliwe, że napisanie programu grającego w kropki było by równie trudne co programu grającego w GO.
Trudnośc w porównaniu była by taka, że zawowode GO produkuje nam witruozów gry w GO - ludzi których zdolności gry w GO są zbliżone do limitów wynikających z budowy mózgu.
Grą w kropki pewnie nikt nie zajął się na tyle powaznie żeby poświęcić jej całe życie, brak turniejów, rywalizacji pomiędzy najlepszymi na świecie itp. Zatem trudno było by sprawdzić czy program który wygrywałby ze mną i z tobą w kropki gra faktycznie deoskonale, czy poprostu nikomu z ludzi nie chciało się nauczyć lepiej grać.

[sphinx10]

W podanym przez Ciebie linku czytam: " ... rozgrywka w kropki bardzo się różni od GO". Ty większej różnicy nie widzisz, ale, jak słusznie napisałeś, patrzysz na GO z pozycji laika.
Jestem ciekawy na jakim serwerze grałeś te 5 partii i na jakiej planszy. Polecam się sprawdzić na stronie www.gokgs.com
Nie od razu dostąpisz zaszczytu gry z posiadaczem DAN.
Zagraj najpierw z jakimś 10-17 kyu. Jeśli wygrasz jakąś partię to będzie znaczyło, że jesteś diamentem do oszlifowania. Póki co, Twoje słowa są dla mnie niewiarygodne.

[llukiz]

> Jestem ciekawy na jakim serwerze grałeś te 5 partii

W GO na pewno gram bardzo słabo, bo w kropki grałem dużo, ale ze słabymi przeciwnikami, co siłą rzeczy wynikało z mojego wieku, bo grałem dawno z kumplami z podstawówki, którzy siłą rzeczy dobrzy być nie mogli. Te 5 partii rozegrałem na kurniku z losowymi osobami, które wybierały sobie spory handicap, a i tak im to nie pomagało. Zapewne nie mieli wcześniej takiego przeszkolenie w kropkach, jakie ja miałem. A tak bardziej na poważnie, to może spróbuje pograć na www.gokgs.com i zorientuję się na ile tak na prawdę umiejętności z kropek mi się przydają. Bo czasami mam wrażenie, że to nie ja jestem w kropki dobry, tylko wszyscy z którymi grałem są beznadziejni. Jak znajdę czas i zagram to może zdam relację.

[facet123]

> Zagraj najpierw z jakimś 10-17 kyu. Jeśli wygrasz jakąś partię to będzie znaczy
> ło, że jesteś diamentem do oszlifowania. Póki co, Twoje słowa są dla mnie niewi
> arygodne.

Wygrana z graczem 10-15kyu pierwszej gry, znając tylko reguły, na planszy 19x19 jest wg mnie niemożliwa. Nawet jeżeli ktoś byłby zdolny przewidywać bardzo głębokie drzewo gry, to ok, nie da się złapać lokalną taktyczną pułapkę, ale strategicznie nie przeskoczy gracza który rozegrał już kilka partii. Gdyby go ograł świadczyło by to o talencie rodzaju Honinbo Shusaku
en.wikipedia.org/wiki/Honinbo_Shusaku