Computer Go - Computer Go

Acest articol este despre studiul Go (joc) în inteligența artificială. Pentru limbajul de programare numit Go, consultați Go (limbaj de programare) .
Nu trebuie confundat cu software-ul Go .
Parte dintr-o serie pe
Merge
Accesați board part.jpg
Specificul jocului
Istorie și cultură
Jucători și organizații
Calculatoare și matematică

Computer Go este domeniul inteligenței artificiale (AI) dedicat creării unui program de computer care joacă jocul de masă tradițional Go . Jocul Go a fost un subiect fertil al cercetării inteligenței artificiale timp de decenii, culminând în 2017, cu AlphaGo Master câștigând trei din cele trei jocuri împotriva lui Ke Jie , care la acea vreme deținea continuu clasamentul nr. 1 mondial timp de doi ani.

Performanţă

Go este un joc de societate complex care necesită intuiție, gândire creativă și strategică. A fost mult timp considerată o provocare dificilă în domeniul inteligenței artificiale (AI) și este considerabil mai dificil de rezolvat decât șahul . Mulți din domeniul inteligenței artificiale consideră că Go necesită mai multe elemente care imită gândirea umană decât șahul . Matematicianul IJ Good a scris în 1965:

Mergi pe computer? - Pentru a programa un computer pentru a juca un joc rezonabil de Go, mai degrabă decât un joc legal - este necesar să se formalizeze principiile bunei strategii sau să se proiecteze un program de învățare. Principiile sunt mai calitative și mai misterioase decât în ​​șah și depind mai mult de judecată. Deci, cred că va fi și mai dificil să programezi un computer pentru a juca un joc rezonabil de Go decât de șah.

Înainte de 2015, cele mai bune programe Go au reușit să ajungă doar la nivel de amatori . Pe placa mică de 9 × 9, computerul s-a descurcat mai bine, iar unele programe au reușit să câștige o fracțiune din jocurile lor de 9 × 9 împotriva jucătorilor profesioniști. Înainte de AlphaGo, unii cercetători susțineau că computerele nu vor învinge niciodată oamenii de top din Go.

Primele decenii

Primul program Go a fost scris de Albert Lindsey Zobrist în 1968 ca parte a tezei sale despre recunoașterea tiparelor . A introdus o funcție de influență pentru a estima teritoriul și hash Zobrist pentru a detecta ko .

În aprilie 1981, Jonathan K Millen a publicat un articol în Byte despre Wally, un program Go cu o placă de 15x15 care se încadrează în memoria 1K RAM a microcomputerului KIM-1 . Bruce F. Webster a publicat un articol în revistă în noiembrie 1984, discutând despre un program Go scris de el pentru Apple Macintosh , inclusiv sursa MacFORTH .

În 1998, jucătorii foarte puternici au reușit să bată programele de computer, oferind în același timp handicapuri de 25-30 de pietre, un handicap enorm pe care puțini jucători umani l-ar lua vreodată. A existat un caz în Campionatul Mondial Computer Computer din 1994 în care programul câștigător, Go Intellect, a pierdut toate cele trei jocuri împotriva jucătorilor tineri în timp ce primea un handicap de 15 pietre. În general, jucătorii care au înțeles și au exploatat punctele slabe ale unui program ar putea câștiga cu handicapuri mult mai mari decât jucătorii tipici.

secolul 21

Dezvoltările în căutarea copacilor din Monte Carlo și învățarea automată au adus cele mai bune programe la nivel înalt de dan pe placa mică de 9x9. În 2009, au apărut primele astfel de programe care ar putea atinge și deține poziții scăzute la nivel de dan și pe serverul KGS Go de pe placa 19x19.

În 2010, la Congresul European Go din 2010 din Finlanda, MogoTW a jucat 19x19 Go împotriva lui Catalin Taranu (5p). MogoTW a primit un handicap de șapte pietre și a câștigat.

În 2011, Zen a ajuns la 5 dan pe serverul KGS, jucând jocuri de 15 secunde pe mișcare. Contul care a atins acel rang folosește o versiune cluster a Zen care rulează pe o mașină cu 26 de nuclee.

În 2012, Zen l-a învins pe Takemiya Masaki (9p) cu 11 puncte la handicapul cu cinci pietre, urmat de o victorie cu 20 de puncte la handicapul cu patru pietre.

În 2013, Crazy Stone l-a învins pe Yoshio Ishida (9p) într-un joc de 19 × 19 la handicapul cu patru pietre.

