Komputer Przejdź - Computer Go

Computer Go to dziedzina sztucznej inteligencji (AI) poświęcona tworzeniu programu komputerowego grającego w tradycyjną grę planszową Go . Gra Go była płodnym tematem badań nad sztuczną inteligencją od dziesięcioleci, których kulminacją był rok 2017, kiedy AlphaGo Master wygrał trzy z trzech gier z Ke Jie , który w tym czasie nieprzerwanie przez dwa lata utrzymywał światowy numer 1 w rankingu.

Wydajność

Go to złożona gra planszowa, która wymaga intuicji, kreatywnego i strategicznego myślenia. Od dawna uważana jest za trudne wyzwanie w dziedzinie sztucznej inteligencji (AI) i jest znacznie trudniejsza do rozwiązania niż szachy . Wiele osób zajmujących się sztuczną inteligencją uważa, że ​​Go wymaga więcej elementów naśladujących ludzką myśl niż szachy . Matematyk IJ Good napisał w 1965 roku:

Wchodzisz na komputer? – Aby zaprogramować komputer, aby grał w sensowną grę w Go, a nie tylko grę legalną – konieczne jest sformalizowanie zasad dobrej strategii lub zaprojektowanie programu uczenia się. Zasady są bardziej jakościowe i tajemnicze niż w szachach i zależą bardziej od osądu. Myślę więc, że zaprogramowanie komputera do rozsądnej gry w Go będzie jeszcze trudniejsze niż w szachy.

Przed 2015 r. najlepsze programy Go zdołały osiągnąć jedynie amatorski poziom dan . Na małej planszy 9×9 komputer radził sobie lepiej, a niektórym programom udało się wygrać ułamek swoich gier 9×9 przeciwko profesjonalnym graczom. Przed AlphaGo niektórzy badacze twierdzili, że komputery nigdy nie pokonają najlepszych ludzi w Go.

Wczesne dziesięciolecia

Pierwszy program Go został napisany przez Alberta Lindseya Zobrist w 1968 roku jako część jego pracy magisterskiej na temat rozpoznawania wzorców . Wprowadzono funkcję wpływu do szacowania terytorium i hashowanie Zobrist do wykrywania ko .

W kwietniu 1981 roku Jonathan K Millen opublikował artykuł w Byte omawiający Wally, program Go z płytą 15x15, która mieści się w 1K RAM mikrokomputera KIM-1 . Bruce F. Webster opublikował artykuł w magazynie w listopadzie 1984 omawiający program Go, który napisał dla Apple Macintosh , w tym źródło MacFORTH .

W 1998 r. bardzo silni gracze byli w stanie pokonać programy komputerowe, dając jednocześnie handicap 25-30 kamieni, co jest ogromnym handicapem, którego nigdy nie przyjęłoby niewielu graczy. Zdarzył się przypadek w 1994 World Computer Go Championship, gdzie zwycięski program, Go Intellect, przegrał wszystkie trzy mecze przeciwko młodym graczom, otrzymując 15-stone handicap. Ogólnie rzecz biorąc, gracze, którzy rozumieli i wykorzystywali słabości programu, mogli wygrywać ze znacznie większymi handicapami niż typowi gracze.

21. Wiek

Rozwój w Monte Carlo poszukiwaniu drzewa i Uczenia Maszynowego przyniósł najlepsze programy na wysokim dan poziomie na małej planszy 9x9. W 2009 roku pojawiły się pierwsze takie programy, które mogły osiągnąć i utrzymać niskie stopnie dan na serwerze KGS Go na tablicy 19x19.

W 2010 roku podczas Europejskiego Kongresu Go w Finlandii MogoTW zagrał 19x19 Go przeciwko Catalin Taranu (5p). MogoTW otrzymał handicap 7-stone i wygrał.

W 2011 Zen osiągnął 5 dan na serwerze KGS, grając w gry po 15 sekund na ruch. Konto, które osiągnęło tę rangę, korzysta z klastrowej wersji Zen działającej na 26-rdzeniowej maszynie.

W 2012 roku Zen pokonał Takemiya Masaki (9p) o 11 punktów przy handicapie pięciu kamieni, a następnie wygrał 20 punktów przy handicapie czterech kamieni.

W 2013 roku Crazy Stone pokonał Yoshio Ishidę (9p) w grze 19×19 z handicapem czterech kamieni.

2014 Codecentric Go Challenge, mecz do dwóch zwycięstw w równej grze 19x19, rozegrano pomiędzy Crazy Stone i Franzem-Jozefem Dickhutem (6d). Żaden silniejszy gracz nigdy wcześniej nie zgodził się na poważną rywalizację z programem go na równych warunkach. Wygrał Franz-Jozef Dickhut, choć Crazy Stone wygrał pierwszy mecz o 1,5 punktu.

