Dlaczego nie ma mechanizmów uczenia się głębokiego wzmocnienia dla szachów, podobnych do AlphaGo?

32

Komputery od dawna potrafią grać w szachy za pomocą techniki „brute-force”, szukając określonej głębokości, a następnie oceniając pozycję. Komputer AlphaGo używa jednak tylko ANN do oceny pozycji (o ile mi wiadomo, nie dokonuje głębokiego przeszukiwania). Czy można stworzyć silnik szachowy, który gra w szachy w taki sam sposób, jak AlphaGo gra Go? Dlaczego nikt tego nie zrobił? Czy ten program działałby lepiej niż dzisiejsze najlepsze silniki szachowe (i szachownicy)?

lijas
źródło
5
Zobacz arxiv.org/abs/1509.01549 (Giraffe: Korzystanie Głębokie zbrojenia nauka gry w szachy) oraz popularne artykułu technologyreview.com/s/541276/... . Również erikbern.com/2014/11/29/deep-learning-for-chess.html
ameba mówi Przywróć Monikę
To tylko kwestia czasu, aż ktoś zacznie to robić poprawnie. Więc miesiąc po opublikowaniu pytania, proszę: arxiv.org/abs/1712.01815 .
ameba mówi Przywróć Monikę

Odpowiedzi:

49

EDYCJA (po przeczytaniu artykułu):

Przeczytałem gazetę z namysłem. Zacznijmy od tego, co twierdzi Google w gazecie:

  • Pokonali Sztokfiszki za pomocą Monte-Carlo-Tree-Search + Głębokie sieci neuronowe
  • Mecz był absolutnie jednostronny, wiele wygranych dla AlphaZero, ale żaden dla Sztokfisza
  • Byli w stanie to zrobić w zaledwie cztery godziny
  • AlphaZero grał jak człowiek

Niestety nie sądzę, że to dobra gazeta. Wyjaśnię za pomocą linków (więc wiesz, że nie śnię):

https://www.chess.com/news/view/alphazero-reactions-from-top-gms-stockfish-author

Same wyniki meczów nie są szczególnie znaczące ze względu na dość dziwny wybór kontroli czasu i ustawień parametrów Sztokfisz: Gry były rozgrywane o ustalonym czasie 1 minuty / ruch, co oznacza, że ​​Sztokfisz nie korzysta z heurystyki zarządzania czasem ( włożono wiele wysiłku w to, aby Sztokfisz zidentyfikował krytyczne punkty w grze i zdecydował, kiedy poświęcić trochę czasu na ruch; w ustalonym czasie na ruch siła znacznie ucierpi).

Sztokfisz nie byłby w stanie grać w najlepsze szachy tylko za minutę na ruch. Program nie został do tego przeznaczony.

  • Sztokfisz działał na zwykłej maszynie komercyjnej, a AlphaZero na 4 milionach + TPU dostrojonych dla AlphaZero. To tak, jakby dopasować swój wysokiej klasy komputer stacjonarny do taniego telefonu z Androidem. Tord napisał:

Jeden to konwencjonalny program szachowy działający na zwykłych komputerach, drugi wykorzystuje zasadniczo różne techniki i działa na specjalnie zaprojektowanym sprzęcie, który nie jest dostępny do zakupu (i byłby znacznie większy niż budżet zwykłych użytkowników, gdyby tak było).

  • Google przypadkowo podał 64 wątki 32-rdzeniowej maszynie dla Sztokfisza. Cytuję GM Larry'ego Kaufmana (światowej klasy eksperta w szachach komputerowych):

http://talkchess.com/forum/viewtopic.php?p=741987&highlight=#741987