Codecentric Go Challenge 2014, cel mai bun din cinci meci într-un joc egal de 19x19, a fost jucat între Crazy Stone și Franz-Jozef Dickhut (6d). Niciun jucător mai puternic nu fusese vreodată de acord să joace o competiție serioasă împotriva unui program de go în condiții egale. Franz-Jozef Dickhut a câștigat, deși Crazy Stone a câștigat primul meci cu 1,5 puncte.

2015 și mai departe: era învățării profunde

Informații suplimentare: AlphaGo versus Fan Hui , AlphaGo versus Lee Sedol și AlphaGo versus Ke Jie

În octombrie 2015, programul Google DeepMind AlphaGo l -a învins pe Fan Hui , campionul European Go, de cinci ori din cinci în condițiile turneului.

În martie 2016, AlphaGo l-a învins pe Lee Sedol în primele trei din cele cinci meciuri. Aceasta a fost prima dată când un maestru de 9 dan a jucat un joc profesional împotriva unui computer fără handicap. Lee a câștigat al patrulea meci, descriindu-i victoria drept „neprețuită”. AlphaGo a câștigat ultimul meci două zile mai târziu.

În mai 2017, AlphaGo l-a învins pe Ke Jie , care la acea vreme era clasat pe primul loc în lume, într-un meci de trei jocuri în timpul Future of Go Summit .

În octombrie 2017, DeepMind a dezvăluit o nouă versiune a AlphaGo, antrenată doar prin auto-joc, care depășise toate versiunile anterioare, depășind versiunea Ke Jie în 89 din 100 de jocuri.

Întrucât principiile de bază ale AlphaGo au fost publicate în revista Nature , alte echipe au reușit să producă programe la nivel înalt. Până în 2017, atât proiectul Zen Art , cât și Tencent , Fine Art, au reușit să învingă profesioniștii de foarte înalt nivel, iar motorul open source Leela Zero a fost lansat.

Obstacole în calea performanței la nivel înalt

Pentru o lungă perioadă de timp, a fost o opinie larg răspândită că computerul Go a pus o problemă fundamental diferită de șahul computerului . Se credea că metodele care se bazează pe căutare globală rapidă, cu cunoștințe relativ reduse în domeniu, nu ar fi eficiente împotriva experților umani. Prin urmare, o mare parte a efortului de dezvoltare a computerului Go s-a concentrat în aceste vremuri pe modalități de reprezentare a cunoștințelor de specialitate umane și combinarea acestora cu căutarea locală pentru a răspunde la întrebări de natură tactică. Rezultatul a fost programe care au gestionat bine multe situații, dar care au avut slăbiciuni foarte pronunțate în comparație cu modul general de gestionare a jocului. De asemenea, aceste programe clasice nu au câștigat aproape nimic din creșterea puterii de calcul disponibile în sine și progresul în domeniu a fost în general lent.

Câțiva cercetători au înțeles potențialul metodelor probabilistice și au prezis că vor ajunge să domine jocurile pe computer, dar mulți alții au considerat un program Go-playing puternic ceva ce ar putea fi realizat doar în viitorul îndepărtat, ca urmare a progreselor fundamentale în tehnologie generală de inteligență artificială. Apariția programelor bazate pe căutarea Monte Carlo (începută în 2006) a schimbat această situație din mai multe puncte de vedere, primii jucători profesioniști Go din 9 dan fiind învinși în 2013 de computere multicore , deși cu handicap în patru pietre.

Dimensiunea plăcii

Placa mare (19 × 19, 361 intersecții) este adesea notată ca fiind unul dintre principalele motive pentru care un program puternic este greu de creat. Dimensiunea mare a plăcii împiedică un căutător alfa-beta să obțină o privire profundă fără extensii de căutare semnificative sau euristici de tăiere .

În 2002, un program de computer numit MIGOS (MIni GO Solver) a rezolvat complet jocul Go pentru placa 5 × 5. Negrul câștigă, luând tot tabloul.

Numărul de opțiuni de mutare

Continuând comparația cu șahul, mișcările Go nu sunt la fel de limitate de regulile jocului. Pentru prima mișcare în șah, jucătorul are douăzeci de opțiuni. Jucătorii Go încep cu alegerea a 55 de mișcări legale distincte, reprezentând simetria. Acest număr crește rapid pe măsură ce simetria este ruptă și în curând trebuie evaluate aproape toate cele 361 de puncte ale tabloului. Unele mișcări sunt mult mai populare decât altele și unele nu se joacă aproape niciodată, dar toate sunt posibile.

Funcția de evaluare