2015 i dalej: Era głębokiego uczenia się

W październiku 2015 r. program AlphaGo Google DeepMind pokonał Fan Hui , mistrza Europy w go, pięć razy na pięć w warunkach turniejowych.

W marcu 2016 AlphaGo pokonało Lee Sedola w pierwszych trzech z pięciu meczów. To był pierwszy raz, kiedy mistrz 9-dan grał profesjonalną grę z komputerem bez utrudnień. Lee wygrał czwarty mecz, określając swoje zwycięstwo jako „bezcenne”. AlphaGo wygrało finałowy mecz dwa dni później.

W maju 2017 roku AlphaGo pokonało Ke Jie , który w tamtym czasie zajmował czołowe miejsce na świecie, w trzymeczowym meczu podczas Future of Go Summit .

W październiku 2017 r. DeepMind ujawnił nową wersję AlphaGo, trenowaną wyłącznie przez samodzielną grę, która przewyższyła wszystkie poprzednie wersje, pokonując wersję Ke Jie w 89 na 100 gier.

Od czasu opublikowania podstawowych zasad AlphaGo w czasopiśmie Nature inne zespoły były w stanie tworzyć programy na wysokim poziomie. Do 2017 roku, zarówno Zen , jak i projekt Tencent Fine Art, były w stanie czasami pokonać profesjonalistów na wysokim poziomie, a silnik Leela Zero został wydany.

Przeszkody w osiąganiu wysokiego poziomu

Przez długi czas panowała opinia, że ​​komputer Go stanowi problem zasadniczo odmienny od szachów komputerowych . Uważano, że metody polegające na szybkim globalnym wyszukiwaniu przy stosunkowo niewielkiej wiedzy dziedzinowej nie będą skuteczne wobec ludzkich ekspertów. Dlatego też znaczna część prac nad rozwojem komputera Go była w tamtych czasach skoncentrowana na sposobach przedstawiania wiedzy eksperckiej podobnej do ludzkiej i łączeniu jej z lokalnymi poszukiwaniami odpowiedzi na pytania o charakterze taktycznym. Rezultatem tego były programy, które dobrze radziły sobie w wielu sytuacjach, ale które miały bardzo wyraźne słabości w porównaniu z ogólną obsługą gry. Ponadto te klasyczne programy nie zyskały prawie nic na zwiększeniu dostępnej mocy obliczeniowej per se, a postęp w tej dziedzinie był generalnie powolny.

Kilku badaczy dostrzegło potencjał metod probabilistycznych i przewidziało, że zdominują one gry komputerowe, ale wielu innych uważało, że silny program do grania w Go jest czymś, co można osiągnąć dopiero w odległej przyszłości, w wyniku fundamentalnych postępów w dziedzinie gier komputerowych. ogólna technologia sztucznej inteligencji. Pojawienie się programów opartych na wyszukiwaniu Monte Carlo (rozpoczęte w 2006 r.) zmieniło tę sytuację pod wieloma względami, a pierwsi profesjonalni gracze Go 9-dan zostali pokonani w 2013 r. przez komputery wielordzeniowe , chociaż z czterostopniowym handicapem.

Rozmiar planszy

Duża plansza (19×19, 361 przecięć) jest często wymieniana jako jeden z głównych powodów, dla których trudno jest stworzyć silny program. Duży rozmiar tablicy uniemożliwia wyszukiwarce alfa-beta osiągnięcie głębokiego wyprzedzenia bez znaczących rozszerzeń wyszukiwania lub przycinania heurystyk.

W 2002 roku program komputerowy o nazwie MIGOS (MIni GO Solver) całkowicie rozwiązał grę Go na planszy 5×5. Czarny wygrywa, biorąc całą planszę.

Liczba opcji ruchu

Kontynuując porównanie do szachów, ruchy Go nie są tak ograniczone przez zasady gry. W pierwszym ruchu w szachach gracz ma dwadzieścia wyborów. Gracze Go zaczynają z wyborem 55 różnych legalnych ruchów, uwzględniając symetrię. Liczba ta szybko rośnie wraz z naruszeniem symetrii i wkrótce prawie wszystkie z 361 punktów planszy muszą zostać ocenione. Niektóre ruchy są znacznie bardziej popularne niż inne, a niektóre prawie nigdy nie są rozgrywane, ale wszystkie są możliwe.

Funkcja oceny

Chociaż ocena liczenia materiału nie jest wystarczająca do przyzwoitej gry w szachy, bilans materiałowy i różne czynniki pozycyjne, takie jak struktura pionków, są łatwe do oszacowania.