Zgadzam się, że test był daleki od uczciwości; Inną kwestią, która dotknęła SF, było to, że najwyraźniej działał na 64 wątkach na 32-rdzeniowej maszynie, ale grałby znacznie lepiej, uruchamiając tylko 32 wątki na tej maszynie, ponieważ prawie nie ma korzyści SMP, która zrównoważyłaby około 5 do 3 spowolnienia. Również wskaźnik kosztów był większy niż powiedziałem; Myślałem, że to 64-rdzeniowa maszyna, ale 32-rdzeniowa maszyna kosztuje około połowy tego, co zgadywałem. Więc może w sumie 30 do 1 nie jest takie złe. Z drugiej strony myślę, że nie doceniasz tego, jak bardzo można by to poprawić.

  • Sztokfisz dał tylko 1 GB tabeli mieszającej. To żart ... Mam większą tabelę skrótów dla mojej aplikacji Stockfish iOS (Uwaga: jestem autorem) na moim iPhonie! Tord napisał:

    ... zdecydowanie za małe tabele skrótów dla liczby wątków ...

Tabela mieszania 1 GB jest absolutnie nie do przyjęcia w przypadku takiego meczu. Sztokfisz często napotyka kolizję haszy. Procesor zastępuje stare wpisy skrótu.

  • Sztokfisz nie jest zaprojektowany do pracy z tak dużą liczbą wątków. W mojej szachowej aplikacji na iOS używa się tylko kilku wątków. Tord napisał:

... bawił się o wiele więcej wątków wyszukiwania niż kiedykolwiek poddano znacznej ilości testów ...

  • Sztokfisz biegł bez książki otwierającej lub 6-częściowego stołu do gry Syzygy. Wielkość próby była niewystarczająca. Wersja Sztokfisz nie była najnowsza. Dyskusja tutaj .

WNIOSEK

Google nie udowodnił bez wątpienia, że ich metody są lepsze niż Sztokfisz. Ich liczba jest powierzchowna i silnie stronnicza w stosunku do AlphaZero. Ich metody nie są powtarzalne przez niezależną stronę trzecią. Jest jeszcze trochę za wcześnie, aby powiedzieć, że głębokie uczenie się jest lepszą metodą niż tradycyjne programowanie szachowe.


EDYCJA (grudzień 2017):