În timp ce o evaluare a numărării materialelor nu este suficientă pentru un joc decent în șah, echilibrul materialului și diferiți factori de poziție, cum ar fi structura pionului, sunt ușor de cuantificat.

Aceste tipuri de reguli de evaluare pozițională nu pot fi aplicate în mod eficient Go. Valoarea unei poziții Go depinde de o analiză complexă pentru a determina dacă grupul este sau nu în viață, care pietre pot fi conectate între ele și euristică în ceea ce privește măsura în care o poziție puternică are influență sau măsura în care o poziție slabă poziția poate fi atacată.

Mai multe mișcări pot fi considerate cele mai bune, în funcție de strategia utilizată. Pentru a alege o mutare, computerul trebuie să evalueze diferite rezultate posibile și să decidă care este cel mai bun. Acest lucru este dificil din cauza compromisurilor delicate prezente în Go. De exemplu, poate fi posibilă capturarea unor pietre inamice cu prețul întăririi pietrelor adversarului în altă parte. Indiferent dacă este o meserie bună sau nu, poate fi o decizie dificilă, chiar și pentru jucătorii umani. Complexitatea de calcul se arată și aici, deoarece o mișcare ar putea să nu fie imediat importantă, dar după multe mișcări ar putea deveni extrem de importante pe măsură ce prind contur și alte zone ale tabloului.

Probleme combinatorii

Uneori se menționează în acest context că diverse probleme combinatorii dificile (de fapt, orice problemă NP-hard ) pot fi convertite în probleme Go-like pe o placă suficient de mare; totuși, același lucru este valabil și pentru alte jocuri de societate abstracte, inclusiv șahul și măturătorul , atunci când sunt generalizate în mod adecvat la un tablou de dimensiuni arbitrare. Problemele NP-complete nu tind în cazul lor general să fie mai ușoare pentru oamenii fără ajutor decât pentru computerele programate corespunzător: este îndoielnic faptul că oamenii fără ajutor ar putea concura cu succes împotriva computerelor în rezolvarea, de exemplu, a cazurilor problemei sumelor de subset .

Endgame

Având în vedere că jocul final conține mai puține mișcări posibile decât jocul de deschidere ( fuseki ) sau de mijloc, s-ar putea presupune că este mai ușor de jucat și, prin urmare, un computer ar trebui să poată aborda cu ușurință. În șah, programele de computer au, în general, performanțe bune în jocurile finale de șah , mai ales odată ce numărul pieselor este redus în măsura în care permite să profite de bazele de tabel rezolvate ale jocului final .

Aplicarea numerelor suprarealiste la finalul jocului Go, o analiză generală a jocului inițiată de John H. Conway , a fost dezvoltată în continuare de Elwyn R. Berlekamp și David Wolfe și prezentată în cartea lor, Mathematical Go ( ISBN  978-1-56881- 032-4 ). Deși nu este de utilitate generală în majoritatea circumstanțelor de joc, ajută foarte mult analiza anumitor clase de poziții.

Cu toate acestea, deși s-a efectuat un studiu elaborat, jocurile finale Go s-au dovedit a fi PSPACE-hard . Există multe motive pentru care sunt atât de dure:

  • Chiar dacă un computer poate juca fiecare zonă de endgame local fără cusur, nu putem concluziona că jocurile sale ar fi impecabile în ceea ce privește întreaga placă. Domenii suplimentare de luare în considerare în endgames includ relațiile sente și gote , prioritizarea diferitelor endgames locale, numărarea și estimarea teritoriului și așa mai departe.
  • Finalul jocului poate implica multe alte aspecte ale Go, inclusiv „viața și moartea”, care sunt, de asemenea, cunoscute ca fiind NP-hard .
  • Fiecare dintre zonele finale ale jocului final se pot afecta reciproc. Cu alte cuvinte, acestea au o natură dinamică, deși izolate vizual. Acest lucru face dificil să se argumenteze atât computerele, cât și oamenii. Această natură duce la unele situații complexe precum Triple Ko, Quadruple Ko, Melasses Ko și Moonshine Life.

Astfel, algoritmii Go tradiționali nu pot reda jocul final Go fără cusur în sensul de a calcula direct cea mai bună mișcare. Algoritmii puternici de la Monte Carlo încă pot rezolva situațiile normale ale jocului final Go suficient de bine și, în general, este puțin probabil ca cele mai complicate clase de probleme ale jocului final viață și moarte să apară într-un joc de nivel înalt.

Ordinea jocului