Tego rodzaju reguły oceny pozycyjnej nie mogą być skutecznie stosowane do Go. Wartość pozycji Go zależy od złożonej analizy, która ma określić, czy grupa żyje, które kamienie mogą być ze sobą połączone oraz heurystyk wokół zakresu, w jakim silna pozycja ma wpływ lub w jakim stopniu słaba pozycja może zostać zaatakowana.

Więcej niż jeden ruch można uznać za najlepszy w zależności od zastosowanej strategii. Aby wybrać ruch, komputer musi ocenić różne możliwe wyniki i zdecydować, który jest najlepszy. Jest to trudne ze względu na delikatne kompromisy obecne w Go. Na przykład może być możliwe przechwycenie niektórych kamieni przeciwnika kosztem wzmocnienia kamieni przeciwnika w innym miejscu. To, czy jest to dobra transakcja, czy nie, może być trudną decyzją, nawet dla ludzkich graczy. Złożoność obliczeniowa pokazuje również tutaj, że ruch może nie być od razu ważny, ale po wielu ruchach może stać się bardzo ważny, gdy inne obszary planszy nabierają kształtu.

Problemy kombinatoryczne

Czasami wspomina się w tym kontekście, że różne trudne problemy kombinatoryczne (w rzeczywistości każdy problem NP-trudny ) można przekształcić w problemy podobne do Go na wystarczająco dużej planszy; jednak to samo dotyczy innych abstrakcyjnych gier planszowych, w tym szachów i saperów , gdy odpowiednio uogólni się je na planszę o dowolnym rozmiarze. Problemy NP-zupełne nie wydają się w ogólnym przypadku łatwiejsze dla ludzi bez pomocy niż dla odpowiednio zaprogramowanych komputerów: wątpliwe jest, aby ludzie bez pomocy byli w stanie skutecznie konkurować z komputerami w rozwiązywaniu, na przykład, przypadków problemu sumy podzbiorów .

Etap końcowy

Biorąc pod uwagę, że gra końcowa zawiera mniej możliwych ruchów niż otwarcie ( fuseki ) lub gra środkowa, można by przypuszczać, że gra się w nią łatwiej, a zatem komputer powinien być w stanie z łatwością sobie z nią poradzić. W szachach programy komputerowe na ogół dobrze radzą sobie w końcówkach szachowych , zwłaszcza gdy liczba bierek jest zmniejszona do tego stopnia, że ​​pozwala to na skorzystanie z rozwiązanych baz tabeli końcówek .

Zastosowanie liczb surrealistycznych w końcowej fazie gry Go, ogólnej analizie gry zapoczątkowanej przez Johna H. Conwaya , zostało rozwinięte przez Elwyna R. Berlekampa i Davida Wolfe'a i opisane w ich książce Mathematical Go ( ISBN  978-1-56881- 032-4 ). Chociaż nie ma ogólnej użyteczności w większości sytuacji gry, bardzo pomaga w analizie niektórych klas pozycji.

Niemniej jednak, chociaż przeprowadzono szczegółowe badania, okazało się, że końcówki Go są trudne do PSPACE . Jest wiele powodów, dla których są tak trudne:

  • Nawet jeśli komputer może bezbłędnie grać w każdym lokalnym obszarze końcowym, nie możemy stwierdzić, że jego gra byłaby bezbłędna w odniesieniu do całej planszy. Dodatkowe obszary do rozważenia w rozgrywkach końcowych obejmują relacje sente i gote , ustalanie priorytetów różnych lokalnych rozgrywek końcowych, liczenie terytorium i szacowanie i tak dalej.
  • Koniec gry może obejmować wiele innych aspektów Go, w tym „życie i śmierć”, które są również znane z tego, że są NP-trudne .
  • Każdy z lokalnych obszarów końcowych może wpływać na siebie nawzajem. Innymi słowy, mają dynamiczny charakter, choć są wizualnie izolowane. Utrudnia to rozumowanie zarówno w przypadku komputerów, jak i ludzi. Ta natura prowadzi do pewnych złożonych sytuacji, takich jak Triple Ko, Quadruple Ko, Melasses Ko i Moonshine Life.

W ten sposób tradycyjne algorytmy Go nie mogą bezbłędnie rozegrać końcowej fazy Go w sensie bezpośredniego obliczania najlepszego ruchu. Silne algorytmy Monte Carlo wciąż wystarczająco dobrze radzą sobie z normalnymi sytuacjami końcowymi w Go, a ogólnie rzecz biorąc, najbardziej skomplikowane klasy problemów końcowych z życia i śmierci raczej nie pojawią się w grze na wysokim poziomie.

Kolejność gry