Jest nowy artykuł od Google Deepmind ( https://arxiv.org/pdf/1712.01815.pdf ) do nauki głębokiego wzmacniania w szachach. Z abstrakcyjnego punktu widzenia, światowy silnik szachowy Stockfish został „przekonująco” pokonany. Myślę, że jest to najważniejsze osiągnięcie w szachach komputerowych od meczu Deep Blue w 1997 roku. Zaktualizuję swoją odpowiedź, kiedy przeczytam artykuł szczegółowo.


Oryginał (przed grudniem 2017 r.)

Wyjaśnijmy twoje pytanie:

  • Nie, silniki szachowe nie używają brutalnej siły.
  • AlphaGo robi poszukiwania wykorzystanie drzewa, używa Monte-Carlo Tree Search . Google „ Monte Carlo Tree Search alphaGo ”, jeśli chcesz się przekonać.

ANN można stosować do silników szachowych:

Czy ten program działałby lepiej niż dzisiejsze najlepsze silniki szachowe (i szachownicy)?

Żyrafa gra na poziomie międzynarodowym, czyli około FIDE 2400. Jednak Sztokfisz, Houdini i Komodo grają około FIDE 3000. To duża różnica. Czemu? Dlaczego nie przeszukać drzewa Monte-Carlo?

  • Heurystyka materialna w szachach jest prosta. W większości przypadków pozycja szachowa wygrywa / przegrywa, po prostu licząc materiały na planszy. Pamiętaj, że liczenie materiałów nie działa w Go. Zliczanie materiałów jest o rząd wielkości szybsze niż uruchamianie sieci neuronowych - można tego dokonać za pomocą bitboardów reprezentowanych przez 64-bitową liczbę całkowitą. W systemie 64-bitowym można to zrobić tylko za pomocą kilku instrukcji maszyny. Wyszukiwanie przy użyciu tradycyjnego algorytmu jest znacznie szybsze niż uczenie maszynowe. Wyższe węzły na sekundę przekładają się na głębsze wyszukiwanie.
  • Podobnie, istnieją bardzo przydatne i tanie techniki, takie jak przycinanie z zerowym ruchem, redukcja późnego ruchu i zabójcze ruchy itp. Są tanie w prowadzeniu i znacznie wydajniejsze od podejścia zastosowanego w AlphaGo.
  • Ocena statyczna w szachach jest szybka i przydatna
  • Uczenie maszynowe jest przydatne do optymalizacji parametrów, ale mamy również SPSA i CLOP do gry w szachy.
  • Istnieje wiele przydatnych wskaźników zmniejszania drzewa w szachach. O wiele mniej w przypadku Go.

Przeprowadzono badania, według których wyszukiwanie drzew Monte Carlo nie sprawdza się w szachach. Go to inna gra niż szachy. Algorytmy szachowe nie działają dla Go, ponieważ szachy opierają się na brutalnej taktyce. Taktyka jest prawdopodobnie ważniejsza w szachach.

Teraz ustaliliśmy, że MCTS działa dobrze dla AlphaGo, ale mniej dla szachów. Dogłębne uczenie się byłoby bardziej przydatne, jeśli:

  • Dostrojona ocena NN jest lepsza niż tradycyjne algorytmy. Jednak ... głębokie uczenie się nie jest magią, ponieważ programista nadal musiałby programować. Jak wspomniano, mamy coś w rodzaju SPSA do samodzielnego grania w celu dostrajania parametrów w szachach.
  • Inwestycja, pieniądze! W szachach nie ma dużo pieniędzy na uczenie maszynowe. Sztokfisz jest darmowy i open source, ale wystarczająco silny, aby pokonać wszystkich ludzkich graczy. Dlaczego Google wydaje miliony, jeśli ktoś może po prostu pobrać Sztokfisz za darmo? Po co płacić za klastry procesorów? Kto zapłaci za talenty? Nikt nie chce tego robić, ponieważ szachy są uważane za grę „rozwiązaną”.

Jeśli głębokie uczenie się może osiągnąć następujące cele, przełamie tradycyjny algorytm:

  • Biorąc pod uwagę pozycję szachową, „poczuj” to jak ludzki arcymistrz. Na przykład ludzki arcymistrz nie popadłby w złą linię - z doświadczenia. Ani tradycyjny algorytm, ani głębokie uczenie się nie mogą tego osiągnąć. Twój model NN może dać ci prawdopodobieństwo [0..1] dla twojej pozycji, ale to nie wystarczy.

Pozwól mi wskazać:

Nie. Giraffe (link opublikowany przez @Tim) nie korzysta z wyszukiwania drzewa w Monte Carlo. Wykorzystuje zwykły algorytm nega-max. Wszystko, co robi, to zastępuje zwykłą funkcję oceny NN i jest to bardzo powolne.

jeszcze jeden:

Chociaż Kasparow został pokonany przez Deep Blue w meczu w 1997 roku. „Ludzkość” naprawdę zaginęła w latach 2003-2005, kiedy Kramnik przegrał mecz z Deep Fritz bez wygranej, a Michael Adams przegrał z maszyną klastrową w meczu jednostronnym. W tym czasie Rybka okazała się zbyt silna nawet dla najlepszych graczy na świecie.

Odniesienie:

http://www.talkchess.com/forum/viewtopic.php?t=64096&postdays=0&postorder=asc&highlight=alphago+chess&topic_view=flat&start=0

Cytuję:

W szachach mamy pojęcie materialności, które już daje rezonansową ocenę wydajności silnika i można je szybko obliczyć. Ponadto istnieje wiele innych aspektów gry, które można zakodować w funkcji oceny statycznej, czego nie można było wykonać w Go. Z powodu wielu heurystyk i dobrej oceny EBF (efektywny czynnik rozgałęziający) jest dość mały. Zastosowanie sieci neuronowej jako zamiennika funkcji oceny statycznej zdecydowanie spowolniłoby silnik o wiele.

SmallChess
źródło
1
Dziękuję Ci. Kilka pytań: silniki szachowe używają algorytmu alfa-beta, czy nie jest to algorytm „brutalnej siły”? Czy „Wyszukiwanie drzewa w Monte Carlo” oznacza, że ​​należy spojrzeć o kilka ruchów przed aktualną pozycję?
lijas,
1
@lijas „brutalna siła” jest ogólnie definiowana jako przeszukiwanie wszystkich możliwości. Silniki szachowe tego nie robią.
SmallChess,
7
@lijas Właśnie odpowiedziałeś na pytanie. Mnożenie macierzy jest powolną operacją.
SmallChess,
3
Wyszukiwarka Alpha Beta to z pewnością „brutalna siła”. Hans Berliner o trendach AI: „Uważam, że najważniejszym trendem było to, że komputery stały się znacznie szybsze w ciągu ostatnich 50 lat. W tym procesie odkryliśmy, że wiele rzeczy, dla których mieliśmy najlepsze rozwiązania antropomorficzne, których w wielu przypadkach nie udało się uchwycić prawdziwa istota ludzkiej metody może być dokonana za pomocą bardziej brutalnych metod, które wymienia się tylko do momentu znalezienia satysfakcjonującego rozwiązania. Jeśli to jest herezja, niech tak będzie. ” (patrz ieeexplore.ieee.org/document/820322/?reload=true )
Daniel Lidström,
1
@smallchess alpha beta jest de facto algorytmem wyszukiwania, nawet jego warianty, takie jak negascout, które są tylko stopniowymi ulepszeniami. Do czego jeszcze mógł się odnosić? Zostało to napisane na długo przed powstaniem systemów głębokiego uczenia się.
Daniel Lidström,
6

DeepBlue pokonało już Kasparowa, więc ten problem rozwiązano dzięki znacznie prostszemu podejściu. Było to możliwe, ponieważ liczba możliwych ruchów w szachach jest znacznie mniejsza niż w ruchu , więc jest to o wiele prostszy problem. Ponadto zauważ, że zarówno NN, jak i brutalna siła potrzebują ogromnych zasobów obliczeniowych ( tutaj możesz znaleźć zdjęcie komputera za AlphaGo, zauważ, że nie używa nawet GPU, ale TPU do obliczeń). Całe zamieszanie z go polegało na tym, że kiedy Deep Blue pokonało Kasparowa, społeczność go twierdziła, że ​​nie byłoby to możliwe z go (z wielu różnych powodów, ale aby podsumować argumenty, muszę szczegółowo przedstawić grę of go). Tak, możesz nauczyć NN grać w szachy, Mario lub spróbować nauczyć go graćStarcraft ...

Wydaje mi się, że powodem tego jest to, że po prostu często nie słyszysz w mediach głównego nurtu o przypadkach, w których ludzie rozwiązują problemy, które już zostały rozwiązane.

Co więcej, twoje założenie jest błędne, głębokie uczenie się jest używane do gry w szachy, np. Jak opisano w Głębokim uczeniu się Maszyna uczy się gry w szachy w ciągu 72 godzin, gra na poziomie międzynarodowym . Zobacz także odpowiedni artykuł Giraffe: Korzystanie z nauki głębokiego wzmocnienia w grze w szachy .

Tim
źródło
3
Pomimo, że oczywiście istnieją pewne programy szachowe trenowane z głębokim uczeniem się wzmacniającym, faktem jest, że nikt nie zbudował takiego, który pokonałby „tradycyjne” silniki szachowe. Zakładam, że dzieje się tak, ponieważ ten problem (pokonanie tradycyjnych silników) po prostu nie jest wystarczająco interesujący / motywuje do zainwestowania dużo wysiłku potrzebnego do opracowania czegoś na poziomie AlphaGo.
ameba mówi Przywróć Monikę
1
@amoeba, powszechnie dostępne oprogramowanie do grania również nie korzysta z głębokiego uczenia się i zwykle jest słabsze od amatorskich graczy 1 dan, o wiele gorsze niż AlphaGo. AlphaGo to dowód koncepcji.
Tim
1
@ rus9384 nie jest to łatwe, ale już go „rozwiązaliśmy”, Deep Bluie pokonało Kasparowa, mamy naszego czarnego łabędzia, który zdał test Turinga w szachy.
Tim
5
Rozwiązana gra to kolejna sprawa: nie wiemy, czy idealna gra gwarantuje zwycięstwo w czerni / bieli lub kończy się remisem.
rus9384,
1
@ rus9384: Fajnie byłoby rozpocząć grę przeciwko idealnej szachowej sztucznej inteligencji i zobaczyć „Białe wygrane. Szachownica w 97 ruchach”.
Eric Duminil,