Motoarele Go bazate pe Monte-Carlo au reputația de a fi mult mai dispuse să joace tenuki , se mută în altă parte pe tablă, mai degrabă decât să continue o luptă locală decât jucătorii umani. Calculul direct când este necesară o mutare locală specifică poate fi dificil. Acest lucru a fost adesea perceput ca o slăbiciune la începutul existenței acestor programe. Acestea fiind spuse, această tendință a persistat în stilul de joc al AlphaGo cu rezultate dominante, astfel încât aceasta poate fi mai mult o „ciudățenie” decât o „slăbiciune”.

Căutare tactică

Una dintre principalele preocupări pentru un jucător Go este ce grupuri de pietre pot fi păstrate în viață și care pot fi capturate. Această clasă generală de probleme este cunoscută sub numele de viață și moarte . Cea mai directă strategie pentru calcularea vieții și a morții este de a efectua o căutare a arborelui în mișcările care pot afecta pietrele în cauză și apoi de a înregistra starea pietrelor la sfârșitul liniei principale de joc.

Cu toate acestea, în limitele de timp și de memorie, nu este, în general, posibil să se determine cu o acuratețe completă care mișcări ar putea afecta „viața” unui grup de pietre. Acest lucru implică faptul că trebuie aplicate unele euristici pentru a selecta care mișcări trebuie luate în considerare. Efectul net este că, pentru orice program dat, există un compromis între viteza de joc și abilitățile de citire a vieții și a morții.

Cu algoritmul lui Benson , este posibil să se determine lanțurile care sunt în viață necondiționate și, prin urmare, nu ar trebui să fie verificate în viitor pentru siguranță.

Reprezentarea statului

O problemă pe care trebuie să o abordeze toate programele Go este cum să reprezinte starea actuală a jocului. Pentru programele care utilizează tehnici extinse de căutare, această reprezentare trebuie copiată și / sau modificată pentru fiecare nouă mișcare ipotetică luată în considerare. Această nevoie plasează constrângerea suplimentară conform căreia reprezentarea trebuie să fie suficient de mică pentru a fi copiată rapid sau suficient de flexibilă pentru a putea fi făcută și anulată cu ușurință.

Cea mai directă modalitate de a reprezenta o placă este ca un tablou unidimensional sau bidimensional, în care elementele din tablou reprezintă puncte de pe tablă și pot lua o valoare corespunzătoare unei pietre albe, unei pietre negre sau a unei intersecții goale. . Sunt necesare date suplimentare pentru a stoca câte pietre au fost capturate, al cui rând este și care intersecții sunt ilegale din cauza regulii Ko .

Majoritatea programelor, cu toate acestea, utilizează mai mult decât informațiile brute ale bordului pentru a evalua pozițiile. Sunt necesare date precum care pietre sunt conectate în șiruri, ce șiruri sunt asociate între ele, ce grupuri de pietre sunt expuse riscului de capturare și ce grupuri de pietre sunt moarte pentru a face o evaluare exactă a poziției. În timp ce aceste informații pot fi extrase doar din pozițiile de piatră, o mare parte din ele pot fi calculate mai repede dacă sunt actualizate într-o bază incrementală, la fiecare mișcare. Această actualizare incrementală necesită stocarea mai multor informații pe măsură ce starea plăcii, ceea ce poate face ca copierea plăcii să dureze mai mult. Acest tip de compromis este indicativ al problemelor implicate în realizarea de programe rapide de computer Go.

O metodă alternativă este să aveți o singură placă și să faceți și să luați înapoi mișcări, astfel încât să minimizați cerințele de memorie a computerului și să aveți rezultatele evaluării plăcii stocate. Acest lucru evită să fie nevoie să copiați informațiile din nou și din nou.

Proiectarea sistemului

Noi abordări ale problemelor

Din punct de vedere istoric, tehnicile GOFAI (Good Old Fashioned AI) au fost folosite pentru a aborda problema Go AI. Mai recent, rețelele neuronale au fost utilizate ca o abordare alternativă. Un exemplu de program care utilizează rețele neuronale este WinHonte.

Aceste abordări încearcă să atenueze problemele jocului Go având un factor de ramificare ridicat și numeroase alte dificultăți.

Rezultatele cercetării Computer Go sunt aplicate în alte domenii similare, cum ar fi știința cognitivă , recunoașterea modelelor și învățarea automată . Teoria jocurilor combinatorii , o ramură a matematicii aplicate , este un subiect relevant pentru computer Go.

Filozofiile de proiectare