Silniki Go z Monte-Carlo mają reputację znacznie chętniej grają w tenuki , poruszają się gdzie indziej na planszy, niż kontynuują lokalną walkę niż ludzie. Bezpośrednie obliczenie, kiedy wymagany jest konkretny ruch lokalny, może być trudne. Często było to postrzegane jako słabość na początku istnienia tych programów. To powiedziawszy, ta tendencja utrzymała się w stylu gry AlphaGo z dominującymi wynikami, więc może to być bardziej „dziwactwo” niż „słabość”.

Poszukiwanie taktyczne

Jednym z głównych problemów gracza Go jest to, które grupy kamieni można utrzymać przy życiu, a które można przechwycić. Ta ogólna klasa problemów nazywana jest życiem i śmiercią . Najbardziej bezpośrednią strategią obliczania życia i śmierci jest przeszukanie drzewa dla ruchów, które potencjalnie wpływają na dane kamienie, a następnie zapisanie statusu kamieni na końcu głównej linii gry.

Jednak przy ograniczeniach czasowych i pamięciowych nie jest na ogół możliwe określenie z całkowitą dokładnością, które ruchy mogą wpłynąć na „życie” grupy kamieni. Oznacza to, że należy zastosować pewną heurystykę, aby wybrać ruchy do rozważenia. Efektem końcowym jest to, że dla każdego programu istnieje kompromis między szybkością gry a umiejętnością czytania życia i śmierci.

Za pomocą algorytmu Bensona można określić, które łańcuchy są bezwarunkowo żywe i dlatego nie będą musiały być sprawdzane w przyszłości pod kątem bezpieczeństwa.

reprezentacja państwowa

Problemem, z którym muszą się zmierzyć wszystkie programy Go, jest sposób reprezentowania aktualnego stanu gry. W przypadku programów, które używają rozbudowanych technik wyszukiwania, ta reprezentacja musi zostać skopiowana i/lub zmodyfikowana dla każdego nowego rozważanego hipotetycznego ruchu. Ta potrzeba nakłada dodatkowe ograniczenie, że reprezentacja powinna być albo wystarczająco mała, aby można ją szybko skopiować, albo wystarczająco elastyczna, aby można było łatwo wykonać i cofnąć ruch.

Najbardziej bezpośrednim sposobem przedstawiania tablicy jest tablica jedno- lub dwuwymiarowa, w której elementy tablicy reprezentują punkty na tablicy i mogą przyjmować wartość odpowiadającą białemu kamieniowi, czarnemu kamieniowi lub pustemu przecięciu . Potrzebne są dodatkowe dane, aby zapamiętać, ile kamieni zostało przechwyconych, czyja jest kolej i które skrzyżowania są nielegalne ze względu na zasadę Ko .

Jednak większość programów wykorzystuje do oceny pozycji więcej niż tylko surowe informacje z tablicy. Dane takie jak, które kamienie są połączone w sznurki, które sznurki są ze sobą powiązane, które grupy kamieni są zagrożone przechwyceniem i które grupy kamieni są faktycznie martwe, są niezbędne do dokładnej oceny pozycji. Chociaż informacje te można wydobyć tylko z pozycji kamieni, większość z nich można obliczyć szybciej, jeśli są aktualizowane w sposób przyrostowy, na podstawie ruchu. Ta przyrostowa aktualizacja wymaga przechowywania większej ilości informacji jako stanu tablicy, co z kolei może wydłużyć kopiowanie tablicy. Ten rodzaj kompromisu wskazuje na problemy związane z tworzeniem szybkich programów komputerowych Go.

Alternatywną metodą jest posiadanie jednej planszy oraz wykonywanie i cofanie ruchów, aby zminimalizować zapotrzebowanie na pamięć komputera i przechowywać wyniki oceny planszy. Pozwala to uniknąć konieczności wielokrotnego kopiowania informacji.

Projekt systemu

Nowe podejście do problemów

Historycznie, techniki GOFAI (Good Old Fashioned AI) były używane do podejścia do problemu Go AI. Ostatnio jako alternatywne podejście zastosowano sieci neuronowe . Jednym z przykładów programu wykorzystującego sieci neuronowe jest WinHonte.

Te podejścia mają na celu złagodzenie problemów związanych z grą w Go, która ma wysoki współczynnik rozgałęzienia i wiele innych trudności.

Wyniki badań Computer Go są stosowane w innych podobnych dziedzinach, takich jak kognitywistyka , rozpoznawanie wzorców i uczenie maszynowe . Kombinatoryczna teoria gier , gałąź matematyki stosowanej , jest tematem istotnym dla komputera Go.

Filozofie projektowania

Jedyny wybór, jakiego musi dokonać program, to gdzie umieścić kolejny kamień. Jednak decyzja ta jest utrudniona ze względu na szeroki zakres oddziaływań pojedynczego kamienia na całą planszę oraz złożone interakcje, jakie różne grupy kamieni mogą mieć ze sobą. W celu rozwiązania tego problemu powstały różne architektury. Najpopularniejsze zastosowanie:

Niewiele programów używa tylko jednej z tych technik; większość łączy części każdego z nich w jeden system syntetyczny.

Wyszukiwanie drzewa Minimax

Jedną z tradycyjnych technik sztucznej inteligencji do tworzenia oprogramowania do gier jest użycie wyszukiwania drzewa minimaksowego . Wiąże się to z wykonaniem wszystkich hipotetycznych ruchów na planszy do pewnego momentu, a następnie wykorzystaniem funkcji oceny w celu oszacowania wartości tej pozycji dla aktualnego gracza. Wybierany jest ruch, który prowadzi do najlepszej hipotetycznej planszy, a proces powtarza się w każdej turze. Podczas gdy wyszukiwanie w drzewach było bardzo skuteczne w szachach komputerowych , przyniosło mniejszy sukces w programach Computer Go. Dzieje się tak częściowo dlatego, że tradycyjnie trudno było stworzyć skuteczną funkcję oceny dla tablicy Go, a częściowo dlatego, że duża liczba możliwych ruchów każdej strony może sprawić, że każdy z nich prowadzi do wysokiego współczynnika rozgałęzienia . To sprawia, że ​​ta technika jest bardzo kosztowna obliczeniowo. Z tego powodu wiele programów, które intensywnie wykorzystują drzewa wyszukiwania, może grać tylko na mniejszej planszy 9×9, a nie na pełnych 19×19.

Istnieje kilka technik, które mogą znacznie poprawić wydajność drzew wyszukiwania zarówno pod względem szybkości, jak i pamięci. Techniki przycinania, takie jak przycinanie alfa-beta , Principal Variation Search i MTD(f) mogą zmniejszyć efektywny współczynnik rozgałęzień bez utraty siły. W obszarach taktycznych, takich jak życie i śmierć, Go jest szczególnie podatny na techniki buforowania, takie jak tabele transpozycji . Mogą one zmniejszyć ilość powtarzanego wysiłku, zwłaszcza w połączeniu z iteracyjnym podejściem pogłębiania . Aby szybko przechować pełnowymiarową tablicę Go w tabeli transpozycji, generalnie konieczna jest technika haszowania do matematycznego podsumowania. Haszowanie Zobrist jest bardzo popularne w programach Go, ponieważ ma niskie współczynniki kolizji i może być aktualizowane iteracyjnie przy każdym ruchu za pomocą zaledwie dwóch XOR , zamiast obliczania od zera. Nawet przy użyciu tych technik zwiększających wydajność, przeszukiwanie całego drzewa na pełnowymiarowej tablicy jest nadal zbyt wolne. Wyszukiwanie można przyspieszyć, używając dużej ilości technik przycinania specyficznych dla danej domeny, takich jak nieuwzględnianie ruchów, w których przeciwnik jest już silny, oraz selektywne rozszerzenia, takie jak zawsze branie pod uwagę ruchów obok grup kamieni, które mają zostać przechwycone . Jednak obie te opcje niosą ze sobą spore ryzyko nie rozważenia ważnego ruchu, który zmieniłby przebieg gry.

Wyniki zawodów komputerowych pokazują, że techniki dopasowywania wzorców w celu wybrania kilku odpowiednich ruchów w połączeniu z szybkimi zlokalizowanymi poszukiwaniami taktycznymi (wyjaśnionymi powyżej) były kiedyś wystarczające do stworzenia konkurencyjnego programu. Na przykład GNU Go było konkurencyjne do 2008 roku.

Systemy oparte na wiedzy

Nowicjusze często wiele się uczą z zapisów starych gier, w które grali mistrzowie. Istnieje silna hipoteza, która sugeruje, że zdobycie wiedzy o Go jest kluczem do stworzenia silnego komputera Go. Na przykład Tim Kinger i David Mechner twierdzą, że „jesteśmy przekonani, że dzięki lepszym narzędziom do reprezentowania i utrzymywania wiedzy o Go, możliwe będzie opracowanie silniejszych programów Go”. Proponują dwa sposoby: rozpoznanie wspólnych konfiguracji kamieni i ich pozycji oraz skupienie się na lokalnych bitwach. „Programom Go wciąż brakuje zarówno pod względem jakości, jak i ilości wiedzy”.