Singura alegere pe care trebuie să o facă un program este unde să-și așeze următoarea piatră. Cu toate acestea, această decizie este dificilă de gama largă de impacturi pe care o singură piatră le poate avea pe întregul tablou și de interacțiunile complexe pe care diferitele grupuri de pietre le pot avea între ele. Diferite arhitecturi au apărut pentru rezolvarea acestei probleme. Cea mai populară utilizare:

Puține programe folosesc doar una dintre aceste tehnici exclusiv; majoritatea combină porțiuni din fiecare într-un singur sistem sintetic.

Căutarea arborelui Minimax

O tehnică tradițională AI pentru crearea unui software de joc este utilizarea unei căutări în arbore minimax . Aceasta implică redarea tuturor mișcărilor ipotetice de pe tablă până la un anumit punct, apoi utilizarea unei funcții de evaluare pentru a estima valoarea acelei poziții pentru jucătorul curent. Se selectează mișcarea care duce la cea mai bună placă ipotetică, iar procesul se repetă la fiecare tură. În timp ce căutările în copaci au fost foarte eficiente în șahul computerizat , au înregistrat un succes mai mic în programele Computer Go. Acest lucru se datorează parțial faptului că a fost în mod tradițional dificil să se creeze o funcție de evaluare eficientă pentru o placă Go și parțial pentru că numărul mare de mișcări posibile pe care fiecare parte le poate face ca fiecare să ducă la un factor de ramificare ridicat . Acest lucru face ca această tehnică să fie foarte costisitoare din punct de vedere al calculului. Din această cauză, multe programe care folosesc extensiv arborii de căutare pot juca doar pe placa mai mică 9 × 9, mai degrabă decât pe cele complete 19 × 19.

Există mai multe tehnici, care pot îmbunătăți foarte mult performanța arborilor de căutare atât în ​​ceea ce privește viteza, cât și memoria. Tehnicile de tăiere precum tăierea alfa-beta , căutarea variației principale și MTD (f) pot reduce factorul efectiv de ramificare fără pierderea puterii. În domenii tactice, cum ar fi viața și moartea, Go este în mod special supus tehnicilor de cache, cum ar fi tabelele de transpunere . Acestea pot reduce cantitatea de efort repetat, mai ales atunci când sunt combinate cu o abordare iterativă de aprofundare . Pentru a stoca rapid o placă Go de dimensiuni mari într-un tabel de transpunere, este în general necesară o tehnică de hash pentru rezumarea matematică. Hash-ul Zobrist este foarte popular în programele Go, deoarece are rate scăzute de coliziune și poate fi actualizat iterativ la fiecare mișcare cu doar două XOR-uri , mai degrabă decât să fie calculat de la zero. Chiar și folosind aceste tehnici de îmbunătățire a performanței, căutările complete în copaci pe o placă de dimensiuni mari sunt încă prohibitive. Căutările pot fi accelerate utilizând cantități mari de tehnici de tăiere specifice domeniului, cum ar fi să nu luați în considerare mișcările în care adversarul dvs. este deja puternic și extensii selective, cum ar fi întotdeauna să ne gândim la mișcări lângă grupuri de pietre care sunt pe cale să fie capturate . Cu toate acestea, ambele opțiuni prezintă un risc semnificativ de a nu lua în considerare o mișcare vitală care ar fi schimbat cursul jocului.

Rezultatele competițiilor pe computer arată că tehnicile de potrivire a modelelor pentru alegerea unei mână de mișcări adecvate combinate cu căutări tactice rapide localizate (explicate mai sus) au fost odată suficiente pentru a produce un program competitiv. De exemplu, GNU Go a fost competitiv până în 2008.

Sisteme bazate pe cunoaștere

Novicii învață adesea multe din înregistrările de jocuri ale jocurilor vechi jucate de maeștrii jucători. Există o ipoteză puternică care sugerează că dobândirea cunoștințelor Go este o cheie pentru a crea un computer puternic Go. De exemplu, Tim Kinger și David Mechner susțin că „credem că, cu instrumente mai bune pentru reprezentarea și menținerea cunoștințelor Go, va fi posibil să dezvoltăm programe Go mai puternice”. Ei propun două moduri: recunoașterea configurațiilor comune ale pietrelor și pozițiile lor și concentrarea asupra bătăliilor locale. „Programele Go încă lipsesc atât în ​​ceea ce privește calitatea, cât și cantitatea de cunoștințe.”