Po wdrożeniu, wykorzystanie wiedzy eksperckiej okazało się bardzo skuteczne w programowaniu oprogramowania Go. Setki wskazówek i zasad dotyczących mocnej gry zostały sformułowane zarówno przez amatorów, jak i profesjonalistów na wysokim poziomie. Zadaniem programisty jest wzięcie tych heurystyk , sformalizowanie ich w kodzie komputerowym i wykorzystanie algorytmów dopasowywania wzorców i rozpoznawania wzorców do rozpoznawania, kiedy te reguły mają zastosowanie. Ważne jest również posiadanie systemu określającego, co zrobić w przypadku, gdy mają zastosowanie dwie sprzeczne wytyczne.

Większość stosunkowo udanych wyników pochodzi z indywidualnych umiejętności programistów w Go i ich osobistych przypuszczeń na temat Go, ale nie z formalnych twierdzeń matematycznych; starają się, aby komputer naśladował sposób, w jaki grają w Go. „Większość konkurencyjnych programów wymagała 5–15 osobolat wysiłku i zawiera 50–100 modułów zajmujących się różnymi aspektami gry”.

Ta metoda była do niedawna najbardziej skuteczną techniką generowania konkurencyjnych programów Go na pełnowymiarowej tablicy. Przykładami programów, które w dużej mierze opierały się na wiedzy eksperckiej, są Handtalk (później znany jako Goemate), The Many Faces of Go, Go Intellect i Go++, z których każdy został w pewnym momencie uznany za najlepszy program Go na świecie.

Niemniej jednak dodanie wiedzy o Go czasami osłabia program, ponieważ pewna powierzchowna wiedza może przynieść błędy: „najlepsze programy zwykle grają dobre ruchy na poziomie mistrzowskim. Jednak, jak każdy gracz w gry wie, tylko jeden zły ruch może zepsuć dobrą grę. Wydajność programu w ciągu pełnej gry może być znacznie niższy niż poziom mistrzowski”.

Metody Monte-Carlo

Jedną z głównych alternatyw dla ręcznie zakodowanej wiedzy i wyszukiwań jest zastosowanie metod Monte Carlo . Odbywa się to poprzez generowanie listy potencjalnych ruchów, a dla każdego ruchu rozgrywanie tysięcy losowych gier na wynikowej planszy. Ruch, który prowadzi do najlepszego zestawu losowych gier dla aktualnego gracza, jest wybierany jako najlepszy ruch. Zaletą tej techniki jest to, że wymaga ona bardzo niewielkiej wiedzy w dziedzinie domeny lub wkładu ekspertów, a kompromisem są zwiększone wymagania dotyczące pamięci i procesora. Ponieważ jednak ruchy używane do oceny są generowane losowo, możliwe jest, że ruch, który byłby doskonały poza jedną konkretną odpowiedzią przeciwnika, zostałby błędnie oceniony jako dobry. Rezultatem tego są programy, które są mocne w ogólnym sensie strategicznym, ale są niedoskonałe taktycznie. Ten problem można złagodzić, dodając pewną wiedzę domenową w generowaniu ruchów i wyższy poziom głębokości wyszukiwania oprócz losowej ewolucji. Niektóre programy wykorzystujące techniki Monte-Carlo to Fuego, The Many Faces of Go v12, Leela, MoGo, Crazy Stone , MyGoFriend i Zen.

W 2006 r. opracowano nową technikę wyszukiwania, górne granice ufności stosowane do drzew (UCT), która została zastosowana w wielu programach Monte-Carlo Go 9x9 z doskonałymi wynikami. UCT wykorzystuje zebrane do tej pory wyniki play-outów , aby poprowadzić poszukiwania wzdłuż bardziej udanych linii gry, jednocześnie umożliwiając eksplorację alternatywnych linii. Technika UCT wraz z wieloma innymi optymalizacjami gry na większej planszy 19x19 sprawiła, że ​​MoGo stało się jednym z najsilniejszych programów badawczych. Pomyślne wczesne zastosowania metod UCT do 19x19 Go obejmują MoGo, Crazy Stone i Mango. MoGo wygrało Olimpiadę Komputerową 2007 i wygrało jedną (z trzech) grę błyskawiczną przeciwko Guo Juanowi, 5 Dan Pro, w znacznie mniej złożonym 9x9 Go. The Many Faces of Go wygrało Olimpiadę Komputerową 2008 po dodaniu wyszukiwania UCT do swojego tradycyjnego silnika opartego na wiedzy.

Nauczanie maszynowe

Chociaż systemy oparte na wiedzy są bardzo skuteczne w Go, ich poziom umiejętności jest ściśle powiązany z wiedzą ich programistów i powiązanych ekspertów dziedzinowych. Jednym ze sposobów na przełamanie tego ograniczenia jest użycie technik uczenia maszynowego , aby umożliwić oprogramowaniu automatyczne generowanie reguł, wzorców i/lub strategii rozwiązywania konfliktów reguł.

Zwykle odbywa się to poprzez umożliwienie sieci neuronowej lub algorytmowi genetycznemu albo przeglądanie dużej bazy danych profesjonalnych gier, albo granie w wiele gier przeciwko sobie lub innym osobom lub programom. Algorytmy te są następnie w stanie wykorzystać te dane w celu poprawy ich wydajności. AlphaGo wykorzystało to z doskonałym skutkiem. Inne programy wykorzystujące sieci neuronowe to NeuroGo i WinHonte.

Techniki uczenia maszynowego mogą być również wykorzystywane w mniej ambitnym kontekście do dostrajania określonych parametrów programów, które opierają się głównie na innych technikach. Na przykład Crazy Stone uczy się wzorców generowania ruchów z kilkuset przykładowych gier, wykorzystując uogólnienie systemu ocen Elo .

AlphaGo

AlphaGo , opracowany przez Google DeepMind , dokonał znacznego postępu, pokonując profesjonalnego gracza w październiku 2015 r., używając technik łączących głębokie uczenie i wyszukiwanie drzewa metodą Monte Carlo . AlphaGo jest znacznie potężniejszy niż inne poprzednie programy Go i jest pierwszym, który pokonał profesjonalnego człowieka 9 dan w grze bez utrudnień na pełnowymiarowej planszy.

Lista programów komputerowych do gry w Go

  • AlphaGo , pierwszy program komputerowy, który wygrywa w równych meczach z profesjonalnym graczem Go
  • AYA autorstwa Hiroshi Yamashita
  • BaduGI autorstwa Jooyoung Lee
  • Crazy Stone autorstwa Rémi Coulom (sprzedawany jako Saikyo no Igo w Japonii)
  • Darkforest przez Facebook
  • Dzieła sztuki autorstwa Tencent
  • Fuego, program Monte Carlo o otwartym kodzie źródłowym
  • Goban, program Macintosh OS X Go firmy Sen:te (wymaga bezpłatnych rozszerzeń Goban)
  • GNU Go , klasyczny program Go o otwartym kodzie źródłowym
  • Go++ Michaela Reissa (sprzedawany jako Strongest Go lub Tuyoi Igo w Japonii)
  • Leela , pierwszy program Monte Carlo na sprzedaż dla publiczności
  • Leela Zero , reimplementacja systemu opisanego w artykule AlphaGo Zero
  • The Many Faces of Go Davida Fotlanda (sprzedawany jako AI Igo w Japonii)
  • MyGoFriend autorstwa Franka Kargera
  • MoGo Sylvaina Gelly; wersja równoległa przez wiele osób.
  • Program Pachi open source Monte Carlo autorstwa Petra Baudiša, wersja online Peepo autorstwa Jonathana Chetwynda, z mapami i komentarzami podczas gry
  • Smart Go autorstwa Andersa Kierulfa, wynalazcy Smart Game Format
  • Steenvreter autorstwa Erika van der Werf
  • Zen Yoji Ojimy aka Yamato (sprzedawany jako Tencho no Igo w Japonii); wersja równoległa autorstwa Hideki Kato.

Konkursy programów komputerowych Go

Pomiędzy programami komputerowymi Go odbywa się kilka corocznych konkursów, z których najważniejszymi są zawody Go na Olimpiadzie Komputerowej . Regularne, mniej formalne zawody pomiędzy programami, które miały miejsce na KGS Go Server (co miesiąc) i Computer Go Server (ciąg dalszy).

Znane programy do grania w go to: Crazy Stone, Zen, Aya, Mogo, The Many Faces of Go, pachi i Fuego, wszystkie wymienione powyżej; oraz Coldmilk autorstwa tajwańskiego, Steenvreter autorstwa holenderskiego i DolBaram autorstwa koreańskiego.

Historia

Pierwszy komputerowy konkurs Go był sponsorowany przez Acornsoft , a pierwsze regularne przez USENIX . Trwały od 1984 do 1988 roku. Te zawody wprowadziły Nemesis, pierwszy konkurencyjny program Go od Bruce'a Wilcoxa i G2.5 autorstwa Davida Fotlanda , który później ewoluował w Cosmos i The Many Faces of Go.

Jednym z pierwszych czynników napędzających badania nad komputerami Go była nagroda Ing, stosunkowo duża nagroda pieniężna sponsorowana przez tajwańskiego bankiera Ing Chang-ki , przyznawana corocznie w latach 1985-2000 na World Computer Go Congress (lub Ing Cup). Zwycięzca tego turnieju mógł zmierzyć się z młodymi graczami z handicapem w krótkim meczu. Jeśli komputer wygrał mecz, nagroda została przyznana i ogłoszono nową nagrodę: wyższą nagrodę za pokonanie graczy z mniejszym handicapem. Seria nagród Ing miała wygasnąć albo 1) w roku 2000, albo 2), kiedy program mógł pokonać profesjonalistę 1-dan bez handicapu za 40.000.000 dolarów NT . Ostatnim zwycięzcą był Handtalk w 1997 roku, zdobywając 250 000 dolarów NT za wygranie 11-stone handicapowego meczu z trzema 11-13-letnimi amatorami 2-6 dans. W momencie, gdy nagroda wygasła w 2000 roku, nieodebrane nagrody wynosiły 400 000 NT dolarów za wygranie 9-cio kamieniowego meczu handicapowego.