După implementare, utilizarea cunoștințelor de specialitate s-a dovedit foarte eficientă în programarea software-ului Go. Sute de linii directoare și reguli generale pentru un joc puternic au fost formulate atât de amatori la nivel înalt, cât și de profesioniști. Sarcina programatorului este să ia aceste euristici , să le formalizeze în codul computerului și să utilizeze algoritmi de potrivire a modelelor și de recunoaștere a modelelor pentru a recunoaște când se aplică aceste reguli. De asemenea, este important să aveți un sistem pentru a determina ce să faceți în cazul în care sunt aplicabile două orientări conflictuale.

Majoritatea rezultatelor relativ reușite provin din abilitățile individuale ale programatorilor la Go și din conjecturile lor personale despre Go, dar nu din afirmații matematice formale; încearcă să facă computerul să imite modul în care joacă Go. „Majoritatea programelor competitive au necesitat 5-15 persoane-ani de efort și conțin 50-100 de module care tratează diferite aspecte ale jocului.”

Această metodă a fost până de curând cea mai de succes tehnică în generarea de programe Go competitive pe o placă de dimensiuni mari. Unele exemple de programe care s-au bazat în mare măsură pe cunoștințe de specialitate sunt Handtalk (mai târziu cunoscut sub numele de Goemate), The Many Faces of Go, Go Intellect și Go ++, fiecare dintre ele fiind considerat la un moment dat cel mai bun program Go din lume.

Cu toate acestea, adăugarea de cunoștințe despre Go uneori slăbește programul, deoarece unele cunoștințe superficiale pot aduce greșeli: "cele mai bune programe joacă de obicei mișcări bune, la nivel de master. Totuși, după cum știe fiecare jucător de jocuri, doar o mișcare proastă poate distruge un joc bun. Performanța programului peste un joc complet poate fi mult mai mic decât nivelul master. "

Metode Monte-Carlo

Articol principal: căutarea arborelui Monte-Carlo

O alternativă majoră la utilizarea cunoștințelor și căutărilor codificate manual este utilizarea metodelor Monte Carlo . Acest lucru se realizează prin generarea unei liste de mișcări potențiale și pentru fiecare mișcare jucând mii de jocuri la întâmplare pe tabloul rezultat. Miscarea care duce la cel mai bun set de jocuri aleatorii pentru jucătorul actual este aleasă ca cea mai bună mișcare. Avantajul acestei tehnici constă în faptul că necesită foarte puține cunoștințe de domeniu sau input de experți, compromisul fiind cerințe sporite de memorie și procesor. Cu toate acestea, deoarece mișcările utilizate pentru evaluare sunt generate la întâmplare, este posibil ca o mișcare care ar fi excelentă, cu excepția unui răspuns specific al adversarului, să fie evaluată din greșeală ca o mișcare bună. Rezultatul acestui lucru sunt programe puternice într-un sens strategic general, dar tactice imperfecte. Această problemă poate fi atenuată prin adăugarea unor cunoștințe de domeniu în generația de mutare și un nivel mai mare de adâncime de căutare pe lângă evoluția aleatorie. Unele programe care folosesc tehnici Monte-Carlo sunt Fuego, The Many Faces of Go v12, Leela, MoGo, Crazy Stone , MyGoFriend și Zen.

În 2006, o nouă tehnică de căutare, limite superioare de încredere aplicate copacilor (UCT), a fost dezvoltată și aplicată multor programe 9x9 Monte-Carlo Go cu rezultate excelente. UCT folosește rezultatele play out-urilor colectate până acum pentru a ghida căutarea de-a lungul liniilor de joc mai reușite, permițând totuși liniilor alternative să fie explorate. Tehnica UCT, împreună cu multe alte optimizări pentru a juca pe placa mai mare de 19x19, a determinat MoGo să devină unul dintre cele mai puternice programe de cercetare. Aplicațiile timpurii de succes ale metodelor UCT la 19x19 Go includ MoGo, Crazy Stone și Mango. MoGo a câștigat Olimpiada de computer din 2007 și a câștigat unul (din trei) blitz împotriva lui Guo Juan, al 5-lea Dan Pro, în mult mai puțin complexul 9x9 Go. The Many Faces of Go a câștigat Olimpiada de computer din 2008 după ce a adăugat căutarea UCT la motorul său tradițional bazat pe cunoștințe.

Învățare automată

În timp ce sistemele bazate pe cunoștințe au fost foarte eficiente la Go, nivelul lor de competențe este strâns legat de cunoștințele programatorilor și experților din domeniu asociați. O modalitate de a sparge această limitare este de a utiliza tehnici de învățare automată pentru a permite software-ului să genereze automat reguli, modele și / sau strategii de rezolvare a conflictelor.