Wiele innych dużych regionalnych turniejów Go („kongresów”) miało dołączony komputerowy turniej Go. Europejski Kongres Go sponsoruje turniej komputerowy od 1987 roku, a impreza USENIX przekształciła się w US/North American Computer Go Championship, odbywające się corocznie w latach 1988–2000 na Kongresie US Go.

Japonia zaczęła sponsorować zawody komputerowe Go w 1995 roku. Puchar FOST odbywał się corocznie w latach 1995-1999 w Tokio. Turniej ten został zastąpiony przez Gifu Challenge, które odbywało się corocznie w latach 2003-2006 w Ogaki, Gifu. Computer Go UEC Cup został odbywa się corocznie od 2007 roku.

Problemy formalizacji reguł w grach komputerowo-komputerowych

Kiedy dwa komputery grają przeciwko sobie w Go, idealnym rozwiązaniem jest traktowanie gry w sposób identyczny, jak gra dwóch ludzi, unikając jakiejkolwiek interwencji ze strony rzeczywistych ludzi. Może to być jednak trudne podczas punktacji końcowej gry. Główny problem polega na tym, że oprogramowanie do gry w Go, które zwykle komunikuje się za pomocą standardowego protokołu Go Text Protocol (GTP), nie zawsze zgadza się w odniesieniu do statusu kamieni żywych lub martwych.

Chociaż nie ma ogólnego sposobu, w jaki dwa różne programy mogą „omówić to” i rozwiązać konflikt, tego problemu można uniknąć w większości za pomocą zasad chińskich , Tromp-Taylor lub American Go Association (AGA), w których kontynuowano grę ( bez kary) jest wymagane do momentu, gdy nie ma już sporu co do statusu jakichkolwiek kamieni na planszy. W praktyce, tak jak na serwerze KGS Go Server, serwer może pośredniczyć w sporze wysyłając specjalną komendę GTP do dwóch programów klienckich wskazującą, że powinny kontynuować umieszczanie kamieni, dopóki nie ma wątpliwości co do statusu żadnej konkretnej grupy (wszystkie martwe kamienie zostały schwytane). Serwer CGOS Go zwykle powoduje rezygnację z programów, zanim gra osiągnie fazę punktacji, ale mimo to obsługuje zmodyfikowaną wersję zasad Tromp-Taylor, która wymaga pełnej gry.

Te zestawy reguł oznaczają, że program, który miał wygrywającą pozycję na koniec gry zgodnie z japońskimi zasadami (gdy obaj gracze spasowali), może przegrać z powodu słabej gry w fazie rozstrzygania, ale nie jest to częste zjawisko i jest uważane za normalna część gry zgodnie ze wszystkimi zestawami zasad obszaru.

Główną wadą powyższego systemu jest to, że niektóre zestawy zasad (takie jak tradycyjne zasady japońskie) karzą graczy za wykonanie tych dodatkowych ruchów, co wyklucza korzystanie z dodatkowej rozgrywki dla dwóch komputerów. Niemniej jednak większość nowoczesnych programów Go obsługuje japońskie zasady przeciwko ludziom i jest kompetentna zarówno w grze, jak i zdobywaniu punktów (Fuego, Many Faces of Go, SmartGo itp.).

Historycznie, inną metodą rozwiązania tego problemu było osądzenie ostatecznej komisji przez eksperta. Wprowadza to jednak subiektywność wyników i ryzyko, że ekspert przeoczy coś, co zobaczył program.

Testowanie

Dostępnych jest wiele programów, które pozwalają silnikom komputerowym Go grać przeciwko sobie i prawie zawsze komunikują się za pomocą protokołu Go Text Protocol (GTP).

GoGUI i jego dodatek gogui-twogtp mogą być używane do gry między dwoma silnikami w jednym systemie komputerowym. SmartGo i Many Faces of Go również zapewniają tę funkcję.

Aby grać jak najróżniejszymi przeciwnikami, KGS Go Server umożliwia grę w trybie Go Engine vs. Go Engine, a także w trybie Go vs. CGOS to serwer dedykowany komputer vs komputer Go.

Zobacz też

Bibliografia

Dalsza lektura

Zewnętrzne linki