Acest lucru se face, în general, permițând unei rețele neuronale sau unui algoritm genetic să fie să revizuiască o bază de date mare de jocuri profesionale, fie să joace multe jocuri împotriva sa sau a altor persoane sau programe. Acești algoritmi sunt apoi capabili să utilizeze aceste date ca mijloc de a-și îmbunătăți performanța. AlphaGo a folosit acest lucru cu un efect deosebit. Alte programe care foloseau rețele neuronale anterior au fost NeuroGo și WinHonte.

Tehnicile de învățare automată pot fi, de asemenea, utilizate într-un context mai puțin ambițios pentru a regla parametrii specifici ai programelor care se bazează în principal pe alte tehnici. De exemplu, Crazy Stone învață modele de generație de mișcare din câteva sute de jocuri eșantion, utilizând o generalizare a sistemului de rating Elo .

AlphaGo

Articol principal: AlphaGo

AlphaGo , dezvoltat de Google DeepMind , a făcut un progres semnificativ prin învingerea unui jucător uman profesionist în octombrie 2015, folosind tehnici care combinau învățarea profundă și căutarea în arbore Monte Carlo . AlphaGo este semnificativ mai puternic decât alte programe Go anterioare și este primul care a învins un profesionist uman de 9 dan într-un joc fără handicap pe o tablă de dimensiuni mari.

Lista programelor de computer Go-playing

A se vedea, de asemenea, software-ul Go
  • AlphaGo , primul program de computer care a câștigat în meciuri uniforme împotriva unui jucător profesionist uman Go
  • AYA de Hiroshi Yamashita
  • BaduGI de Jooyoung Lee
  • Crazy Stone de Rémi Coulom (vândut sub numele de Saikyo no Igo în Japonia)
  • Darkforest de Facebook
  • Artă plastică de Tencent
  • Fuego, un program open source Monte Carlo
  • Programul Goban, Macintosh OS X Go de Sen: te (necesită extensii Goban gratuite)
  • GNU Go , un program open source clasic Go
  • Go ++ de Michael Reiss (vândut ca Strongest Go sau Tuyoi Igo în Japonia)
  • Leela , primul program Monte Carlo de vânzare pentru public
  • Leela Zero , o reimplementat a sistemului descris în AlphaGo Zero hârtie
  • The Many Faces of Go de David Fotland (vândut ca AI Igo în Japonia)
  • MyGoFriend de Frank Karger
  • MoGo de Sylvain Gelly; versiune paralelă de către mulți oameni.
  • Programul Pachi open source Monte Carlo de Petr Baudiš, versiunea online Peepo de Jonathan Chetwynd, cu hărți și comentarii pe măsură ce joci
  • Smart Go de Anders Kierulf, inventatorul formatului Smart Game
  • Steenvreter de Erik van der Werf
  • Zen de Yoji Ojima aka Yamato (vândut sub numele de Tencho no Igo în Japonia); versiune paralelă de Hideki Kato.

Competiții între programele computer Go

Între programele de computer Go au loc mai multe competiții anuale, cele mai proeminente fiind evenimentele Go de la olimpiada de computer . Competiții regulate, mai puțin formale, între programele care se desfășurau pe KGS Go Server (lunar) și Computer Go Server (continuu).

Printre programele de joacă importante se numără Crazy Stone, Zen, Aya, Mogo, The Many Faces of Go, pachi și Fuego, toate enumerate mai sus; și lapte rece de autor taiwanez, Steenvreter de olandeză și DolBaram de autor coreean.

Istorie

Prima competiție computer Go a fost sponsorizată de Acornsoft , iar primele obișnuite de USENIX . Au concurs între 1984 și 1988. Aceste competiții au introdus Nemesis, primul program Go competitiv de la Bruce Wilcox și G2.5 de David Fotland , care va evolua ulterior în Cosmos și The Many Faces of Go.

Unul dintre primii factori ai cercetării computer Go a fost Premiul Ing, un premiu relativ mare, sponsorizat de bancherul taiwanez Ing Chang-ki , oferit anual între 1985 și 2000 la World Computer Go Congress (sau Ing Cup). Câștigătorului acestui turneu i s-a permis să provoace tineri jucători cu handicap într-un meci scurt. Dacă computerul a câștigat meciul, premiul a fost acordat și un nou premiu a fost anunțat: un premiu mai mare pentru înfrângerea jucătorilor la un handicap mai mic. Seria de premii Ing trebuia să expire fie 1) în anul 2000, fie 2) când un program ar putea învinge un profesionist 1-dan fără handicap pentru 40.000.000 de dolari NT . Ultimul câștigător a fost Handtalk în 1997, pretinzând 250.000 de dolari NT pentru câștigarea unui meci de handicap de 11 pietre împotriva a trei amatori de 11–13 ani, 2–6 dans. La momentul în care premiul a expirat în 2000, premiul nerevendicat era de 400.000 de dolari NT pentru câștigarea unui meci cu handicap de nouă pietre.

Multe alte mari turnee regionale Go („congrese”) aveau atașat un eveniment Go computerizat. Congresul European Go a sponsorizat un turneu pe computer încă din 1987, iar evenimentul USENIX a evoluat în Campionatul SUA / North American Computer Go, desfășurat anual în perioada 1988-2000 la Congresul US Go.

Japonia a început să sponsorizeze competiții de computer Go în 1995. Cupa FOST a avut loc anual în perioada 1995-1999 la Tokyo. Turneul respectiv a fost înlocuit de Provocarea Gifu, care a avut loc anual din 2003 până în 2006 în Ogaki, Gifu. Computer Go UEC Cup a fost organizat anual din 2007.

Probleme de formalizare a regulilor în jocurile computer-computer

Când două computere joacă un joc de Go unul împotriva celuilalt, idealul este să tratezi jocul într-un mod identic cu doi oameni care joacă evitând orice intervenție din partea oamenilor reali. Cu toate acestea, acest lucru poate fi dificil în timpul scorului final al jocului. Problema principală este că software-ul de joc Go, care comunică de obicei utilizând protocolul Go Text standardizat (GTP), nu va fi întotdeauna de acord cu privire la starea vie sau moartă a pietrelor.

Deși nu există o modalitate generală pentru ca două programe diferite să „vorbească” și să rezolve conflictul, această problemă este evitată în cea mai mare parte prin utilizarea regulilor chinezești , Tromp-Taylor sau American Go Association (AGA) în care se continuă jocul ( fără penalizare) este necesară până când nu mai există dezacord cu privire la starea oricărei pietre de pe tablă. În practică, cum ar fi pe serverul KGS Go, serverul poate media o dispută prin trimiterea unei comenzi GTP speciale către cele două programe client care indică faptul că ar trebui să continue plasarea pietrelor până când nu există nicio întrebare cu privire la starea unui anumit grup (toate pietrele moarte) au fost capturate). CGOS Go Server vede de obicei programele să renunțe înainte ca un joc să ajungă chiar la faza de scor, dar acceptă totuși o versiune modificată a regulilor Tromp-Taylor care necesită o redare completă.

Aceste seturi de reguli înseamnă că un program care se afla într-o poziție câștigătoare la sfârșitul jocului în conformitate cu regulile japoneze (când ambii jucători au trecut) ar putea pierde din cauza jocului slab în faza de rezoluție, dar acest lucru nu este un eveniment obișnuit și este considerat o parte normală a jocului sub toate seturile de reguli de zonă.

Principalul dezavantaj al sistemului de mai sus este că unele seturi de reguli (cum ar fi regulile tradiționale japoneze) penalizează jucătorii pentru efectuarea acestor mișcări suplimentare, excluzând utilizarea unui playout suplimentar pentru două computere. Cu toate acestea, majoritatea programelor Go moderne susțin regulile japoneze împotriva oamenilor și sunt competente atât în ​​joc cât și în scor (Fuego, Many Faces of Go, SmartGo etc.).

Din punct de vedere istoric, o altă metodă de rezolvare a acestei probleme a fost aceea de a avea un expert uman care să judece comisia finală. Cu toate acestea, acest lucru introduce subiectivitatea în rezultate și riscul ca expertul să rateze ceva ce a văzut programul.

Testarea

Sunt disponibile multe programe care permit motoarelor computer Go să se joace unul împotriva celuilalt și comunică aproape întotdeauna prin Go Text Protocol (GTP).

GoGUI și addon gogui-twogtp pot fi folosite pentru a juca două motoare unul împotriva celuilalt pe un singur computer. SmartGo și Many Faces of Go oferă, de asemenea, această caracteristică.

Pentru a juca o varietate cât mai mare de oponenți, KGS Go Server permite jocul Go motor vs. Go motor, precum și Go motor vs. CGOS este un server dedicat pentru computer vs. computer Go.

Vezi si

Referințe

Lecturi suplimentare

linkuri externe